Game Theory Discussion Group - Spring 2005


This discussion group is intended for (but not limited to) computer scientists doing research in a game theory-related area including (but not limited to) mechanism design, equilibrium finding, 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
February 7, 2005
6:00 -- 7:30 PM
Wean 4625Vince Conitzer Automatically Designing Multistage Mechanisms

We present the first general-purpose techniques for automatically designing multistage mechanisms. These can reduce elicitation burden by only querying agents for information that is relevant given their answers to previous queries. We first show how to turn a given (e.g., automatically designed) single-stage mechanism into the most efficient corresponding multistage mechanism given a specified elicitation tree. We then present greedy and dynamic programming algorithms that will determine the elicitation tree (optimal in the DP case). Next, we show how the query savings inherent in the multistage model can be used to design the underlying single-stage mechanism to maximally take advantage of this approach. Finally, we present negative results on the design of multistage mechanisms that do not correspond to dominant-strategy single-stage mechanisms: an optimal multistage mechanism in general has to randomize over queries to hide information from the agents.

March 14, 2005
6:00 -- 7:30 PM
Wean 4623Liz Crawford The General Game Playing Competition and Multi-Agent Meeting Scheduling

This talk will be in two parts. And both parts will be informal. In the first part I will describe the General Game Playing Competition which is being held for the first time at AAAI this year. In the second part I will describe our work on the Multi-Agent Meeting Scheduling Problem. I will talk about the difficulties we encountered in trying to use a Mechanism Design approach and some of our current work on intelligent negotiation.

March 21, 2005
6:00 -- 7:30 PM
Wean 4623Vince Conitzer A Technique for Reducing Normal Form Games to Compute a Nash Equilibrium

We present a technique for reducing a normal-form game, $O$, to a smaller normal-form game, $R$, for the purpose of computing a Nash equilibrium. This is done by computing a Nash equilibrium for a subgame, $G$, of $O$ for which a certain condition holds. We also show that such a subgame $G$ on which to apply the technique can be found in polynomial time (if it exists). We show that the technique does not extend to computing Pareto-optimal or welfare-maximizing equilibria. Finally, we present a class of games, which we call ALAGIU (Any Lower Action Gives Identical Utility) games, for which recursive application of (special cases of) the technique is sufficient for finding a Nash equilibrium in linear time.

March 28, 2005
6:00 -- 7:30 PM
Wean 4623Nina Balcan Attribute Auctions

In an attribute auction, a seller (auctioneer) is marketing some good of unlimited supply to n bidders, each of whom has a set of public attributes. The goal of the seller is to achieve a revenue competitive with the best pricing function in some given class of functions over the attributes. This setting was introduced in [Blum, Hartline 2005], where the special case of 1-dimensional real-valued attributes was considered, and results were given for the comparison class of piecewise-constant functions with k pieces.

In this work, we consider attribute auctions more generally, and show a natural strategy by which an auctioneer can perform nearly as well as the best pricing scheme in any given class, so long as the number of bidders is large enough as a function of an appropriate measure of the complexity of the class. We do this by making a natural connection to the notion of sample-complexity in machine learning, though from a learning perspective the auction setting presents certain unique challenges: in particular, the loss function is discontinuous and asymmetric, and the range of bid values may be large. We also consider a partial-information setting in which the auctioneer only gets information by making offers that are either accepted or rejected, and provide bounds for that case as well.

Joint work with Avrim Blum, Jason Hartline, and Yishay Mansour.

April 4, 2005
6:00 -- 7:30 PM
Wean 4623Andrew Gilpin Repeated Games of Incomplete Information

Consider a repeated game in which players are only partially informed about the actual stage game. The theory of repeated games of incomplete information characterizes the optimal strategies each player should play. In this overview talk, I will present the basic theory for two-player zero-sum games of incomplete information, with lack of information on one side.

I will conclude with a few thoughts about the computational problem of computing optimal strategies.

April 18, 2005
4:15 -- 5:30 PM
Wean 4623Vince Conitzer How Mechanism Design and Computer Science Can (and Should) Interact

Practice talk for thesis proposal.

Old pages: Fall 2004, Spring 2004
Last updated: April 18, 2005