TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 03.07.2014

isti-logo

Page Content

to Navigation

Fair Division of Indivisible Goods

Prof. Toby Walsh (University of New South Wales)

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.

Date
Speaker
Location
Language
03.07.2014 16:15
Toby Walsh
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe