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

In diesem Vorhaben werden zwei Themengebiete der algorithmischen Spieltheorie und „computational social choice“ behandelt: Die Manipulation von Wahlverfahren und die Bildung von Koalitionen in hedonischen Spielen. Ein Wahlverfahren ist nicht-manipulierbar - oder strategiesicher - wenn kein Agent durch das strategische Verfälschen seiner Präferenzen ein, aus seiner Sicht, bevorzugtes Ergebnis erzielen kann. Gibbard und Satterthwaite haben gezeigt, dass resolute Wahlverfahren, d.h. Wahlverfahren, die immer ein einziges Ergebnis liefern, im Allgemeinen manipulierbar sind. Das hat erhebliche Auswirkungen auf deren Anwendbarkeit in Multiagentensystemen und Online-Bündelungsmechanismen. Ähnliche Probleme treten im spezielleren Kontext von hedonischen Spielen, einem eleganten und vielseitigen Modell der Koalitionsbildung, auf. Auch in diesem Zusammenhang lag der Fokus bisher auf resoluten Mechanismen. Wir argumentieren, dass das Aufheben der Resolutheitseinschränkung in beiden Szenarien ein vielversprechender Ansatz zum Erreichen von Robustheit gegenüber Manipulation ist. Dieser Ansatz verlangt ein formales Verständnis der verschiedenen Möglichkeiten wie Präferenzen über einzelnen Ergebnissen zu Präferenzen über Mengen von Ergebnissen erweitert werden können. Wir beabsichtigen in diesem Zusammenhang, (i) zu untersuchen welche nicht-resoluten Wahlverfahren gemäß üblicher Präferenzerweiterungen strategiesicher sind, (ii) die Berechnungskomplexität stabiler Partionen in hedonischen Spielen zu analysieren, (iii) strategiesichere nicht-resolute Mechanismen zum Erreichen von stabilen Partitionen zu entwickeln und (iv) die Anwendbarkeit von verallgemeinerten Turnierlösungen auf hedonische Spiele zu eruieren.

• DFG Programme: Research Grants