Atsushi Iwasaki

AAAI Conference 2025 Conference Paper

Approximate State Abstraction for Markov Games

• Hiroki Ishibashi
• Kenshi Abe
• Atsushi Iwasaki

This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs) where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following a Markov decision processes. For example, in games like soccer, the value of actions changes according to the state of play, we should describe them as Markov games. In TZMGs, the more the number of states becomes, the more difficult computing the equilibrium becomes. Therefore, we abstract the states of TZMGs and examine the performance. State abstraction reduces the number of states by treating multiple different states as a single state, and there is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. This study extends the state abstraction for MDPs to Markov games. In this case, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.

ICLR Conference 2025 Conference Paper

Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games

• Kenshi Abe
• Mitsuki Sakamoto
• Kaito Ariu
• Atsushi Iwasaki

This paper presents a payoff perturbation technique, introducing a strong convexity to players' payoff functions in games. This technique is specifically designed for first-order methods to achieve last-iterate convergence in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. Although perturbation is known to facilitate the convergence of learning algorithms, the magnitude of perturbation requires careful adjustment to ensure last-iterate convergence. Previous studies have proposed a scheme in which the magnitude is determined by the distance from a periodically re-initialized anchoring or reference strategy. Building upon this, we propose Gradient Ascent with Boosting Payoff Perturbation, which incorporates a novel perturbation into the underlying payoff function, maintaining the periodically re-initializing anchoring strategy scheme. This innovation empowers us to provide faster last-iterate convergence rates against the existing payoff perturbed algorithms, even in the presence of additive noise.

ICML Conference 2024 Conference Paper

Adaptively Perturbed Mirror Descent for Learning in Games

• Kenshi Abe
• Kaito Ariu
• Mitsuki Sakamoto
• Atsushi Iwasaki

This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. The optimistic family of learning algorithms, exemplified by optimistic MD, successfully achieves last-iterate convergence in scenarios devoid of noise, leading the dynamics to a Nash equilibrium. A recent re-emerging trend underscores the promise of the perturbation approach, where payoff functions are perturbed based on the distance from an anchoring, or slingshot, strategy. In response, we propose Adaptively Perturbed MD (APMD), which adjusts the magnitude of the perturbation by repeatedly updating the slingshot strategy at a predefined interval. This innovation empowers us to find a Nash equilibrium of the underlying game with guaranteed rates. Empirical demonstrations affirm that our algorithm exhibits significantly accelerated convergence.

IJCAI Conference 2022 Conference Paper

Anytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search

• Kenshi Abe
• Junpei Komiyama
• Atsushi Iwasaki

This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical residency match, each hospital accepts a limited number of doctors. Such capacity constraints are typically given in advance. However, such exogenous constraints can compromise the welfare of the doctors; some popular hospitals inevitably dismiss some of their favorite doctors. Meanwhile, it is often the case that the hospitals are also benefited to accept a few extra doctors. To tackle the problem, we propose an anytime method that the upper confidence tree searches the space of capacity expansions, each of which has a resident-optimal stable assignment that the deferred acceptance method finds. Constructing a good search tree representation significantly boosts the performance of the proposed method. Our simulation shows that the proposed method identifies an almost optimal capacity expansion with a significantly smaller computational budget than exact methods based on mixed-integer programming.

UAI Conference 2022 Conference Paper

Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games

• Kenshi Abe
• Mitsuki Sakamoto
• Atsushi Iwasaki

In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when time-averaging the strategies, while a lot of variants suffer from the issue of limit cycling behavior, i. e. , lack the last-iterate convergence guarantee. To this end, we propose mutant FTRL (M-FTRL), an algorithm that introduces mutation for the perturbation of action probabilities. We then investigate the continuous-time dynamics of M-FTRL and provide the strong convergence guarantees toward stationary points that approximate Nash equilibria under full-information feedback. Furthermore, our simulation demonstrates that M-FTRL can enjoy faster convergence rates than FTRL and optimistic FTRL under full-information feedback and surprisingly exhibits clear convergence under bandit feedback.

AAAI Conference 2020 Conference Paper

Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach

• Atsushi Iwasaki
• Tadashi Sekiguchi
• Shun Yamamoto
• Makoto Yokoo

This paper studies repeated games where two players play multiple duopolistic games simultaneously (multimarket contact). A key assumption is that each player receives a noisy and private signal about the other’s actions (private monitoring or observation errors). There has been no game-theoretic support that multimarket contact facilitates collusion or not, in the sense that more collusive equilibria in terms of permarket profits exist than those under a benchmark case of one market. An equilibrium candidate under the benchmark case is belief-free strategies. We are the first to construct a non-trivial class of strategies that exhibits the effect of multimarket contact from the perspectives of simplicity and mild punishment. Strategies must be simple because firms in a cartel must coordinate each other with no communication. Punishment must be mild to an extent that it does not hurt even the minimum required profits in the cartel. We thus focus on two-state automaton strategies such that the players are cooperative in at least one market even when he or she punishes a traitor. Furthermore, we identify an additional condition (partial indifference), under which the collusive equilibrium yields the optimal payoff.

AAAI Conference 2018 Conference Paper

Approximately Stable Matchings With Budget Constraints

• Yasushi Kawase
• Atsushi Iwasaki

This paper examines two-sided matching with budget constraints where one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota; thus, the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, in contrast, a hospital has a fixed budget; that is, the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence, we extend the “matching with contracts” model of Hatfield and Milgrom so that it deals with approximately stable matchings where each of the hospitals’ utilities after deviation can increase by a factor up to a certain amount. We then propose two novel mechanisms that efficiently return a stable matching that exactly satisfies the budget constraints. Specifically, by sacrificing strategy-proofness, our first mechanism achieves the best possible bound. We also explore a special case on which a simple mechanism is strategy-proof for doctors, while maintaining the best possible bound of the general case.

JAAMAS Journal 2018 Journal Article

Coalition structure generation in cooperative games with compact representations

• Suguru Ueda
• Atsushi Iwasaki
• Makoto Yokoo

Abstract This paper presents a new way of formalizing the coalition structure generation problem (CSG) so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions to maximize social surplus. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than treating the function as a black box. Then we can solve the CSG problem more efficiently by directly applying constraint optimization techniques to this compact representation. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of CSG under these representation schemes. In this context, the complexity is driven more by the number of rules than by the number of agents. As an initial step toward developing efficient constraint optimization algorithms for solving the CSG problem, we also develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well.

AAAI Conference 2017 Conference Paper

Achieving Sustainable Cooperation in Generalized Prisoner’s Dilemma with Observation Errors

• Fuuki Shigenaka
• Tadashi Sekiguchi
• Atsushi Iwasaki
• Makoto Yokoo

A repeated game is a formal model for analyzing cooperation in long-term relationships, e. g. , in the prisoner’s dilemma. Although the case where each player observes her opponent’s action with some observation errors (imperfect private monitoring) is difficult to analyze, a special type of an equilibrium called belief-free equilibrium is identified to make the analysis in private monitoring tractable. However, existing works using a belief-free equilibrium show that cooperative relations can be sustainable only in ideal situations. We deal with a generic problem that can model both the prisoner’s dilemma and the team production problem. We examine a situation with an additional action that is dominated by another action. To our surprise, by adding this seemingly irrelevant action, players can achieve sustainable cooperative relations far beyond the ideal situations. More specifically, we identify a class of strategies called one-shot punishment strategy that can constitute a belief-free equilibrium in a wide range of parameters. Moreover, for a two-player case, the obtained welfare matches a theoretical upper bound.

JAIR Journal 2017 Journal Article

Controlled School Choice with Soft Bounds and Overlapping Types

• Ryoji Kurata
• Naoto Hamada
• Atsushi Iwasaki
• Makoto Yokoo

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., “financially-distressed” and “minority” types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Furthermore, we introduce an extended model that can handle both type-specific ceilings and floors and propose a extended mechanism DA-OT* to handle the extended model. Computer simulation results illustrate that DA-OT outperforms an artificial cap mechanism where we set a hard-bound for each type in each school. DA-OT* can achieve stability in the extended model without sacrificing students’ welfare.

IJCAI Conference 2017 Conference Paper

Near-Feasible Stable Matchings with Budget Constraints

• Yasushi Kawase
• Atsushi Iwasaki

This paper deals with two-sided matching with budget constraints where one side (firm or hospital) can make monetary transfers (offer wages) to the other (worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota: the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, a hospital instead has a fixed budget: the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking the existence is hard. To deal with the nonexistence of stable matchings, we extend the “matching with contracts” model by Hatfield and Milgrom, so that it handles near-feasible matchings that exceeds each budget of the hospitals by a certain amount. We then propose two novel mechanisms that efficiently return such a near-feasible matching that is stable with respect to the actual amount of wages allocated by each hospital. In particular, by sacrificing strategy-proofness, our second mechanism achieves the best possible bound.

AAMAS Conference 2016 Conference Paper

Achieving Sustainable Cooperation in Generalized Prisoner's Dilemma with Observation Errors (Extended Abstract)

• Fuuki Shigenaka
• Shun Yamamoto
• Motohide Seki
• Tadashi Sekiguchi
• Atsushi Iwasaki
• Makoto Yokoo

A repeated game is a formal model for analyzing cooperation in long-term relationships. The case where each player observes her opponent’s action with some observation errors (imperfect private monitoring) is difficult to analyze, and existing works show that cooperative relations can be sustainable only in ideal situations. We deal with a generic problem that can model both the prisoner’s dilemma and the team production problem. We examine a situation with an additional action that is dominated by another action. By adding this seemingly irrelevant action, players can achieve sustainable cooperative relations far beyond the ideal situations. Moreover, for a two-player case, the obtained welfare matches a theoretical upper bound.

AAMAS Conference 2016 Conference Paper

How Is Cooperation/Collusion Sustained in Repeated Multimarket Contact with Observation Errors? (Extended Abstract)

• Atsushi Iwasaki
• Tadashi Sekiguchi
• Shun Yamamoto
• Makoto Yokoo

This paper analyzes repeated multimarket contact with observation errors where two players operate in multiple markets simultaneously. Multimarket contact has received much attention in economics, management, and so on. Despite vast empirical studies that examine whether multimarket contact fosters cooperation or collusion, little is theoretically known as to how players behave in an equilibrium when each player receives a noisy and different observation or signal indicating other firms’ actions (private monitoring). To the best of our knowledge, we are the first to construct a strategy designed for multiple markets whose per-market equilibrium payoffs exceed one for a single market, in our setting. We first construct an entirely novel strategy whose behavior is specified by a non-linear function of the signal configurations. We then show that the per-market equilibrium payoff improves when the number of markets is sufficiently large.

AAMAS Conference 2016 Conference Paper

Simplifying Urban Network Security Games with Cut-Based Graph Contraction

• Hiroaki Iwashita
• Kotaro Ohori
• Hirokazu Anai
• Atsushi Iwasaki

The scalability of the algorithm for solving urban network security games, which is an important challenge concerning security game problems, was improved. State-of-the-art solvers have been scaled up to handle real-world networks with tens of thousands of edges; however, it can take days or more when the inputs are varied. Since they do not essentially overcome exponential growth of the strategy space with increasing graph size, an approach, which can be combined with previous ones, is proposed. In particular, a practical approach of simplifying the graphs so that they can be handled within a realistic time is devised and tested. The key idea behind this approach is to restrict the defender’s pure strategies to potential ones before calculating an equilibrium solution. The restriction can be tightened for faster computation and loosened for better solution. The following three techniques for computing an optimal solution to the restricted game are proposed and evaluated: (i) contraction of the network based on the restriction, (ii) compact formulation of the optimization problem using weighted edges in place of multiple edges, and (iii) efficient solution using a mixed-integer quadratic programming oracle. They can naturally cope with an extension of the game to one taking width of the roads into account. Furthermore, a heuristic algorithm of finding effective restriction of the game is also proposed.

AIJ Journal 2016 Journal Article

Strategyproof matching with regional minimum and maximum quotas

• Masahiro Goto
• Atsushi Iwasaki
• Yujiro Kawasaki
• Ryoji Kurata
• Yosuke Yasuda
• Makoto Yokoo

This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i. e. , a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.

AAAI Conference 2015 Conference Paper

Controlled School Choice with Soft Bounds and Overlapping Types

• Ryoji Kurata
• Masahiro Goto
• Atsushi Iwasaki
• Makoto Yokoo

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the balance on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e. g. , “financially-distressed” and “minority” types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus, we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model, and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Computer simulation results illustrate that the DA-OT outperforms an artificial cap mechanism, where the number of seats for each type is fixed.

AIJ Journal 2015 Journal Article

Finding core for coalition structure utilizing dual solution

• Atsushi Iwasaki
• Suguru Ueda
• Naoyuki Hashimoto
• Makoto Yokoo

When forming the grand coalition is not possible or optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative exact algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward exact algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal value of the optimal coalition structure so that there exists no blocking coalition. Next, it checks whether the optimal value equals the minimal value We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core+, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core+.

AAMAS Conference 2012 Conference Paper

Automated Equilibrium Analysis of Repeated Games with Private Monitoring: A POMDP Approach

• YongJoon Joe
• Atsushi Iwasaki
• Michihiro Kandori
• Ichiro Obara
• Makoto Yokoo

The present paper investigates repeated games with imperfect private monitoring, where each player privately receives a noisy observation (signal) of the opponent’s action. Such games have been paid considerable attention in the AI and economics literature. Identifying pure strategy equilibria in this class has been known as a hard open problem. Recently, we showed that the theory of partially observable Markov decision processes (POMDP) can be applied to identify a class of equilibria where the equilibrium behavior can be described by a finite state automaton (FSA). However, they did not provide a practical method or a program to apply their general idea to actual problems. We first develop a program that acts as a wrapper of a standard POMDP solver, which takes a description of a repeated game with private monitoring and an FSA as inputs, and automatically checks whether the FSA constitutes a symmetric equilibrium. We apply our program to repeated Prisoner’s dilemma and find a novel class of FSA, which we call k-period mutual punishment (k-MP). The k-MP starts with cooperation and defects after observing a defection. It restores cooperation after observing defections k-times in a row. Our program enables us to exhaustively search for all FSAs with at most three states, and we found that 2-MP beats all the other pure strategy equilibria with at most three states for some range of parameter values and it is more efficient in an equilibrium than the grim-trigger.

AAMAS Conference 2012 Conference Paper

False-name-proofness in Online Mechanisms

• Taiki Todo
• Takayuki Mouri
• Atsushi Iwasaki
• Makoto Yokoo

In real electronic markets, each bidder arrives and departs over time. Thus, such a mechanism that must make decisions dynamically without knowledge of the future is called an \emph{online mechanism}. In an online mechanism, it is very unlikely that the mechanism designer knows the number of bidders beforehand or can verify the identity of all of them. Thus, a bidder can easily submit multiple bids (\emph{false-name bids}) using different identifiers (e. g. , different e-mail addresses). In this paper, we formalize false-name manipulations in online mechanisms and identify a simple property called (value, time, identifier)-monotonicity that characterizes the allocation rules of false-name-proof online auction mechanisms. To the best of our knowledge, this is the first work on false-name-proof online mechanisms. Furthermore, we develop a new false-name-proof online auction mechanism for $k$ identical items. When $k$=1, this mechanism corresponds to the optimal stopping rule of the secretary problem where the number of candidates is unknown. We show that the competitive ratio of this mechanism for efficiency is 4 and independent from $k$ by assuming that only the distribution of bidders' arrival times is known and that the bidders are impatient.

AAMAS Conference 2012 Conference Paper

Handling Negative Value Rules in MC-net-based Coalition Structure Generation

• Suguru Ueda
• Takato Hasegawa
• Naoyuki Hashimoto
• Naoki Ohta
• Atsushi Iwasaki
• Makoto Yokoo

A Coalition Structure Generation (CSG) problem involves partitioning a set of agents into coalitions so that the social surplus is maximized. Recently, Ohta et al. developed an efficient algorithm for solving CSG, assuming that a characteristic function is represented as a set of rules, such as marginal contribution networks (MC-nets). In this paper, we extend the formalization of CSG in Ohta et al. so that it can handle negative value rules. Here, we assume that a characteristic function is represented by either MC-nets (without externalities) or embedded MC-nets (with externalities). Allowing negative value rules is important since it can reduce the efforts for describing a characteristic function. In particular, in many realistic situations, it is natural to assume that a coalition has negative externalities to other coalitions. To handle negative value rules, we examine the following three algorithms: (i) a full transformation algorithm, (ii) a partial transformation algorithm, and (iii) a direct encoding algorithm. We show that the full transformation algorithm is not scalable in MC-nets (the worst-case representation size is $\Omega(n^2)$, where n is the number of agents), and does not seem to be tractable in embedded MC-nets (representation size would be $\Omega(2^n)$). In contrast, by using the partial transformation or direct encoding algorithms, an exponential blow-up never occurs even for embedded MC-nets. For embedded MC-nets, the direct encoding algorithm creates less rules than the partial transformation algorithm. Experimental evaluations show that the direct encoding algorithm is scalable, i. e. , an off-the-shelf optimization package (CPLEX) can solve problem instances with 100 agents and rules within 10 seconds.

AAMAS Conference 2012 Conference Paper

Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas

• Suguru Ueda
• Daniel Fragiadakis
• Atsushi Iwasaki
• Peter Troyan
• Makoto Yokoo

We consider the problem of allocating objects to agents when the objects have minimum quotas. There exist many realworld settings where minimum quotas are relevant. For example, in a hospital-resident matching problem, unconstrained matching may produce too few assignments to a rural hospital. Surprisingly, almost 50 years have passed after the seminal work by Gale and Shapley, no existing mechanism can guarantee minimum quotas so far; we did not know how to guarantee that a rural hospital has at least one resident. In this paper, we propose mechanisms that can satisfy minimum quotas as well as standard maximum quotas. More specifically, we propose extended seat (ES) and multi-stage (MS) mechanisms modeled after the well-known deferredacceptance (DA) and top trading cycles (TTC) mechanisms. Our proposed mechanisms are all strategy-proof, but a tradeoff exists between the DA and TTC based mechanisms regarding Pareto efficiency and elimination of justified envy. In addition, there exist a tradeoff between ES and MS mechanisms depending on the size of minimum quotas.

AAMAS Conference 2011 Conference Paper

Concise Characteristic Function Representations in Coalitional Games Based on Agent Types

• Suguru Ueda
• Makoto Kitaki
• Atsushi Iwasaki
• Makoto Yokoo

Forming effective coalitions is a major research challenge in AI and multi-agent systems. Thus, coalitional games, including coalition structure generation, have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. In this paper, we develop a new concise representation scheme for a characteristic function, which is based on the idea of agent types. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size.

IJCAI Conference 2011 Conference Paper

Concise Characteristic Function Representations in Coalitional Games Based on Agent Types

• Suguru Ueda
• Makoto Kitaki
• Atsushi Iwasaki
• Makoto Yokoo

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.

AAMAS Conference 2011 Conference Paper

Extension of MC-net-based Coalition Structure Generation: Handling Negative Rules and Externalities

• Ryo Ichimura
• Takato Hasegawa
• Suguru Ueda
• Atsushi Iwasaki
• Makoto Yokoo

Forming effective coalitions is a major research challenge in AI and multi-agent systems. A Coalition Structure Generation (CSG) problem involves partitioning a set of agents into coalitions so that the social surplus is maximized. Ohta et al. introduce an innovative direction for solving CSG, i. e. , by representing a characteristic function as a set of rules, a CSG problem can be formalized as the problem of finding a subset of rules that maximizes the sum of rule values under certain constraints. This paper considers two significant extensions of the formalization/algorithm of Ohta et al. , i. e. , (i) handling negative value rules and (ii) handling externalities among coalitions.

AAMAS Conference 2011 Conference Paper

False-name Bidding in First-price Combinatorial Auctions with Incomplete Information

• Atsushi Iwasaki
• Atsushi Katsuragi
• Makoto Yokoo

False-name bids are bids submitted by a single agent under multiple fictitious names such as multiple e-mail addresses. False-name bidding can be a serious fraud in Internet auctions since identifying each participant is virtually impossible. It is shown that even the theoretically well-founded Vickrey-Clarke-Groves auction (VCG) is vulnerable to falsename bidding. Thus, several auction mechanisms that cannot be manipulated by false-name bids, i. e. , false-name-proof mechanisms, have been developed. This paper investigates a slightly different question, i. e. , how do they affect (perfect) Bayesian Nash equilibria of first-price combinatorial auctions? The importance of this question is that first-price combinatorial auctions are by far widely used in practice than VCG, and can be used as a benchmark for evaluating alternate mechanisms. In an environment where false-name bidding are possible, analytically investigating bidders' behaviors is very complicated, since nobody knows the number of real bidders. As a first step, we consider a kind of minimal settings where falsename bids become effective, i. e. , an auction with two goods where one naive bidder competes with one shill bidder who may pretend to be two distinct bidders. We model this auction as a simple dynamic game and examine approximate Bayesian Nash equilibria by utilizing a numerical technique. Our analysis revealed that false-name bidding significantly affects the first-price auctions. Furthermore, the shill bidder has a clear advantage against the naive bidder.

AAMAS Conference 2011 Conference Paper

False-name-proof Mechanism Design without Money

• Taiki Todo
• Atsushi Iwasaki
• Makoto Yokoo

Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically report their preferences. In traditional settings, it is assumed that a mechanism can enforce payments to give an incentive for agents to act honestly. However, in many Internet application domains, introducing monetary transfers is impossible or undesirable. Also, in such highly anonymous settings as the Internet, declaring preferences dishonestly is not the only way to manipulate the mechanism. Often, it is possible for an agent to pretend to be multiple agents and submit multiple reports under different identifiers, e. g. , by creating different e-mail addresses. The effect of such false-name manipulations can be more serious in a mechanism without monetary transfers, since submitting multiple reports would have no risk. In this paper, we present a case study in false-name-proof mechanism design without money. In our basic setting, agents are located on a real line, and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. This setting is called the facility location problem and can represent various situations where an agent's preference is single-peaked. First, we fully characterize the deterministic false-name-proof facility location mechanisms in this basic setting. By utilizing this characterization, we show the tight bounds of the approximation ratios for two objective functions: social cost and maximum cost. We then extend the results in two natural directions: a domain where a mechanism can be randomized and a domain where agents are located in a tree. Furthermore, we clarify the connections between false-name-proofness and other related properties.

IJCAI Conference 2011 Conference Paper

Generalizing Envy-Freeness toward Group of Agents

• Taiki Todo
• Runcong Li
• Xuemei Hu
• Takayuki Mouri
• Atsushi Iwasaki
• Makoto Yokoo

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group. They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.

AAMAS Conference 2011 Conference Paper

Pseudo-tree-based Algorithm for Approximate Distributed Constraint Optimization with Quality Bounds

• Tenda Okimoto
• YongJoon Joe
• Atsushi Iwasaki
• Makoto Yokoo

Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter.

IJCAI Conference 2011 Conference Paper

Real-Time Solving of Quantified CSPs Based on Monte-Carlo Game Tree Search

• Baba Satomi
• YongJoon Joe
• Atsushi Iwasaki
• Makoto Yokoo

We develop a real-time algorithm based on a Monte-Carlo game tree search for solving a quantified constraint satisfaction problem (QCSP), which is a CSP where some variables are universally quantified. A universally quantified variable represents a choice of nature or an adversary. The goal of a QCSP is to make a robust plan against an adversary. However, obtaining a complete plan off-line is intractable when the size of the problem becomes large. Thus, we need to develop a real-time algorithm that sequentially selects a promising value at each deadline. Such a problem has been considered in the field of game tree search. In a standard game tree search algorithm, developing a good static evaluation function is crucial. However, developing a good static evaluation function for a QCSP is very difficult since it must estimate the possibility that a partially assigned QCSP is solvable. Thus, we apply a Monte-Carlo game tree search technique called UCT. However, the simple application of the UCT algorithm does not work since the player and the adversary are asymmetric, i. e. , finding a game sequence where the player wins is very rare. We overcome this difficulty by introducing constraint propagation techniques. We experimentally compare the winning probability of our UCT-based algorithm and the state-of-the-art alpha-beta search algorithm. Our results show that our algorithm outperforms the state-of-the-art algorithm in large-scale problems.

AAAI Conference 2010 Conference Paper

Coalition Structure Generation based on Distributed Constraint Optimization

• Suguru Ueda
• Atsushi Iwasaki
• Makoto Yokoo
• Marius Silaghi
• Katsutoshi Hirayama
• Toshihiro Matsui

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure Generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a coalition structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i. e. , we assume that the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might imagine that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve O(2n ) DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w∗ + 1), k/⌊n/2⌋) of the optimal CS, where w∗ is the tree width of a constraint graph. When k = 1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.

AAMAS Conference 2010 Conference Paper

Cooperative Problem Solving against Adversary: Quantified Distributed Constraint Satisfaction Problem

• Satomi Baba
• Atsushi Iwasaki
• Makoto Yokoo
• Marius Silaghi
• Katsutoshi Hirayama
• Toshihiro Matsui

In this paper, we extend the traditional formalization ofa Distributed Constraint Satisfaction Problems (DisCSP)to a Quantified DisCSP. A Quantified DisCSP includes several universally quantifiedvariables, while all of the variables in a traditional DisCSP areexistentially quantified. A universally quantified variable represents a choice of the nature oran adversary. A Quantified DisCSP formalizes a situation where a team of agents istrying to make a robust plan against the nature or an adversary. In this paper, we present the formalization of such aQuantified DisCSP and develop an algorithm for solving it. This algorithm generalizes the asynchronous backtracking algorithmused for solving a DisCSP. In this algorithm, agents communicate a value assignment calleda good in addition to the nogood used inasynchronous backtracking. Interestingly, the procedures executed by an adversarial/cooperative agent for good/nogood are totally symmetrical. Furthermore, we develop a method for improving this basic algorithm. Experimental evaluation results illustrate that we observe an easy-hard-easy transition by changing the tightness of constraints, while very loose problem instances are relatively hard. Also, the modification of the basic algorithm is effective and can achieve about 25\% reduction of cycles for the hardest problem instances.

AAMAS Conference 2010 Conference Paper

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

• Atsushi Iwasaki
• Vincent Conitzer
• Yoshifusa Omori
• Yuko Sakurai
• Taiki Todo
• Mingyu Guo
• Makoto Yokoo

This paper analyzes the worst-case efficiency ratio of false-name-proofcombinatorial auction mechanisms. False-name-proofness generalizesstrategy-proofness, by assuming that a bidder can submit multiple bidsunder fictitious identifiers. Even the well-known Vickrey-Clarke-Grovesmechanism is not false-name-proof. It has previously been shown thatthere is no false-name-proof mechanism that always achieves a Paretoefficient allocation. Hence, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplusmust be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider thefraction of the Pareto-efficient surplus that we obtain, and try tomaximize this fraction in the worst case, under the constraint offalse-name-proofness. As far as we are aware, this is the first attempt to examine theworst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proofmechanism that satisfies some apparently minor assumptions is atmost $2/(m+1)$ for auctions with $m$ different goods. We also observe that the worst-case efficiency ratioof existing false-name-proof mechanisms is generally $1/m$ or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism, which is false-name-proof when all bidders are single-minded, and its worst-case efficiency ratio is $2/(m+1)$, i. e. , optimal.

AAMAS Conference 2009 Conference Paper

Characterizing False-name-proof Allocation Rules in Combinatorial Auctions

• Taiki Todo
• Atsushi Iwasaki
• Makoto Yokoo
• Yuko Sakurai

A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategyproof allocation rules. In particular, a condition called weakmonotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity. In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. Falsename-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-nameproof, do not satisfy sub-additivity; they are not false-nameproof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.

AAMAS Conference 2008 Conference Paper

Anonymity-Proof Shapley Value: Extending Shapley Value for Coalitional Games in Open Environments

• Naoki Ohta
• Vincent Conitzer
• Yasufumi Satoh
• Atsushi Iwasaki
• Makoto Yokoo

Coalition formation is an important capability for automated negotiation among self-interested agents. In order for coalitions to be stable, a key question that must be answered is how the gains from cooperation are to be distributed. Coalitional game theory provides a number of solution concepts for this. However, recent research has revealed that these traditional solution concepts are vulnerable to various manipulations in open anonymous environments such as the Internet. To address this, previous work has developed a solution concept called the anonymity-proof core, which is robust against such manipulations. That work also developed a method for compactly representing the anonymity-proof core. However, the required computational and representational costs are still huge. In this paper, we develop a new solution concept which we call the anonymity-proof Shapley value. We show that the anonymity-proof Shapley value is characterized by certain simple axiomatic conditions, always exists, and is uniquely determined. The computational and representational costs of the anonymity-proof Shapley value are drastically smaller than those of existing anonymity-proof solution concepts.

AAMAS Conference 2008 Conference Paper

Beyond quasi-linear utility: strategy/false-name-proof multi-unit auction protocols

• Yuko Sakurai
• Yasumasa Saito
• Atsushi Iwasaki
• Makoto Yokoo

We develop strategy/false-name-proof multi-unit auction protocols that can handle non-quasi-linear utilities. One almost universal assumption in auction theory literature is that each bidder has quasi-linear utility, except for some works on budget-constrained bidders. In particular, the celebrated VCG protocol is strongly believed to critically depend on the quasi-linear assumption and will break down if this assumption does not hold. We show that with a simple modification, the VCG can handle non-quasi-linear utilities by sacrificing efficiency to a certain extent. The basic idea of this modification is that tentative allocation and payments are determined assuming quasi-linear utilities, but each bidder can choose the actual number of units to obtain based on his non-quasi-linear utility. The modified VCG only uses the gross utility of each bidder. Requiring gross utilities only is an advantage since collecting the entire utility function can be costly. However, determining tentative allocation and payments without considering actual non-quasi-linear utilities can cause significant efficiency loss. Furthermore, the VCG is not robust against false-name-proof. Thus, we propose a new false-name-proof open ascending auction protocol in which each bidder declares his demand for a series of prices. This protocol can improve efficiency without collecting entire utility functions.

AAMAS Conference 2006 Conference Paper

False-name-proof Combinatorial Auction Protocol

• Makoto Yokoo
• Toshihiro Matsutani
• Atsushi Iwasaki