|Monday 5th May, 2014|
|9:00am – 10:30am||
|11:00am – 12:30pm||
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.
The Shapley value is arguably the most central normative solution concept in cooperative game theory. It species 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. . 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 infinity. On the other hand, when a finite number of samples is drawn, an unquantiable 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 signicantly 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 eectiveness of using stratied sampling for improving the bounds further.
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.
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|
|2:00pm – 3:00pm||
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|
|4:00pm – 6:00pm||
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.
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 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.  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  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.
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 different 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 define 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 protable 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 dene 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.
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.