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

Date/Time | Location | Speaker | Title and abstract |
---|---|---|---|

February 7, 2005 6:00 -- 7:30 PM | Wean 4625 | Vince Conitzer |
Automatically Designing Multistage Mechanisms
We present the first general-purpose techniques for automatically
designing |

March 14, 2005 6:00 -- 7:30 PM | Wean 4623 | Liz 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 4623 | Vince 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 4623 | Nina 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 4623 | Andrew 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 4623 | Vince 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