BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Pareto Optimality in Coalition Formation - Paul Harrenstein (Unive
 rsity of Oxford)
DTSTART:20130218T150000Z
DTEND:20130218T160000Z
UID:TALK42350@talks.cam.ac.uk
CONTACT:Felix Fischer
DESCRIPTION:A minimal requirement on allocative efficiency in the social s
 ciences is Pareto optimality. In this paper\, we identify a close structur
 al connection between Pareto optimality and perfection that has various al
 gorithmic consequences for coalition formation. Based on this insight\, we
  formulate the _Preference Refinement Algorithm (PRA)_ which computes an i
 ndividually rational and Pareto optimal outcome in hedonic coalition forma
 tion games. \nOur approach also leads to various results for specific clas
 ses of hedonic games. In particular\, we show that computing and verifying
  Pareto optimal partitions in general hedonic games\, anonymous games\, th
 ree-cyclic games\, room-roommate games and B-hedonic games is intractable 
 while both problems are tractable for roommate games\, W-hedonic games\, a
 nd house allocation with existing tenants.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR