💻 computer science

A General Theory of Proportionality with Additive Utilities

Diese Arbeit erweitert die Axiome der Proportionalität von Approval-Ballots auf kardinale Ballots innerhalb eines allgemeinen Modells zur beschränkten Auswahl und schlägt neue Regeln vor, die proportionale Ergebnisse sicherstellen und proportionale Rangfolgen für Anwendungen wie partizipative Budgetierung und öffentliche Entscheidungsfindung generieren.

Ursprüngliche Autoren: Piotr Skowron

Veröffentlicht 2026-02-10

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Piotr Skowron

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie organisieren ein riesiges Gemeinschaftsfestival. Sie haben eine Liste potenzieller Aktivitäten (Kandidaten), eine Gruppe von Nachbarn (Wähler) und ein begrenztes Budget (Machbarkeitsbeschränkungen). Einige Aktivitäten kosten mehr als andere, und einige können einfach nicht zusammen stattfinden (wie ein lautes Rockkonzert und eine ruhige Yoga-Sitzung im selben Zelt).

Das Ziel ist es, eine Auswahl an Aktivitäten zu treffen, die sich für alle fair anfühlt. Wenn eine Gruppe von Nachbarn 20 % der Menge repräsentiert und alle eine bestimmte Art von Musik lieben, sollten sie auch etwa 20 % der „Musikzeit“ des Festivals erhalten.

Dieses Paper befasst sich mit einer sehr kniffligen Version dieses Problems: Was ist, wenn Menschen nicht nur sagen „Ich mag das“ oder „Ich mag das nicht“? Was ist, wenn sie sagen: „Ich mag das Rockkonzert ein bisschen, aber die Jazzband liebe ich noch viel mehr“?

Hier ist eine Aufschlüsselung der Ideen des Papers unter Verwendung einfacher Analogien.

1. Das Problem: Die Lücke zwischen „Approval“ und „Utility“

Die meisten bisherigen Regeln für eine faire Auswahl gingen davon aus, dass Wähler nur einen „Ja/Nein“-Knopf hatten (Approval/Zustimmung).

Approval: „Ich mag das Rockkonzert.“ (Wert = 1)
Utility (Die neue Herausforderung): „Ich mag das Rockkonzert ein wenig, aber die Jazzband ist mein absoluter Favorit.“ (Rock = 0,2, Jazz = 1,0).

Das Paper argumentiert, dass das echte Leben voller dieser „Utility“-Präferenzen ist. Selbst wenn man für ein Projekt mit „Ja“ stimmt, kann man es vielleicht mehr schätzen, wenn es 100 $ kostet, als wenn es nur 10 $ kostet. Die Autoren wollten Regeln entwickeln, die diese nuancierten Gefühle handhaben können, nicht nur einfache „Ja/Nein“-Stimmen.

2. Die Kernidee: Kandidaten mit „virtuellem Geld“ kaufen

Die Autoren schlagen ein System vor, bei dem Wähler im Laufe der Zeit virtuelles Geld verdienen, wie ein Wasserhahn, aus dem Münzen in ihre Taschen tropfen.

Der alte Weg (Phragmén’s Regel): Sobald eine Gruppe von Menschen genug Münzen hat, um einen Kandidaten, den sie mögen, zu kaufen, kaufen sie ihn sofort. Dies ist ein „gieriger“ (greedy) Ansatz.
Der neue Weg (PropRank & Equal Shares): Die Autoren haben erkannt, dass es manchmal eine schlechte Idee ist, einen Kandidaten jetzt zu kaufen. Vielleicht ist es besser, 5 Minuten zu warten, um genug Geld für einen besseren Kandidaten zu haben, den man noch viel mehr liebt.

Die Analogie: Stellen Sie sich vor, Sie sind in einem All-you-can-eat-Buffet, aber Sie bezahlen pro Minute.

Gierig (Greedy): Sie sehen einen Burger, den Sie mögen, also schnappen Sie ihn sofort.
Klug (Die Methode des Papers): Sie sehen den Burger, aber Sie wissen, dass in 2 Minuten ein Steak serviert wird. Sie warten. Sie berechnen: „Wenn ich mein Geld jetzt für den Burger ausgebe, verpasse ich vielleicht das Steak. Aber wenn ich warte, kann ich das Steak bekommen, das mir mehr ‚Glück‘ pro Dollar bringt.“

Das Paper führt einen mathematischen „Voraussichts“-Mechanismus ein. Es simuliert die Zukunft, um zu entscheiden: Ist es wert, auf ein besseres Angebot zu warten, oder sollte ich das jetzt kaufen?

3. Die zwei Hauptregeln

A. PropRank (Der „Zeitreisende“ Selektor)

Diese Regel ist darauf ausgelegt, eine Rangfolge (eine Liste von Platz 1 bis zum letzten Platz) zu erstellen, statt nur eine endgültige Liste.

Wie es funktioniert: Wähler verdienen Geld. Der Algorithmus schaut sich jeden Kandidaten an und fragt: „Wer ist bereit, dafür zu bezahlen, und zu welchem Preis?“
Der Clou: Er kauft nicht einfach das Billigste. Er berechnet einen „Preis pro Einheit an Glück“. Wenn ein Kandidat teuer ist, aber einer Gruppe von Wählern riesiges Glück bereitet, könnte er in Bezug auf das Glück „günstiger“ sein als ein billiger, langweiliger Kandidat.
Das Ergebnis: Er erstellt eine faire Liste, bei der jeder obere Teil der Liste (das „Präfix“) für sich genommen ein faires Komitee darstellt.

B. Die Methode der gleichen Anteile (Method of Equal Shares – Der „Budget-Allokator“)

Dies ist eine aggressivere Version. Anstatt Geld langsam zu tropfen, gibt sie jedem einen großen Brocken virtuelles Geld vorab und lässt sie dieses ausgeben.

Die Innovation: Die Autoren haben diese Methode, die zuvor nur für einfache Budgetierungen verwendet wurde, beigebracht, wie man komplexe Beschränkungen handhabt (wie z. B. „wir können nicht sowohl das Rockkonzert als auch die Yoga-Klasse haben“).
Wie sie Beschränkungen handhabt: Wenn der Algorithmus versucht, eine Menge an Kandidaten zu kaufen, die die Regeln verletzt (z. B. das Budget überschreitet oder die „kein Rock/Yoga zusammen“-Regel bricht), stoppt er, rechnet neu und findet die beste machbare Teilmenge, die er stattdessen kaufen kann.

4. Die „Heuristiken“ (Die smarten Abkürzungen)

Die Autoren stellten fest, dass ihre perfekten mathematischen Regeln manchmal Geld liegen ließen (Wähler hatten Geld übrig, das sie nicht ausgegeben hatten). Um dies zu beheben, entwickelten sie „Heuristik“-Versionen (smarte Vermutungen):

PropRankRem: Wenn ein Kandidat aus der Liste entfernt wird (weil er zu teuer ist oder mit anderen in Konflikt steht), drückt der Algorithmus auf „Reset“. Er sagt den Wählern: „Okay, vergesst diesen Kandidaten. Lasst uns den Ausgabenplan ohne ihn neu starten.“ Dies verhindert, dass Wähler Geld horten, während sie auf einen Kandidaten warten, der niemals gewählt wird.
Backtracking: Das ist wie das Spielen eines Videospiels. Der Algorithmus probiert einen Pfad aus. Wenn er stecken bleibt, geht er ein paar Schritte zurück, ändert seine Meinung darüber, auf welche Kandidaten er warten sollte, und versucht es erneut. Das ist langsamer, findet aber oft eine perfektere Lösung.

5. Was haben sie herausgefunden? (Die Ergebnisse)

Die Autoren testeten diese Regeln mit realen Daten aus dem Participatory Budgeting (wo echte Städte entscheiden lassen, wie öffentliches Geld ausgegeben wird).

Der „Warte“-Faktor: Sie fanden heraus, dass das Einstellen des „Warte“-Parameters (genannt $\kappa$ ) auf 1 (was bedeutet, dass Wähler sehr bereit sind, auf bessere Angebote zu warten) am besten für die Fairness funktionierte.
Fairness vs. Glück: Ihre neuen Regeln waren unglaublich fair. Sie verletzten die Fairness-Regeln (genannt Extended Justified Representation) nur sehr selten.
Vergleich:
- Die Greedy-Methode (einfach die beliebtesten Dinge auswählen) war effizient, aber unfair gegenüber kleineren Gruppen.
- Die neuen Regeln (PropRank und Equal Shares) waren viel fairer gegenüber diversen Wählergruppen und stellten sicher, dass Minderheitenpräferenzen tatsächlich repräsentiert wurden und nicht nur die Favoriten der Mehrheit.
- Die Heuristik-Versionen (mit den „Reset“- und „Backtrack“-Funktionen) funktionierten fast perfekt und erzeugten Ergebnisse mit fast null Fairness-Verletzungen.

Zusammenfassung

Das Paper sagt: „Wir haben einen neuen Weg entwickelt, um Gruppenentscheidungen zu treffen, der respektiert, wie sehr Menschen die Dinge wirklich mögen, nicht nur, ob sie sie mögen. Indem wir ein ‚virtuelles Geld‘-System nutzen, das Wähler dazu ermutigt, auf das beste ‚Glück-pro-Dollar‘-Angebot zu warten, können wir fairere Ergebnisse für komplexe Situationen schaffen, wie etwa Stadtbudgets oder Komitee-Auswahlen, bei denen man nicht alles auswählen kann.“

Sie haben mathematisch bewiesen, dass diese Regeln fair sind, und sie mit realen Daten getestet, um zu zeigen, dass sie besser funktionieren als ältere Methoden.

Technisches Resümee: Eine allgemeine Theorie der Proportionalität mit additiven Nutzenfunktionen

1. Problemstellung

Die Arbeit befasst sich mit dem Problem der Auswahl einer zulässigen Teilmenge von Kandidaten aus einer Menge $C$ basierend auf Wählerpräferenzen, unterliegt allgemeinen Zulässigkeitsbeschränkungen, die durch eine Familie von Teilmengen $\mathcal{F} \subseteq 2^C$ definiert sind. Dieser Rahmen generalisiert mehrere etablierte Modelle in der Theorie der sozialen Wahl (Social Choice Theory), darunter:

Komitee-Wahlen: Auswahl einer festen Anzahl von Kandidaten.
Partizipative Budgetierung (PB): Auswahl von Projekten innerhalb eines Gesamtbudgets.
Öffentliche Entscheidungsfindung und Aggregation von Urteilen: Entscheidungen über mehrere unabhängige Themen zu treffen.
Diversitätsbeschränkungen: Sicherstellung spezifischer struktureller Eigenschaften (z. B. Geschlechterparität) in der ausgewählten Menge.

Während Axiome der Proportionalität (wie Justified Representation) bereits für dieses allgemeine Modell definiert wurden, konzentrieren sich bestehende Regeln primär auf Approval-Ballots (bei denen Wähler den Nutzen 0 oder 1 zuweisen). Die vorliegende Arbeit konzentriert sich auf das komplexere Szenario von additiven Nutzenfunktionen, bei dem jeder Wähler $i$ jedem Kandidaten $c$ einen numerischen Nutzen $u_i(c) \geq 0$ zuweist. Das Ziel ist es, Regeln zu entwerfen, die eine faire Repräsentation kohärenter Gruppen von Wählern unter diesen allgemeinen Beschränkungen und kardinalen Nutzenfunktionen gewährleisten.

2. Methodik

Die Autoren schlagen zwei primäre algorithmische Ansätze vor, die von dem Konzept inspiriert sind, dass Wähler Kandidaten mit virtueller Währung „kaufen“.

2.1 Die PropRank-Regel

PropRank ist eine sequentielle Regel, die von der Phragmén-Sequenzregel inspiriert, jedoch für additive Nutzenfunktionen angepasst wurde.

Mechanismus: Wähler verdienen über die Zeit eine virtuelle Währung in einer konstanten Rate. Die Regel simuliert einen Kaufprozess, bei dem Wähler entscheiden, wie viel sie für Kandidaten ausgeben.
Voraussichtsmechanismus (Foresight Mechanism): Im Gegensatz zu Standard-Greedy-Ansätzen antizipieren die Wähler in PropRank zukünftige Möglichkeiten. Sie berechnen einen „Skalierungsfaktor“ $\lambda_i$ basierend auf dem bestmöglichen Zahlungs-zu-Nutzen-Verhältnis, das sie erreichen könnten, wenn sie auf einen begehrenswerteren Kandidaten warten würden, bis dieser erschwinglich wird.
Ausgabefunktion: Ein Wähler $i$ erklärt sich bereit, höchstens $x_i(c, r)$ für den Kandidaten $c$ in Runde $r$ auszugeben, definiert durch eine Formel, die den aktuellen Budgetstand, den Nutzen des Kandidaten und den Skalierungsfaktor berücksichtigt. Dies stellt sicher, dass das Zahlungs-zu-Nutzen-Verhältnis nicht das beste fraktionale Kaufangebot überschreitet.
Ranking: Der Algorithmus erstellt ein vollständiges Ranking von Kandidaten nach ihren Kauf-Zeitstempeln. Da unzulässige Kandidaten während des Prozesses nicht entfernt werden (nur am Ende der Ranking-Konstruktion für spezifische Komiteegrößen), erfüllt jedes Präfix des Rankings die Proportionalität.

2.2 Generalisierte Methode der gleichen Anteile (MES)

Die Autoren erweitieren die Methode der gleichen Anteile (ursprünglich für PB entwickelt) auf allgemeine Beschränkungen.

Struktur: Der Algorithmus operiert in Runden. In jeder Runde bestimmt er den maximalen Betrag an Geld, der an Wähler alloziert werden kann, sodass die „Equal Shares“-Subroutine eine Menge von Kandidaten kaufen kann, ohne die Zulässigkeitsbeschränkungen zu verletzen.
Voraussicht in MES: Ähnlich wie PropRank beinhaltet das generalisierte MES einen Voraussichtsmechanismus. Es berechnet Obergrenzen für die Ausgaben ($capi$), um zu verhindern, dass Wähler zu früh für Kandidaten ausgeben, die weniger effizient sein könnten als jene in zukünftigen Iterationen.
Backtracking-Heuristiken: Die Arbeit führt heuristische Varianten ein (PropRankRem, PropRankBacktrack), die das Verfahren neu starten oder Backtracking betreiben, wenn Kandidaten entfernt werden, mit dem Ziel, ungenutzte Budgets zu reduzieren und die praktische Leistung zu verbessern, obwohl diese nicht dieselben theoretischen Garantien wie die Basarregeln besitzen.
Begrenztes Überziehen (Bounded Overspending - BOS): Eine Anpassung der BOS-Methode wird für allgemeine Beschränkungen vorgeschlagen, wobei der Algorithmus den größten gültigen Zeitstempel für den Kauf identifiziert, bevor die Zulässigkeit verletzt wird.

3. Zentrale Beiträge

3.1 Theoretischer Rahmen

Proportionalitätsaxiome für additive Nutzenfunktionen: Die Arbeit generalisiert Axiome wie Extended Justified Representation (EJR) und Proportional Justified Representation (PJR) auf das Setting der additiven Nutzenfunktionen mit allgemeinen Beschränkungen.
Proportionalitätsgrad: Die Autoren definieren und analysieren den „Proportionalitätsgrad“, der die durchschnittliche Zufriedenheit einer kohärenten Gruppe quantifiziert. Sie stellen die Beziehung zwischen EJR und dem Proportionalitätsgrad her und zeigen, dass der Garantiewert für allgemeine Beschränkungen von der Größe der kohärenten Gruppe ( $\gamma = |S|/n$ ) abhängt.

3.2 Theoretische Garantien

PropRank-Garantien:
- Für Partizipative Budgetierungs-Beschränkungen erfüllt PropRank einen Proportionalitätsgrad von $d(\alpha) = (\alpha - u_{max})/2$ .
- Für Allgemeine Beschränkungen erfüllt es einen Grad von $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$ .
- Für Matroid-Beschränkungen erfüllt es einen schwachen Proportionalitätsgrad von $(\alpha - u_{max})/2$ .
PJR-Garantien: Die Regeln erfüllen PJR-Grad-Garantien von $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$ , wobei $\kappa$ ein Parameter ist, der die Flexibilität der Ausgaben steuert.

3.3 Algorithmische Erweiterungen

Die Arbeit liefert die erste Generalisierung der Methode der gleichen Anteile auf beliebige Zulässigkeitsbeschränkungen mit additiven Nutzenfunktionen.
Sie führt Heuristiken (PropRankRem, PropRankBacktrack) ein, um das Problem ungenutzter Budgets in praktischen Szenarien anzugehen.

4. Experimentelle Ergebnisse

Die Autoren evaluierten ihre Regeln an über 1.300 realen Instanzen der partizipativen Budgetierung aus dem Pabulib-Datensatz.

Metriken: Die Evaluierung basierte auf EJR+-Verletzungen (Proportionalität), der Ausschlussquote (Anteil der Wähler mit Nutzen Null) und der durchschnittlichen Kosten-Zufriedenheit (utilitaristische Effizienz).
Ergebnisse:
- $\kappa$ -Parameter: Die Experimente zeigen, dass PropRank mit $\kappa = 1$ (was flexiblere Ausgaben erlaubt) in Bezug auf die Proportionalität (weniger EJR+-Verletzungen) signifikant besser abschneidet als $\kappa = 0$ .
- Heuristiken: Die heuristischen Varianten (PropRankRem, PropRankBacktrack) in Kombination mit $\kappa = 0$ zeigten sehr wenige EJR+-Verletzungen und günstige Ausschlussquoten und übertrafen in praktischen Metriken oft das Basis-PropRank, obwohl sie keine formalen Beweise für diese spezifischen Heuristiken besitzen.
- BOS-Adaption: Die adaptierte Methode der gleichen Anteile mit begrenztem Überziehen (Bounded Overspending) schnitt außergewöhnlich gut ab, übertraf das ursprüngliche BOS-PB bei EJR+-Verletzungen und erreichte es bei der Ausschlussquote und dem Nutzen. Sie wurde auch als die recheneffizienteste der vorgeschlagenen Techniken identifiziert.
- Vergleich: Die vorgeschlagenen Regeln erreichten im Allgemeinen eine Kosten-Zufriedenheit, die vergleichbar mit oder besser als bestehende PB-spezifische Regeln (MES-PB, BOS-PB) ist, während sie allgemeine Beschränkungen handhaben.

5. Bedeutung und Ansprüche

Die Arbeit beansprucht, eine allgemeine Theorie der Proportionalität zu liefern, die die Lücke zwischen spezifischen Modellen (wie Komitee-Wahlen und PB) und der breiteren Landschaft der beschränkten Selektionsprobleme schließt.

Generalisierung: Sie zeigt, dass etablierte Methoden (Phragmén und Equal Shares) auf beliebige Zulässigkeitsbeschränkungen und additive Nutzenfunktionen erweitert werden können, ohne ihre wesentlichen Proportionalitätseigenschaften zu verlieren.
Ranking: Ein bedeutender Beitrag ist die Fähigkeit, proportionale Rankings zu generieren (bei denen jedes Präfix ein proportionales Komitee ist), womit eine Lücke in der Literatur geschlossen wird.
Praktikabilität: Während die theoretischen Garantien stark sind, merken die Autoren bescheiden an, dass heuristische Varianten, die etwas theoretische Handhabbarkeit zugunsten einer besseren praktischen Leistung (Reduzierung ungenutzter Budgets) opfern, sehr effektiv sind.
Einschränkungen: Die Arbeit räumt ein, dass die Beweistechniken für die Basisalgorithmen sich nicht direkt auf die heuristischen Varianten übertragen lassen und dass die Rechenkomplexität der Backtracking-Heuristiken exponentiell sein kann (abgemildert durch einen Parameter $\sigma$ ).

Zusammenfassend lässt sich sagen, dass die Arbeit ein robustes theoretisches Fundament für proportionale Repräsentation unter allgemeinen Beschränkungen und additiven Nutzenfunktionen schafft und sowohl beweisbare faire Algorithmen als auch praktische Heuristiken bietet, die auf realen Daten gut abschneiden.