Soziale Wahl, Pfeilsatz und offene Probleme?

In den letzten Monaten habe ich angefangen, mir Vorlesungen über soziale Entscheidungen, den Satz von Arrow und verwandte Ergebnisse zu machen.

Nachdem ich die wegweisenden Ergebnisse gelesen hatte, fragte ich mich, was mit partiellen Bestellpräferenzen passiert. Die Antwort ist in der Arbeit von Pini et al. : Teilweise geordnete Präferenzen aggregieren: Unmöglichkeit und Möglichkeit ergeben sich . Dann habe ich mich gefragt, ob es möglich ist, eine Charakterisierung zulässiger sozialer Wahlfunktionen zu finden. Und wieder hat es jemand getan ( Vollständige Charakterisierung von Funktionen, die die Bedingungen des Pfeilsatzes von Mossel und Tamuz erfüllen). Ich werde keine vollständige Liste geben, aber ich kann mir vorstellen, welche Probleme im Zusammenhang mit der sozialen Wahl in den letzten 5 Jahren gelöst wurden :(

Wissen Sie also, ob es eine Umfrage darüber gibt, was in letzter Zeit auf dem Gebiet getan wurde und was nicht?

Eine andere Frage ist: Sind Sie sich der Komplexität und der Probleme im Zusammenhang mit der sozialen Auswahl bewusst (z. B. der Komplexität, die größte Teilmenge von Benutzern zu finden, die für mindestens eine soziale Auswahlfunktion kompatibel sind, oder dieser Art von Frage).

Ihre Frage ist zum richtigen Zeitpunkt gestellt, da die neueste Ausgabe des CACM einen Artikel enthält, der genau dies tut: http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections /voller Text

Kurz gesagt, es gibt eine Menge Arbeit von Conitzer, Tovey und anderen über die tatsächliche Härte von Abstimmungsmechanismen, die im Prinzip mit dem Pfeil-Theorem zerbrechlich sind, sowohl im schlimmsten Fall als auch unter Verteilungsannahmen.

Es gibt viele Komplexitätsprobleme, die mit vielen der Themen zusammenhängen, die in der sogenannten Social Choice-Theorie auftauchen. Dazu gehört die Komplexität der Entscheidung, wer der Gewinner ist, wenn mit einer bestimmten Methode die Stimmzettel eines bestimmten Typs zu einer Wahl für die Gesellschaft zusammengefasst werden. Es gibt auch Komplexitätsprobleme beim Versuch, einen Weg zu finden, strategisch zu wählen (anstatt die wahren Präferenzen zu verwenden), wenn Informationen über die Präferenzen anderer Wähler verfügbar sind, wenn eine bestimmte Methode verwendet wird, um ein besseres Ergebnis für eine bestimmte Person zu erzielen oder eine Gruppe von Menschen. Komplexität zeigt sich auch beim Entwurf "sicherer" Online-Abstimmungssysteme.

Dies ist eine riesige Literatur über soziale Entscheidungen, aber einige gute Bücher für Interessierte wären:

Donald Saari, Entscheidungen und Wahlen, Cambridge U. Press, 2001.

Donald Saari, Entsorgung von Diktatoren, Entmystifizierung von Wahlparadoxen, Cambridge U. Press, 2008.

Alan Taylor, Social Choice und die Mathematik der Manipulation, Cambridge U. Press, 2005.

In letzter Zeit gab es viele Entwicklungen zu den rechnerischen Aspekten der sozialen Wahl. Die folgende Website gibt viele Hinweise auf die einschlägige Literatur:

http://www.illc.uva.nl/COMSOC/

Der Satz von Arrow ist ein klassischer Satz. Ein offenes Problem zu finden, ist für Theoretiker sozialer Entscheidungen (oder zumindest für mich) nicht einfach.

Mein allgemeiner Rat an Studierende der Volkswirtschaftslehre lautet: "Halten Sie sich vom Theorem fern, es sei denn, Sie können Ihren Beitrag auf einige neuere Ideen beziehen (z. B. neu vorgeschlagene Axiome, etwas untersuchte Lösungen und modische Verhaltensannahmen). Versuchen Sie, ein Problem zu finden, das nicht mit dem Satz von Arrow zusammenhängt. Erst wenn Sie eine allgemeine Vorstellung davon haben, welche Art von Problem Sie verfolgen möchten, lesen Sie das Handbuch für soziale Entscheidungen und Wohlfahrt .

Rechenprobleme könnten eine dieser "neueren" Ideen sein. Obwohl die Untersuchung der Komplexität (der Regeln oder der Manipulation oder der Lösung usw.) das Hauptanliegen der Informatiker ist (wie von anderen vorgeschlagen), gibt es Exit-Papers (wie Mihara, 1997, Arrow's Theorem und Turing Computability) , Economic Theory 10: 257-276), die das (grundlegende?) Problem der Berechenbarkeit im Rahmen von Arrow untersucht. ;-)

Lassen Sie mich auf die beiden von Ihnen vorgeschlagenen Probleme eingehen.

1. Ich bin mir nicht sicher, ob Theoretiker sozialer Entscheidungen es versäumt haben, Teilordnungen zu berücksichtigen. Wenn ja, dann wahrscheinlich, weil "Parteilichkeit" durch strenge Präferenzen ausgedrückt werden kann (wie bei Kumabe und Mihara, Präferenzaggregationstheorie ohne Azyklizität: Kern ohne Mehrheitsunzufriedenheit, Spiele und wirtschaftliches Verhalten , in der Presse). (Vergessen Sie in diesem Fall die schwache Präferenz R besser oder definieren Sie sie anders [damit sie nicht vollständig wird]: Wenn Sie xRy [x ist schwach bevorzugt gegenüber y] definieren, wenn nicht yPx [nicht y ist bevorzugt gegenüber x], haben wir P ist asymmetrisch, wenn R vollständig ist !)

2. Einige Autoren sind es nicht, aber ich denke, die meisten Sozialwahltheoretiker sind vorsichtig genug, um nicht zu behaupten, dass eine diktatorische soziale Wohlfahrtsfunktion die IIA erfüllt. Zum Beispiel sage ich (Mihara, 1997), dass innerhalb der sozialen Wohlfahrtsfunktionen, die IIA erfüllen , eine Regel diktatorisch ist, wenn sie eine bestimmte Bedingung erfüllt. Sie wussten, dass das Problem offen war, waren aber wahrscheinlich nicht daran interessiert, diktatorische Funktionen weiter zu klassifizieren. (Vielleicht können Mossel und Tamuz Armstrongs von Mihara zitierte Errata kommentieren. Sie identifizieren eine Folge von Diktatoren oder Ultrafiltern.) Dies legt eine andere Forschungsstrategie nahe (die ich nicht empfehlen kann): Versuchen Sie, ein Problem zu finden, das für Theoretiker sozialer Entscheidungen uninteressant ist.