Probability Bounds for Overlapping Coalition Formation

1 Introduction

Cooperative transferable utility (TU) games [Chalkiadakis et al., 2011] have been widely studied as they provide a rich framework for cooperation and coordination among rational agents. In such games, agents make binding agreements for jointly tackling tasks that result to some utility (coalitional value) awarded to the team (coalition). The importance of their study arises from the fact that in many real-world settings it may be impossible for agents to achieve their goals on their own, or that it is simply more profitable for them to form coalitions. Moreover, interconnected electronic societies and social networks offer a natural environment for the completion of goals of individuals, most of the times by completing tasks through common actions. In this setting, the

Georgios Chalkiadakis

Electrical and Computer Engineering Technical University of Crete Chania, Greece gehalk@intelligence.tuc.gr

formation of a coalition is feasible only if its members are interconnected [Myerson, 1977].

Even though the vast majority of the literature assumes that coalitions have to be disjoint-i.e., an agent can belong in only one coalition at a time-this assumption does not hold in many realistic scenarios. In our work, agents can decide to join a number of overlapping coalitions, also referred to as partial coalitions [Chalkiadakis et al., 2010].

Moreover, in realistic settings it is natural that agents contribute some amount of their (divisible) resource in order to complete the coalitional task. It is conceivable that an agent is certain only of the quantity of her own resource, while she has private beliefs about others' potential contribution. Thus, acting under incomplete information, she can only probabilistically reason about the success of a potential coalition [Chalkiadakis et al., 2007; Kraus et al., 2003]. Against this background, we provide three novel methods that allow agents to establish probability bounds on the corresponding uncertainty. The bounds are derived given private agent beliefs about others' potential resource investment. These beliefs correspond to Beta and Dirichlet distributions which can be easily manipulated and updated in a principled manner. Our first method exploits an improvement of the Paley-Zygmund inequality [Paley and Zygmund, 1932], while the second and the third proceed by appropriately handling the two-sided Chebyshev's inequality [Mitzenmacher and Upfal, 2005] and the Hoeffding's inequality [Hoeffding, 1963], respectively. Agents using any of them can demand an arbitrary confidence level for the resource contribution of a coalition.

In order for agents to complete tasks by forming overlapping coalitions, an appropriate protocol is required. Thus, we provide a generic protocol for iterated overlapping coalition formation. Under this protocol, in each iteration (round) a number of tasks arrives, and a proposer gets assigned to each task, who is responsible for forming a coalition so that the task gets completed; naturally, the underlying graph structure influences the plausibility of emergence of the coalitions.

To the best of our knowledge, this is the first paper to compute probability bounds for coalition formation under uncertainty. Moreover, this is the first work to tackle overlapping coalition formation (OCF) under uncertainty. We evaluate our methods by conducting experiments over both a 300 nodes Erd˝os-Renyi random graph and a real social network which is a 4039 nodes snapshot from Facebook [Leskovec and Krevl,

2014]. Our results show that our methods consistently outperform, in terms of effectiveness in task completion, a baseline method that selects coalitions based only on expected resource quantity. Moreover, they are also time-efficient, and their behaviour is robust against increases in demanded confidence level. As such, we can conclude that they are indeed suitable for probabilistic reasoning in order to decide which coalitions to form in real-world networks.

2 Background and RelatedWork

The study of domains with overlapping coalitions was initiated by [Shehory and Kraus, 1998], who provided an approximate solution to the corresponding optimal coalition structure generation (CSG) problem [Chalkiadakis et al., 2011]. The subsequent work of [Dang et al., 2006] presented two domain-oriented algorithms for (overlapping) CSG in sensor networks. The formal definition of cooperative games with overlapping coalitions, however, was not until [Chalkiadakis et al., 2010]. In that model, an agent can participate in more than one coalition, by contributing to each a portion of her resources; thus, a partial coalition is given by a vector rC = (r1C , . . . , rnC ), where riC ∈ [0, 1] denotes the resource fraction which agent i contributes to coalition C, so riC = 0 means that agent i is not part of coalition C. In this way an overlapping coalition formation game is given by (i) a set of players N = {1, . . . , n} and (ii) a function v : [0, 1]n ↦→ R.

In [Chalkiadakis et al., 2010], an expressive class of OCF games, threshold task games (TTGs) is also put forward. A threshold task game G = (N;w; t) is given by (i) a set of agents N = {1, . . . , n}, (ii) a vector w = (w1, . . . , wn) ∈ R+ denoting the quantity of resources the agents possess and (iii) a list t = (t1, . . . , tl) of task types where each th is described by a threshold value Th ≥ 0 and a utility vh ≥ 0, so a task type is denoted as th = (Th, vh). In TTGs, agents form coalitions to complete tasks, in order to gain utility vh by fulfilling the requirement Th for th.

Coalition formation (focusing on coalitional stability) under uncertainty was studied in [Chalkiadakis and Boutilier, 2004; Ieong and Shoham, 2008; Suijs et al., 1999], while [Kraus et al., 2003] dealt with forming coalitions via auctions. Finally, cooperative games on graphs have been widely studied, both in non-overlapping and in overlapping settings (see, e.g., [Myerson, 1977; Deng and Papadimitriou, 1994; Chalkiadakis et al., 2012; Zick et al., 2012]). However, no previous work has explicitly dealt with the decision problem agents face in uncertain overlapping coalitional settings.

3 Modeling Uncertainty

In [Ueda et al., 2011] a concise representation scheme based on the idea of agent types is proposed, where agents i, j ∈ N are recognizably equivalent if for any coalition C, i, j /∈ C : v(C ∪ i) = v(C ∪ j). Such a representation cannot apply as a scheme for conciseness in threshold task games, as a task is characterized by a scalar, which is the sum of the resources required for its completion, and not by type vectors (as in [Ueda et al., 2011]). However, we achieve representational conciseness by restricting the quantities of the agent resources and the threshold values of the task types to be integer values. Without these restrictions, the number of possible partial coalitions would be infinite. We assume that resources are integers, and qmax ∈ N+ is such that an agent i ∈ N possesses a resource amount wi ∈ {1, . . . , qmax}.

Agent beliefs. Each agent i knows only the quantity of her own resource, while she has a private belief Xi j about the resource investment of any other agent j. Belief Xi j is composed of random variables Dij and Bi j , distributed as follows:

• Dij ∼ Multinomial(pij = (pij 1 , . . . , pij qmax )), where pij r is the probability that j offers quantity r of her resource in a coalition.
• pij ∼Dirichlet(αij ), αij = (αij 1 , . . . , αij qmax )
• Bi j ∼ Binomial(qij ), where qij is the probability that j accepts an offer by i for participation in a coalition.
• qij ∼ Beta(aij , bij ), where aij (bij ) corresponds to the number of i's proposals that j has accepted (declined).

Note that αij , aij and bij above are hyperparameters corresponding to easily updated counters. We estimate pij r as αij r / ∑ αij , and qij as aij /(aij + bij ). Thus, E[Xi j ] = qij ∑qmax r=1 pij r ·r. Therefore, the expected, according to i's beliefs, quantity of the sum of resource contribution of a group of agents XiC = ∑j∈C Xi j , C ⊆ N \ i, can be computed in O(n · qmax) time, through linearity of expectations. We assume that Xi1 , . . . ,X i i-1 , Xi i+1 , . . .Xin are independent. Due to independence, the variance of XiC is the sum of the variances of each Xi j , j ∈ C, and thus it can be computed in O(n · qmax) time as well.

4 Obtaining and Exploiting Bounds

In real-world TTG settings, agents act under uncertainty regarding the amount of resources that others may contribute to a coalition. They can thus obtain probability bounds over the resource contribution of a group, and exploit them to select with confidence groups that can carry out their tasks (Alg.1). We henceforth refer to XiC as X, for fixed i ∈ N and

C ⊆ N \ i, when this causes no confusion. The threshold value T of a task must be exceeded, so that utility u is granted to the members of the successful coalition, and thus agent i is interested in computing P(X ≥ T). Since the cost of this computation can be extremely high, 1 the agents resort to computing bounds over this quantity.

4.1 The IPZYMethod

Our first method builds on an improvement of the PaleyZygmund inequality (IPZY). Firstly, we present the PaleyZygmund inequality [Paley and Zygmund, 1932]:

1 The distribution of the sum of independent integer-valued random variables can be computed via the Convolution Theorem, which exploits Fast Fourier Transform [Proakis and Manolakis, 1996], in O(n2 · qmax · log(n · qmax)) time. However, for large n, this computation time can be prohibitive. By contrast, we obtain probability bounds in O(n · qmax) time, since the inequalities we utilize depend, at worst, on the expected value and variance of X.

Theorem 1 (Paley-Zygmund inequality). Let a random variable X ≥ 0 with finite variance and 0 ≤ θ ≤ 1. It holds:

The Paley-Zygmund inequality can be written as:

We now state the following inequality:

Theorem 2. Let a random variable X ≥ 0 with finite variance, and 0 ≤ θ ≤ 1. It holds that:

Proof. Our proof is based on the one-sided Chebyshev's inequality. We do not present it due to space restrictions. 2

Clearly, Eq. (2) provides a better bound than Eq. (1), since for lower bounds greater values are preferred, and the denominator of Eq. (2) is smaller than the one of Eq. (1). Hence, lower probability bounds can be obtained using Eq. (2).

Agent i wants to assess the ability of a group of agents C to complete task t = (T, u). Thus, a lower bound for P (X > T ) can be obtained using Eq. (2), by setting:

Notice that it must hold that E[X] > T , or else θ ≥ 1.

Furthermore, let i demand a certain confidence level c, 0 < c < 1, so that the bound obtained for a group, using Eq. (2), with θ set as in Eq. (3), is at least c. To select a group of agents, either to directly join or invite its members to join forces together, i would select the group that has the smallest size among those that offer her confidence level of at least c (cf. Alg. 1). In this way, i would have her confidence requirement satisfied; and by selecting an appropriate group with the smallest possible size, a greater portion of u could be distributed to each individual of the coalition.

4.2 The CH2SMethod

Our second method builds on a manipulation of the two-sided Chebyshev's inequality, and it is thus termed CH2S.

Theorem 3 (Two-sided Chebyshev's inequality). Let a random variable X with finite variance, for any k > 0:

Now, we can manipulate Eq. (4), in order to obtain a lower probability bound, in the following way:

The probability bound obtained by Eq. (5) can be exploited in a similar way as in the IPZY method, so we adopt the same notation as before. Here again, agent i wants to assess the ability of a group C to complete task t = (T, u), and the lower bound of Eq. (5) can be obtained, by setting:

2 Note also that an alternative proof appears in Wikipedia.

Thus, i can obtain a lower bound, equal to 1-V ar[X]/k2 , for the probability of the event that X ∈ (T, E[X]+k). Agent i can select a group of agents, out of potentially many, as follows. She chooses the one that has the smallest size among those which provide her with a bound, computed by Eq. (5), and with k as in Eq. (6), that exceeds her required confidence level c, 0 < c < 1.

4.3 The HFMethod

The third method (HF) is based on Hoeffding's inequality.

Theorem 4 (Hoeffding's inequality). Let X1, . . . ,Xn be independent random variables, where all Xi are bounded so that Xi ∈ [li, ui], and let X = ∑ni=1 Xi. Then it holds that:

Hoeffding's inequality can be applied since random variables Xi j are independent and Xi j takes integer values in [0, qmax]. HF exploits Eq. (7) identically to the manner that CH2S exploits Eq.(4), since both Eq.(4) and Eq.(7) provide upper bounds on both tails, and thus their difference is only on the value of the obtained bound.

Algorithm 1: Selecting a coalition that meets an agent's required confidence level

4.4 Discussion

The power of our methods lies in the fact that they do not need to compute the exact distribution of X, since they obtain probability bounds. We have assumed variable independence, and thus an agent's beliefs can be represented by easy-to-maintain conjugate priors (Betas and Dirichlets) over these variables [Grimmett and Stirzaker, 2001]. However, our methods do not depend in any way on the exact priors used.

Note also that IPZY and CH2S do apply if dependence among the variables holds, as well. Computing the distribution of X would then require the computation of the joint probability distribution of the dependent variables, leading to the following computation for P (XiC ≥ T ) and |C| = m:

where the first equality holds since the events are mutually exclusive. The number of solutions to the equation Xi1 +. . .+Xim = κ, where every Xi j is a non-negative integer, is known [Komatsu, 2003] to be (κ+m-1 m-1 ) = O((κ + m)m). Therefore, the computation of P(X ≥ T) is exponential in the number of the agents when Xi j , j ∈ C, are dependent. However, IPZY and CH2S would still work though requiring more time, since computing the variance of X would now take O((n · qmax)2 ), due to the computation of the covariance of each pair of variables. Moreover, a different modeling of beliefs as Dirichlets over the Cartesian product of all variables, or as Dirichlet mixture models, would also be required. Experimentation with dependent variables is future work.

5 An OCF Protocol

We now propose a generic protocol for iterated overlapping coalition formation. It models real-world situations where S tasks per iteration arrive, over a period of I iterations (or rounds), and the resources of the agents are replenished at the end of each round (as such, there is no need for long-term strategic planning on the part of the agents). Note that the protocol can be applied whether there exists an underlying graph in the environment or not. The agents of a coalition C must be connected by some path, however not all agents connected by a given path have to be members of C. The protocol, summarized in Alg. 2, is kept simple, so that it does not interfere with the agents' deliberation over bounds. To the best of our knowledge, this is the first protocol for decentralized overlapping coalition formation under uncertainty.

At each round, tasks are exogenously created and a distinct proposer is exogenously associated with each task. The assignment of proposers to tasks takes place uniformly at random. Following that, the proposers are concurrently asked to form proposals. Thus, each proposer has to select a group of agents, offering a portion of u (the utility granted by the completion of task t = (T, u)) to each of its members, and asking in return for a resource quantity so that the threshold T is met. A proposer can receive proposals from other proposers.

Group selection. The number of possible groups of agents is O(2n ), and thus taking all of them under consideration would be inefficient for a proposer. Instead, we let a proposer i sample K groups of agents, where each agent j ∈ N \ i is included in a group with probability 2-D(i,j) , where D(i, j) is the geodesic distance (shortest path) between nodes i and j. Such a distance between every pair of nodes can be computed in an offline step. Hence, the closer i is to j, with respect to their distance in the (undirected) graph, the more likely it is that j will be included in a group sampled by i, while if i and j are not connected, that is D(i, j) = ∞, then they cannot cooperate. In this way, the position of an agent in the social network affects the likelihood of making a proposal to another agent, for cooperation towards completing a common task. Thereafter, the proposer uses one of our methods in order to select one of the K groups, and then submits individual 〈q, π〉 proposals to its members. The requested quantity q ∈ N+ is the rounded average of samples taken from αij multiplied by qij (the belief that j accepts a proposal), and agent payoff π ∈ R+ is proportional to q, and is distributed to j upon the completion of the task.

Only the proposer and the proposed-to agent have knowledge of the proposal submitted. Furthermore, all proposals to an agent are revealed to her simultaneously.

Response to proposals. Each agent, who has received at least one proposal, responds by either accepting or rejecting each of the proposals. Therefore, agent j has to select which of the, at most S, proposals of the form 〈q, π〉 to accept, where q ∈ N+ and π ∈ R+, in order to maximize her gained utility (at the completion of the tasks), given her resource quantity wj ∈ N+. Thus, the optimal response of an agent is the one that maximizes ∑τ xτ · πτ , subject to ∑τ xτ · qτ ≤ wj, where x is a binary vector of size equal to the number of the proposals that agent j has received. Proposition 1 below follows from a straightforward reduction from KNAPSACK.

Proposition 1. The optimal response of an agent is NP-Hard.

Notice that a responder has no knowledge of the other members that a proposer has proposed to, and hence she cannot infer the probability of task completion. Since an agent's response does not depend on the responses of others, the independence assumption regarding agents' beliefs is reasonable.

Beliefs update. If the response of j to proposal 〈q, π〉, submitted by proposer i, is positive then i increases both aij (Beta update) and αij q (Dirichlet update) by 1. If the response is negative then bij (only Beta update) is increased by 1. Furthermore, if coalition C succeeds in completing a task, then every member of C gets to learn the contribution of every other member, and has her Dirichlet distribution updated in an identical way to that of the proposer.

Notice this allows the modeling of agent behaviour and preferences, e.g. an agent could observe that another agent accepts proposals from the rest of the agents but not from her. We aim to study such phenomena in future work. Finally, after receiving the responses, if the proposer's task has not been accomplished, she covers its remaining needs (if possible).

6 Experimental Evaluation

In this section we provide results on the effectiveness of our methods. We conducted experiments on both an Erd˝os-Renyi random graph [Bollob´as, 2001] of 300 nodes-agents and a real social network-a snapshot of a part of Facebook with 4039 agents [Leskovec and Krevl, 2014]. Our methods are tested for different values of confidence level c demanded by the agents. We compare our methods to a baseline method, in which the group that an agent chooses to make proposals

1 I ←number of rounds 2 S ←number of tasks per round 3 for i = 1 to I do 4 tasks ← createT asks(S) 5 proposers ← createP roposers(tasks) 6 proposers form proposals concurrently, each by sampling K groups and selecting one using {IPZY, CH2S, or HF} and Algorithm 1 7 inform proposed members 8 agents accept or reject the proposals they received 9 inform proposers about responses 10 foreach uncompleted t ∈ tasks do 11 Let proposer of t complete it if she can 12 foreach completed t ∈ tasks do 13 informmembers about the participation of the rest and distribute utility 14 replenish agents' resources and update beliefs

to is the smallest among those whose expected value E[X] exceeds the task threshold value T. 3 Thus, we refer to this method as EV. Selecting EV as the baseline is natural: EV essentially describes the simplest course of action that an agent acting under uncertainty could take. Moreover, there is no pool of alternative decision-making methods we can use as a baseline in such a setting. 4

Game parameters. In the experiments on both graphs, qmax was set to 30 and the resource weight wi of each agent was a (rounded to integer) sample from N(15, 52 ). The hyperparameters of each agent's Beta were initialized to aij = 1 and bij = 1; and the αij r of the Dirichlets to αij r = wj/(D(i, j) · (|r -wj| +1)). In this way αij is bellshaped, with its mode being at wj, the actual (maximum offerable) resource quantity of j. Furthermore, the smaller D(i, j) is, the more sharply peaked the prior is, so the belief updates on αij have greater impact. The value of K, the number of groups that a proposer i samples, was set to 30. The number of samples taken from αij , for defining the requested quantity q of i's proposal 〈q, π〉 to j, was set to 20. The number of rounds I and the number of tasks per round S were set to 200 and 16, respectively, 5 for each run on both graphs. Before making proposals, a proposer invests 75% of her resource to a task.

All results are average values across 30 runs for each experimental setting. The same set of proposers and tasks were generated at the xth round of the yth run in each setting (x ∈ {1, . . . , I = 200} and y ∈ {1, . . . , 30}). We report on the total number of completed tasks by the agents, where for each setting the used method and the value of c were the same for all agents. We tested values of c ∈ {0.5, 0.6, 0.7, 0.8, 0.9}. (In the case of EV there is no c.) We also present the (average) size of the group that the proposers, using each method, choose as the best one to make proposals to. Furthermore, since there is no guarantee that the agents will have their demand for confidence level c fulfilled, we report the confidence fails, the number of times that a proposer failed to achieve that c. In those cases, we let the proposer make proposals to the group which provided the confidence level closest to c. Henceforth, we denote the best group size by bgs, and the confidence fails by cf. The total number of tasks in a run was I · S = 200 · 16 = 3200 (thus cf has a max value of 3200). The implementation was in Python 3 and experiments were run on a PC with an i3 3.3GHz processor and 4GB of RAM.

3 The smaller the group, the greater the portion of utility u its members receive upon task completion.

4 The computation of a centralized solution is intractable, and thus it cannot be used as a means of comparison. Even the positive results in [Zick et al., 2012] hold for very restricted cases.

5 In our experiments we used the standard pseudopolynomial dynamic programming algorithm for KNAPSACK [Kellerer et al., 2004], which, due to the limited number of tasks (and hence proposals), performed in a fraction of time (< 1 ms), as expected (despite Proposition 1); so, agent responses were in fact optimal.

6.1 Erd˝os-Renyi GraphModel

In this random graph model, edge {i, j} is added on the (undirected) graph with probability p. In our setting, we set n = 300 and p = 0.03 (average node distance = 2.83). The threshold values T of the generated tasks were sampled from N(200, 102 ), and the utility u of each task was 10 · T .

As shown in Table 1, our methods consistently outperform EV. Even for IPZY with c = 0.5, the number of completed tasks is much larger compared to that of EV, with a very small increase in bgs. The standard deviation of the number of completed tasks is small for every method. Furthermore, when c ≤ 0.8, proposers using IPZY or CH2S have their required confidence satisfied almost always. For c = 0.9 however, the number of cf increases steeply: for instance, for CH2S with c = 0.8, only 1.33% = 42.7/3200 of the proposals did not meet that requirement, while for CH2S with c = 0.9 that percentage increased to 33.33% = 1066.8/3200. Now, lack of confidence, caused by uncertainty, is a major source of downturns in economic environments [Caldara et al., 2016]. Ideally, we would like to have a metric defining the quality of a method, depending on the number of completed tasks and cofidence fails, but it is not obvious which one that should be. Thus, HF can be deemed unsuitable for this setting, since the number of cf for every value of c is at least 1022.4, and so are IPZY and CH2S for c = 0.9-notwithstanding that for c = 0.9 more tasks were completed, since their completion came with an abrupt increase in cf. On the other hand, both IPZY and CH2S achieve a confidence level of c = 0.8 while maintaining a reasonably low cf number. Then, for IPZY and CH2S, results presented in Table 3 suggest that the more demanding the agents are (with respect to their confidence level), the better the ratio of the number of completed tasks to best group size is. Overall, Tables 1 and 3 suggest that CH2S performs slightly better than IPZY.

Finally, we report that the average time for an entire round to be completed, including coalitional evaluations for all 16 tasks and belief updates for all agents-for some multiple times, since they can participate in multiple tasks-was 2.7 sec for IPZY, 2.9 sec for CH2S and 1.8 sec for HF.

6.2 Facebook Snapshot Graph

The graph of the snapshot of Facebook we experimented on consists of 4039 connected nodes (agents). The threshold values T of the generated tasks were sampled from N(2250, 402 ), and the utility u of each task was 10 · T .

As observed in Table 2, task completion was more challenging in this sparser network (with an average node distance of 3.69). However, the ordering of the methods, for IPZY and CH2S, based on the ratio of the number of completed tasks to bgs, was virtually the same with that of the Erd˝os-Renyi graph, as observed in Table 3. Moreover, we observe that proposers using HF completed more tasks compared to the other two methods, for every value of c, with the value of cf not being tremendously larger. The values in Table 3 corresponding to HF were greater compared to those of IPZY and CH2S for any value of c, and monotonically increase with c, even exceeding 3 for c = 0.9. Thus, our methods outperform the baseline in this environment as well; and HF is a winner.

The difficulty in achieving the completion of tasks can be attested by the fact that even when proposers used the EV

method, about 6.5% = 207.2/3200 of them could not find a (sampled) group whose expected value exceeded the task threshold value. In that case they selected the one with the highest expected value. Thus, it is not surprising that for all our three methods, and for every value of confidence level c, proposers frequently could not fulfill their requirement for exceeding c. The fact that cf increases smoothly with c, as seen in Table 2, combined with the significant increase of the ratio of completed tasks to best group size for c = 0.9, observed in Table 3, lets us conclude that the best value of c in this setting would be 0.9. The average time for the completion of an entire round was 26.5 sec for IPZY, 27.7 sec for CH2S, and 21.3 sec for HF.

7 Conclusions and FutureWork

We presented, for the first time in the literature, three methods that derive probability bounds for effective overlapping coalition formation, where the agents have incomplete information of the value of the resources that the other agents can invest. This setting extends straightforwardly to environments with multiple (rather than one) resource types. All three of them allow agents to demand confidence levels; and significantly outperformed the baseline (which picked coalitions based solely on their expected resource quantity) in terms of the number of tasks completed, and the ratio of this quantity to the size of the group the proposers selected.

Future work includes testing our methods using alternative formation protocols. Moreover, we intend to experiment with settings that allow resources to be depleted over time. This would necessitate long-term strategic planning, which would naturally influence the agents' attempts to derive bounds.

Acknowledgments

Michail Mamakos gratefully acknowledges financial support from the Hellenic Artificial Intelligence Society (EETN) for attending this conference.