27 September 2013, Computational Social Choice Seminar, Judy Goldsmith
Hedonic coalition formation games are characterized by agents who have preferences only about their own coalition, not about the overall partition of agents into coalitions. Consider mission assignments, where the size of the mission is limited by the number of seats in a vehicle. I might prefer a team consisting of an astrogator, an engineer, and a programmer, but only if I were the astrogator. We introduce Roles and Teams Hedonic Games (RTHGs), in which agents have preferences over both the composition of their team and their assigned role within that composition. In this talk, I will define RTHGs and notions of optimization and stability for RTHGs, and give other applications. I will present computational complexity results for optimization and stability, and experimental results for heuristic solvers. This is joint work with Matthew Spradling.