Technische Samenvatting: Het Doel Heiligt de Middelen: Een Lineaire Rangschikkingsregel voor Proportionele Sequentiële Beslissingen

1. Probleemstelling

Het artikel adresseert de uitdaging van het collectief kiezen van een beslissingsregel voor herhaald gebruik in contexten van democratisch ontwerp, zoals AI-uitlijning, toewijzing van middelen (bijvoorbeeld nieruitwisseling, voedseldonatie) en participatief ontwerp. De auteurs richten zich specifiek op lineaire rangschikkingsregels, waarbij een batch van $m$ items $X = (x_1, \dots, x_m)$, elk beschreven door een kenmerkvector $x \in \mathbb{R}^d$, wordt gerangschikt op basis van een score $s_\theta(x) = \langle \theta, x \rangle$ die is afgeleid van een vaste scoringsvector $\theta$.

Het kernaggregatieprobleem wordt als volgt gedefinieerd: Gegeven $n$ kiezerstypes met ideale scoringsvectoren $\theta^{(1)}, \dots, \theta^{(n)}$ en populatiefracties $\alpha^{(1)}, \dots, \alpha^{(n)}$, hoe moet men een collectieve scoringsvector $\theta^*$ selecteren?

De centrale zorg is representatieve ongelijkheid in de tijd. Een vaste regel die herhaaldelijk wordt toegepast, kan consequent aansluiten bij de voorkeuren van een meerderheid terwijl minderheidsstandpunten systematisch worden genegeerd. Het artikel zoekt een aggregatiemechanisme dat voldoet aan Individuele Proportionaliteit (IP): als kiezerstype $i$ een fractie $\alpha^{(i)}$ van de populatie uitmaakt, moet de collectieve rangschikking overeenkomen met de voorkeursrangschikking van type $i$ op ten minste een fractie $\alpha^{(i)}$ van de itemparen.

Het artikel onderscheidt twee noties van IP:

1. IP op de Lange Termijn: Proportionaliteit geldt in verwachting over batches getrokken uit een verdeling $\mathcal{D}$.
2. IP per Batch: Proportionaliteit geldt voor elke specifieke batch $X$ (of in verwachting over de minimale overeenstemming binnen een batch).

2. Methodologie en Theoretisch Kader

2.1. Het Falen van het Rekenkundig Gemiddelde

De standaardbenadering in de literatuur is het rekenkundig gemiddelde ($\theta_{\text{arith}}$), gedefinieerd als het gewogen gemiddelde van individuele scoringsvectoren. De auteurs citeren Feffer et al. [2023] om aan te tonen dat $\theta_{\text{arith}}$ ernstig meerderheidsgericht is. Bij "Antipodale Constructies" (waarbij twee kiezerstypes diametraal tegenovergestelde vectoren hebben), kan het rekenkundig gemiddelde volledig convergeren naar de vector van de meerderheid, wat resulteert in nul overeenstemming voor de minderheid, ongeacht de batchgrootte of verdeling.

2.2. Het Hoekgemiddelde ($\theta_{\text{ang}}$)

De primaire methodologische bijdrage is het voorstellen van het hoekgemiddelde als alternatieve aggregatieregel. Het wordt gedefinieerd als de minimalizer van de gewogen som van de kwadratische hoekafstanden:
$$\theta_{\text{ang}} := \arg\min_{\theta \in S^{d-1}} \sum_{i=1}^n \alpha^{(i)} \angle(\theta, \theta^{(i)})^2$$
In tegenstelling tot het rekenkundig gemiddelde, dat de Euclidische afstand minimaliseert, werkt het hoekgemiddelde op de sfeer $S^{d-1}$, waarbij de geometrische aard van rangschikkingsrichtingen wordt gerespecteerd.

2.3. Theoretische Analyse

De auteurs analyseren de eigenschappen van $\theta_{\text{ang}}$ onder de aanname van sferisch symmetrische itemverdelingen ($\mathcal{D}^\circ$).

• IP op de Lange Termijn: Zij bewijzen dat $\theta_{\text{ang}}$ voldoet aan IP op de Lange Termijn (d.w.z. een proportionaliteitsniveau van ten minste 1 bereikt) voor elk profiel. Dit rust op een fundamentele geometrische eigenschap: het hoekgemiddelde ligt binnen een hoek van $(1 - \alpha^{(i)})\pi$ van de ideale vector $\theta^{(i)}$ van elke kiezer.
• IP per Batch: Het artikel stelt een onmogelijkheidstheorema vast voor IP per Batch. Geen enkele vaste lineaire rangschikkingsregel kan proportionaliteit garanderen voor elke afzonderlijke batch, zelfs niet wanneer rechten integraal zijn. Dit komt door "bijna-collineaire" batches waarbij items zich zodanig aligneren dat een lineaire regel gedwongen wordt om volledig in strijd te zijn met ten minste één kiezerstype.
• Convergentie: Echter, de auteurs bewijzen dat de kloof tussen IP per Batch en IP op de Lange Termijn snel krimpt naarmate de batchgrootte $m$ toeneemt. Specifiek wordt de afwijking begrensd door $O(\sqrt{\frac{\min(\log n, d \log(m/d))}{m}})$.

3. Belangrijkste Bijdragen

1. Bestaan van een Proportionele Lineaire Regel: Het artikel bewijst dat het hoekgemiddelde een eenvoudige, interpreteerbare, vaste lineaire regel is die Individuele Proportionaliteit op de Lange Termijn garandeert voor sferisch symmetrische verdelingen. Dit lost de open vraag op of enige vaste lineaire regel uiteenlopende meningen kan balanceren zonder inherent meerderheidsgericht te zijn.
2. Fundamentele Geometrische Eigenschap: De auteurs stellen een nieuw theorema vast (Theorema 3.3) met betrekking tot het hoekgemiddelde in $d$ dimensies: voor elk profiel wordt gegarandeerd dat het hoekgemiddelde binnen een hoek van $(1 - \alpha^{(i)})\pi$ ligt van de vector van elke kiezer $i$. Dit generaliseert bekende 2D-resultaten naar hogere dimensies.
3. Onmogelijkheid en Convergentiegrenzen: Het artikel bewijst formeel dat IP per Batch onmogelijk is voor vaste lineaire regels (Theorema 4.3), maar toont aan dat het verlies dat wordt geleden door te beperken tot vaste regels verwaarloosbaar is voor grote batchgroottes (Theorema 4.5).
4. Robuustheid: Het hoekgemiddelde blijkt robuust te zijn; als een scoringsvector dicht bij $\theta_{\text{ang}}$ ligt in termen van hoekafstand, verslechteren de proportionaliteitsgaranties slechts additief.

4. Empirische Resultaten

De auteurs evalueren vijf aggregatiemechanismen op drie real-world datasets (Moral Machine, Nieruitwisseling, Voedselredding) en hun synthetische 2D-varianten die zijn ontworpen om kiezerheterogeniteit te vergroten:

• Geteste Regels: Rekenkundig Gemiddelde ($\theta_{\text{arith}}$), Hoekgemiddelde ($\theta_{\text{ang}}$), Geometrisch Mediaan, Borda-telling en Proportionele Sequentiële Borda (PSB).
• Homogene Regimes: Op de originele datasets waar kiezerpreferenties relatief vergelijkbaar zijn, presteren alle regels (inclusief het rekenkundig gemiddelde) vergelijkbaar en voldoen ze aan proportionaliteit.
• Heterogene Regimes (2D-data): Wanneer kiezervectoren verspreid zijn over een brede boog (wat hoge onenigheid simuleert):
  • Het rekenkundig gemiddelde en het geometrisch mediaan falen aanzienlijk, vaak dalend onder het proportionele recht (Long-IP < 1).
  • Het hoekgemiddelde presteert aanzienlijk beter dan het rekenkundig gemiddelde en het geometrisch mediaan, en handhaaft Long-IP $\ge 1$.
  • PSB (een niet-lineaire, niet-vaste regel) presteert het beste, wat bevestigt dat het loslaten van de "vaste lineaire" constraint verdere winst oplevert, maar het hoekgemiddelde blijft de best presterende vaste lineaire regel.
• Convergentie: Empirische resultaten bevestigen dat IP per Batch zeer snel convergeert naar IP op de Lange Termijn naarmate de batchgrootte $m$ groeit, zelfs voor kleine $m$.

5. Betekenis en Claims

Het artikel claimt een best-case benchmark te bieden voor het aggregeren van beslissingsregels. Door aan te tonen dat een vaste lineaire regel (het hoekgemiddelde) kan voldoen aan proportionaliteit op de lange termijn, betogen de auteurs dat pipelines met lagere informatie (die regels moeten leren uit ruisende data) moeten streven naar het behoud van de structuur van het hoekgemiddelde.

De betekenis ligt in:

• Correctie van een Meerderheidsfout: Het identificeert een eenvoudige, interpreteerbare alternatief voor het rekenkundig gemiddelde dat de "tyrannie van de meerderheid" in herhaalde besluitvorming voorkomt.
• Theoretische Garanties: Het biedt het eerste bewijs dat een vaste lineaire regel kan voldoen aan individuele proportionaliteit op de lange termijn, een eigenschap die eerder als moeilijk of onmogelijk werd beschouwd voor vaste regels.
• Praktische Toepasbaarheid: Het hoekgemiddelde is computationeel hanteerbaar (via gradient-gebaseerde optimalisatie) en in de praktijk robuust tegen niet-sferische verdelingen, waardoor het een levensvatbare kandidaat is voor real-world toepassingen in AI-uitlijning en participatief ontwerp.

De auteurs blijven bescheiden over de beperkingen, en erkennen dat hoewel $\theta_{\text{ang}}$ het probleem op de lange termijn oplost, het de sterkere garantie per batch niet kan bereiken zonder de "vaste lineaire" constraint op te offeren, een trade-off die afneemt bij grotere batchgroottes.