Game Theory Discussion Group - Fall 2005

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.

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.

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.)

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.

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.

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).