Preferences over Sets in Coalition Formation and Strategic Voting

• Applicant: Professor Dr. Felix Brandt
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 197185415

• Final Report Year: 2019

Final Report Abstract

The project proposal focussed on two related topics from computational social choice and algorithmic game theory: strategyproof irresolute social choice functions and algorithmic aspects of coalition formation. Highlights of this project include • the development of computer-assisted theorem proving in computational social choice using SAT solvers, which has found various applications beyond the scope of this project, • the discovery of sweeping impossibilities for strategyproof irresolute social choice functions, • the development of the Preference Refinement Algorithm in coalition formation, and • the introduction of Fractional Hedonic Games, which has sparked a remarkable amount of follow-up work. Given the limited funding and the breadth of results already obtained in the aforementioned areas, the in-depth study of strategyproof coalition formation mechanisms and stable sets of partitions via generalized tournament solutions has to be postponed to future research.

Publications

• (2019) Fractional Hedonic Games. ACM Trans. Econ. Comput. (ACM Transactions on Economics and Computation) 7 (2) 1–29
  Aziz, Haris; Brandl, Florian; Brandt, Felix; Harrenstein, Paul; Olsen, Martin; Peters, Dominik
  
• Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195:316–334, 2013
  H. Aziz, F. Brandt, and H. G. Seedig
  
• Pareto optimality in coalition formation. Games and Economic Behavior, 82:562–581, 2013
  H. Aziz, F. Brandt, and P. Harrenstein
  
• Set-monotonicity implies Kelly-strategyproofness. Social Choice and Welfare, 45(4):793–804, 2015
  F. Brandt
  
• Strategic abstention based on preference extensions: Positive results and computer-generated impossibilities. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 18–24. AAAI Press, 2015
  F. Brandl, F. Brandt, C. Geist, and J. Hofbauer
  
• Finding strategyproof social choice functions via SAT solving. Journal of Artificial Intelligence Research, 55:565–602, 2016
  F. Brandt and C. Geist