Game Theory Discussion Group - Fall 2005


This discussion group is intended for (but not limited to) researchers in a game theory-related area including (but not limited to) mechanism design, equilibrium finding, auction theory, e-commerce, etc. The group meets once a week where someone gives a 1-1.5 hour presentation on current research. The emphasis is on research that is not yet published. Also, overview talks are encouraged. Presentations are informal (i.e. no slides).

Mailing list

The mailing list is (subscribe). This list is not intended for discussion, but rather for announcements and organization. If you have trouble using the list then let Andrew know.


Date/TimeLocationSpeakerTitle and abstract
September 13, 2005
6:30 - 8:00 PM
Wean 7220Andrew Gilpin Mixed-Integer Programming Methods for Finding Nash Equilibria

We present, to our knowledge, the first mixed integer program (MIP) formulations for finding Nash equilibria in games (specifically, two-player normal form games). We study different design dimensions of search algorithms that are based on those formulations. Our MIP Nash algorithm outperforms Lemke-Howson but not Porter-Nudelman-Shoham (PNS) on GAMUT data. We argue why experiments should also be conducted on games with equilibria with medium-sized supports only, and present a methodology for generating such games. On such games MIP Nash drastically outperforms PNS but not Lemke-Howson. Certain MIP Nash formulations also yield anytime algorithms for epsilon-equilibrium, with provable bounds. Another advantage of MIP Nash is that it can be used to find an optimal equilibrium (according to various objectives). The prior algorithms can be extended to that setting, but they are orders of magnitude slower.

September 20, 2005
6:00 - 7:30 PM
Wean 8220Rudolf Müller
Maastricht University
On the bisection auction

One of the issues in mechanism design is communication of information, and how much information needs to be revealed to the center in order to implement a particular allocation rule. We discuss these issues in a simple setting: private value, single item auctions. We present the bisection auction, which performs better in terms of these issues than classical auctions. However, for continous types, it cannot overcome the difficulty that a truthful, efficient auction would require full revelation of the second highest valuation, which is impossible if types can take any real numbers. We proof a very strong formalization of this impossibility. Finally, we show that the continuous bisection auction performs close to what is best possible.

September 27, 2005
6:00 - 7:30 PM
Wean 8220Vince Conitzer Computing Kemeny and Slater Rankings

In a voting (or rank aggregation) setting, each voter ranks all the candidates (this ranking is called a vote), and these rankings are aggregated into a single ranking. The mapping from vote vectors to aggregate rankings is called the voting rule. Two important voting rules are the Kemeny rule, which minimizes the number of times that the aggregate ranking disagrees with a vote on the ranking of a pair of candidates; and the Slater rule, which minimizes the number of times that the aggregate ranking disagrees with the majority of votes on the ranking of a pair of candidates. Unfortunately, both of these rules are NP-hard to execute. I will talk about various computational techniques for executing these rules, including bounds for use in search and a powerful preprocessing technique.

(This research was done while I was visiting IBM Research this summer and is joint work with Andrew Davenport and Jayant Kalagnanam.)

October 18, 2005
6:00 - 7:30 PM
Wean 8220Nina Balcan Mechanism Design via Machine Learning

In this work, we make an explicit connection between machine learning and mechanism design. In doing so, we obtain a unified approach for considering a variety of profit maximizing mechanism design problems, including many that have been previously considered in the literature. In particular, we use techniques from sample-complexity in machine learning theory to reduce problems of incentive-compatible mechanism design to standard algorithmic questions. We apply these results to a wide variety of revenue-maximizing pricing problems, including the problem of auctioning a digital good, the attribute auction problem, and the problem of item-pricing in unlimited-supply combinatorial auctions.

This is joint work with Avrim Blum, Jason Hartline, and Yishay Mansour, to appear in FOCS'05.

October 25, 2005
6:00 - 7:30 PM
Wean 8220No meeting -- FOCS
November 8, 2005
6:00 - 7:30 PM
Wean 8220Rob Shields Eliciting Bid Taker Non-price Preferences in (Combinatorial) Auctions

Recent algorithms provide powerful solutions to the problem of determining cost-minimizing (or revenue-maximizing) allocations of items in combinatorial auctions. However, in many settings, criteria other than cost (e.g., the number of winners, the delivery date of items, etc.) are also relevant in judging the quality of an allocation. Furthermore, the bid taker is usually uncertain about her preferences regarding tradeoffs between cost and non-price features. We describe new methods that allow the bid taker to determine (approximately) optimal allocations despite this. These methods rely on the notion of minimax regret to guide the elicitation of preferences from the bid taker and to measure the quality of an allocation in the presence of utility function uncertainty. Computational experiments demonstrate the practicality of minimax computation and the efficacy of our elicitation techniques.

December 13, 2005
6:00 - 7:30 PM
Wean 8220Vince Conitzer Computing the Optimal Strategy to Commit to

In multiagent systems, strategic settings are often analyzed under the assumption that the players choose their strategies simultaneously. However, this model is not always realistic. In many settings, one player is able to commit to a strategy before the other player makes a decision. Such models are synonymously referred to as leadership, commitment, or Stackelberg models, and optimal play in such models is often significantly different from optimal play in the model where strategies are selected simultaneously.

The recent surge in interest in computing game-theoretic solutions has so far ignored leadership models (with the exception of the interest in mechanism design, where the designer is implicitly in a leadership position). In this paper, we study how to compute optimal strategies to commit to under both commitment to pure strategies and commitment to mixed strategies, in both normal-form and Bayesian games. We give both positive results (efficient algorithms) and negative results (NP-hardness results).

Old pages: Spring 2005, Fall 2004, Spring 2004
Last updated: December 9, 2005