Sanningsfull tårtskärning

Truthful cake-cutting är studiet av algoritmer för rättvis cake-cutting som också är sanningsenliga mekanismer , dvs de uppmuntrar deltagarna att avslöja sina sanna värderingar för de olika delarna av kakan.

Den klassiska dela och välj- proceduren för kakskärning är inte sanningsenlig: om skäraren känner till väljarens preferenser kan han få mycket mer än 1/2 genom att agera strategiskt. Anta till exempel att skäraren värderar en bit efter dess storlek medan väljaren värderar en bit efter mängden choklad i den. Så skäraren kan skära kakan i två delar med nästan samma mängd choklad, så att den mindre biten har lite mer choklad. Sedan kommer väljaren att ta den mindre biten och skäraren vinner den större biten, som kan vara värd mycket mer än 1/2 (beroende på hur chokladen fördelas).

Randomiserade mekanismer

Det finns en trivial randomiserad sanningsenlig mekanism för rättvis tårtskärning : välj en enskild agent jämnt slumpmässigt och ge honom/henne hela kakan. Denna mekanism är trivialt sanningsenlig eftersom den inte ställer några frågor. Dessutom är det rimligt i förväntan: det förväntade värdet för varje partner är exakt 1/ n . Den resulterande tilldelningen är dock inte rättvis. Utmaningen är att utveckla sanningsenliga mekanismer som är rättvisa i efterhand och inte bara i förväg. Flera sådana mekanismer har utvecklats.

Exakt uppdelningsmekanism

En exakt division (aka consensus division ) är en uppdelning av kakan i n bitar så att varje agent värderar varje bit till exakt 1/ n . Förekomsten av en sådan uppdelning är en följd av Dubins-Spaniers konvexitetsteorem . Dessutom finns det en sådan division med högst $n(n-1)^{2}$ snitt; detta är en följd av Stromquist-Woodall-satsen och halsbandsdelningssatsen .

I allmänhet kan en exakt division inte hittas med en ändlig algoritm. Det kan dock finnas i vissa speciella fall, till exempel när alla agenter har stycklinjära värderingar. Anta att vi har en icke sanningsenlig algoritm (eller orakel) för att hitta en exakt division. Den kan användas för att konstruera en randomiserad mekanism som är sanningsenlig i förväntan. Den randomiserade mekanismen är en direktavslöjande mekanism - den börjar med att be alla agenter att avslöja hela deras värdemått:

Be ombuden att rapportera sina värdemått.
Använd den befintliga algoritmen/oraklet för att generera en exakt division.
Utför en slumpmässig permutation på konsensuspartitionen och ge varje partner en av bitarna.

Här är det förväntade värdet för varje agent alltid 1/ n oavsett den rapporterade värdefunktionen. Därför är mekanismen sanningsenlig – ingen agent kan vinna något på att ljuga. Dessutom garanteras en sanningsenlig partner ett värde på exakt 1/ n med sannolikhet 1 (inte bara i förväntan). Därför har partnerna ett incitament att avslöja sina verkliga värdefunktioner.

Superproportionell mekanism

En superproportionell division är en kak-division där varje agent får strikt mer än 1/ n av sina egna värdemått. En sådan uppdelning är känd för att existera om och endast om det finns minst två agenter som har olika värderingar till minst en bit av kakan. Varje deterministisk mekanism som alltid returnerar en proportionell division, och alltid returnerar en superproportionell division när den finns, kan inte vara sanningsenlig.

Mossel och Tamuz presenterar en superproportionell randomiserad mekanism som är sanningsenlig i förväntan:

Välj en division från en viss fördelning D över divisioner.
Be varje agent att utvärdera hans/hennes verk.
Om alla n utvärderingar är fler än 1/ n , implementera allokeringen och avsluta.
Använd annars mekanismen för exakt uppdelning.

Fördelningen D i steg 1 bör väljas så att det, oavsett ombudens värderingar, finns en positiv sannolikhet att en superproportionell division väljs om den finns. Sedan, i steg 2, är det optimalt för varje agent att rapportera det sanna värdet: att rapportera ett lägre värde har antingen ingen effekt eller kan få agentens värde att sjunka från superproportionellt till bara proportionellt (i steg 4); att rapportera ett högre värde har antingen ingen effekt eller kan få agentens värde att sjunka från proportionellt till mindre än 1/ n (i steg 3).

Ungefärlig exakt uppdelning med hjälp av frågor

Antag att agenterna, i stället för att direkt avslöja sina värderingar, avslöjar sina värden indirekt genom att svara på mark- och eval -frågor (som i Robertson-Webb-modellen).

Branzei och Miltersen visar att den exakta divisionsmekanismen kan "diskretiseras" och exekveras i frågemodellen. Detta ger, för alla $\epsilon >0$ , ett randomiserat frågebaserat protokoll, som frågar högst $O(n^{2}/\epsilon )$ frågor , är sanningsenlig i förväntan och tilldelar varje agent ett värde mellan $1/n-\epsilon$ och $1/n+\epsilon$ , genom värderingarna av alla agenter.

Å andra sidan bevisar de att, i varje deterministiskt sanningsenligt frågebaserat protokoll, om alla agenter värderar alla delar av kakan positivt, finns det åtminstone en agent som får den tomma biten. Detta innebär att om det bara finns två agenter så är minst en agent en "diktator" och får hela kakan. Uppenbarligen kan en sådan mekanism inte vara avundsfri.

Randomiserad mekanism för styckvis konstanta värderingar

Anta att alla agenter har styckvis konstanta värderingar . Detta innebär att kakan för varje agent är uppdelad i ändligt många delmängder och agentens värdedensitet i varje delmängd är konstant. I det här fallet Aziz och Ye en randomiserad algoritm som är mer ekonomiskt effektiv: Begränsad seriediktatur är sanningsenlig i förväntan, robust proportionell och uppfyller en egenskap som kallas enhällighet : om varje agents mest föredragna 1/ n längd av kakan är osammanhängande från andra agenter, då får varje agent sin mest föredragna 1/ n längd av kakan. Detta är en svag form av effektivitet som inte tillfredsställs av de mekanismer som bygger på exakt uppdelning. När det bara finns två agenter är det också polynomtid och robust avundsfritt.

Deterministiska mekanismer: styckvis konstanta värderingar

För deterministiska mekanismer är resultaten mestadels negativa, även när alla agenter har styckvis konstanta värderingar.

Kurokawa, Lai och Procaccia bevisar att det inte finns någon deterministisk, sanningsenlig och avundsfri mekanism som kräver ett begränsat antal Robertson-Webb-frågor.

Aziz och Ye bevisar att det inte finns någon deterministisk sanningsenlig mekanism som uppfyller någon av följande egenskaper:

Proportionell och Pareto-optimal;
Robust-proportionell och icke-slösaktig ("icke-slöseri" betyder att ingen bit tilldelas en agent som inte vill ha den; den är svagare än Pareto-optimalitet).

Menon och Larson introducerar begreppet ε-truthfulness , vilket innebär att ingen agent vinner mer än en bråkdel ε på felrapportering, där ε är en positiv konstant oberoende av agenternas värderingar. De bevisar att ingen deterministisk mekanism uppfyller någon av följande egenskaper:

ε -sanningsfull, approximativt proportionell och icke-slösaktig (för approximationskonstanter högst 1/ n );
Sanningsriktig, approximativt proportionell och sammankopplad (för approximationskonstant högst 1/ n ).

De presenterar en mindre modifiering av Even–Paz-protokollet och bevisar att det är ε -sanningsfullt med ε = 1 - 3/(2 n ) när n är jämnt, och ε = 1 - 3/(2 n ) + 1/ n ² när n är udda.

Bei, Chen, Huzhang, Tao och Wu bevisar att det inte finns någon deterministisk, sanningsenlig och avundsfri mekanism, ens i modellen för direktuppenbarelse, som uppfyller någon av följande ytterligare egenskaper:

Anslutna delar;
Ej slösaktigt;
Position omedveten - tilldelningen av en kakdel baseras endast på agenternas värderingar av den delen, och inte på dess relativa position på kakan.

Observera att dessa omöjlighetsresultat håller med eller utan fri förfogande.

På den positiva sidan, i en replikekonomi, där varje agent replikeras k gånger, finns det avundsfria mekanismer där sanningssägande är en Nash-jämvikt :

Med anslutningskrav, i vilken avundsfri mekanism som helst, konvergerar sanningssägande till en Nash-jämvikt när k närmar sig oändligheten;
Utan anslutningskrav, i mekanismen som fördelar varje homogent delintervall lika mellan alla agenter, är sanningssägande en Nash-jämvikt redan när k ≥ 2.

Tao förbättrar det tidigare omöjlighetsresultatet av Bei, Chen, Huzhang, Tao och Wu och visar att det inte finns någon deterministisk, sanningsenlig och proportionell mekanism, inte ens i modellen för direktuppenbarelse, och även när alla följande gäller:

Det finns bara två agenter;
Agenter är hungriga: varje agents värdering är positiv (dvs. kan inte vara 0);
Mekanismen tillåts lämna en del av kakan otilldelad.

Det är öppet om detta omöjlighetsresultat sträcker sig till tre eller flera agenter.

På den positiva sidan presenterar Tao två algoritmer som uppnår en svagare uppfattning som kallas "proportional risk-averse truthfulness" (PRAT). Det betyder att det, i varje lönsam avvikelse för agent i , finns värderingar av de andra agenterna, för vilka i får mindre än hans proportionella andel. Den här egenskapen är starkare än "riskbenägen sanningsenlighet", vilket innebär att det, i varje lönsam avvikelse för i, finns värderingar av de andra agenterna, för vilka i får mindre än hans värde i en sanningsenlig rapportering. Han presenterar en algoritm som är PRAT och avundsfri, och en algoritm som är PRAT, proportionell och kopplad.

Styckvis enhetliga värderingar

Anta att alla agenter har styckvis enhetliga värderingar . Detta betyder att det för varje medel finns en delmängd av kakan som är önskvärd för medlet, och medlets värde för varje bit är bara mängden önskvärd kaka som den innehåller. Anta till exempel att vissa delar av kakan täcks av ett enhetligt lager choklad, medan andra delar inte är det. En agent som värderar varje bit endast efter mängden choklad den innehåller har en bitvis enhetlig värdering. Detta är ett specialfall av styckvis konstanta värderingar. Flera sanningsenliga algoritmer har utvecklats för detta speciella fall.

Chen, Lai, Parkes och Procaccia presenterar en direktuppenbarelsemekanism som är deterministisk , proportionell, avundsfri , Pareto-optimal och polynomisk tid. Det fungerar för hur många agenter som helst. Här är en illustration av CLPP-mekanismen för två medel (där kakan är ett intervall).

Be varje agent att rapportera sina önskade intervaller.
Varje delintervall, som inte önskas av någon agent, kasseras.
Varje delintervall, som önskas av exakt en agent, tilldelas den agenten.
Delintervallen, som önskas av båda agenterna, tilldelas så att båda agenterna får samma totala längd .

Nu, om en agent säger att han vill ha ett intervall som han faktiskt inte vill ha, då kan han få mer onödig kaka i steg 3 och mindre användbar kaka i steg 4. Om han säger att han inte vill ha ett intervall som han faktiskt vill ha , då får han mindre nyttig tårta i steg 3 och mer nyttig tårta i steg 4, dock delas mängden som ges i steg 4 med det andra medlet, så allt som allt går det liggande medlet med förlust. Mekanismen kan generaliseras till valfritt antal medel.

CLPP-mekanismen förlitar sig på antagandet om fritt omhändertagande , dvs förmågan att kassera bitar som inte önskas av någon agent.

Obs : Aziz och Ye presenterade två mekanismer som utökar CLPP-mekanismen till styckvis konstanta värderingar - Constrained Cake Eating Algorithm och Market Equilibrium Algorithm. Båda dessa tillägg är dock inte längre sanningsenliga när värderingarna inte är styckvis enhetliga.

Maya och Nisan visar att CLPP-mekanismen är unik i följande mening. Tänk på specialfallet med två agenter med styckvis enhetliga värderingar, där kakan är [0,1], Alice vill bara ha delintervallet [0, a ] för vissa a <1, och Bob önskar bara delintervallet [1- b , 1] för vissa b <1. Tänk bara på mekanismer som inte är slösaktiga – mekanismer som tilldelar varje del som önskas av minst en spelare till en spelare som vill ha den. Varje sådan mekanism måste ge Alice en delmängd [0, c ] för någon c <1 och Bob en delmängd [1- d ,1] för någon d <1. I denna modell:

En icke-slösaktig determininistisk mekanism är sanningsenlig om, för någon parameter t i [0,1], den ger Alice intervallet [0, min( a , max(1- b , t ))] och Bob intervallet [1- min( b ,max(1- a ,1- t )),1]
En sådan mekanism är avundsfri om t =1/2; i detta fall är det ekvivalent med CLPP-mekanismen

De visar också att, även för två agenter, uppnår varje sanningsenlig mekanism högst 0,93 av den optimala sociala välfärden.

Li, Zhang och Zhang visar att CLPP-mekanismen fungerar bra även när det finns externa effekter (dvs vissa agenter drar viss nytta av det värde som ges till andra), så länge som externa effekter är tillräckligt små. Å andra sidan, om de externa effekterna (antingen positiva eller negativa) är stora, finns det ingen sanningsenlig icke-slösaktig och positionsoberoende mekanism.

Alijani, Farhadi, Ghodsi, Seddighin och Tajik presenterar flera mekanismer för speciella fall av styckvis enhetliga värderingar:

Expansionsprocessen hanterar styckvis enhetliga värderingar där varje agent har ett enda önskat intervall , och dessutom uppfyller agenternas önskade intervall en beställningsegenskap . Det är polynom-tid, sanningsenligt, avundslöst och garanterar sammanhängande bitar.
Expansionsprocessen med upplåsning hanterar styckvis enhetliga värderingar där varje agent har ett enda önskat intervall, men utan beställningskrav. Det är polynom-tid, sanningsenligt, avundslöst och inte nödvändigtvis kopplat, men det gör som mest 2 n -2 snitt.

Bei, Huzhang och Suksompong presenterar en mekanism för två agenter med styckvis enhetliga värderingar, som har samma egenskaper som CLPP (sann, deterministisk, proportionell, avundsfri, Pareto-optimal och löper i polynomtid), men garanterar att hela tårta tilldelas:

Hitta det minsta x i [0,1] så att Alices önskade längd i [0, x ] är lika med Bobs önskade längd i [ x ,1].
Ge Alice intervallen i [0, x ] värderade av Alice och intervallen i [ x ,1] som inte värderas av Bob; ge resten till Bob.

BHS-mekanismen fungerar både för kakskärning och för sysslouppdelning (där agenternas värderingar är negativa). Observera att BHS inte uppfyller vissa naturliga önskvärda egenskaper:

Det garanterar inte kopplade bitar , till exempel när Alice vill ha [0,1] och Bob vill ha [0,0,5], då x =0,25, Alice får [0,0,25] och [0,5,1] och Bob får [0,25 0,5].
Den är inte anonym (se symmetrisk rättvis kakskärning ) : om Alice vill ha [0,1] och Bob vill ha [0,0,5], så får Alice en önskad längd på 0,75 och Bob får 0,25, men om värderingarna ändras ( Alice vill ha [0,0,5] och Bob vill ha [0,1]), sedan x =0,5 och båda agenterna får önskad längd 0,5.
Den är inte omedveten om positionen : om Alice vill ha [0,0,5] och Bob vill ha [0,1] får båda agenterna värdet 0,5, men om Alices önskade intervall flyttas till [0,5,1] så får x =0,75 och Alice får 0,25 och Bob får 0,75.

Detta är inte ett problem med den specifika mekanismen: det är bevisligen omöjligt att ha en sanningsenlig och avundsfri mekanism som allokerar hela kakan och garanterar någon av dessa tre egenskaper, även för två agenter med styckvis enhetliga värderingar.

BHS-mekanismen utvidgades till valfritt antal agenter, men bara för ett specialfall av styckvis enhetliga värderingar, där varje agent bara önskar ett enda intervall av formen [0, x i _] .

Ianovsky bevisar att ingen sanningsenlig mekanism kan uppnå en utilitaristiskt optimal kakskärning , även när alla agenter har styckvis enhetliga värderingar. Dessutom kan ingen sanningsenlig mekanism uppnå en allokering med utilitaristisk välfärd som är minst lika stor som någon annan mekanism. Det finns dock en enkel sanningsenlig mekanism (betecknad Lex Order) som inte är slösaktig : ge agent 1 alla delar som han gillar; ge sedan till agent 2 alla delar som han gillar och som ännu inte har getts till agent 1; etc. En variant av denna mekanism är längdspelet, där agenterna döps om efter den totala längden av deras önskade intervall, så att agenten med det kortaste intervallet kallas 1, agenten med det näst kortaste intervallet kallas 2 , etc. Detta är dock inte en sanningsenlig mekanism:

Om alla agenter är sanningsenliga, ger det en utilitaristiskt optimal allokering.
Om agenterna är strategiska, är alla dess väluppfostrade Nash-jämvikter Pareto-effektiva och avundsfria, och ger samma utdelning som CLPP-mekanismen.

Sammanfattning av sanningsenliga mekanismer och omöjlighetsresultat

namn	Typ	Deterministisk?	#agents( $n$ )	Värderingar	Sysslor?	Körtid	Allt?	PO?	EF?	Anon?	Conn?	Pos.Ob.?	Inget avfall?
Exakt uppdelning	Direkt	Nej	Många	Allmän	Ja	Gränslös	Ja	Nej	Ja	Ja	Nej	?	?
Superproportionell	Direkt	Nej	Många	Allmän	Ja	Gränslös	Ja	Nej	Nej	Ja	Nej	?	?
Diskret exakt uppdelning	Frågor	Nej	Många	Allmän	Ja	$O(n^{2}/\epsilon )$	Ja	Nej	$\epsilon$ -EF	Ja	Nej	?	?
Begränsad seriediktatur	Direkt	Nej	Många	PWC	?	?	Nej	Enhällighet	Stötta.	?	Nej	?	?
CLPP	Direkt	Ja	Många	PWU	Nej	Polynom	Nej	Ja	Ja	Ja	Nej	?	Ja
BHS 1, 2	Direkt	Ja	2	PWU	Ja	Polynom	Ja	Ja	Ja	Nej	Nej	Nej	Ja
BHS 3, 4	Direkt	Ja	Många	PWU1	Ja	Polynom	Ja	Ja	Ja _{(för kakor)}	?	?	?	Ja
Expansion	Direkt	Ja	Många	PWU1+order	?	Polynom	?	?	Ja	?	Ja	?	?
Expansion+ Upplåsning	Direkt	Ja	Många	PWU1	?	Polynom	?	?	Ja	?	2 n -2 skärningar	?	?
OMÖJLIGA KOMBINATIONER:
[BM]	Frågor	Ja	2+	Några
[ BHS]	Direkt	Ja	2+	PWU			Ja		Ja	Ja
[ BHS]	Direkt	Ja	2+	PWU			Ja		Ja		Ja
[ BHS]	Direkt	Ja	2+	PWU			Ja		Ja			Ja
[T]	Direkt	Ja	2+	PWC					Ja _{(även för Prop.)}
[BCHTW]	Direkt	Ja	2+	PWC			Ja		Ja		Ja
[BCHTW]	Direkt	Ja	2+	PWC			Ja		Ja			Ja
[BCHTW]	Direkt	Ja	2+	PWC			Ja		Ja				Ja
[BCHTW]	Sekventiell	Ja	2+	PWC			Ja		Ja

Se även