Handling Uncertainty in Cooperative Games
Mar 18, 2015

A group of agents works jointly, generating revenue. How should profits be divided? Cooperative games offer a useful framework for formally defining fair and stable revenue divisions.

In the first part of the talk, we introduce some fundamental concepts in cooperative games, such as the core and the Shapley value.

One of the main drawbacks of cooperative games is the amount of information that they require in order to compute revenue divisions; essentially, one needs to know the value of every subset of players. We present two approaches for handling uncertainty in cooperative games.

First,we examine the effect of the quota on voting power (measured by the Shapley value) in weighted voting games, where player weights are not fixed, but are rather the result of a stochastic process. We show that the behavior of the Shapley value is intimately linked to the quota (i.e. the number of votes needed to pass a bill); even small changes to the quota can cause dramatic changes in voting power.

Next, we apply a PAC learning model to cooperative games. In this setting we are interested in two questions: first, given m random samples of coalitions and their values, can we predict the values of unseen coaltions? We study the PAC learnabilty of several well-known classes of cooperative games. We establish a novel connection between PAC learnability and core stability: for games that are efficiently learnable, it is possible to find payoff divisions that are likely to be stable.