Proportionell kakskärning med olika rättigheter

I problemet med att skära av rättvis kakor har partnerna ofta olika rättigheter. Till exempel kan resursen tillhöra två aktieägare så att Alice innehar 8/13 och George innehar 5/13. Detta leder till kriteriet viktad proportionalitet (WPR): det finns flera vikter $w_{i}$ som summerar till 1, och varje partner $i$ bör få minst en bråkdel ${ \displaystyle w_{i}}$ av resursen genom sin egen värdering.

Däremot i den enklare proportionella kakskärningsinställningen är vikterna lika: $w_{i}=1/n$ för alla $i$

Flera algoritmer kan användas för att hitta en WPR-division.

Kloning

Anta att alla vikter är rationella tal, med gemensam nämnare $D$ . Så vikterna är ${\displaystyle p_{1}/D,\dots ,p_{n}/D} ,$ med $p_ {1}+\cdots +p_{n}=D$ . För varje spelare $i$ , skapa ${\displaystyle p_{i}}-$ kloner med samma värde-mått. Det totala antalet kloner är $D$ . Hitta en proportionell kakfördelning bland dem. Till sist, ge varje partner $i$ bitarna av hans $p_{i}$ kloner.

Robertson och Webb visar en enklare procedur för två partners: Alice skär tårtan i $D$ lika stora bitar i hennes ögon; George väljer de $p_{G}$ mest värdefulla pjäserna i sina ögon, och Alice tar de återstående $p_{A}$ pjäserna.

Denna enkla procedur kräver $D-1$ snitt, som kan vara mycket stora. Till exempel, om Alice har rätt till 8/13 och George har rätt till 5/13, så behövs 13-1=12 snitt i den initiala partitionen.

Antalet obligatoriska frågor är $D\lceil \log _{2}(D)\rceil .$

Ramsey skiljeväggar

Anta att en kaka måste delas mellan Alice och George, Alice har rätt till 8/13 och George har rätt till 5/13. Kakan kan delas enligt följande.

• Alice skär kakan i 6 bitar med värderingsförhållanden 5:3:2:1:1:1 .
• George markerar de pjäser som har för honom åtminstone det värde som nämns av Alice.

Nu finns det två "bra" fall - fall där vi kan använda dessa bitar för att uppnå en viktad proportionell uppdelning med respekt för de olika rättigheterna:

Fall 1: Det finns en delmängd av de markerade pjäserna vars summa är 5. T.ex. om George markerar 3-bitarna och de tre 1-bitarna. Sedan ges denna delmängd till George och resten ges till Alice. George har nu minst 5/13 och Alice har exakt 8/13.

Fall 2: Det finns en delmängd av de omärkta pjäserna vars summa är 8. T.ex. om George markerar 3-biten och bara en 1-bit. Sedan ges denna delmängd till Alice och resten ges till George. Alice har nu exakt 8 och George har gett upp en summa på mindre än 8, så han har minst 5/13.

Det går att bevisa att de goda fallen är de enda möjliga fallen. Dvs varje delmängd av 5:3:2:1:1:1 har ANTINGEN en delmängd som summerar till 5, ELLER har dess komplement en delmängd som summerar till 8. Därför hittar ovanstående algoritm alltid en WPR-allokering med den givna förhållanden. Antalet snitt som används är endast 5.

McAvaney, Robertson och Webb generaliserar denna idé med begreppet Ramsey-partitioner (uppkallad efter Ramsey-teorin) .

Formellt: om $k_{1}$ och $k_{2}$ är positiva heltal, en partition $P$ av $k_{1}+ k_{2}$ kallas en Ramsey-partition för paret $k_{1},k_{2}$ , om för någon underlista $L\subseteq P$ , antingen finns det en underlista av $L$ som summerar till $k_{1}$ , eller så finns det en underlista med $P\setminus L$ som summerar till ${\ displaystyle k_{2}}$ .

I exemplet ovan, $k_{1}=8$ och $k_{2}=5$ och partitionen är 5:3:2:1:1:1, som är en Ramsey-partition. Dessutom är detta den kortaste Ramsey-partitionen i det här fallet, så det tillåter oss att använda ett litet antal snitt.

Ramsey-partitioner finns alltid. Dessutom finns det alltid en unik kortaste Ramsey-partition. Den kan hittas med en enkel variant av den euklidiska algoritmen . Algoritmen är baserad på följande lemma:

Om $p_{1}<a<b$ , och $P=(p_{1},\dots ,p_{n} )$ är en partition av $b$ , och $P'=(b,p_{1},\dots ,p_{n})$ , då är $P'$ en partition av $a+b$ . Dessutom $P'$ en minimal Ramsey-partition för paret $a,b$ if-and-only-if $P$ är en minimal Ramsey-partition för paret $a,ba$ .

Detta lemma leder till följande rekursiva algoritm.

$FindMinimalRamsey(a,b)$ :

1. Ordna ingångarna så att $a<b$ .
2. Tryck $a$ .
3. Om $a=ba=1$ , tryck sedan $1,1,1$ och avsluta.
4. Om $ba\neq 1$ , då $FindMinimalRamsey(a,ba)$ .

När en minimal Ramsey-partition har hittats kan den användas för att hitta en WPR-avdelning som respekterar rättigheterna.

Algoritmen behöver minst $\log _{\phi }\min(a,b)$ skärningar, där $\phi = (1+{\sqrt {5}})/2$ är det gyllene snittet. I de flesta fall är detta nummer bättre än att göra $a+b-1$ snitt. Men om $a=1$ , då behövs ${\displaystyle b=a+b-1} snitt, eftersom den enda Ramsey-partitionen i paret$$b,1$ är en sekvens med $b+1$ ettor.

Klipp-nära-halvor

Anta igen att Alice har rätt till 8/13 och George har rätt till 5/13. Kakan kan delas enligt följande.

• George skär kakan i två delar i förhållandena 7:6.
• Alice väljer en av bitarna, som är värd för henne åtminstone dess deklarerade värde. Tänk på två fall:
  • Alice väljer 7:an. Sedan har Alice rätt till 1 till, och den återstående biten ska delas i förhållandet 5:1.
  • Alice väljer 6:an. Sedan har Alice rätt till 2 till, och den återstående biten ska delas i förhållandet 5:2.
• I båda fallen är den återstående biten mindre och förhållandet mindre. Så småningom blir förhållandet 1:1 och den återstående kakan kan delas med hjälp av klipp och välj .

Den allmänna idén liknar Even-Paz-protokollet : $CutNearHalves(a,b)$ :

1. Ordna ingångarna så att $a<b$ . Anta att Alice har rätt till $b/(a+b)$ och George har rätt till $a/(a+b)$ .
2. Be George skära kakan till nästan halvor, dvs.
   • om $a+b$ är jämnt skär George kakan i två lika stora delar i hans ögon;
   • om $a+b$ är udda så skär George kakan i två delar vars värderingskvot är $(a +b-1)/2:(a+b+1)/2$ i hans ögon.
3. Åtminstone en av bitarna är värd för Alice åtminstone det värde som George deklarerade; ge den här biten till Alice.
4. Anta att pjäsen som Alice tagit är pjäsen med värdet $c/(a+b)$ , där $c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)$ . Kalla $CutNearHalves(b,ac)$ .

Cut-near-halves-algoritmen behöver som mest $\log _{2}\min(a,b)$ nedskärningar, så den är alltid mer effektiv än Ramsey-partitionsalgoritmen .

Cut-near-halves-algoritmen är inte alltid optimal. Anta till exempel att förhållandet är 7:3.

• Klipp-nära-halvor kan behöva minst fyra snitt: först klipper George i förhållandet 5:5 och Alice får 5. Sedan klipper Alice i förhållandet 3:2; anta att George väljer 2:an. Sedan skär George i förhållandet 2:1; anta att Alice väljer 1:an. Slutligen klipper de och väljer resten.
• Vi kan göra bättre genom att låta George skära i förhållandet 6:4. Om Alice väljer 4:an blir förhållandet 3:3 och vi kan använda klipp-och-välj direkt. Om Alice väljer 6:an blir förhållandet 3:1. Alice klipper i förhållandet 2:2, George väljer 2, och vi behöver ytterligare ett steg för att klippa och välja. Allt som allt behövs högst tre snitt.

Det är en öppen fråga hur man hittar den bästa initiala minskningen för varje rättighetskvot.

Algoritmen kan generaliseras till n agenter; antalet nödvändiga $n(n-1)\lceil \log _{2}(D)\rceil .$

Cseh och Fleiner presenterade en algoritm för att dela upp en flerdimensionell kaka mellan valfritt antal agenter med alla rättigheter (inklusive irrationella rättigheter), i ett begränsat antal frågor. Deras algoritm kräver $2(n-1)\lceil \log _{2}(D)\rceil$ frågor i Robertson–Webb-frågemodellen ; sålunda är det effektivare än agentkloning och halvor. De bevisar att denna runtime-komplexitet är optimal.

Algoritmer för irrationella rättigheter

När rättigheterna inte är rationella tal kan metoder baserade på kloning inte användas eftersom nämnaren är oändlig. Shishido och Zeng presenterade en algoritm som heter mark-cut-choose , som också kan hantera irrationella rättigheter, men med ett obegränsat antal nedskärningar.

Algoritmen för Cseh och Fleiner kan också anpassas för att arbeta med irrationella rättigheter i ett begränsat antal frågor.

Antal nödvändiga snitt

Förutom antalet erforderliga förfrågningar är det också intressant att minimera antalet nödvändiga klipp, så att uppdelningen inte blir för mycket fraktionerad. Shishido-Zeng-algoritmerna ger en rättvis division med högst $2\cdot 3^{n-2}$ snitt, och en mycket rättvis division med högst ${ \displaystyle 4\cdot 3^{n-2}}$ klipp.

I värsta fall kan minst $2(n-1)$ snitt behövas. Brams, Jones och Klamler visar ett exempel för n =2. En kaka gjord av fyra på varandra följande regioner måste delas upp mellan Alice och George, vars värderingar är följande:

Alices värde	2	2	2	2
Georges värde	1	3	3	1

Observera att det totala tårtvärdet är 8 för båda parter. Om $w_{A}\geq 0,75$ , så har Alice rätt till ett värde på minst 6. För att ge Alice sin rätta andel i en sammankopplad pjäs måste vi ge henne antingen de tre skivorna längst till vänster eller de tre skivorna längst till höger. I båda fallen får George en pjäs med ett värde på endast 1, vilket är mindre än hans förfallna andel på 2. För att uppnå en WPR-delning i det här fallet måste vi ge George hans rätta andel i mitten av kakan, där hans värde är relativt stor, men då får Alice två frånkopplade bitar.

Segal-Halevi visar att om kakan är cirkulär (dvs de två ändpunkterna identifieras) så är en ansluten WPR-delning för två personer alltid möjlig; detta följer av Stromquist-Woodall-satsen . Genom att rekursivt tillämpa denna sats för att hitta exakta divisioner är det möjligt att få en WPR-division med högst $2n\cdot (\log _{2}n-1 )+2$ skär när n är en potens av 2, och ett liknande tal när n är generellt.

Crew, Narayanan och Spirkle förbättrade denna övre gräns till 3 n -4 med hjälp av följande protokoll:

• Be varje agent i att markera ett x så att V _i (0, x )=1/2.
• Beställ agenterna i ökande ordning efter deras varumärke, bryt banden godtyckligt.
• Lägg till agenterna i ovanstående ordning i en uppsättning P . Stanna strax innan den totala vikten av medel i P går över 1/2.
• Den första agenten som inte lades till P kallas t , och uppsättningen agenter efter t kallas Q . Nu:
  • Alla medel i P- värde (0, x ) minst 1/2, och deras totala vikt är högst 1/2;
  • Alla medel i Q-värde ( x,1 ) minst 1/2, och deras totala vikt är högst 1/2;
  • Agent t värderar både (0,x) och ( x,1 ) till exakt 1/2.
• Om både P och Q inte är tomma, delas agent t mellan P och Q så att den totala vikten i varje uppsättning är exakt 1/2. Kakan skärs vid x och proceduren fortsätter rekursivt. Detta leder till följande återfallsrelation (där k är antalet agenter i P , exklusive klonen av agent t ): ${\text{Cuts}}(n+1)\leq \max _{1\leq k\leq n-1}(1+{\text{Cuts} }}(k+1)+{\text{Cuts}}(n-k+1))$ . Lägga till det initiala villkoret ${\text{Cuts}}(2)=2$ ger det påstådda antalet ${\text{Cuts}}( n)\leq 3n-4$ .

• Det svårare fallet är att P är tomt (fallet att Q är tomt är analogt). Detta innebär att vikten av t är minst 1/2, och alla agenters värde (0, x ) högst 1/2. I det här fallet hittar vi något y så att agent t värderar (0, y ) exakt w _t , och försöker partitionera agenterna i P och Q som tidigare. Om återigen en av dessa uppsättningar är tom, vet vi att alla agenter värderar (0, y ) minst w _t . Därför måste det enligt mellanvärdessatsen finnas ett värde z i ( x , y ) för vilket en av agenterna, som inte är t , värderar (0, z ) exakt samma som t . Sedan kan vi skära kakan vid z och återvända som i det första fallet.

Det exakta antalet nedskärningar som krävs är fortfarande en öppen fråga. Det enklaste öppna fallet är när det finns 3 agenter och vikterna är 1/7, 2/7, 4/7. Det är inte känt om antalet nödvändiga snitt är 4 (som i den nedre gränsen) eller 5 (som i den övre gränsen).

Se även

Zeng presenterade en algoritm för ungefärlig avundsfri kakskärning med olika rättigheter.

Dall'Aglio och MacCheroni bevisade förekomsten av proportionell kakskärning med olika rättigheter även när agenternas preferenser beskrivs av icke-additiva preferensrelationer, så länge de uppfyller vissa axiom.