CMU Game Theory Discussion Group - Fall 2008
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
August 26th
Ariel Procaccia
Ariel Procaccia
Approximating Lewis Carroll's Voting Rule
Charles Dodgson (better known by his pen name, Lewis Carroll)
suggested an appealing voting system in 1876. Unfortunately,
at the time Dodgson did not take into account such futuristic
considerations as computational complexity, and, as it turned
out more than a century later, computing the Dodgson score of
a candidate is NP-hard.
I will present two very different approximation algorithms, as well as inapproximability results, for the Dodgson score and a related problem, the Young score. I will also try to position this work in the context of a wider agenda: studying the desirability of approximation algorithms as voting rules. Care will be taken to present the necessary concepts from social choice theory using as many PowerPoint animations as humanly possible.
NB: Special Time/Place - 1pm @ NSH 3305
I will present two very different approximation algorithms, as well as inapproximability results, for the Dodgson score and a related problem, the Young score. I will also try to position this work in the context of a wider agenda: studying the desirability of approximation algorithms as voting rules. Care will be taken to present the necessary concepts from social choice theory using as many PowerPoint animations as humanly possible.
NB: Special Time/Place - 1pm @ NSH 3305
October 7th
Andrew Gilpin
Andrew Gilpin
Theory and Applications of the Kelly
Criterion
I will discuss the Kelly criterion, which specifies the optimal amount to
wager when facing infinitely repeated wagers. The Kelly criterion
maximizes growth rate and makes bankruptcy impossible. I will review the
basic theory behind the criterion and discuss two previously published
algorithms for computing optimal wager amounts when facing multiple
wagers. I will describe a few applications of the criterion, including one
that is in current deployment. I will describe why these algorithms can't
be easily extended to the case of optimal wagering in a prediction market
using the logarithmic market scoring rule, and present some ideas for an
algorithm that might extend to this case.
Previous Years