Game Theory Discussion Group

In recent years, certain formalizations of combinatorial negotiation settings, most notably combinatorial auctions, have been intensively studied in our community. A pervasive assumption has been that of no externalities: the agents deciding on a variable (such as whether a trade takes place between them) are the only ones affected by how this variable is set.

This does not capture significant aspects of many important negotiation settings, leading to a loss in welfare. For instance, when an agent is deciding whether to build a public good such as a bridge, many other agents may be affected by this decision as they could use the bridge. As another example, a company setting its pollution level may affect the health and safety of many. To date, there has been no widely studied formalization of combinatorial negotiation settings with externalities. In this paper, we introduce such a formalization.

We show that in a number of key special cases, it is NP-complete to find a feasible nontrivial solution (and therefore the maximum social welfare is completely inapproximable). However, for one important special case, we give an algorithm which converges to the solution with the maximal concession by each agent (in linear time for piecewise constant functions). Maximizing social welfare, however, remains NP-complete even in this setting. We also briefly mention a special case which can be solved (in polynomial time) by linear programming.

A fundamental problem in game theory and artificial intelligence is computing an equilibrium in an extensive form game. In this paper, we study ways of extending previous work on equilibrium computation to games with a large representation. We introduce an automatic way of reducing an extensive form game to a smaller representation which results in faster solution times with standard equilibrium finding algorithms. We describe game transformations from a theoretical point of view and discuss desiderata of a game transformation that we consider necessary for an application of game transformations. We introduce the notion of an extensive game isomorphism and the related notion of the subgame isomorphic game abstraction transformation. We prove that a Nash equilibrium in the smaller, abstracted game can be easily converted to a Nash equilibrium in the original game, thus demonstrating the power and efficacy of our method. We present experimental results for a class of poker games, and we find an equilibrium for the largest poker games to date. We also present an algorithm, GameShrink, which provides an efficient method of performing the subgame isomorphic game abstraction transformations. Finally, we conclude with game approximation methods that do not support equilibrium preservation, but nevertheless result in strategies that work well in practice.

In this talk, I will briefly review games in extensive form. I will also survey previous work including the sequence form representation of a game in extensive form as well as methods for computing equilibria in two-player zero-sum games. Thus, there is no necessary background for this talk.

I will give an exponential time construction that shows that asymmetry is almost as powerful as randomization in auction design (clearly, with computational issues aside). In particular, for the unlimited supply auction problem, this shows that for any randomized competitive auction there exists a asymmetric deterministic auction that obtains almost the same performance guarantees. This is a work in progress, we are still trying to show that there exists a polynomial time computable deterministic competitive auction. This is joint work with Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Nicole Immorlica, Anna Karlin, and Madhu Sudan (who all visited MSR/SVC this summer at roughly the same time).

We consider a procurement auction between a buyer and competitive suppliers in a single period model. At the time of the auction the buyer's demand is uncertain. After being awarded a supply contract the winning supplier decides and invests in the production capacity. We consider the optimal auction mechanism for the buyer for both the cases when the supplier's capacity investment is observable to the buyer, and when it is unobservable. The performance of a few simplier and practically used mechanisms that imply different sources of risks are examined compared to the optimal result. The pay-on-production mechanism bound by a service level agreement achieves near optimal profits.

Consider the problem of matching doctors to training positions, where each doctor supplies a list, ranking the training positions in order of preference. In this talk, we will briefly discuss various definitions of a 'good' matching, before concentrating on the so called popularity metric - A matching M is said to be popular if there is no matching M' such that the number of doctors preferring M' to M exceeds the number of doctors preferring M to M'.

This talk will be accessible to anyone with a general computer science background.

We determine the communication complexity of a number of well-known voting protocols. For each protocol, we first give an upper bound on the communication complexity by providing a communication protocol for it and analyzing how many bits need to be transmitted in this protocol. For many of the voting protocols, it will turn out that we cannot do better than simply letting each voter immediately communicate all her (potentially relevant) information. However, for some protocols (such as the Plurality with Runoff, STV and Cup protocols) there is a natural multistage communication protocol that, with some analysis, can be shown to significantly outperform the immediate communication of all (potentially relevant) information. Finally, for some protocols (such as the Bucklin protocol), we need to introduce a nontrivial communication protocol to achieve the best possible upper bound. Then, we show that our upper bounds are tight by giving a matching lower bound on each voting protocol's communication complexity (with the exception of STV, for which our upper and lower bounds are apart by a factor $\log m$).