Program

CoopMAS2014
  Monday 5th May, 2014
9:00am – 10:30am

Computational Aspects of Cooperative Game Theory
with Mike Wooldridge

Computational Aspects of Cooperative Game Theory
Presented by Mike Wooldridge
Located in TBD

11:00am – 12:30pm

A Study of Proxies for Shapley Allocations of Transport Costs
with Casey Cahan, Haris Aziz, Charles Gretton, Phillip Kilby, Nicholas Mattei, and Toby Walsh

A Study of Proxies for Shapley Allocations of Transport Costs
Presented by Casey Cahan, Haris Aziz, Charles Gretton, Phillip Kilby, Nicholas Mattei, and Toby Walsh
Located in TBD

We consider the traveling salesperson game (TSG) in which agents correspond to a set of locations, and the cost of each subset of locations is the length of the optimal tour for that subset. The Shapley value, one of the most important normative division schemes in cooperative games, is a principled way of dividing transport costs among such locations. We prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. In view of this negative result, we consider six proxies for the Shapley value which are easier to compute, with two of the proxies appealing to the well-known Held-Karp and Christofides TSP heuristics, respectively. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for fast-moving consumer goods scenarios. Our experiments show that several computationally tractable proxies give good approximations of Shapley allocations in practice.

Bounding the Estimation Error of Sampling-based Shapley Value Approximation
with Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers

Bounding the Estimation Error of Sampling-based Shapley Value Approximation
Presented by Sasan Maleki, Long Tran-Thanh, Greg Hines, Talal Rahwan, and Alex Rogers
Located in TBD

The Shapley value is arguably the most central normative solution concept in cooperative game theory. It speci es a unique way in which the reward from cooperation can be "fairly" divided among players. While it has a wide range of real world applications, its use is in many cases hampered by the hardness of its computation. A number of researchers have tackled this problem by (i) focusing on classes of games where the Shapley value can be computed efficiently, or (ii) proposing representation formalisms that facilitate such efficient computation, or (iii) approximating the Shapley value in certain classes of games. For the classical characteristic function representation, the only attempt to approximate the Shapley value for the general class of games is due to Castro et al. [5]. While this algorithm provides a bound on the approximation error, this bound is asymptotic, meaning that it only holds when the number of samples increases to infi nity. On the other hand, when a finite number of samples is drawn, an unquanti able error is introduced, meaning that the bound no longer holds. With this in mind, we provide non-asymptotic bounds on the estimation error for two cases: where (i) the variance, and (ii) the range, of the players' marginal contributions is known. Furthermore, for the second case, we show that when the range is signi cantly large relative to the Shapley value, the bound can be improved (from O(r=m) to O(?r=m)). Finally, we propose, and demonstrate the e ectiveness of using strati ed sampling for improving the bounds further.

Non Myopic Collaborators (nearly) Get Their Way
with Yair Zick, Yoram Bachrach, Ian Kash, and Peter Key

Non Myopic Collaborators (nearly) Get Their Way
Presented by Yair Zick, Yoram Bachrach, Ian Kash, and Peter Key
Located in TBD

We consider revenue division problems in iterative settings. In our model, a group of players has some initial resources, used in order to generate revenue. At every time-step, the revenue shares received at time t are player resources at time t + 1, and the game is repeated. The key issue here is that the way resources are shared has a dramatic effect on long-term social welfare, so in order to maximize individual long-term revenue one must consider the welfare of others, a behavior not captured by other models of cooperation among economic agents. Our work focuses on homogeneous production functions. We identify conditions that ensure that what players find best for themselves is “nearly” what is best for the group. We apply our results to some families of utility functions, and discuss their implication in these domains.

Similarities and differences between Success and Decisiveness
with Josep Freixas, and Montserrat Pons

Similarities and differences between Success and Decisiveness
Presented by Josep Freixas, and Montserrat Pons
Located in TBD

We consider binary voting systems in which a probability distribution over coalitions is known. In this broader context decisiveness is an extension of the Penrose-Banzhaf index and success an extension of the Rae index for simple games. Although decisiveness and success are conceptually different we analyze their numerical behavior. The main result provides necessary and sufficient conditions for the ordinal equivalence of them. Indeed, under anonymous probability distributions they become ordinally equivalent. Moreover, it is proved that for these distributions, decisiveness and success respect the strength of the seats, whereas luckiness reverses the order.

12:30pm – 2:00pm

Lunch

2:00pm – 3:00pm

Invited talk: Cooperative Game Theory and Water Resources Management: Contributions and Challenges
with Kaveh Madani

Invited talk: Cooperative Game Theory and Water Resources Management: Contributions and Challenges
Presented by Kaveh Madani
Located in TBD

Managing water resources often involves conflicts. Maximization of individual gains by water resource beneficiaries based on self-interest in non-cooperative environments creates major externalities, affecting the health of the resource and the overall gains of its users. The existing water resource literature promotes developing social planner solutions that maximize the total gains of the system based...

3:00pm – 3:30pm

Lightning talks

4:00pm – 6:00pm

Cooperative Game Solution Concepts that Maximize Stability under Noise
with Yuqian Li, and Vincent Conitzer

Cooperative Game Solution Concepts that Maximize Stability under Noise
Presented by Yuqian Li, and Vincent Conitzer
Located in TBD

In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V(S), which is not yet known. In this context, we investigate which solution concepts maximize the probability of ex-post stability (after the true values are revealed). We show how various conditions on the noise characterize the least core and the nucleolus as optimal. Modifying some aspects of these conditions to (arguably) make them more realistic, we obtain characterizations of new solution concepts as being optimal, including the partial nucleolus, the multiplicative least core, and the multiplicative nucleolus.

Cost Allocation for Efficient and Effective Implementation of Product Take-Back Legislation
with Luyi Gui, Atalay Atasu, Ozlem Ergun, and L. Beril Toktay

Cost Allocation for Efficient and Effective Implementation of Product Take-Back Legislation
Presented by Luyi Gui, Atalay Atasu, Ozlem Ergun, and L. Beril Toktay
Located in TBD

Extended Producer Responsibility (EPR) is a major product take-back policy tool that holds producers nancially responsible for the post-use treatment of their products. EPR implementations in practice are typically collective - a large collection and recycling network (CRN) handles multiple producers' products. A major policy challenge is to properly allocate the resulting cost among participating producers. In our study, we address this problem using a cooperative network ow game approach. We identify implementable adjustments to the prevalent proportional methods to ensure core allocations. We also demonstrate the tradeo between coalitional stability and other environmental objectives associated with cost allocation in the EPR context based on a biform game model.

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time
with Anja Rey, and Jorg Rothe

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time
Presented by Anja Rey, and Jorg Rothe
Located in TBD

False-name manipulation refers to the question of whether a player in a weighted voting game can increase her power by splitting into several players and distributing her weight among these false identities. Analogously to this splitting problem, the beneficial merging problem asks whether a coalition of players can increase their power in a weighted voting game by merging their weights. Aziz et al. [1] analyze the problem of whether merging or splitting players in weighted voting games is beneficial in terms of the Shapley–Shubik and the normalized Banzhaf index, and so do Rey and Rothe [20] for the probabilistic Banzhaf index. All these results provide merely NP-hardness lower bounds for these problems, leaving the question about their exact complexity open. For the Shapley–Shubik and the probabilistic Banzhaf index, we raise these lower bounds to hardness for PP, “probabilistic polynomial time,” and provide matching upper bounds for beneficial merging and, whenever the new players’ weights are given, also for beneficial splitting, thus resolving previous conjectures in the affirmative. It follows from our results that beneficial merging and splitting for these two power indices cannot be solved in NP, unless the polynomial hierarchy collapses, which is considered highly unlikely.

Paths to Stability in Two-Sided Matching under Uncertainty
with Emiliya Lazarova, and Dinko Dimitrov

Paths to Stability in Two-Sided Matching under Uncertainty
Presented by Emiliya Lazarova, and Dinko Dimitrov
Located in TBD

In the present paper we re-visit the question whether an equilibrium outcome in the standard one-to-one, two-sided market can be reached in a decentralized manner when, realistically, the assumption of perfect information is removed. In our setup, market participants have preferences over the types of agents with whom they can be matched, but not over their identities. We keep information requirements to the minimum, that is, initially, players only know their own type, which is allowed to be independent of individual preferences. Thus, two agents of the same type may have di fferent preferences. Agents gather information about the type of their partners in the process of matching and thus, each player's information set expands by matching with a new partner. We defi ne an outcome for such a two-sided matching problem under uncertainty to consist of a matching and a system of beliefs collecting each agent's beliefs about the type of the agents from the opposite side of the market. We focus on outcomes where the system of beliefs is consistent with the process of learning via matching and where there are no further pro table deviations for any pair of players. Using these main ingredients of our setup, we address the question whether it is possible to reach a stable and consistent outcome from any initial self-consistent outcome, and answer it in the positive (Theorem 1). We then turn to the study of the links of a matching problem under uncertainty and the corresponding problem under complete information, where agents' preferences over individuals in the latter follow their preferences over types in the former. We can readily show that the matching part of any stable and consistent outcome for the problem under uncertainty is a stable matching for the problem under complete information (Theorem 2). In order to connect, however, a stable matching for the latter problem to a stable and consistent outcome of the former, we need to take into account the way in which types are attributed to agents. If types are assigned as random independent draws from the set of types without replacement, then any stable matching under complete information is part of a stable and consistent outcome of the corresponding matching problem under uncertainty (Theorem 3). If, on the other hand, types are assigned to agents as random independent draws from the set of types with replacement, then two important features connecting the problem under uncertainty and its corresponding problem under complete information play a crucial role: (1) strict preferences over types do not imply strict preferences over potential partners any more, and (2) knowing the type of one partner is not informative about the probability with which other potential partners are ranked higher than the current one. We handle these issues by restricting our analysis to matching problems where agents of the same type have preferences which are dichotomously aligned, that is, we require for any two agents of the same type that the sets of their individually rational types as well as their top types coincide. Then, our nal result (Theorem 4) relates any stable matching for the problem under complete information to a homomorphic matching and a consistent system of beliefs for the problem under uncertainty, provided that agents' preferences over types are dichotomously aligned. Here we de ne two matchings to be homomorphic if the number of same-type agents who are matched to a given type of agents on the other side of The market is equal in both matchings.

Stable collaboration in unstable environments
with Pascal Francois Faye, Samir Aknine, Onn Shehory, and Mbaye Sene

Stable collaboration in unstable environments
Presented by Pascal Francois Faye, Samir Aknine, Onn Shehory, and Mbaye Sene
Located in TBD

We present a novel coalition formation mechanism where coalition robustness and stability cannot be computed ahead of task execution. We deal with the context in which the tasks evolve over time, agent availability varies and stability during collaborative task execution is required. Our method combines alliances and recommendations in order to form stable coalition despite the dynamics of the tasks and the instability of the agents. We study our mechanism theoretically and then evaluate analytically and experimentally.