CMU Game Theory Discussion Group - Spring 2009
Overview
The Game Theory Discussion Group is intended for (but not limited to) researchers in a game theory-related area including (but not limited to) computational game theory, algorithmic game theory, 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).
Abe Othman coordinates the discussion group. All meetings will take place in the AMEM lab, Wean 3203 at 5pm.
Mailing List
The mailing list is gametheory-discussiongroup at lists.andrew.cmu.edu (subscribe). This list is not intended for discussion, but rather for announcements and organization. If you have trouble using the list then let Abe know.
Schedule
February 16th
Sam Ganzfried
Sam Ganzfried
The Mathematics of Poker
I will present several interesting examples from the recent book "The Mathematics of Poker" by Ankenman and Chen. This book presents and solves many simplified poker games in which, rather than being dealt cards from a discrete set, players are dealt real numbers uniformly at random from [0,1]. If there is time, I will describe an algorithm I developed (joint with Tuomas Sandholm) that generalizes the approach used in this book to several new settings and leads to stronger play in two-player limit Texas hold'em.
March 30th
Abe Othman
Abe Othman
Finding Approximate Competitive Equilibria in Combinatorial Assignment
The combinatorial assignment problem involves allocating a set of objects with integral capacity to
a set of agents with qualitative preferences over
bundles of objects; the application we explore in
this paper is course allocation to students. We
investigate how to computationally implement an
approach to this problem which uses approximate
competitive equilibria to balance notions of ef?ciency, fairness, and incentives; participants are en-
dowed with budgets of “funny money” and anonymous prices are set on objects. This is similar to
the winner determination problem in combinatorial auctions (WDCA), except there is no numeraire
with which to compare individual utilities, since
the currency here has no value after the assignment. Despite the similarities between the problems, we show that the mixed integer programming
(MIP) approach used in clearing WDCA cannot
be tractably represented in this new context. We
present a solution that uses tabu search to guide
price determination, and MIPs to solve individual
demand problems in parallel at each iteration. Our
approach is the first to effectively clear large-scale
markets of this kind in practice. Joint work with Eric Budish (HBS/Chicago Booth) and Tuomas Sandholm.
Previous Years