Dividing the Indivisible
- 16:30 5th September 2012 ( Trinity Term 2012 )Lecture Theatre B
We study in detail a simple sequential procedure for allocating a set of indivisible goods to multiple agents. Agents take turns to pick items according to a policy. For example, in the alternating policy, agents simply alternate who picks the next item. Many of us used such a procedure at school when we were picking teams to play football. A similar procedure has been used by Harvard Business School to allocate courses to students. We study here the impact of strategic behavior on the complete-information extensive-form game of such sequential allocation procedures. We show that computing the subgame-perfect Nash equilibrium is PSPACE-hard in general, but takes only linear time with two agents. Finally we compute the optimal policies for two agents in different settings, including when agents behave strategically and when agents can give away items.
Speaker bio
Toby Walsh is Research Group Leader at NICTA. He is adjunct Professor at the University of New South Wales, external Professor of Uppsala University and an honorary fellow of Edinburgh University. He has been elected a fellow of both the Association for the Advancement of Artificial Intelligence and the European Coordinating Committee for AI. He is one of the Editors of the Handbook for Constraint Programming, and the Handbook for Satisfiability. He has been Program and/or Conference Chair of the CP, SAT, IJCAR and IJCAI conferences.Share this:
