SOCIAL SOFTWARE for elections, the allocation of tenders and coalition/alliance formation (SSEAC)
Zusammenfassung der Projektergebnisse
Im Rahmen der Arbeiten der Kieler Gruppe, im Originalantrag mit Individual Project 4 bezeichnet, wurden neue Methoden zur Analyse und für den Entwurf von Abstimmungssystemen, sogenannten Einfachen Spielen (engl. simple games), entwickelt. Aufbauend auf die theoretischen Ergebnisse wurde weiterhin eine web-basierte Software implementiert und veröffentlicht, welche die Ergebnisse für Anwender und Forscher (z.B. aus der Politologie, der Soziologie oder den Wirtschaftswissenschaften) unmittelbar nutzbar macht. Schließlich wurde noch das existierende RelView System gründlich überarbeitet, auch im Hinblick auf den Einsatz in der Spiel- und der Sozialwahltheorie. Abstimmungssysteme spielen heutzutage in vielen Bereichen eine große Rolle, etwa wenn politische Entscheidungen im Rat der Europäischen Union oder anderen solchen Gremien getroffen werden. Der Entwurf solcher Systeme stellt jedoch eine Herausforderung dar, weil Abstimmungssysteme teils kompliziert sind und es damit oft schwer fällt, die genauen Mechanismen zu verstehen und zu bewerten. Diese Probleme stehen jedoch einem fairen Entwurf von Abstimmungssystemen entgegen. Das mathematische Modell für solche Abstimmungssysteme sind sogenannte Einfache Spiele, welche äquivalent sind zu monotonen Booleschen Funktionen. Für Boolesche Funktionen ist bereits lange bekannt, dass sogenannte (quasi-)reduzierte und geordnete binöre Entscheidungsdiagramme (Qobdds, bzw. Robdds) diese oft sehr kompakt darstellen können, sofern die dargestellte Funktion strukturell einfach ist. Dies ist insbesondere bei Einfachen Spielen für Abstimmungssysteme in der Praxis der Fall, wie wir bei zahlreichen Experimenten mit dem Robdd-basierten Werkzeug RelView festgestellt haben. Davon ausgehend haben wir dann begonnen, Probleme für Einfache Spiele direkt mit Hilfe von Qobdds zu lösen, um so die teils ineffizienten relationalen Konstruktionen des RelView Systems zu vermeiden. Anders als sonst üblich, werden in der Praxis verwendete Darstellungen von Einfachen Spielen, z.B. mit einer Quote und einer Liste von Gewichten für die Teilnehmer, wie es bei gewichteten Mehrheitsspielen der Fall ist, zunächst in ein Qobdd überführt. Probleme werden dann mit dem Qobdd als Eingabe gelöst, wobei die Berechnung von sogenannten Machtindizes (z.B. Banzhaf Index, Shapley-Shubik Index) ein typisches Problem bei Abstimmungssysteme darstellt. Trotz des erwarteten zeitlichen Mehraufwandes durch diese Art der Zwischendarstellung, ist das zeitliche Defizit überraschend gering. Bei gewichteten Darstellungen ist dies dadurch begründet, dass Qobdds lediglich explizite Darstellungen der Berechnungen sind, welche Algorithmen sonst vornehmen. Der benötigte Platz för die Speicherung eines Qobdds ist jedoch bei einigen wenigen Instanzen in der Praxis problematisch. Besonders gewinnbringend beim Einsatz von Qobdds zur Lösung von Problemen für Einfache Spiele ist, dass die entwickelten Algorithmen für jedes Einfache Spiel angewendet werden können, sofern das Qobdd aus der jeweilig verwendeten Darstellung in der Praxis erzeugt werden kann. Dies ist jedoch für gewichtete Darstellungen und darauf basierende komplexere Darstellungen der Fall, da hier bereits Standardalgorithmen (z.B. binäre Synthese) für Qobdds ausreichen. Andere in der Literatur vorgestellte Ansätze beschränken sich oft auf nur eine in der Praxis verwendete Darstellung und nur ein Problem, bzw. eine Klasse von Problemen (z.B. die Berechnung von Machtindizes). Dies hat dazu geführt, dass sich bisherige Software für die Analyse von Abstimmungssystemen nur für wenige in der Praxis auftretende Spiele nutzen lasst. Dieser Missstand wird durch unseren allgemeineren Ansatz weitestgehend behoben.
Projektbezogene Publikationen (Auswahl)
- (2010). Problem solving on simple games via BDDs. In V. Conitzer und J. Rothe (Eds.), Proceedings of the 3rd International Workshop on Computation Social Choice, pp. 11–12. Universität Düsseldorf
Berghammer, R. und S. Bolus
- (2009). An interdisciplinary approach to coalition formation. European Journal of Operational Research 195 (2), 487–496
Berghammer, R., A. Rusinowska und H. de Swart
- (2009). Computational social choice using relation algebra and RelView. In R. Berghammer, A. Jaoua und B. Möller (Eds.), Relations and Kleene algebra in Computer Science, Volume 5827, pp. 13– 28. Springer
Swart H. de, R. Berghammer und A. Rusinowska
- (2010). Applying relation algebra and RelView to measures in a social network. European Journal of Operational Research 202 (1), 182–195
Berghammer, R., A. Rusinowska und H. de Swart
- (2010). On the use of BDDs for solving problems on simple games. In B. Steinbach (Ed.). Proceedings of the International Workshop on Boolean Problems, pp. 113–124. TU Bergakademie Freiberg
Berghammer, R. und S. Bolus
- (2011). A relation-algebraic approach to simple games. European Journal of Operational Research 210 (1), 68– 80
Berghammer, R., S. Bolus, A. Rusinowska und H. de Swart
- (2011). Computations on simple games using RelView. In V. Gerdt, W. Koepf, E. Mayr und E. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing, Volume 6885, pp. 49–60. Springer
Berghammer, R., A. Rusinowska und H. de Swart
- (2011). Power indices of simple games and vector-weighted majority games by means of binary decision diagrams. European Journal of Operational Research 210 (2), 258–272
Bolus, S.
- (2011). Social networks: Prestige, centrality, and influence. In H. de Swart (Ed.), Relational and Algebraic Methods in Computer Science, Volume 6663, pp. 22–39. Springer
Rusinowska, A., R. Berghammer, H. de Swart und M. Grabisch
- (2012). On the use of BDDs for solving problems on simple games. European Journal of Operational Research 222 (3), 529–541
Berghammer, R. und S. Bolus
