Arrow Research search

Author name cluster

Suguru Ueda

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
1 author row

Possible papers

12

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.

Details DOI

AIJ Journal 2017 Journal Article

Strategy-proof school choice mechanisms with minimum quotas and initial endowments

  • Naoto Hamada
  • Chia-Ling Hsu
  • Ryoji Kurata
  • Takamasa Suzuki
  • Suguru Ueda
  • Makoto Yokoo

We consider a school choice program where minimum quotas are imposed for each school, i. e. , a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i. e. , each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program. We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student-optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms.

Details DOI

AAMAS Conference 2016 Conference Paper

Pareto Efficient Strategy-proof School Choice Mechanism with Minimum Quotas and Initial Endowments

  • Ryoji Kurata
  • Naoto Hamada
  • Chia-Ling Hsu
  • Takamasa Suzuki
  • Suguru Ueda
  • Makoto Yokoo

This paper develops a strategy-proof and Pareto efficient mechanism for a school choice program called Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS). We consider a setting where minimum quotas are imposed for each school, i. e. , a school is required to be assigned at least a certain number of students to operate, and the obtained matching must respect initial endowments, i. e. , each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms achieve both of them simultaneously. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas and cannot guarantee Pareto efficiency. TTCR-SS is based on Top Trading Cycles (TTC) mechanism, while it is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. Our simulation results show TTCR-SS is significantly better than an existing TTC-based mechanism in terms of students’ welfare.

PDF

AAMAS Conference 2016 Conference Paper

Strategyproof Matching with Minimum Quotas and Initial Endowments (Extended Abstract)

  • Naoto Hamada
  • Ryoji Kurata
  • Suguru Ueda
  • Takamasa Suzuki
  • Makoto Yokoo

Although minimum quotas are important in many real-world markets, existing strategyproof mechanisms require an unrealistic assumption that all students consider all schools acceptable (and vice-versa). We develop a strategyproof matching mechanism called Priority-List based Deferred Acceptance mechanism with Minimum Quotas (PLDA-MQ), which works under more realistic assumptions: (i) a student considers (at least) one particular school, which we call her initial endowment school, acceptable, and vice-versa, and (ii) the initial endowments satisfy all the minimum quotas. We require a matching to respect initial endowments; each student must be assigned to a school that is at least as good as her initial endowment. PLDA-MQ obtains the student-optimal matching within all matchings that respect minimum quotas/initial endowments and satisfies a stability requirement called Priority-List based (PL-) stability. CCS Concepts •Computing methodologies → Multi-agent systems; •Applied computing → Economics;

PDF

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+.

Details DOI

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.

PDF

AAMAS Conference 2012 Conference Paper

Reformulation of Cooperative Game Theory based on Concise Representation Scheme

  • Suguru Ueda

Forming effective coalitions is a major research challenge in AI and multi-agent systems. Thus, cooperative games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a cooperative game is a black-box function called a characteristic function. Therefore, many problems in cooperative games, including CSG, tend to be computationally intractable. In my thesis, I develop new representation schemes, which are concise and can enable efficient computation for solving various problems related to cooperative game theory.

PDF

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.

PDF

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.

PDF

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.

PDF Details DOI

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.

PDF

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.

PDF Details