Wahlregeln durch datengestützte Ansätze lernen

Wenn Gruppen von Leuten gemeinsam eine Entscheidung treffen müssen, stehen sie oft vor der Herausforderung, verschiedene individuelle Vorlieben in eine kollektive Wahl zu kombinieren. Das kann ein kniffliger Prozess sein, besonders in Bereichen wie der Informatik, wo es wichtig ist, Systeme für Empfehlungen, Spiele und mehr zu entwickeln.

Forscher haben sich schon eine ganze Weile damit beschäftigt, wie man diese kollektiven Entscheidungen treffen kann, vor allem durch die Brille der Sozialwahltheorie. Diese Theorie untersucht die besten Wege, um Algorithmen zu erstellen, die individuelle Vorlieben gemäss bestimmter Standards, den sogenannten Axiomen, sammeln und verarbeiten können. Allerdings kann es sehr schwierig sein, diese Algorithmen zu erstellen, und manchmal ist es sogar nachweislich unmöglich.

Anstatt diese Algorithmen Schritt für Schritt zu programmieren, gibt es einen neuen Ansatz: zu lernen, wie man Entscheidungen aus bestehenden Daten trifft. Diese Methode konzentriert sich hauptsächlich auf Abstimmungsregeln, die eine beliebte Möglichkeit für Gruppen sind, Entscheidungen zu treffen. Frühere Bemühungen in diesem Bereich sind jedoch auf Probleme gestossen, wie die Notwendigkeit grosser Modelle oder Einschränkungen in der Art und Weise, wie individuelle Vorlieben dargestellt werden können.

Wir schlagen eine Methode vor, die das Erstellen einer guten Abstimmungsregel als Lernen aus Beispielen betrachtet, insbesondere durch die Verwendung probabilistischer Modelle. Diese Modelle helfen, eine Reihe möglicher Entscheidungen auszugeben, anstatt nur einen einzigen Gewinner zu bestimmen. Der Schlüssel zu unserer Methode liegt in der Verwendung von neuronalen Netzwerken, einer Art Computerprogramm, das nachahmt, wie unser Gehirn funktioniert, um das zu lernen, was als probabilistische soziale Wahlfunktionen bezeichnet wird.

Unsere Forschung zeigt, dass die Verwendung massgeschneiderter Darstellungen der Vorlieben von Wählern uns hilft, bestehende Abstimmungsregeln effektiver zu lernen. Das gilt besonders, wenn die Darstellung mit den spezifischen Lernzielen übereinstimmt. Darüber hinaus haben wir festgestellt, dass diese gelernten Regeln angepasst werden können, um neue Abstimmungsregeln mit besseren Eigenschaften gemäss den festgelegten Axiomen zu schaffen. In einem unserer Ergebnisse zeigen wir, dass das Anpassen aktueller Abstimmungsregeln helfen kann, Probleme wie das No-Show-Paradoxon zu beheben, bei dem ein Wähler ein günstigeres Ergebnis erzielen kann, indem er überhaupt nicht wählt.

#Verständnis von Entscheidungsmechanismen

In der kollektiven Entscheidungsfindung äussern die Individuen ihre Vorlieben für verschiedene Optionen, und es wird ein System benötigt, um diese in ein einzelnes Ergebnis zu kombinieren. Das Design dieser Systeme ist ein grosses Thema in Bereichen wie Computational Social Choice und Algorithmic Game Theory. Das Ziel ist es, Mechanismen zu schaffen, die nicht nur gut funktionieren, sondern auch bestimmten Prinzipien oder Axiomen genügen.

Eine wichtige Entdeckung in diesem Bereich ist Arrow's Allgemeines Unmöglichkeitstheorem. Dieses Theorem erklärt, dass es unmöglich ist, dass irgendein Entscheidungsprozess gleichzeitig alle gewünschten Axiome erfüllt. Seit Arrows Arbeiten haben Forscher herausgefunden, welche Axiome verschiedene Mechanismen erfüllen können und welche Kombinationen zu Unmöglichkeit führen. Darüber hinaus widmen sich diese Studien den algorithmischen Aspekten, bei denen analysiert wird, wie effizient diese Prozesse umgesetzt werden können.

Abstimmungsregeln zu finden, die bestimmten Axiomen entsprechen, kann eine harte Nuss sein, insbesondere wenn unklar ist, ob eine solche Regel überhaupt existiert. In letzter Zeit gab es einen Trend zur Verwendung von maschinellen Lernmethoden, um neue Mechanismen zu schaffen, die in diese Kategorie passen. Diese Philosophie hat ihren Weg in verschiedene Bereiche gefunden, einschliesslich Auktionen und Abstimmungssysteme.

Frühere Versuche, maschinelles Lernen für Abstimmungsregeln zu nutzen, standen jedoch vor erheblichen Hindernissen. Die Hürden umfassten die Notwendigkeit umfangreicher und komplexer neuronaler Netzwerke, eingeschränkte Datenverfügbarkeit und die Unfähigkeit, die Auswirkungen von Designentscheidungen vollständig zu berücksichtigen.

Unser Ansatz zielt darauf ab, das Lernen bestehender und neuer Abstimmungsregeln zu verbessern, indem wir durchdachte Darstellungen aus der Literatur zur sozialen Wahl verwenden. Diese Darstellungen optimieren den Lernprozess, ermöglichen weniger Parameter und eine bessere Skalierbarkeit bei grösseren Gruppen. Unsere Methode reduziert die Eingangsgrösse für das neuronale Netzwerk, was die Anzahl der benötigten Parameter erheblich verringert. Frühere Arbeiten haben festgestellt, dass ihre Entwürfe für neuronale Netzwerke durch eine feste Eingangsgrösse eingeschränkt waren, was sie dazu brachte, komplexere Architekturen zu erstellen, um die Grösse zu erhöhen und für kleinere Profile zu polstern. Im Gegensatz dazu ermöglichen unsere Darstellungen eine flexible Eingabeschichtgrösse, wodurch es einfacher wird, zu verallgemeinern, wenn sich die Anzahl der Wähler ändert.

In Übereinstimmung mit früheren Studien erkennen wir an, dass Entscheidungsmechanismen bewertet werden können, indem man betrachtet, welche Informationen sie aus Vorliebenprofilen nutzen oder übersehen. Ein wesentlicher Beitrag unserer Studie besteht darin, das Bewusstsein dafür zu verbessern, wie die Wahl der Darstellung mit der Effektivität dieser Systeme beim Lernen und Funktionieren zusammenhängt. Unsere Experimente haben neue theoretische Fragen darüber aufgeworfen, wie viele Informationen durch diese Darstellungen erhalten bleiben und welchen Einfluss sie auf das Lernen von Regeln haben.

#Wie Abstimmung aussieht

Wenn viele Menschen an Abstimmungen denken, stellen sie sich oft traditionelle Regeln vor, die Vorlieben von einer kleinen Gruppe aufnehmen und einen einzigen Gewinner produzieren. In der Realität ist die Welt der sozialen Wahl viel breiter und umfasst Mechanismen, die verschiedene Arten von Dateneingaben und -ausgaben verarbeiten können. Beispielsweise können Wähler Zustimmungen abgeben, Kandidaten bewerten oder ihren Entscheidungen Gewichte zuweisen. Die Ergebnisse können einen einzelnen Gewinner, eine Gruppe von Gewinnern oder eine geordnete Liste von Kandidaten umfassen, unter anderem.

Wir interessieren uns besonders für probabilistische soziale Wahlfunktionen (PSCFs), die eine Reihe von Vorlieben nehmen und eine Wahrscheinlichkeitsverteilung über die Kandidaten bereitstellen. PSCFs haben mehrere Vorteile, wenn es darum geht, Abstimmungsregeln mit neuronalen Netzwerken zu lernen, im Vergleich zu traditionellen Ein-Winner-Regeln. Durch die Ausgabe einer Verteilung vermeiden wir die Komplikationen, die durch das Brechen von Gleichständen entstehen. Zufälliges Brechen von Gleichständen kann ebenfalls nicht effektiv gelernt werden.

Unsere erste Aufgabe besteht darin, zu zeigen, wie etablierte Regeln effizient durch diese Darstellungen gelernt werden können. Danach nehmen wir die Herausforderung an, bestehende Regeln zu verfeinern, um ihre Eigenschaften basierend auf den etablierten Axiomen zu verbessern. Wir konzentrieren uns speziell auf das No-Show-Paradoxon, das auftritt, wenn ein Wähler ein besseres Ergebnis erzielt, indem er nicht wählt.

Einige traditionelle Regeln wie Pluralität, Borda und Simpson-Kramer sind dafür bekannt, dass sie das Partizipationsaxiom erfüllen, was bedeutet, dass kein Wähler von der Enthaltung profitieren kann und somit das Paradoxon vermeidet. Viele andere gängige Abstimmungsregeln fallen jedoch diesem Problem zum Opfer. In unseren Experimenten nehmen wir Modelle, die auf bestehenden PSCFs trainiert wurden, und passen sie mit einer Verlustfunktion an, die eine entspannte Version des Partizipationsaxioms einbezieht, um zu zeigen, wie Regeln geändert werden können, um die Anfälligkeit für das Paradoxon zu verringern, ohne die Genauigkeit zu verlieren.

Das Partizipationsaxiom wird als inter-profilaxiom bezeichnet, da es erfordert, zu berücksichtigen, was hätte passieren können, wenn die Wähler anders gehandelt hätten. Diese Art von Axiom ist besonders herausfordernd für das Lernen, da es die Rechenkomplexität bei der Berechnung von Verlustfunktionen erhöht. Es erfordert auch, dass das Modell Profile unterschiedlicher Grösse verarbeitet, was durch unsere Darstellungen erleichtert wird.

#Die Beziehung zwischen Agenten und Vorlieben

In unserem Forschungsszenario definieren wir eine Gruppe von Wählern und eine Reihe von Kandidaten. Jeder Wähler gibt eine strenge Rangfolge aller Kandidaten an, die seine Vorliebe darstellt. Diese Rangfolge erstellt ein Profil, das einfach die Sammlung aller Stimmen der Wähler ist.

Die Anzahl möglicher Rangfolgen ist riesig, was zu vielen verschiedenen Profilen führt. Die Herausforderung liegt darin, eine Funktion zu erstellen, die als probabilistische soziale Wahlfunktion (PSCF) bekannt ist und ein Profil nimmt und eine Lotterie (eine Wahrscheinlichkeitsverteilung) über die Kandidaten zurückgibt. Jede PSCF kann verwendet werden, um eine nicht-deterministische Abstimmungsregel aufzustellen, indem zufällig ein Gewinner aus der gegebenen Lotterie ausgewählt wird.

Eine deterministische PSCF wählt immer denselben Kandidaten für jedes Profil aus. In vielen Fällen erzeugen die Lotterien, die wir betrachten, Ergebnisse, die für mehrere Kandidaten gleiche Chancen zeigen, was zu komplexeren Ergebnissen führt, als einfach einen Gewinner auszuwählen.

Für neuronale Netzwerke, die Regeln basierend auf dem vollständigen Profil lernen, macht die Notwendigkeit einer Eingabeschicht von fester Grösse die Dinge kompliziert. Wenn die Anzahl der Wähler steigt, steigt auch die Eingangsgrösse, was die Skalierbarkeit behindern kann. Wenn die Anzahl der Wähler sinkt, ist sorgfältiges Polstern erforderlich, um die Integrität des Modells zu erhalten. Um diese Herausforderung zu überwinden, erstellen wir Darstellungen, die relevante Informationen bewahren, während sie eine feste Grösse beibehalten, was Flexibilität bei der Anzahl der Wähler ermöglicht, die in die Eingabedaten einbezogen werden können. Jede Art von Darstellung behält unterschiedliche Mengen der Informationen des ursprünglichen Profils, was beeinflusst, wie gut das Netzwerk verschiedene Regeln lernen kann.

Unsere drei Darstellungen basieren auf der Literatur zu Abstimmungsmechanismen, obwohl sie in der Gemeinschaft des maschinellen Lernens nicht weit verbreitet sind. Jede Darstellung stammt aus einem Stimmprofil, variiert jedoch in der Menge an Informationen, die sie bewahrt.

#Unsere probabilistischen sozialen Wahlfunktionen

Wir haben verschiedene Arten von PSCFs, die wir untersuchen. Zum Beispiel haben wir Punktesysteme wie Borda und Pluralität. Das Ergebnis dieser Punktesysteme kann direkt aus Profilen berechnet werden. Der Borda-Score für einen Kandidaten wird ermittelt, indem die Stimmen aus Profilen gezählt werden, während der Pluralitäts Score einfach den Kandidaten auswählt, der von den meisten Wählern am höchsten eingestuft wird.

Andere Methoden, wie Copeland und Simpson-Kramer, werden im Allgemeinen als Turnierregeln kategorisiert, da ihr Ergebnis aus ihren jeweiligen Matrizen der Präferenzvergleiche abgeleitet werden kann.

In unserer Analyse legen wir besonderen Wert auf die Erhaltung der PSCFs durch verschiedene Darstellungen. Eine Darstellung gilt als erhaltend für eine PSCF, wenn sie genügend Informationen bewahrt, sodass die Funktion intakt bleibt, wenn sie durch die Linse der Darstellung betrachtet wird.

Einige Darstellungen, wie diejenigen, die Präferenzordnungen sortieren, bewahren alle notwendigen Informationen für bestimmte Funktionen. Andere könnten an der Vollständigkeit fehlen, was die Bedeutung der Auswahl der richtigen Darstellung für verschiedene Regeln unterstreicht.

#Lernen aus probabilistischen sozialen Wahlfunktionen

In unseren Experimenten zeigen wir, dass wir mit den richtigen Darstellungen PSCFs lernen können, die gängig verwendete Abstimmungsregeln widerspiegeln, ohne dass übermässig komplexe neuronale Netzwerkdesigns erforderlich sind. Wir haben verschiedene Paare von Regeln und Darstellungen trainiert und getestet, um ihre Leistung genau zu vergleichen und zu verdeutlichen, wie entscheidend die Wahl der Darstellung für effektives Lernen ist.

Wir haben unsere PSCFs mit zufällig generierten Profilen trainiert, um eine vielfältige Auswahl an Vorliebenkombinationen sicherzustellen. Die verwendeten Embeddings boten mehrere Vorteile, insbesondere die Reduzierung der Grösse der Eingabeschicht in unseren neuronalen Netzwerken. Dieses einzigartige Merkmal ermöglichte es uns, dieselbe Architektur für alle Trainingssessions zu nutzen.

Wir verwendeten eine spezifische mehrschichtige Struktur für unsere Netzwerke, die moderne Aktivierungsfunktionen beinhaltete, um effektive Ausgaben zu erzeugen. Unsere Experimente zeigten, dass beim Abgleichen von Regeln mit geeigneten Darstellungen das Lernen dieser Regeln schneller und genauer erfolgt.

Beispielsweise zeigten Regeln wie Pluralität und Borda schnelle Lernraten und konvergierten schnell zu niedrigen Fehlerraten. Dennoch stellten wir auch fest, dass bestimmte Darstellungen für spezifische Regeln am besten abschnitten, während sie bei anderen Schwierigkeiten hatten.

Als wir unsere Modelle skalieren, um unterschiedliche Wählerzahlen zu behandeln, variierte die Leistung. Obwohl es möglicherweise einen leichten Rückgang der Genauigkeit bei grösseren Gruppen gab, hielten die meisten Regeln relativ niedrige Fehlerraten über verschiedene Darstellungen hinweg aufrecht. Diese Flexibilität, sich an unterschiedliche Wählerzahlen anzupassen, ohne die Eingabeschichtgrösse zu ändern, war eine vorteilhafte Eigenschaft unserer Darstellungen.

#Umgang mit dem No-Show-Paradoxon

Das No-Show-Paradoxon stellt eine Herausforderung für viele Abstimmungsregeln dar. Dieses Paradoxon tritt auf, wenn ein Wähler von der Enthaltung profitiert, anstatt seine Stimme abzugeben. Wir haben dieses Problem angegangen, indem wir unsere Modelle neu trainiert haben, um die Auswirkungen dieses Paradoxons zu minimieren, während wir die Genauigkeit beibehalten.

In unseren Tests haben wir untersucht, wie sich verschiedene PSCFs beim Umgang mit dem No-Show-Paradoxon schlagen. Die Ergebnisse zeigten, dass einige Ein-Winner-Regeln wie Borda und Pluralität dieses Paradoxon vollständig vermeideten, während andere auf Herausforderungen stiessen.

Unser Retraining umfasste die Hinzufügung eines Terms zum Lernprozess, der speziell darauf abzielte, das No-Show-Paradoxon zu überwinden. Diese Methode lieferte Einblicke, wie effektiv jede Abstimmungsregel potenzielles strategisches Verhalten von Wählern widerstehen kann.

Durch unsere Analyse haben wir faszinierende Ergebnisse zusammengetragen. Obwohl einige Regeln das Partizipationsaxiom natürlich erfüllen, zeigten die gelernten Modelle dieser Regeln ähnliche Partizipationsverluste wie andere, die anfälliger für das Paradoxon sind. Die Ausmasse der Partizipationsverluste deuteten darauf hin, dass das Lernen von Regeln ein Verständnis dafür erfordert, wie man die Anreize der Wähler zur Enthaltung minimiert.

Die Verwendung weniger Wähler für das Retraining war eine strategische Entscheidung, die auch eine effizientere Berechnung ermöglichte. Angesichts der Komplexität der Bewertung von Verlusten basierend auf potenziellen Alternativen verbesserte diese Anpassung unsere Fähigkeit, zu analysieren, wie gut unsere PSCFs sich an das Partizipationsaxiom anpassen konnten.

#Einsichten und zukünftige Richtungen

Zusammenfassend haben wir gezeigt, dass es möglich ist, bekannte probabilistische soziale Wahlfunktionen effizient zu lernen und sie auf Weisen zu verbessern, die traditionelle Designmethoden nicht erreicht haben. Unser Fokus auf die richtigen Darstellungen für die Wählervorlieben hat uns geholfen, effektive Ergebnisse beim Lernen und beim Entwerfen neuer Regeln zu erzielen.

Als nächsten Schritt streben wir an, zu erforschen, ob andere Darstellungen entwickelt werden können, die die bereits aus der sozialen Wahl-Literatur abgeleiteten übertreffen. Diese Exploration könnte neue Einblicke liefern, insbesondere für Regeln, die auf traditionelle Weise schwer oder rechenintensiv zu analysieren sind.

Insgesamt ebnet unsere Arbeit den Weg für fortlaufende Forschung, die maschinelles Lernen mit etablierten Prinzipien der sozialen Wahl kombiniert, mit dem Potenzial, die Mechanismen zu verfeinern, durch die Entscheidungen in unterschiedlichen Gruppensettings getroffen werden.