Arbitration and Stability in Cooperative Games with Overlapping Coalitions

1 Introduction

Consider the following scenario: a group of agents is tasked with completing some projects; the agents divide into groups, and using the resources available to each group, agents generate profits, which must in turn be divided among group members. Cooperative game theory [Peleg and Sudh¨olter, 2007] studies such scenarios; formally, Given a set of agents N = {1, . . . , n}, the value of each subset S of N is given by a function v : 2N → R. Agents first form a coalition structure CS by partitioning into disjoint sets; then, the value of each subset S ∈ CS is divided among the members of S. Such payoff divisions are also called imputations. Given a game G = 〈N, v〉, a solution concept for G is a set of imputations that share some desirable properties; for example, the core of a game G is the set of all payoff divisions such that for all S ⊆ N, the total payoff to S is at least v(S). That is, the core is the set of all stable payoff divisions, from which no subset of agents would want to deviate.

Classic cooperative game theory assumes that when agents form coalition structures, each agent is a member of only one coalition. In Overlapping Coalition Formation (OCF) games [Chalkiadakis et al., 2010], agents can participate in several coalitions. Each agent i ∈ N controls some finite resource such as time, computational power, or money. The key feature of OCF games is that unlike classic cooperative games, agents are allowed to concurrently commit resources to several coalitions. Thus, a coalition is no longer a subset of N, but rather a vector c in [0, 1]n , where the i-th coordinate of c, ci , denotes how much of i's resource is devoted to c. The valuation function v is now from [0, 1]n to R, rather than from 2N to R. Under this setting, a coalition structure CS is a list of vectors in [0, 1]n , (c1, . . . , ck), and its value is simply ∑kj=1 v(cj). Having formed CS, agents must divide the payoffs from CS in some manner; such a payoff division, x = (x1, . . . , xk), consists of vectors xj, such that ∑ni=1 xij = v(cj). Similarly to the non-overlapping setting, if cij = 0, i.e. agent i does not contribute to cj , then i may not receive any payoff from cj. Those agents for which cij > 0 are called the support of cj. The pair (CS, x) is called an outcome of G.

As noted in [Chalkiadakis et al., 2010], stability in OCF games is a complicated matter; when deviating from (CS , x), a set S may abandon some, but not all of the coalitions it is but they limit their attention to a class of OCF games called threshold task games. We study computational aspects of games with overlapping coalitions in [Zick et al., 2012a], with the additional assumption that agent resources are given by integer weights, and that they may only allocate an integer amount of resources to a coalition. This is a natural discretization of the classic OCF model. Given a discrete OCF game G = 〈N, v〉 and an arbitration function A, we analyze the computational complexity of optimization and stability in OCF games, e.g. computing an optimal coalition structure, deciding the most a set can get by deviating, and deciding whether a given outcome is stable.

Perhaps unsurprisingly, such questions turn out to be NPhard. We then turn to exploring what underlying structural properties of OCF games induce NP-hardness. It turns out that intractability stems to some extent from agents having large weights, but to a greater degree it stems from complex agent interaction. We show that if one assumes that agents have polynomially bounded weights and interactions are simple, then all above questions can be answered in polynomial time. Interactions must be simple in two respects. First, agents must not be allowed to form coalitions with whoever they wish; we show that if agents form a hierarchical interaction structure (i.e. a tree), or have an interaction structure that is nearly hierarchical (i.e. has a bounded treewidth), then all above questions can be answered in polynomial time. Second, agents' reaction to deviation must be local in nature. Recall that given an outcome (CS, x), a set S and S's proposed deviation, the arbitration function A needs to assign a value α(c) for each coalition c in CS . α(c) can depend, in general, on S's effect on coalitions other than c. However, we show that if A allows this (a behavior type which we term global), then one cannot compute the most S can get by deviating in polynomial time, unless P equals NP. Thus, it is important to assume that decisions on how much should S get from c should depend solely an S's effect on c.

2.2 Characterizing Stable OCF Games

The arbitrated core of an OCF game is an appealing solution concept; however, it is often the case that it is empty. The objective of [Zick et al., 2012b] is to provide characterizations of stable games, and offer sufficient conditions for arbitrated core non-emptiness. Given an OCF game G = 〈N, v〉, we can construct an non-OCF game ̂ G = (N,Uv) where Uv is a function on subsets of N, with Uv(S) equaling the most that S can make on its own. In a sense, ̂ G can be seen as a discrete, optimized version of G. We show that G has a nonempty conservative core if and only if ̂ G has a non-empty core. Moreover, we show that our condition for conservative core non-emptiness implies the convexity condition stated in [Chalkiadakis et al., 2010]. We also characterize coalition structures that can be stabilized w.r.t. the refined arbitration function; our result is similar to the Bondareva-Shapley [Shapley, 1967] characterization of stable non-OCF games. Using this characterization, we identify a sufficient condition on v which ensures that the refined core is not empty. Finally, we introduce a class of games which are guaranteed to have a non-empty optimistic core, which we call Linear Bottleneck Games (LBGs). Briefly, an LBG is described by a list of tasks T = (T1, . . . , Tk), where each task requires the participation of some set of agents Aj ⊆ N; if the least contribution of the agents in Aj is x, then the profit generated by Tj is xpj, where pj is the value of Tj. These games model a variety of optimization problems, such as multicommodity flow games. Using linear programming techniques, we show that LBGs have a non-empty optimistic core.

3 Discussion

We introduce a general framework for handling deviation in OCF games, and analyze algorithmic and game-theoretic properties of the resulting model. Our work can be extended in several interesting ways. First, while we provide exact algorithms for computing solution concepts in OCF games, it would be useful to study approximation algorithms for finding coalition structures and stable payoff divisions in OCF games. Second, while we identify properties of OCF games that ensure stability for a given arbitration function, one can alternatively fix an OCF game G, and identify arbitration functions that ensure that G is stable. Finally, while our definition of arbitration functions is applied only to a specific type of strategic agent interaction, namely cooperative games with overlapping coalitions, we believe that our approach is much more general. The effect that non-deviators have on the desirability of deviation can be studied in any agent setting where agents may still interact with non-deviators after their deviation. This occurs, for example, in congestion games, matching markets, and collaboration networks. It would be interesting to see what results would our methodology yield in such settings.