提携形成における問題記述法と制約付きマッチングに関する研究

(1)

提携形成における問題記述法と制約付きマッチングに関する研究

上田, 俊

https://doi.org/10.15017/1398385

出版情報：Kyushu University, 2013, 博士（情報科学）, 課程博士バージョン：

権利関係：Fulltext available.

(2)

Compact Representation and Constrained Matching

Suguru Ueda

May 2013

(3)

divide the gain of the coalition among them. Forming an eﬀective coalition is a key capability in automated negotiation among self-interested agents. Also, the growth of Internet and e-commerce has expanded its application area. Traditionally, the input of a cooperative game is assumed to be given as a black-box function, i.e., a characteristic function. This representation is too abstract. As a result, representing a problem instance, or solving various problems related to cooperative game theory, becomes intractable for large-scale problem instances. Thus, We need an alternative problem representation.

In this dissertation, we consider compact representation schemes for cooperative game thoery and constrained coalition formation problem. More precisely, we ﬁrst develop new compact representation schemes which are based on Distributed Con- straint Optimization Problem and the idea of agent types. Then, we develop new algorithms for existing representation schemes. Futhermore, we develop strategyproof mechanisms for matchings with minimum and maximum quotas.

(4)

Acknowledgments

First of all, I would like to thank my adviser Makoto Yokoo at Kyushu University.

He has always been a great adviser. Through meetings and discussions during the four years I have spent here, he has taught me how to ﬁnd a problem, develop an initial idea, obtain a concrete answer, and extend it to more general problems. He has also allowed me to deﬁne my own research direction, while mentoring me in a gentle and patient way. Without his support, I would have never completed the works described in this dissertation.

I would also like to thank the members of my thesis committee, Ryuzo Hasegawa and Masafumi Yamashita at Kyushu University, who gave me a lot of helpful sugges- tions from the perspective of their own ﬁelds.

Now, I must thank my collaborators, Daniel Fragiadakis, Katsutoshi Hirayama, Toshihiro Matsui, Marius C. Silaghi, and Peter Troyan for their eﬀorts in our joint work. I would like to give special thanks to Atsushi Iwasaki, with whom I have had countless discussions.

During my four years at the graduate school, Mitsuko Kaneuchi gave me conscien- tious support in arranging the oﬃce procedures. In addition, I have beneﬁtted from discussions with my colleagues including Masahiro Goto, Takato Hasegawa, Naoyuki Hashimoto, Ryo Ichimura, Kitaki Makoto, Naoki Ohta, Tenda Okimoto, and Taiki Todo.

Finally, I thank my family, especially my parents Hiroshi and Hatsuko and my brother Satoru for their support over the past 25 years.

(5)

Chapter 1 Introduction

1.1 Background

Forming an effective coalition is a key capability in automated negotiation among self- interested agents. Cooperative game theory deals with how selfish agents can create a coalition and divide the gain of the coalition among them. This topic has more than 60-year tradition. Also, the growth of Internet and e-commerce has expanded its application area. For example, consider a large number of companies, some subsets of which could form profitable virtual organizations that can respond to larger or more diverse orders than an individual company can. The Internet makes forming such virtual organizations much easier.

Let us show an example of a coalition formation problem.

Example 1 Let us assume a president of a company is considering the organization of groups (coalitions) in his/her company. There are three personnel (agents), Alice, Becky and Carol. The president has some knowledge, such as only Alice can handle Becky, so they should be in the same group. Also, he/she knows that Alice and Carol never get along well, so they should be in different groups. His/her goal is to find the best division of the personnel so that the sum of productivities of the groups is maximized. Then, he/she should divide the profits among themselves so that all the agents agree the division.

In the above example, the coalition formation process can generally contain three main problems [14].

a. Computing the value of every possible coalitions that can be formed.

b. Computing the set of disjoint coalition (coalition structure) that have the maximum total value.

c. Computing the rewards that each agent in a coalition should obtain as a result of the actions taken by the coalition as a whole.

(9)

Example 2 More precisely, the president ﬁrstly estimate the values of seven coali- tions from his/her knowledge. For example, Becky can earn 200, the coalition of Alice and Becky can earn 400, the coalition of Alice and Carol can earn 100 and so on.

Secondly, the president decides the organization (coalition structure). In this case, the coalition structure that consists of the coalition of Alice and Becky and the coalition of Carol herself maximize the sum of the values. Finally, the president computes the division of proﬁts that all the agents agree. For example, Becky may not accept a payoﬀ less than 200, because Becky can earn 200 by herself.

In Economics, coalition formation problem has been considered in cooperative game theory. Game theory is a branch of micro-economics that is largely concerned with the theory of decision making in environments populated by self-interested en- tities. In that literature, the main research interest lies on how to divide the earned proﬁts/payoﬀs in the consequence of agents’ cooperation, i.e., designing and charac- terizing solution concepts in the problem (c) I listed above.

A solution concept defines a certain rule that prescribes how agents distribute their cooperative surplus. These solution concepts consider some desirable properties such as stability, i.e., what are the incentives for agents to stay in the coalition, and fairness, i.e., how each agent’s payoff reflects his/her contribution. For example, the core is a solution concept that considers the stability of a coalition and the Shapley value is a solution concept that considers the fairness among agents. Other several solution concepts, such as the nucleolus, the kernel, the bargaining set, and so on, have been proposed and investigated.

In contrast, computing the value of a coalition and coalition structure generation were paid less attention. For the problem (a), the value of a coalition is given by a characteristic function. This characteristic function is represented as a black-box function. The value of a coalition represents the optimal gain achieved by agents in the coalition when they work together. Thus, it is natural to think that the value should be computed from some prior knowledge. For the problem (b), a characteristic function is usually assumed to be super-additive, i.e., a coalition can always do at least as well as if the agents in the coalition had stayed in separate (disjoint) coalitions.

However, if the number of agents grows, super-additivity does not always make sense.

Thus, in a practice of cooperative game theory, it is quite important to consider those problems, in addition to determining an appropriate value division.

Coalition formation problem has become a popular research topic in AI and multi- agent systems [14]. Synthesizing those three problems, the literature of AI and multi- agent systems has shed a light on the usefulness of cooperative game theory for automated negotiation and issues involving selﬁsh agents.

For the problem (a), traditionally, the input of a cooperative game is assumed to be given as a black-box function, i.e., a characteristic function. However, this representation is too abstract. As a result, representing a problem instance, or solving various problems related to cooperative game theory, becomes intractable for large- scale problem instances. For example, if we naively represent a characteristic function

(10)

as a table, we need 2ⁿ space (wheren is the number of agents). Also, obtaining solution concepts (e.g., the core, Shapley value), or ﬁnding an optimal coalition structure, becomes intractable. For example, to check whether a value division is in the core, we need to consider 2ⁿblocking coalitions, which means we need to solve Linear Pro- gramming with 2ⁿ constraints. Thus, this representation is computationally unusable in practice.

The main cause of the above mentioned problems is the fact that the characteristic function representation (i.e., the black box function representation) is too abstract. We need an alternative problem representation that satisﬁes the following requirements.

• The representation should be concise, i.e., it requires exponentially less space than 2ⁿ.

• The representation should be general, i.e., it can represents any characteristic function.

• The representation should enable eﬃcient computation for solving various problems related to cooperative game theory, e.g.,

ﬁnding the core, Shapley value, and an optimal coalition structure.

Recently, from computer scientists, several concise representation schemes for a characteristic function have been proposed, e.g., synergy coalition group (SCG) [16] and marginal contribution nets (MC-nets) [34]. These schemes represent a characteristic function as a set of rules rather than as a single black-box function and can eﬀectively reduce the representation size. We will introduce these two concise representation schemes in Chapter 2.

For the problem (b), in traditional cooperative game theory, a characteristic function is assumed to be super-additive and solution concepts distribute the value of the grand coalition. However, super-additivity does not always make sense. For example, there might be coordination overhead for a large group of agents. Also, collaborative optimization problems may be much harder. When super-additivity does not hold, making the grand coalition is not necessarily optimal. Coalition Structure Genera- tion (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. The partition is called a coalition structure (CS). This problem has become a popular research topic in AI and multi-agent systems (MAS). Various algorithms for solving CSG have been developed [58, 52, 60, 63, 77].

For the problem (c), we can mainly consider three computational problems related to solution concepts as follows:

• Non-emptiness: asking whether there exists any outcome (payoﬀ division) that is rational according to a solution concept,

(11)

• Membership: asking whether a given candidate outcome is rational according to a solution concept,

• Computation: computing an outcome that is rational according to a solution concept.

A key issue in AI and multi-agent systems has been the development of techniques for eﬃciently solving these problems.

Along with those studies, constrained coalition formation is a prominent research area reﬂecting real-world applications. In many real-world applications, there can be constraints on possible coalitions. Thus, we can take these constraints into account for eﬃcient computation of coalition formation.

One example of constrained coalition formation is the idea of available coalitions.

In a traditional model of coalitional game theory, it is assumed that all coalitions are possible. However, organizing a large coalition can be costly, e.g., there might be coordination overhead like communication costs. Also, if time is limited, the agents may not have time to carry out the communications and computations required to coordinate eﬀectively within the composite coalition, so component coalitions may be more advantageous.

Furthermore, in many real-world applications, there can be inherent constraints on possible coalitions. For example, in many countries, anti-trust laws prohibit the formation of certain coalitions of companies (cartels) that can dominate an entire market. Also, constraints may be placed on coalition sizes, where certain sizes are permitted/prohibited. Furthermore, there can be some underlying graphical structure that determines the possible communication patterns among agents. Therefore, it is natural to assume that making a coalition is possible only when the members of the coalition can communicate with each other. There exist several works that consider such constraints on possible coalitions [44, 67, 54, 40].

Another example of coalition formation is the matching theory. The matching theory literature has developed numerous mechanisms to solve the problem of assigning objects to a group of agents when the agents have privately known preferences and the objects have priorities over the agents. Many problems ﬁt broadly into this con- text, including assigning students to schools [2], kidneys to patients [74], or housing to undergraduates [1]. Two-sided matching problem can be considered as a coalition formation problem where coalitions that contain agents of both side can have a positive value. For example, in school choice problem setting, a coalition formed by schools or students only does not make sense.

1.2 Overview of the Dissertation

In this section, we will explain the results in this dissertation. This dissertation deals with two topic; (i) concise representation and (ii) constrained coalition formation.

(12)

For (i), we propose two new concise representations i.e., Distributed Constraint Op- timization Problem (DCOP) based representation and type-based representation. We then extend the formalization of CSG in Ohtaet al.[46] to handle negative values and games with externalities. For (ii), we consider a coalition formation problem where available coalitions are limited. We then propose a strategy-proof mechanism for two sided matching with minimum and maximum quotas. Now let us brieﬂy introduce the results presented in the dissertation.

DCOP based Representation A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. 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 DCOP problem among the agents of a coalition. 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(2ⁿ) 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, wherew^∗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.

Type-based Representation 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 ﬁxed. Our idea of using agent types is inspired by the recent work of Shrot et al. [68] They assume that a game is already represented by some concise representation. The goal of their work is to identify agent types and to solve problems in coalitional games by eﬃciently utilizing knowledge of agent types.

In contrast to their study, our work introduces concise representation schemes based on agent types and considers a wider range of problems in coalitional games including CSG.

Handling Negative Value Rules We extend the formalization of CSG in Ohta et al. [46] 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 can reduce the eﬀorts for describing a characteristic function. Also, by using negative value rules, the represen-

(13)

tation size of a problem can be much more concise. Also, 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, which transforms all negative value rules into positive value rules, (ii) a partial transformation algorithm, which transforms all negative value rules into positive value rules and some negative rules that have a special form, and (iii) a direct encoding algorithm, which creates a set of dummy rules so that negative value rules are handled appropriately.

We show that the full transformation algorithm is not scalable in MC-nets (representation size is at least O(n²), where n is the number of agents), and seems not tractable in embedded MC-nets (representation size can be O(2ⁿ)). 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 also creates less rules than the partial transformation algorithm.

Experimental evaluations show that the direct encoding algorithm is scalable, i.e., an oﬀ-the-shelf optimization package (CPLEX) can solve problem instances with 100 agents/rules within 10 seconds.

Finding the Core for a Coalition Structure in Constrained Coalition Formation When forming the grand coalition is not possible/optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. We propose an efficient algorithm calledCoreD for checking core-non-emptiness for coalition structures. Existing algorithm called CoreP first obtains the value of the optimal coalition structure V(CS^∗), by solving a mixed integer programming problem. Then, it checks whetherV(CS^∗) can be divided without making a blocking (dissatisfied) coalition. In contrast, our proposed algorithm called CoreD first finds the minimal amount V^∗ so that there exists no blocking coalition. Then, it checks whether V(CS^∗) can be equal to V^∗. We experimentally show that when the core is empty, CoreD is by far superior toCoreP. Since the core can be empty, we propose a new solution concept called the weak ε-core⁺, which can utilize the approximate value ofV(CS^∗). Furthermore, based on the idea ofCoreD, we develop an algorithm for checking the non-emptiness of the weak ε-core⁺.

Two-sided Matching with Minimum and Maximum Quotas We consider the problem of allocating objects to agents when the objects have minimum quotas (in addition to the standard maximum quotas). We propose extended seat (ES) and multi-stage (MS) mechanisms modeled after the well-known Gale-Shapley (GS) and top trading cycles (TTC) mechanisms. Our proposed mechanisms are all strategyproof, but a tradeoff exists between the GS and TTC based mechanisms regarding Pareto efficiency and elimination of justified envy. In addition, we use computer simulations to study an additional tradeoff between the ES and MS mechanisms regarding the size of the minimum quotas. When the minimum quotas are small, the MS mechanisms perform well in eliminating the number of traditional blocking pairs;

when the minimum quotas are large, the ES mechanisms perform better.

Our direct application is a problem of assigning students to computer science

(14)

labs in universities, in which it is not often desirable if some labs are left empty, even if all other labs have seats remaining. Our model can apply to many real-world settings where minimum quotas are relevant, such as school choice and hospital- resident matching problems, where unconstrained resident matching may produce too few assignments in rural hospitals.

The organization of the rest of the dissertation is as follows. In Chapter 2, we will introduce general deﬁnitions/notations for cooperative game theory and cite previous results of compact representation. Chapter 3 focuses on a coalition formation problem based on distributed constraint optimization problem, based on a joint work with Atsushi Iwasaki, Makoto Yokoo, Marius C˘alin Silaghi, Katsutoshi Hirayama, and Toshihiro Matsui [72]. Chapter 4 focuses on a concise characteristic function based on agent types, based on a joint work with Makoto Kitaki, Atsushi Iwasaki, and Makoto Yokoo [73]. Chapter 5 focuses on the extensions of MC-net-based representation, based on a joint work with Takato Hasegawa, Atsushi Iwasaki, and Makoto Yokoo [71].

Chapter 6 focuses on a constrained coalition formation utilizing dual solutions, based on a joint work with Makoto Kitaki, Atsushi Iwasaki, and Makoto Yokoo. Chapter 7 focuses on two-sided matchings with minimum quotas, based on a joint work with Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, and Makoto Yokoo [70]. Finally, in Chapter 8, we will conclude this dissertation and describe future works.

(15)

Chapter 2 Preliminaries

2.1 Basic Model

In this section, we introduce the basic notations of cooperative game theory to handle coalition formation problems.

Let A be a set of agents, where |A| = n. We study coalition formation in char- acteristic function games. The value of each coalition is given by a characteristic function deﬁned as follows:

Deﬁnition 1 (Coalition) A coalition S is a subset of agents A.

Deﬁnition 2 (Characteristic function) v : 2^A → R is a characteristic function, which maps each coalition S ⊆ A to a real number v(S). v(S) is called the value of coalition S.

Then, we deﬁne a characteristic function game as follows:

Deﬁnition 3 (Characteristic function games) A characteristic function gameG is given by a pair (A, v).

Let me show an example of a characteristic function game.

Example 3 Let there be four agents a, b, c, and d, i.e., A ={a, b, c, d} and n = 4.

There are 15 coalitions and the characteristic function is given as follows:

v({a}) = 3, v({b}) = 3, v({c}) = 2, v({d}) = 2, v({a, b}) = 6, v({a, c}) = 5, v({a, d}) = 5, v({b, c}) = 5, v({b, d}) = 5, v({c, d}) = 2, v({a, b, c}) = 8, v({a, b, d}) = 8, v({a, c, d}) = 5, v({b, c, d}) = 5, v({a, b, c, d}) = 5.

(16)

Throughout this thesis, we assume that the value of empty coalition v(∅) is 0.

Also, we assume the value of each coalition is non-negative, i.e., ∀S ⊆ A, v(S) ≥ 0.

As shown in [63], even if some coalition’s values are negative, as long as each coalition’s value is bounded (i.e., not inﬁnitely negative), we can normalize the coalition values so that all values are non-negative. This rescaled game is strategically equivalent to the original game.

There are some subclasses of characteristic function games. The most relevant one is superadditive games.

Deﬁnition 4 (Superadditive games) A characteristic function game G = (A, v) is said to be superadditive if it satisﬁes v(S₁∪S₂)≥v(S₁) +v(S₂) for all S₁ and S₂, where S₁∩S₂ =∅, S₁, S₂ ⊆A.

Super-additive means that any pair of coalitions is better oﬀ by merging into one.

One might think that super-additivity holds in most of the cases since the agents in the composite coalition can work separately and perform at least as well as the case that they were in diﬀerent coalitions. However, organizing a large coalition can be costly, e.g., there might be coordination overhead like communication costs, or possible anti-trust penalties. Also, if time is limited, the agents may not have time to carry out the communications and computations required to coordinate eﬀectively within the composite coalition, so component coalitions may be more advantageous.

In superadditive games, solving CFG becomes trivial, i.e., the grand coalition (the coalition of all agents) is optimal. Thus, in this thesis, we assume a characteristic function can be non-superadditive.

An outcome of a characteristic function game consists of two parts. The ﬁrst part is how to partition agents into coalitions. A partition of agents is called coalition structure. The second part is how to divide the value of the coalition among agents.

We will introduce both of these parts.

We introduce the ﬁrst part of an outcome, which is a coalition structure. A formal deﬁnition of a coalition structure is as follows:

Deﬁnition 5 (Coalition Structure) A coalition structure CS is a partition of A, into disjoint, exhaustive coalitions. i.e., CS = {S₁, S₂, . . .} satisﬁes the following conditions: ∀i, j (i ̸= j), Si ∩ Sj = ϕ, ∪

Si∈CSSi = A. The value of a coalition structure CS, denoted as V(CS), is given by: V(CS) = ∑

Si∈CSv(S_i).

InCS, each agent belongs to exactly one coalition, and some agents may be alone in their coalitions. An optimal coalition structure CS^∗ is a coalition structure that satisﬁes the following condition: ∀CS, V(CS^∗)≥V(CS).

The second part of an outcome is how to divide the value of each coalition into agents.

Definition 6 (Payoff vector) A vectory= (y₁, y₂, . . . , y_n)is a payoff vector, which distributes the value of each coalition among its members.

(17)

The least requirements for a payoff vector are the efficiency condition and the individual rationality condition defined as follows:

Definition 7 (Efficiency condition) A payoff vector y is efficient if ∑

i∈Ayi = V(A) holds.

Deﬁnition 8 (Individual rationality condition) A payoﬀ vector y is individu- ally rational if ∀i∈A, yi ≥v({i}) holds.

A payoff vector y is said to be imputation if it satisfies the efficiency condition and the individual rationality condition. If a payoff vector is imputation, each player weakly prefers being in the grand coalition to being on his/her own. In this section, we assume that a payoff vector distributes a value of the grand coalition v(A). We will define a payoff vector and other concepts for coalition structure in Chapter 6.

A solution concept assigns to each coalitional game a set of reasonable payoﬀ vectors. Two of the best-known ones are the core and the Shapley value.

First, we review the core, which is a prominent solution concept focusing on stability.

Definition 9 (Core) The core is the set of all payoff vectors y which satisfy the effi- ciency condition: ∑

i∈Ay_i =v(A), and the non-blocking condition: ∀S ⊆A,∑

i∈Sy_i ≥ v(S).

If there exists a blocking coalition S such that ∑

i∈Sy_i < v(S) holds, then the agents in S have an incentive to collectively deviate from the grand coalition and divide v(S) themselves. Thus, in other words, a payoﬀ vector is in the core if it is blocked by no coalition. In general, the core can be empty or contain a large set of payoﬀ vectors.

Next, we show the Shapley value, which is another prominent solution concept focusing on fairness.

Deﬁnition 10 The Shapley value of agent i, ϕi, is deﬁned as:

ϕ_i = ∑

S⊆A\{i}

|S|!(n− |S| −1)!

n! (v(S∪ {i})−v(S)).

One intuitive interpretation of the Shapley value is that it averages an agent’s marginal contribution over all possible orders in which the agent may join the coalition.

2.2 Concise Representation Schemes

In this section, we will introduce two concise representation schemes for a characteristic function game; Synergy Coalition Groups (SCG) [16] and Marginal Contribution networks (MC-nets) [34].

We ﬁrst show the deﬁnition of SCG [16]. The main idea is to explicitly represent the value of a coalition only when there exists some positive synergy.

(18)

Deﬁnition 11 An SCG consists of a set of pairs of the form: (S, v(S)). For any coalition S, the value of the characteristic function is: v(S) = max{∑

Si∈pSv(S_i)}, where pS is a partition of S, i.e., all Si are disjoint and ∪Si∈p_SSi =S, and for all the S_i, (S_i, v(S_i))∈ SCG. To avoid senseless cases that have no feasible partitions, we require that ({a},0)∈SCGwhenever {a} does not receive a value elsewhere in SCG.

Using this original deﬁnition, we can represent only super-additive characteristic functions. To allow for characteristic functions that are not super-additive, Ohta et al. [46] slightly modify the deﬁnition, i.e., they add the following requirement for partition p_S: ∀p^′_S ⊆ p_S, where |p^′_S| ≥ 2,(∪Si∈p^′_SS_i, v(∪Si∈p^′_SS_i)) is not an element of SCG.

Example 4 The SCG representation for Example 3 is given as follows:

({a},3), ({b},3), ({c},2), ({d},2), ({c, d},2), ({a, b, c, d},5).

Here, the SCG representation deﬁnes the value of six coalitions, while the character- istic function representation needs to describe ﬁfteen possible coalitions. The value of other nine coalitions is calculated by the value of six coalitions in SCG. For example, v({a, b, c}) =v({a}) +v({b}) +v({c}) = 8.

Then, we show the deﬁnition of MC-nets [34].

Deﬁnition 12 (MC-nets) AnMC-netconsists of set ofrulesR. Each ruler∈R is of the form: (L_r)→v_r, where L_r is a condition of this rule, which is the conjunctions of literals over A, i.e., a1∧ · · · ∧ak∧ ¬ak+1∧ · · · ∧ ¬am. We call{a1, . . . , ak}positive literals and{a_k+1, . . . , a_m}negative literals. We say rulerisapplicableto coalitionS if L_r is true when the values of all Boolean variables that correspond to the agents in S are set to true, and the values of all Boolean variables that correspond to agents in A\S are set to false, i.e.,∧

a∈Sa∧∧

b∈A\S¬b |=L_r holds. Without loss of generality, we assume each rule has at least one positive literal.

In MC-nets, the condition of a rule must be the conjunctions of the literals. We say such a rule is basic. Also, we call a rule that has more complicated condition as non-basicrule. A non-basic rule must be transformed into multiple basic rules, whose conditions are disjointed with each other. For example, a non-basic rule that has form (a∨b∨c)→v, is transformed into three basic rules, i.e., (a)→v, (¬a∧b)→v, and (¬a∧ ¬b∧c)→v.

Example 5 The MC-nets representation for Example 3 is given as follows:

r1 : (a∧ ¬b)→3, r2 : (b∧ ¬a)→3, r₃ : (c∧ ¬d)→2, r₄ : (d∧ ¬c)→2, r₅ : (a∧b∧ ¬c)→6, r₆ : (a∧b∧ ¬d)→6, r7 : (a∧b∧c∧d)→5.

(19)

Here, the MC-nets representation consists of seven rules, while the characteristic function representation needs to describe ﬁfteen possible coalitions. In this case, r₄ and r5 are applicable to coalition {a, b, d}, but other rules are not. Thus, v({a, b, d}) is equal to 2 + 6 = 8.

Ohta et al. [46] identified a relation between two rules that can be classified into four non-overlapping and exhaustive cases. Based on this classification, they identified the condition of a set of rules as consistent, i.e., there exists at least one coalition structure CS such that each rule is applicable to a coalition in CS. Furthermore, they develop mixed integer programming (MIP) formulations for finding a consistent rule set that maximizes the sum of the rule values.

(20)

Chapter 3 Coalition Structure Generation based on Distributed Constraint Optimization

3.1 Introduction

Coalition formation is an important capability in automated negotiation among self- interested agents. 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). This problem has become a popular research topic in AI and multi-agent systems (MAS). Possible applications of CSG include distributed vehicle routing [64], multi-sensor networks [17], etc. Solving CSG is equivalent to a complete set partition problem [77], and various algorithms for solving CSG have been developed [58, 52, 60, 63, 77]. In these traditional works, the value of a coalition is given by a black box function called a characteristic function. A notable exception is [46]. In this work, the value of a coalition is calculated by applying a set of rules, such as MC-nets [34], rather than a single black box function. The motivation for using a set of rules rather than a black box function is to represent a characteristic function more concisely. However, it remains unclear what kinds of problem domains can be concisely represented by such rules.

Let us reconsider the meaning of the value of a coalition. It represents the optimal gain achieved by agents in the coalition when they work together. Thus, it is natural to think that the value is obtained by solving some optimization problem among the agents of the coalition. This idea is also pointed out in [63]. Deng et al. [21]

also present a concept called combinatorial optimization games, in which the value of a coalition is given by solving various graph-related combinatorial optimization problems, such as the maximum ﬂow problem.

After a pioneering work by [43], a Distributed Constraint Optimization Problem

(21)

(DCOP) has become a popular approach for modeling cooperative agents. Various algorithms have been developed, including DPOP [50], OptAPO [39], NCBB [15], etc.

In DCOP, each agent has a choice of actions (values). Reward/cost is determined by the combination of values. The goal is to maximize/minimize the sum of the rewards/costs. This framework is quite general and can represent various application domains in cooperative MAS. In this research, we assume that the value of a coalition is given by an optimal solution of a DCOP among the agents of the coalition.

Let us introduce some motivating examples that can be formalized as CSG based on DCOPs. Consider the problem of forming rescue groups in a disaster area. There exists a set of people T. Each person has following different capabilities: providing medical treatment, driving a vehicle, acting as a firefighter, etc. We want to create as many rescue groups as possible, but at the same time, we need to make sure that the members of each group have enough capabilities. Having people with identical capabilities in one group can be wasteful. We can assume that each person is a variable, whose domain consists of the possible combinations of his/her capabilities to perform. Thus, there exist positive relations/rewards between complementary capabilities, and there exist negative relations/rewards between substitutable capabilities.

Also, the vehicle routing problem described in [61] can be formalized as CSG based on DCOPs, where geographically dispersed dispatch centers of diﬀerent companies cooperate.

Although a DCOP is a very general and powerful framework, the required computational costs might be too expensive, because 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(2ⁿ) 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 finding the value of the grand coalition (the coalition of all agents), 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. More specifically, assuming the size of a variable domain (the number of possible values) is d, the search space size of a DCOP is dⁿ, while the search space size of the approximation algorithm is (d+ 1)ⁿ for k = 1. Also, we develop an anytime algorithm that repeatedly applies the approximation algorithm and experimentally show that the average approximation ratio of the approximation algorithm is by far superior to the theoretical worst-case bound.

The contribution of this work is two-fold: (1) for CSG research, this work introduces a novel representation scheme of a characteristic function and eﬃcient approximation algorithms with worst-case guarantees, and (2) for DCOP research, this work introduces a promising new, but computationally challenging application domain that requires an extension of traditional DCOP formalization. We believe these results introduces a new exciting research domain, which is built on the success of existing CSG and DCOP research.

(22)

3.2 Model

In this chapter, we assume that the value of a coalition S, v(S), is deﬁned as an optimal solution of a DCOP among the agents of coalition S. Agent i has variable x_i, which represents the choice of its action. Agent i chooses the value of x_i from a ﬁnite, discrete domainD_i. The rewards on the values of these variables are determined as below. For notation simplicity, we assume that reward functions are either unary or binary, which is a standard convention used in DCOP literature. The results presented in this paper hold when there exist k-ary reward functions for k≥3.

There exists unary reward r_i :D_i →R on the value d_i ∈D_i of variable x_i, which represents reward r_i(d_i) when agent i chooses value (action) d_i. We assume that there exists at least one valued_i ∈D_i such that r_i(d_i)≥0. Also, there exists binary reward r_i,j :D_i×D_j →R on variablesx_i and x_j, which represents reward r_i,j(d_i, d_j) when agentsi andj are in the same coalition and chooses values (actions)d_i and d_j, respectively. Let us denote that X ∈ Π_i_∈_SD_i is a value assignment to all variables.

Thus,v(S) is deﬁned as:

maxX {∑

i∈S

ri(di) + ∑

i,j∈S

ri,j(di, dj)}.

The value of a coalition structureCS, denoted as V(CS), is the sum of the value of coalitions, V(CS) =∑

Si∈CSv(S_i), or equivalently, V(CS) = max

X { ∑

i∈S∈CS

r_i(d_i) + ∑

i,j∈S∈CS

r_i,j(d_i, d_j)}.

An optimal coalition structureCS^∗maximizes the social surplus, i.e.,CS^∗satisﬁes the following condition:

∀CS, V(CS)≤V(CS^∗), or equivalently, CS^∗ = arg max

CS max

X { ∑

i∈S∈CS

r_i(d_i) + ∑

i,j∈S∈CS

r_i,j(d_i, d_j)}.

In a standard DCOP, the goal is to ﬁnd an optimal value assignment such that v(A) = {∑

i∈Ar_i(d_i) +∑

i,j∈Ar_i,j(d_i, d_j)} is maximized. On the other hand, in our CSG formalization, if two agents work in diﬀerent coalitions, there exists no positive/negative interaction between them. The goal is to partition agents into groups so that the obtained social surplus is maximized. In this formalization, there exists no positive/negative interaction among coalitions. This corresponds to a commonly used assumption in coalitional game theory called no externality, i.e., the gain of a coalition is independent from other coalitions.

We say a characteristic function is super-additive, if for any disjoint sets S_i, S_j, v(Si∪Sj)≥v(Si)+v(Sj) holds. In super-additive cases, solving CSG becomes trivial, i.e., the grand coalition (the coalition of all agents) is optimal. In our DCOP formalization, we can represent a non-super-additive characteristic function. Furthermore,

(23)

Figure 3.1: Reward Functions in Example 1

a characteristic function is not restricted to monotone, i.e., in our DCOP formaliza- tion, there is a chance that for two coalitions, S and S^′, where S ⊃ S^′, v(S) can be smaller thanv(S^′).

Example 6 Let there be three agents a, b, and c. We assume that each agent has two actions. Thus, we assume that there are three variables x_a, x_b, and x_c, and the domain of each variable is {0,1}.

The unary/binary rewards are as follows. We assume that all reward values that are not explicitly described are 0 (Figure 3.1).

ra(1) = 5, rb(1) = 3, rc(0) = 4, r_c(1) = 2, r_a,b(1,0) = 4, r_a,b(1,1) = −2, r_a,c(1,0) =−3, r_a,c(1,1) = 1.

The value of v({a, b, c}) is obtained by solving a DCOP among three agents. The optimal value assignment is x_a = 1, x_b = 0, x_c = 1, and v({a, b, c}) is calculated as r_a(1) + r_b(0) +r_c(1) +r_a,b(1,0) + r_b,c(0,1) + r_a,c(1,1) = 12. Also, the value of v({a, b}) is obtained by solving a DCOP between x_a andx_b. The optimal assignment is x_a = 1, x_b = 0, and v({a, b}) is calculated as r_a(1) +r_b(0) +r_a,b(1,0) = 9. In this case, if agent c acts alone, it can obtain unary reward 4 by setting its value to 0.

Thus, in this case, the grand coalition is not optimal. The optimal coalition structure is {{a, b},{c}} and the optimal value assignment is x_a = 1, x_b = 0, x_c= 0.

(24)

3.3 Representation Size of DCOP Formalization

To explicitly represent a characteristic function, we need to specify the value of a coalition for all 2ⁿ possible coalitions. If the number of reward functions is small, say, there exist only unary/binary rewards, the number of reward functions is only O(n²). Thus, we can represent a characteristic function much more concisely. Obvi- ously, using k-ary reward functions, we can represent any characteristic function as a DCOP. However, the motivation for using our DCOP formalization is not to represent an arbitrary characteristic function, but to directly represent the underlying optimization problem among agents.

Our scheme can compactly represent any characteristic function that can be compactly represented by other schemes, such as Marginal contribution networks (MC- nets) [34] and Synergy coalition group (SCG) [16]. On the other hand, there exists a characteristic function that can be compactly represented by our scheme, but other schemes need exponentially more space, i.e., the following theorems hold.

Theorem 1 Any characteristic function that is compactly represented by MC-nets can also be compactly represented using a DCOP formalization. More speciﬁcally, the number of required rules/constraints increases at most in O(n).

Proof We show how a rule can be represented using a DCOP formalization. We assume that each agent has only one action. Thus, for each variable x_i, which rep- resents the possible actions of agent i, its domain is {1}. Furthermore, for each rule R_k : (P_r, N_r) → v_r, where P_r ={x_p₁, . . . , x_p_s}, N_r ={x_n₁, . . . , x_n_t}, we introduce an auxiliary variable x_R_k, whose domain is {0,1}. When x_R_k = 0, the rule is inactive, and when x_R_k = 1, the rule is active. We set a reward function among x_R_k and x_p₁, . . . , x_p_s, i.e., r_R_k_,x_p

1,...,xps(1, . . . ,1) = v_r. This reward function means v_r is ob- tained when all agents in P_r join the same coalition andx_R_k = 1. For eachx_n_j ∈N_r, we set a binary reward between x_R_k, i.e., r_R_k_,n_j(1,1) = −∞. This reward function means that when at least one of the agents in N_r joins the coalition of positive liter- als, x_R_k must be zero, thus this rule must be inactive. By solving a DCOP among the agents of a coalition S and all rule variables, a rule variable that is applicable to S becomes 1 (otherwise 0). Thus, the reward of an optimal solution becomes identical to the characteristic function given by the rules in the MC-nets.

On the other hand, the following theorem holds.

Theorem 2 There exists a characteristic function that can be represented compactly using a DCOP formalization, while MC-nets require exponentially more space to rep- resent this characteristic function.

Proof Consider the following DCOP problem instance. We assume that the number of agents is n, where n is even, and each agent has two actions. Thus, the domain

(25)

of each variable is {0,1}. We set reward values as follows, where all reward values that are not explicitly described are 0:

r_i(1) =−i, r_i,j(1,1) = n^i+j

2−2, where i < j.

Let us calculate v(S), where |S|< ⁿ₂ −1. If each agent chooses 1, v(S) =∑

i∈S−i+

ni

2−2 ×(|S| −1)≤ 0 holds. Thus, all agents in S choose 0 and v(S) = 0 holds. For any coalition S, where |S| = ⁿ₂ −1, v(S) = 0 also holds. In this case, if all agents choose 1, v(S) = ∑

i∈S{−i+ nⁱ

2−2 ×(ⁿ₂ −2)} = 0 holds. Also, consider v(S), where

|S|= ⁿ₂. The optimal choice is that all agents choose 1, since v(S) =∑

i∈S{−i+ nⁱ

2−2 ×(ⁿ₂ −1)}

=∑

i∈S 2i n−4,

≥0.

Also, for all S_i, S_j, where |S_i|=|S_j|= ⁿ₂ and S_i ̸=S_j, v(S_i)̸=v(S_j) holds.

Since we use only unary/binary rewards, the representation size of this DCOP formalization is O(n²).

Next, let us represent this characteristic function using MC-nets. For each coali- tion S, where |S| = ⁿ₂, we need at least one rule to specify v(S). This is because for all S^′, where |S^′| ≤ ⁿ₂ −1, v(S^′) = 0, and for all Si, Sj, where |Si| = |Sj| = ⁿ₂ and S_i ̸= S_j, v(S_i) ̸= v(S_j) holds. The number of coalitions S, where |S| = ⁿ₂, is given as (n

n 2

) = ₍n^n!

2!)². Using Stirling’s approximation, i.e., n! ≈√

2πnⁿ_eⁿn, we obtain (_n

n 2

) ≈ ^√_πn^2πn2ⁿ. Thus, the MC-nets representation requires at least O(2ⁿ) space to specify this characteristic function.

Accordingly, MC-net representation requires exponentially more space than the DCOP formalization.

We obtained similar results for SCG [16]. These results are intuitively natural since characteristic functions represented by DCOP formalization would be more complex than those of MC-nets and SCG.

3.4 Complexity of CSG with DCOP

One of the central research questions in compact representation schemes of a characteristic function is the computational complexity of ﬁnding or proving the existence of solution concepts (e.g., core, Shapley value). Our DCOP formalization is not good for this purpose. Actually, even a very simple problem, i.e., checking the feasibility of an imputation (a value distribution among agents of a coalition), is NP-complete since we need to solve a DCOP.

Theorem 3 Checking whether an imputation is feasible is NP-complete.

(26)

Proof When the value assignments of variables are given, calculating the value of a coalition and checking the value is more than or equal to the sum of the values in the imputation can be done in polynomial time. Thus, this problem is in class NP.

Next, we reduce a decision version of a standard COP problem, i.e., checking whether there exists a solution of a COP better than a given threshold τ, to this feasibility checking problem. For the original COP, we create a feasibility checking problem instance with exactly the same variables and reward functions. Also, we create an imputation where the sum of the values in the imputation is equal to τ. If the answer to the obtained feasibility checking problem instance is “yes,” then the answer to the original problem is also “yes,” and vice versa. Since the decision problem of a COP is NP-complete, this feasibility check problem must be NP-hard.

Also, since it is in class NP, it is NP-complete.

Next, we examine the computational complexity of CSG using our DCOP formalization. We prove that a decision problem of CSG using a DCOP formalization is NP-complete.

Theorem 4 A decision problem of CSG using a DCOP formalization, i.e., checking whether there exists a CS where V(CS) is greater than a given threshold is NP- complete.

Proof For a given CS and value assignments, checking whether V(CS) is greater than or equal to a given threshold can be solved in polynomial time. Thus, this problem is in class NP. Next, we reduce a standard COP problem, where all reward values are non-negative, toCSG. For the original COP, we create a CSG problem instance with exactly the same variables and reward functions. Since all reward values are non- negative, a CS that contains only the grand coalition is optimal. More speciﬁcally, if CS^∗ contains multiple coalitions, then we can create another CS^′, which uses the same value assignments as CS^∗ but all coalitions are merged into a single coalition.

Since all binary reward values are non-negative, v(CS^∗) ≤ v(CS^′) holds. Thus, an optimal solution of the original COP must be identical to the solution in the CSG problem instance. Since the decision problem of a COP is NP-complete, a CSG with DCOP is NP-hard. Since it is also in class NP, it is NP-complete.

3.5 Approximation Algorithm

3.5.1 Basic Ideas

The main idea of our approximation algorithm is to only search for a restricted subset of all coalition structures without explicitly calculating the value of coalitions.

More speciﬁcally, we search for coalition structures, each of which contains only k coalitions with multiple agents (referred to as multi-agent coalitions). Except for the multi-agent coalitions, every other coalition contains only a single agent (referred to

(27)

as single-agent coalition). To search for a restricted subset of coalition structures, we slightly modify the original DCOP instance.

3.5.2 Details of Approximation Algorithm

We create a DCOP problem instance by slightly modifying the original DCOP problem as follows, so that we can search for coalition structures that contain at most k multi-agent coalitions.

• We add one new value for each variable called “independent,” which means that the agent acts independently. The unary reward of “independent” equals the maximal unary reward for other values.

• Also, agent i has k copies of its domain D_i. For example, consider the case where i has D_i = {d₁, d₂} and k = 2. Then, agent i has a new domain D_i^′ = {d_1,1, d_2,1, d_1,2, d_2,2, independent}.

• Each value in a copied domain indicates which action the agent chooses and to which coalition it belongs.

• All binary rewards related to at least one “independent” value are 0, since the agent who chooses “independent” forms its own coalition.

• The unary reward value of a copied value is identical with the original value. In the above example,r_i(d_1,1) = r_i(d_1,2) =r_i(d₁) and r_i(d_2,1) =r_i(d_2,2) = r_i(d₂).

• A binary reward value between copied values belonging to the same coalition equals the original binary reward values, otherwise, the reward value is 0.

We can solve this new DCOP using any existing algorithms that can obtain an optimal solution, such as ADOPT, DPOP, etc. (or any centralized COP algorithms, e.g., [19], if we can collect all information to a centralized server)¹. By using the obtained solution, we create a CS where an agent who chooses “independent” forms its own coalition, and an agent who chooses a value within j-th copy joins j-th coalition².

The search space of this DCOP is (kd+ 1)ⁿ, where d is the domain size of the original DCOP. When k = 1, the search space is (d + 1)ⁿ. Thus, if k = 1, the computational cost of this algorithm is about the same as solving the original DCOP, whose search space is dⁿ.

Let us show a simple example where k= 1.

1To be more precise, some existing algorithms including ADOPT are originally designed for cost-minimizing problems. Also, the existence of negative rewards can be problematic for pruning.

However, we can directly apply DP-based algorithms such as DPOP. Furthermore, we can apply a simple modification of ADOPT by assuming the possible value of each reward function is bounded.

2In (kd+ 1)ⁿsearch space, there arek! duplicated solutions, since the names of groups/coalitions are “indistinguishable.” We can reduce such duplicated solutions by adding symmetry breaking constraints [27].