Symmetrisk rättvis tårtskärning

Symmetrisk rättvis tårtskärning är en variant av problemet med rättvis tårtskärning , där rättvisa tillämpas inte bara på det slutliga resultatet, utan också på tilldelningen av roller i delningsförfarandet.

Som ett exempel, ta en födelsedagstårta som måste delas mellan två barn med olika smak, så att varje barn känner att hans/hennes andel är "rättvis", dvs värd minst 1/2 av hela tårtan. De kan använda den klassiska dela och välj -proceduren: Alice skär tårtan i två delar värda exakt 1/2 i hennes ögon, och George väljer den bit som han anser vara mer värdefull. Resultatet är alltid rättvist. Proceduren är dock inte symmetrisk: medan Alice alltid får ett värde på exakt 1/2 av sitt värde, kan George få mycket mer än 1/2 av sitt värde. Så även om Alice inte avundas Georges del, avundas hon Georges roll i proceduren.

Tänk däremot på det alternativa förfarandet där Alice och George båda gör halvmärken på kakan, dvs var och en av dem markerar platsen där kakan ska skäras så att de två delarna är lika i hans/hennes ögon. Sedan skärs kakan exakt mellan dessa snitt – om Alices snitt är a och Georges snitt är g , så skärs kakan vid (a+g)/2. Om a < g får Alice pjäsen längst till vänster och George pjäsen längst till höger; annars får Alice pjäsen längst till höger och George pjäsen längst till vänster. Slutresultatet är fortfarande rättvist. Och här är rollerna symmetriska: det enda fallet där rollerna gör skillnad i slutresultatet är när a = g , men i det här fallet har båda delarna ett värde på exakt 1/2 för båda barnen, så rollerna gör ingen skillnad i slutvärdet. Därför är det alternativa förfarandet både rättvist och symmetriskt.

Idén presenterades först av Manabe och Okamoto, som kallade den meta-avundsfri .

Flera varianter av symmetrisk rättvis tårtskärning har föreslagits:

• Anonym rättvis tårtskärning kräver att inte bara värdena är lika, utan att även bitarna i sig är lika. Detta innebär symrisk rättvisa, men det är starkare. Till exempel är det inte tillfredsställt med den symmetriska-dela-och-välj ovan, eftersom i fallet att a = g , den första agenten alltid får pjäsen längst till vänster och den andra agenten alltid den högra pjäsen.
• Aristotelisk rättvis kakskärning kräver bara att agenter med identiska värdemått får samma värde. Detta antyds av symmetrisk rättvisa, men det är svagare. Till exempel är det tillfredsställt med den asymmetriska versionen av dividera-och-välj: om agenternas värderingar är identiska får de båda ett värde på exakt 1/2.

Definitioner

Det finns en kaka C , vanligtvis antas vara ett 1-dimensionellt intervall. Det finns n personer. Varje person i har värdefunktion V _i som mappar delmängder av C till svagt positiva tal.

En divisionsprocedur är en funktion F som mappar n värdefunktioner till en partition av C . Den bit som F tilldelas Vn _till agent i betecknas med F ( V ₁ ,..., ; i ).

Symmetrisk procedur

En divisionsprocedur F kallas symmetrisk om, för varje permutation p av (1,..., n ), och för varje i :

Vi _F ( ( V ₁ , ..., Vn ; ₍ i ) ) = Vi _F ( ( V _p(1) ,..., V p _n) ( ; p ^-1 i )))

I synnerhet när n =2 är en procedur symmetrisk om:

V ₁ ( F ( V ₁ , V ₂ ; 1)) = V ₁ ( F ( V ₂ , V ₁ ; 2)) och V ₂ ( F ( V ₁ , V ₂ ; 2)) = V ₂ ( F ( V ₂ , V ₁ ; 1))

Det betyder att agent 1 får samma värde oavsett om han spelar etta eller tvåa, och detsamma gäller för agent 2. Som ett annat exempel, när n =3, innebär symmetrikravet (bland annat):

Vi ( F ( V1 _, V2 ₎ , V3 _{) ;} 1 ₎ V3 , _V1 ) ₌ V3 , _V1 Vi ( F ( V2 , _{; 3} ) ₌ Vi ( _F ( , V2 ; _ 2)).

Anonym procedur

En divisionsprocedur F kallas anonym om, för varje permutation p av (1,..., n ), och för varje i :

F ( V1 ,..., Vn _Vp ; i ) = F ( Vp ₍₁₎ , ..., ( _n) ; p ⁻¹ ( _i ))

Varje anonym procedur är symmetrisk, eftersom om bitarna är lika - deras värden är säkert lika.

Men motsatsen är inte sant: det är möjligt att en permutation ger en agent olika pjäser med lika värde.

Aristotelisk procedur

En divisionsprocedur F kallas aristotelisk om, närhelst V _i = V _k :

Vi _Vn F Vn ₍ ( V1 , ..., ; ₎ i ) ) = Vk _, ( F ( V1 ..., ; _{k )}

Kriteriet är uppkallat efter Aristoteles , som skrev i sin bok om etik: "... det är när jämlikar äger eller tilldelas ojämna andelar, eller personer som inte är lika lika delar, som bråk och klagomål uppstår". Varje symmetrisk procedur är aristotelisk. Låt p vara permutationen som byter i och k . Symmetri innebär att:

Vi (F ₍ V1 , .... Vi _{Vn ,} ..., Vk , _{... ,} ; _Vi i ) ) = ( F ₍ V1 , .... Vk _{, ..} ., V _i,..., Vn ₎ ; k )

Men eftersom V _i = V _k är de två sekvenserna av värdemått identiska, så detta innebär definitionen av aristotelisk. Dessutom är varje förfarande utan avundsjuka tårtskärning aristotelisk: avundslöshet innebär att:

_Vn Vi (F ( V1 _, ..., ; _... i ) Vn ₎ (F ≥ Vi _F ( ( V1 _, ..., ; ₎ k ) ) Vk ( V1 _, , V _n ; k )) ≥ V _k ( F ( V ₁ ,..., V _n ; i ))

Men eftersom V _i = V _k , innebär de två olikheterna att båda värdena är lika.

En procedur som uppfyller det svagare villkoret för proportionell kakskärning är inte nödvändigtvis aristotelisk. Cheze visar ett exempel med 4 medel där Even-Paz-proceduren för proportionell kakskärning kan ge olika värden till medel med identiska värdemått.

Följande diagram sammanfattar relationerna mellan kriterierna:

• Anonym → Symmetrisk → Aristotelisk
• Avundsfri → Aristotelisk
• Avundsfri → Proportionell

Förfaranden

Varje procedur kan göras "symmetrisk ex-ante" genom randomisering. Till exempel, i det asymmetriska dela-och-välj, kan avdelaren väljas genom att kasta ett mynt. Ett sådant förfarande är dock inte symmetriskt i efterhand. Därför fokuserar forskningen angående symmetrisk rättvis kakskärning på deterministiska algoritmer .

Manabe och Okamoto presenterade symmetriska och avundsfria ("meta-avundsfria") deterministiska procedurer för två och tre agenter.

Nicolo och Yu presenterade ett anonymt, avundslöst och Pareto-effektivt delningsprotokoll för två agenter. Protokollet implementerar allokeringen i subgame perfect equilibrium , förutsatt att varje agent har fullständig information om värderingen av den andra agenten.

Det symmetriska skär-och-välj-förfarandet för två medel studerades empiriskt i ett labbexperiment. Alternativa symmetriska, rättvisa kakskärningsprocedurer för två medel är märket längst till höger och bladen längst till vänster .

Cheze presenterade flera procedurer:

• Ett allmänt schema för att omvandla vilken som helst avundslös procedur till en symmetrisk deterministisk procedur: kör den ursprungliga proceduren n ! gånger, en gång för varje permutation av medlen, och välj ett av resultaten enligt något topologiskt kriterium (t.ex. minimering av antalet snitt). Denna procedur är inte praktisk när n är stort.
• En aristotelisk proportionell procedur för n agenter, som kräver O( n ³ ) frågor och ett polynomantal aritmetiska operationer av domaren.
• En symmetrisk proportionell procedur för n agenter, som kräver O( n ³ ) frågor, men som kan kräva ett exponentiellt antal aritmetiska operationer av domaren.

Aristotelisk proportionell procedur

Chezes aristoteliska förfarande för proportionell kakskärning utökar proceduren för ensamdelare . För enkelhetens skull normaliserar vi värderingarna så att värdet på hela kakan är n för alla agenter. Målet är att ge varje agent en pjäs med ett värde på minst 1.

1. En godtyckligt vald spelare, kallad avdelaren , skär kakan i n bitar vars värde i hans/hennes ögon är exakt 1.
2. Konstruera en tvådelad graf G = ( X+Y , E ) där varje vertex i X är en agent, varje vertex i Y är en bit och det finns en kant mellan en agent x och en bit y iff x värder y minst 1.
3. matchning utan avundsjuka utan maximal kardinalitet i G (en matchning där ingen omatchad agent finns intill en matchad pjäs). Observera att avdelaren ligger intill alla n stycken, så | NG ₍ X ) |= n ≥ |X| (där NG ₎ ( X ) är mängden grannar till X i Y . Därför finns en matchning utan avundsjuka. Anta wlog att EFM matchar agenterna 1,..., k till bitar X ₁ ,...,X _k , och lämnar agenterna och bitarna från k +1 till n omatchade .
4. För varje i i 1,..., Xi _k för vilket Vi ₎ ( = 1 - ge X _i till agent i . Nu tilldelas avdelaren och alla agenter vars värdefunktion är identisk med avdelarens en bit och har samma värde.
5. Betrakta nu agenterna i i 1,..., k för vilka V _i ( X _i ) > 1. Dela upp dem i delmängder med identisk värdevektor för bitarna X ₁ ,...,X _k . För varje delmängd, dela rekursivt sina bitar mellan dem (till exempel om agenterna 1, 3, 4 är överens om värdena för alla bitarna 1,..., k, dela sedan bitarna X 1 _, X _3, X ₄ rekursivt mellan dem). Nu tilldelas alla agenter vars värde-funktion är identisk till samma delmängd, och de delar en delkaka vars värde för dem är större än deras antal, så förutsättningen för rekursion är uppfylld.
6. Dela rekursivt de omatchade bitarna Xk _{. +1} , ..., Xn _bland de omatchade agenterna Observera att, genom att matchningen inte är avundsjuk, värderar varje omatchad agent varje matchad bit till mindre än 1, så han värderar de återstående bitarna till mer än antalet agenter, så att förutsättningen för rekursion är uppfylld.