Rättvis uppdelning

Equitable division (DB, engelska equitable division , EQ) är en uppdelning av ett inhomogent objekt (till exempel en kaka ), som ett resultat av vilket de subjektiva värdena för alla deltagare är desamma, det vill säga varje deltagare är lika nöjd med sin andel. Matematiskt betyder detta att för alla deltagare i och j ,

V_{i}(X_{i})=V_{j}(X_{j})

var

$X_{i}$ är en tårta tilldelad deltagare i ;
$V_i$ är poängfunktionen för deltagare i . Detta är en verkligt värderad funktion som, för varje tårta, returnerar ett tal som representerar mängden användbarhet för medlem i i den biten. Vanligtvis är dessa funktioner normaliserade så att och (hela kakan) för alla i . $V_{i}(\emptyset )=0$ $V_{i}=1$

Jämförelse med andra kriterier

Opartiskhet (DB) jämför poängen för olika personer i olika delar;
Frånvaron av avund (OZ, engelska Envy-freeness , EF) jämför en persons bedömningar av olika delar;
Exakt division (TD, eng. Exact division , EX) jämför uppskattningarna av olika personer av samma bitar.

Följande tabell visar skillnaden. I alla exempel är det två deltagare, Alice och Bob. Alice får vänster sida och Bob får höger sida.

division

DB?

UNS?

TD?

A:	femtio%	femtio%
B:	femtio%	femtio%

A:	60 %	40 %
B:	40 %	60 %

(Alice och Bob är inte överens om utvärderingen av bitarna).

A:	40 %	60 %
B:	60 %	40 %

(Alice och Bob är avundsjuka på varandra).

A:	70 %	trettio%
B:	40 %	60 %

(Alice är mer nöjd med sin andel än Bob är med sin).

A:	60 %	40 %
B:	60 %	40 %

(Bob är avundsjuk på Alice).

A:	60 %	40 %
B:	70 %	trettio%

Observera att tabellen bara har 6 rader, eftersom 2 kombinationer är omöjliga - TD + OD-divisionen måste vara en DB, och TD + DB-divisionen måste vara en CV.

Att hitta en lika uppdelning för två deltagare

One cut - fullständig information

När det är två deltagare är det möjligt att få en opartisk division med ett enda snitt, men detta kräver full kunskap om deltagarnas poäng [1] . Antag att kakan är segmentet [0,1]. För varje , beräknar vi och och markerar dem på samma graf. Observera att den första grafen ökar från 0 till 1 och den andra grafen minskar från 1 till 0, så de har en skärningspunkt. Att skära kakan vid denna tidpunkt ger en opartisk uppdelning. Detta snitt har ett antal ytterligare egenskaper: $x\in[0,1]$ $u_{1}([0,x])$ $u_{2}([x,1])$

Snittet är EP eftersom varje deltagare får ett värde på minst 1/2.
Cut är inte en icke-AP, eftersom värdet för varje deltagare kan vara större än 1/2.
Skivningen är Pareto - effektiv ( PE) bland alla divisioner med en enda skivning . Det kan dock finnas mer effektiva skärningar med två eller flera skärningar [2] .
Om kakans riktning väljs slumpmässigt (det vill säga kakan kan vändas så att 0 blir 1 och 1 blir 0), så är denna procedur återigen svagt sann i följande mening: endast genom att tillhandahålla rimliga sannolikhetsmått kan deltagarna vara se till att få minst hälften av kakan [1] .

Samma procedur kan tillämpas på uppdelningen av rutinarbete (om utvärderingen av stycket tas med motsatt tecken).

Proportionellt opartisk version

Det fullständiga informationsförfarandet har en variant [3] som tillgodoser de svagare typerna av opartiskhet och de strängare typerna av noggrannhet. Proceduren hittar först medianen för varje deltagare. Antag att medianen för medlem A är , och medianen för medlem B är , där . Sedan får A och B får . Nu finns en balans som är uppdelad mellan deltagarna i lika stora proportioner . Så, till exempel, om A uppskattar återstoden till 0,4 och B uppskattar den till 0,2, kommer A att få dubbelt så mycket värde från som B. Protokollet kommer alltså inte att vara opartiskt, men det kommer fortfarande att vara OZ. Det är svagt ärligt i följande mening: den riskvilliga spelaren har ett incitament att ange den sanna uppskattningen, eftersom han kan få ett lägre värde genom att indikera en uppskattning som inte överensstämmer med sanningen. $a$ $b$ $0<a<b<1$ $[0,a]$ $[b,1]$ $[a,b]$ $[a,b]$

Två snitt - rörlig kniv

Austins "Moving Knife"-procedur ger var och en av de två deltagarna en bit med ett subjektivt värde på exakt 1/2. Således är denna division DB, TD och OZ. Proceduren kräver två snitt och ger en av deltagarna två frånkopplade bitar.

Många klipp - helt öppna inställningar

Om det är tillåtet att göra mer än två nedskärningar är det möjligt att uppnå en division, som inte bara blir DB, utan även OZ och EP . Vissa författare kallar en sådan uppdelning "perfekt" [4] .

Det minsta antalet klipp som krävs för en EP-OZ-DB-delning beror på deltagarnas poäng. I de flesta praktiska fall (inklusive fall där uppskattningarna är linjära bitvis) är antalet nödvändiga skärningar ändligt. I dessa fall kan både det optimala antalet snitt och deras exakta placering hittas. Algoritmen kräver full kunskap om deltagarnas poäng [4] .

Körtid för algoritmen

Alla ovanstående procedurer är kontinuerliga - den andra proceduren kräver att kniven rör sig kontinuerligt, andra kräver att graferna för de två utvärderingsåtgärderna är kontinuerliga. Således kan dessa procedurer inte slutföras i ett begränsat antal diskreta steg.

Denna egenskap av oändlighet är en egenskap hos divisionsproblem som kräver exakta resultat (se artikeln Exakt division: omöjlighet ).

Ett snitt är en nästan opartisk indelning

En nästan opartisk division är en division där poängen för varje spelare inte skiljer sig mer än för någon fast . En nästan opartisk division för två spelare kan hittas i ändlig tid för enhetsskärningsvillkoret [5] . $\epsilon$ $\epsilon >0$

Hitta en rättvis skillnad för tre eller fler deltagare

Den rörliga kniven

Austin-proceduren kan utökas till n deltagare. Proceduren ger varje deltagare ett subjektivt värde på exakt . Denna division är en DB, men inte nödvändigtvis en TD, OZ eller EP (eftersom vissa deltagare kan värdera andelen som överförs till andra deltagare mer än ). $1/n$ $1/n$

Anslutna bitar är helt öppna inställningar

Johnson-proceduren med helt öppna preferenser kan utökas till deltagare enligt följande [3] : $n$

För varje beställning av deltagare skriver vi ut en uppsättning ekvationer med variabler - variablerna är skärpunkter, och ekvationerna bestämmer opartiskheten för angränsande deltagare. till exempel, om det finns 3 deltagare i ordningen A:B:C, så finns det två variabler (klipppunkt för A och B) och , och de två ekvationerna skulle vara och . Dessa ekvationer har minst en lösning där alla deltagare har samma värde. $n!$ $n-1$ $n-1$ $n-1$ $x_{AB}$ $x_{BC}$ $V_{A}(0,x_{AB})=V_{B}(x_{AB},x_{BC})$ $V_{B}(x_{AB},x_{BC})=V_{C}(x_{BC},1)$
Av alla beställningar väljer vi den beställning där (samma) värde för alla deltagare var störst. $n!$

Observera att det maximala opartiska värdet måste vara minst , eftersom vi redan vet att proportionell division (som ger varje deltagare minst ) är möjlig. $1/n$ $1/n$

Om antalet deltagare är absolut kontinuerliga i förhållande till varandra, måste varje försök att öka värdet på en deltagare minska värdet på en annan deltagare. Detta innebär att denna lösning har EP-egenskapen bland alla lösningar med sammankopplade delar.

Omöjlighet

Brahms, Jones och Klamler studerade divisionen, som är både DB och EP, och OZ (de kallade en sådan division "perfekt").

Först bevisade de att för 3 deltagare, om de skulle få sammankopplade bitar, kanske DB+OZ-snittet inte existerade [3] . De gjorde detta genom att beskriva 3 specifika mått på poäng för en endimensionell tårta för vilken en 2-skuren DB-division inte skulle vara en EP.

Sedan bevisade de att för 3 eller fler deltagare i EP+OD+DB, kanske uppdelningen inte existerar även om frånkopplade delar löses [2] . De gjorde detta genom att beskriva 3 specifika utvärderingsåtgärder för en endimensionell tårta med följande egenskaper:

För 2 snitt kommer varje DB-snitt varken att vara OZ eller EP (men det finns snitt som är OZ och 2-EP eller DB och 2-EP).
För 3 snitt kommer alla DB-klipp inte att vara en EP (men det finns klipp av DB + OZ).
För 4 snitt kommer alla DB-snitt inte att vara OC (men det finns DB+EP-snitt).

Dela pajen

En paj är en kaka i form av en endimensionell cirkel (se problemet med rättvis skärning av pajen ).

Barbanel, Brahms och Stromqvist har studerat förekomsten av en pajstyckning som är både DB och OZ. Följande resultat har bevisats utan att ange en specifik divisionsalgoritm [6] :

För två deltagare finns det alltid en opartisk uppdelning av kakan, där det inte finns någon avundsjuka. Om mått på deltagarpreferenspoäng är absolut kontinuerliga med avseende på varandra (det vill säga varje del som har ett positivt värde för en deltagare har ett positivt värde för andra deltagare också), finns det en avundsfri tårtdistribution som är både opartisk och icke-dominerad.
För 3 eller fler deltagare kanske det inte går att hitta en opartisk tårtutdelning som är fri från avundsjuka. Det finns dock alltid en uppdelning som är både opartisk och icke-dominant.

Uppdelning av delbara objekt

Proceduren Justerbar vinnare beräknar en opartisk, avundslös, Pareto-effektiv uppdelning av delbara objekt mellan två deltagare.

Sluttabell

namn	Sorts	Antal deltagare	antal nedskärningar	Egenskaper
Jones algoritm [1]	Helt öppna inställningar	2	1 (optimalt)	BD, OZ, 1-EP
Brahms-Jones-Klumler-förfarande [ 3]	Helt öppna inställningar	n	n −1 (optimalt)	DB, ( n -1)-EP
Austin procedur	Procedur för att flytta kniv	2	2	DB, OZ, TD
Austin procedur	Procedur för att flytta kniv	n	massor	DB
Barbanel-Brahms förfarande [4]	Helt öppna inställningar	2	massor	DB, OZ, EP
Cheklarova -Pillarova procedur [5]	Diskret approximation	2	1 (optimalt)	nästan DB

Anteckningar

↑ 1 2 3 Jones, 2002 , sid. 275–283.
↑ 1 2 Brams, Jones, Klamler, 2013 , sid. 35.
↑ 1 2 3 4 Brams, Jones, Klamler, 2007 .
↑ 1 2 3 Barbanel, Brams, 2014 , sid. 23.
↑ 1 2 Cechlárová, Pillárová, 2012 , sid. 1321.
↑ Barbanel, Brams, Stromquist, 2009 , sid. 496.

Litteratur

Jones MA . Rättvis, avundsfri och effektiv tårtskärning för två personer och dess tillämpning på delbara varor // Mathematics Magazine. - 2002. - T. 75 , nr. 4 . — S. 275–283 . - doi : 10.2307/3219163 . — .
Steven J. Brams, Michael A. Jones, Christian Klamler. Bättre sätt att skära en tårta – Revisited // Meddelanden från AMS. – 2007.
Julius B. Barbanel, Steven J. Brams. Tårtskärning för två personer: det optimala antalet snitt // Den matematiska intelligensen. - 2014. - T. 36 , nr. 3 . - doi : 10.1007/s00283-013-9442-0 .
Katarina Cechlárová, Eva Pillárová. En nästan rättvis algoritm för 2-personers tårtskärningsalgoritm // Optimering. - 2012. - T. 61 , nr. 11 . - doi : 10.1080/02331934.2011.563306 .
Barbanel JB, Brams SJ, Stromquist W. Cutting a Pie is Not a Piece of Cake // American Mathematical Monthly. - 2009. - T. 116 , nr. 6 . - doi : 10.4169/193009709X470407 .
Steven J. Brams, Michael A. Jones, Christian Klamler. N-Person Cake-Cutting: There May Be No Perfect Division // The American Mathematical Monthly. - 2013. - T. 120 . doi : 10.4169 / amer.math.monthly.120.01.035 .