![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Monday 18 February 2013, 15:00-16:00
Pareto Optimality in Coalition Formation
- 👤 Speaker: Paul Harrenstein (University of Oxford)
- 📅 Date & Time: Monday 18 February 2013, 15:00 - 16:00
- 📍 Venue: MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
Abstract
A minimal requirement on allocative efficiency in the social sciences is Pareto optimality. In this paper, we identify a close structural connection between Pareto optimality and perfection that has various algorithmic consequences for coalition formation. Based on this insight, we formulate the Preference Refinement Algorithm (PRA) which computes an individually rational and Pareto optimal outcome in hedonic coalition formation games. Our approach also leads to various results for specific classes of hedonic games. In particular, we show that computing and verifying Pareto optimal partitions in general hedonic games, anonymous games, three-cyclic games, room-roommate games and B-hedonic games is intractable while both problems are tractable for roommate games, W-hedonic games, and house allocation with existing tenants.
Series This talk is part of the Optimization and Incentives Seminar series.
Included in Lists
- All CMS events
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- CMS Events
- DPMMS info aggregator
- DPMMS lists
- DPMMS Lists
- Economics and Computer Science Talks
- Hanchen DaDaDash
- Interested Talks
- MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- Optimization and Incentives Seminar
- School of Physical Sciences
- Statistical Laboratory info aggregator
- Trust & Technology Initiative - interesting events
- yk449
Note: Ex-directory lists are not shown.