Fair Cake Cutting Challenge

Den rättvisa skärningen av kakan är ett slags rättvis uppdelningsproblem . Problemet handlar om en heterogen resurs, till exempel en tårta med olika dekorationer (från grädde , bär, choklad ), som antas vara delbar - det vill säga en godtyckligt liten bit kan skäras ur den utan att förstöra hela värdet. Resursen behöver delas upp på flera partners som har olika preferenser för olika delar av kakan. Vissa föredrar till exempel chokladdekorationer, andra föredrar körsbär, medan andra bara vill ha en större bit. Uppdelningen ska vara subjektivt rättvis, varje deltagare ska få en bit som han/hon anser vara en rimlig del.

Termen "kaka" är bara en metafor , kakskärningsprocedurer kan användas för att separera olika typer av resurser, såsom markägande , reklamutrymme eller sändningstid.

Tårtskärningsproblemet föreslogs av Hugo Steinhaus efter andra världskriget [1] och har varit föremål för intensiva studier i matematik , datavetenskap , ekonomi och statsvetenskap [2] .

Antaganden

Det finns en kaka , som vanligtvis antas vara ett ändligt endimensionellt segment, en tvådimensionell polygon eller en ändlig delmängd av ett högredimensionellt euklidiskt utrymme .

Det finns en person med lika rättigheter till [3] .

måste delas upp i sådana disjunkta delmängder att varje deltagare får en separat delmängd. Det stycke som är avsett för deltagaren betecknas som , och .

Varje deltagare måste få en pjäs med ett "rättvist" värde. Rättvisa bestäms utifrån subjektiva värdefunktioner . Varje ansikte har en subjektiv värdefunktion som mappar delmängder till siffror.

Funktionerna antas vara absolut kontinuerliga i längd, area eller (i allmänhet) Lebesgue-måttet [4] . Det betyder att det inte finns några "atomer", det vill säga singulära punkter som tilldelas ett positivt värde av en eller flera agenter. Således är alla delar av kakan delbara.

I vissa fall antas även utvärderingsfunktionerna vara sigma-additiva .

Ett exempel på en tårta

Vi kommer att använda följande tårta som illustration:

Krav på rättvisa

Det ursprungliga och mest allmänna kriteriet för rättvisa är proportionalitet (PR, engelsk  proportionalitet , PR). I den proportionella uppdelningen av tårtan får varje deltagare en bit, vars värde han uppskattar åtminstone i det totala värdet av hela tårtan. I exemplet ovan kan en proportionell uppdelning erhållas genom att ge hela vaniljportionen och 4/9 av chokladportionen till George (med en totalpoäng på 6,66), och de återstående 5/9 av chokladportionen ges till Alice (med totalt 5 poäng). Symboliskt:

.

Proportionalitetskriteriet kan generaliseras till situationer där människors rättigheter inte är lika. Till exempel, när man delar en kaka proportionellt med olika andelar , tillhör kakan aktieägarna, så en av dem äger 20 % och den andra 80 % av kakan. Detta leder till ett kriterium om viktad proportionalitet :

,

där w i är vikter vars summa är 1.

Ett annat typiskt kriterium är frånvaron av avund (OZ, engelska  envy-freeness , EF). Med en avundsjuk uppdelning [5] får varje person en pjäs, vars värde enligt denna person inte är mindre än värdet av de andra pjäserna. Formellt språk:

.

I vissa fall finns det ett implikationsförhållande (konsekvens) mellan proportionalitet och frihet från avundsjuka, vilket återspeglas i följande tabell:

Agenter Betyg från OZ följer PR? från PR följer OZ?
2 tillsats Ja Ja
2 allmän Inte Ja
3+ tillsats Ja Inte
3+ allmän Inte Inte

Det tredje, mindre använda kriteriet är opartiskhet ( engelsk  equitability , EQ). I en opartisk division äter varje person en bit med exakt samma utvärderingsvärde. I tårtexemplet kan opartisk skärning erhållas genom att ge varje deltagare hälften av chokladen och hälften av vaniljbitarna, så att varje deltagare får ett värde på 5. Symboliskt:

.

Det fjärde kriteriet är noggrannhet . Om andelen för varje partner i är lika med w i , är en exakt division en division där:

.

Om alla vikter är lika (1/ n ), så kallas snittet perfekt och

.

Geometriska krav

I vissa fall måste de bitar som är avsedda för deltagarna uppfylla vissa geometriska begränsningar förutom rättvisa.

Ytterligare krav

Inom rättspraxis övervägs ofta kostnadseffektiviteten av uppdelning. Se artikeln " Effektiv kakskärning ".

Förutom de önskvärda egenskaperna hos finita skärningar finns det också önskvärda egenskaper hos delningsprocessen. En sådan egenskap är sanningsenlighet (även känd som stimuluskompatibilitet ), som kan vara av två nivåer.

Resultat

2 personer - en proportionell och avundsfri uppdelning

För människor finns OD-delningen alltid och kan hittas med hjälp av dividera-och-välj- protokollet . Om utvärderingsfunktionerna är additiv kommer denna nedskärning också att vara PR, annars garanteras inte proportionalitet.

Proportionell uppdelning

För n personer med additiva poäng finns det alltid en proportionell minskning. Mest använda protokoll:

Se artikeln " Proportionell uppdelning av en kaka med olika proportioner " för detaljer och en fullständig bibliografi.

Ovanstående algoritmer fokuserar främst på agenter med lika stor andel av resurskraven. Du kan dock generalisera dem och få Proportionell uppdelning av kakan med olika andelar .

Avundsjuk division

PO-delningen för en person existerar även om betygen inte är additiva, så länge de representeras av konsekventa preferensuppsättningar. OD-indelningen studerades separat för fallet då bitarna måste kopplas ihop, och för fallet då bitarna kan bestå av separata frånkopplade delar.

För anslutna delar är huvudresultaten:

Båda dessa algoritmer är oändliga: den första är kontinuerlig, medan den andra kan ta oändligt lång tid att konvergera. Faktum är att avundsfria snitt i anslutna intervaller för 3 eller fler personer inte kan hittas av något ändligt protokoll.

För (möjligen) frånkopplade bitar är huvudresultaten:

Det negativa resultatet i det allmänna fallet är mycket svagare än i fallet med anknytning. Allt vi vet är att alla avundsfria skivningsalgoritmer måste använda åtminstone frågor. Det finns ett stort gap mellan detta resultat och beräkningskomplexiteten hos kända procedurer.

Se avundsfri kakskärning [ 5 ] för detaljer och en fullständig bibliografi . 

Effektiv uppdelning

När utvärderingsfunktionerna är additiva finns det ett verktygssnitt ( Utilitarian-maximal , UM) .  Intuitivt, för att skapa ett RP-snitt, måste vi ge varje deltagare en tårta med ett värde som är maximalt för honom. I exemplet RP-kaka kommer skärning att ge all choklad till Alice och all vanilj till George, vilket uppnår användbarhet .

Denna process är lätt att implementera om utvärderingsfunktionerna är styckvis konstanta, det vill säga kakan kan delas upp i bitar så att pristätheten på varje bit är konstant för alla deltagare. När estimatorfunktionerna inte är styckvis konstanta, är förekomsten av RP-snitt baserad på en generalisering av denna procedur för estimatorfunktioner med hjälp av Radon-Nikodim- satsen, se sats 2 i Dubins och Spanier [9] .

När kakan är endimensionell och bitarna måste kopplas ihop (det vill säga kontinuerliga segment) fungerar inte den enkla algoritmen för att tilldela biten till den agent som är mest signifikant. I detta fall är uppgiften att hitta RP för snittet NP-hård, och dessutom är inget FPTAS- schema möjligt om inte P = NP. Det finns en 8-faldig approximationsalgoritm och en parameteriserad komplexitetsalgoritm som är exponentiell i antalet spelare [12] .

För alla positiva vikter kan den viktade RP-partitionen hittas med liknande metoder. Därför finns det alltid Pareto - effektiva ( PE) partitioner . 

Procedurrättvisa

På senare tid har det funnits ett intresse inte bara för rättvisan i den slutliga uppdelningen, utan också för rättvisan i delningsförfarandet - det ska inte vara någon skillnad mellan olika roller i förfarandet. Viss processuell rättvisa har studerats:

Se artikeln " Symmetrisk rättvis tårtskärning " för detaljer och länkar.

Effektiv rättvis uppdelning

För n personer med additiv värdefunktioner finns det alltid en EPOS-indelning [13] .

Om kakan är ett endimensionellt intervall och varje deltagare måste erhålla ett kopplat intervall, gäller följande generella resultat: om utvärderingsfunktionerna är strikt monotona (varje deltagare föredrar starkt en bit, och inte någon av hans egna delmängder), då alla OZ-divisioner kommer också att vara en EP [14] . Därför ger Simons protokoll i detta fall EPOS-delning.

Om kakan är en endimensionell cirkel (till exempel ett intervall där två ändpunkter identifieras topologiskt) och varje yta måste få en ansluten båge, är det tidigare resultatet inte korrekt - OD-delningen kommer inte nödvändigtvis att vara en EP. Dessutom finns det par (icke-additiva) estimatorfunktioner för vilka det inte finns någon EPOS-delning. Men om det finns 2 agenter och minst en av dem har en additiv utvärderingsfunktion, så finns EPOS-avdelningen [15] .

Om kakan är endimensionell, men vilken person som helst kan få en diskontinuerlig delmängd av den, kommer OD-indelningen inte nödvändigtvis att vara EP. I det här fallet krävs mer komplexa algoritmer för att hitta EPOS för divisionen.

Om utvärderingsfunktionerna är additiva och styckvis konstanta, så finns det en algoritm som hittar EPOS-divisionen [16] . Om estimatordensitetsfunktionerna är additiva och Lipschitz-kontinuerliga , så kan de approximeras av styckvis konstanta funktioner "så nära vi vill", så denna algoritm approximerar EPOS-divisionen "så nära vi vill" [16] .

OD-divisionen är inte nödvändigtvis RP [17] [18] . Ett av tillvägagångssätten för att hantera denna svårighet är att söka efter uppdelningen med det maximala nyttovärdet bland alla möjliga OC av OC. Detta problem studerades för en kaka, som är ett endimensionellt intervall, från vilket varje person kan få diskontinuerliga delar, och utvärderingsfunktionerna är additiv [19] .

Icke-additiva procedurer

De flesta av de befintliga procedurerna för rättvis delning som beskrivs ovan förutsätter additiv nytta för spelarna. Med andra ord, om en spelare får lite nytta av 25 g chokladkaka, antas det att han kommer att få exakt dubbelt så mycket nytta av 50 g av samma chokladkaka.

2013 visade Rishi S. Mirchandani att de flesta befintliga algoritmer för rättvis division är inkompatibla med icke-additiva verktygsfunktioner [20] . Han bevisade också att det speciella fallet med rättvis divisionsproblemet, där spelarna har icke-additiva nyttofunktioner, inte kan ha proportionella lösningar.

Mirchandani föreslog att problemet med rättvis division kunde lösas med hjälp av icke-linjära optimeringstekniker. Frågan kvarstår dock om det finns bättre algoritmer för specifika delmängder av icke-additiva hjälpfunktioner.

Se även

Anteckningar

  1. ↑ 1 2 Steinhaus, 1948 , sid. 101–4.
  2. ↑ Procaccia, 2016 .
  3. ↑ Mänskliga rättigheter diskuteras inte här, uppgiften är att dela upp kakan så att varje person får en rättvis del.
  4. ↑ Hill, Morrison, 2010 , sid. 281.
  5. ↑ 1 2 Ofta översatt med "division utan avund" (spårpapper från engelska), även om det är förekomsten av avund som spelar huvudrollen i denna division.
  6. ↑ Det vill säga så att dess längd och bredd är nära.
  7. ↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , sid. 1–28.
  8. ↑ Chen, Lai, Parkes, Procaccia, 2013 , sid. 284–297.
  9. ↑ 1 2 Dubins, Spanien, 1961 , sid. 1–17.
  10. ↑ Fair Division Calculator (nedlänk) . Hämtad 12 oktober 2019. Arkiverad från originalet 28 februari 2010. 
  11. ↑ Ivars Peterson. En rättvis deal för hemmakamrater . MathTrek (13 mars 2000). Hämtad 12 oktober 2019. Arkiverad från originalet 20 september 2012.
  12. ↑ Aumann, Dombb, Hassidim, 2013 .
  13. ↑ Weller, 1985 , sid. 5–17.
  14. ↑ Berliant, Thomson, Dunz, 1992 , sid. 201.
  15. ↑ Thomson, 2006 , sid. 501–521.
  16. ↑ 1 2 Reijnierse, Potters, 1998 , sid. 291–311.
  17. ↑ Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, 2011 , sid. 589.
  18. ↑ Aumann, Dombb, 2010 , sid. 26.
  19. ↑ Cohler, Lai, Parkes, Procaccia, 2011 .
  20. ↑ Mirchandani, 2013 , sid. 78–91.

Litteratur

Länkar