Hill-Beck landdelningsproblem

Hill-Beck-problemet med markdelning är en variant av det rättvisa kakskärningsproblemet som föreslogs av Tad Hill 1983 [1] .

Förklaring av problemet

Det finns ett territorium D i anslutning till n länder. Varje land uppskattar (på sitt eget sätt) delmängder av territoriet D . Länder vill dela upp territoriet D rättvist mellan sig, där "rättvisa" betyder proportionell uppdelning . Dessutom måste de delar som tilldelas varje land vara anslutna till och gränsa till det tilldelade landet . Dessa geografiska begränsningar skiljer problemet från det klassiska rättvisa kakskärningsproblemet .

Formellt måste vilket land C i som helst ta emot osammanhängande delar av territorium D , som vi betecknar med D i , så att delar av gränsen mellan C i och D finns inom . $C_{i}\cup D_{i}$

Omöjlighet och möjlighet

Det finns fall då problemet inte kan lösas:

Om det finns en punkt där allt markens värde är koncentrerat (till exempel en "helig plats"), är det uppenbart att territoriet inte kan delas proportionellt. För att förhindra sådana situationer antar vi att alla länder tilldelar värdet 0 till alla individuella poäng.
Om D är en kvadrat, finns det 4 länder som vidrör 4 sidor av den kvadraten, och varje land ser allt markvärde i gränsen för den motsatta sidan av kvadraten, sedan varje fördelning som förbinder, säg, ett nordligt land med det önskade södra sidan gör det omöjligt att koppla samman det östra landet med den önskade västra sidan av torget (om vi pratar om ett tvådimensionellt plan). För att förhindra sådana situationer antar vi att alla länder antar ett nollpris D .

Hill bevisade 1983 att om varje enskild punkt i D har ett värde på 0 för alla länder, och gränsen för D har ett värde på 0 för alla länder, finns det en proportionell uppdelning som är föremål för närliggande begränsningar. Hans bevis gällde bara existensen, han presenterade ingen algoritm [1] .

Algoritm

Fyra år senare beskrev Anatole Beck ett protokoll för att uppnå en sådan uppdelning [2] . I huvudsak är protokollet en utveckling av " sista-minimum "-protokollet. Protokollet tillåter länder att ansöka om delar av territoriet D , ger den del som har den minsta ansökan till sökanden och delar upp återstoden mellan de återstående länderna. Viss variation behövs för att säkerställa att närliggande begränsningar uppfylls. $n-1$

Single Connected Territory

Om territoriet D helt enkelt är anslutet används följande algoritm:

Hitta Riemann-avbildningen h som avbildar D till enhetscirkeln , så att för alla länder värdet av en cirkel som är centrerad vid origo är 0 och värdet av en radie från origo är 0 (existensen av en sådan mappning h är bevisad genom att räkna argument).
Vi ber varje land att rita på enhetens displaycirkel h ( D ) en skiva centrerad vid origo (skivans centrum h ( D )) och ett värde på . Detta är möjligt på grund av det faktum att alla cirklar centrerade vid origo har värdet 0. ${\tfrac {1}{n))$
Hitta skivan D 1 med den minsta radien r 1 .

Det finns två fall.

Ensam vinnare

4. Om D 1 dras av endast ett land, säg C i , så ger vi skivan till land C i . Dess värde för andra länder är strikt mindre än , så vi kan ge land C i en liten extra bit intill den tilldelade disken. ${\tfrac {1}{n))$

För att göra detta, låt oss rita en sektor som förbinder D 1 med gränsen till cirkeln D . Låt varje land (annat än C i ) skära av från denna sektor så att disk- och sektorpoolningsvärdena tillsammans inte överstiger . Detta är möjligt på grund av villkoret att värdena för alla radier från ursprunget är 0. Låt oss ge landet C i föreningen av D 1 och den trunkerade sektorn. ${\tfrac {1}{n))$

Det återstående territoriet är helt enkelt anslutet och har ett värde åtminstone för de återstående länderna, så uppdelningen kan fortsätta rekursivt från steg 1. ${\tfrac {n-1}{n))$ $n-1$

Flera vinnare

Om del D 1 har begärts av k >1 länder, krävs det några mer sofistikerade auktioner för att hitta ett land som vi kan ge skiv- och länksektorn till.

5. Låt oss välja ett godtyckligt vinnande land och kalla det deklaratorn , C 1 . Låt henne lägga till en sektor som ansluter D 1 till hennes nuvarande territorium och låt andra länder skära av från denna sektor, så:

För varje förlorande land har inte värdet av D 1 plus den avskurna sektorn företräde (detta är möjligt eftersom värdet på D 1 för dem är mindre än ). ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
För varje vinnande land är värdet på den trunkerade sektorn mindre än . ${\tfrac {1}{n))$

6. Låt vart och ett av de vinnande länderna föreslå en ny radie r (mindre än deras ursprungliga förslag), så att värdet på den avskurna delen av sektorn plus skivan med radie r värderas till exakt . Vi väljer den minsta sådan skivan D 2 . Återigen finns det två fall: ${\tfrac {1}{n))$

Om C 1 är ett av länderna som ansökte om D 2 , så ger vi det helt enkelt area D 2 (som är något mindre än den ursprungliga ansökan D 1 ) och den anslutande sektorn. C 1 håller med om att värdet är , och andra länder håller med om att värdet inte är större än , så vi kan fortsätta rekursivt från steg 1. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Annars håller C 1 med om att det totala värdet av D 2 och den anslutande sektorn är mindre än . Alla förlorare måste också acceptera detta, eftersom D 2 är mindre än D 1 . Således tas C 1 och alla andra länder som håller med om detta bort från uppsättningen av vinnare. ${\tfrac {1}{n))$

7. Bland de återstående vinnarna kommer vi att välja en ny sökande C 2 . Låt honom lägga till en annan sektor som ansluter D 2 till det aktuella territoriet, och låt andra länder trunkera denna sektor som i steg 5.

Observera att nu är territoriet D 2 förbundet med två territorier - C 1 och C 2 . Detta är ett problem eftersom det gör resten av området osammanhängande. För att lösa detta problem tillåts C 2 välja en annan sektor vars längd är mindre än 1, så att den inte bryter anslutningen [2] . Denna tredje sektor trunkeras återigen av alla länder, som i steg 5. Som svar måste C2 ge tillbaka någon del av sektorn som förbinder D2 till C1 , vars värde är lika med värdet av den mottagna tredjedelen sektor.

Skärningen som föreslagits av land C 2 innehåller nu följande delar: D 2 , en sektor med längden 1 som förbinder D 2 med C 2 , och två korta sektorer som inte når gränsen för D . Värdet av denna konstruktion för C 2 är lika med , för förlorarna är värdet mindre än , och värdet för andra vinnare överstiger inte . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Denna process fortsätter med de återstående vinnarna tills det bara finns en vinnare kvar.

Visst anslutet territorium

Om territoriet D är k -förbundet med ändligt k , kan divisionen göras genom induktion på k .

Om D är ansluten och kan delas med protokollet från föregående avsnitt. $k=1,$

I annat fall betecknar den yttre gränsen för D som B 1 och de inre gränserna som . $(k>1)$ ${\displaystyle B_{2},\dots ,B_{k))$

Vi finner linjen L som förbinder den yttre gränsen B 1 med den inre gränsen B k , så att för alla länder är värdet på denna linje L lika med 0. Detta kan göras med tanke på följande argument. Det finns ett oräkneligt antal parvisa icke-korsande linjer som förbinder B 1 och Bk som finns i D . Men deras mått i D är ändligt, så antalet linjer med positivt mått måste kunna räknas, och sedan finns det en linje med noll mått.

Uppsättningen är -ansluten. Låt oss dela upp det rekursivt och sedan tilldela L godtyckligt till alla länder som detta område gränsar till. Detta bryter inte mot uppdelningens rättvisa, eftersom värdet på L för alla länder är 0. $D\setminus L$ $(k-1)$

Se även

Fair Cake Cutting Challenge

Anteckningar

↑ 12 Hill , 1983 , sid. 438–442.
↑ 12 Beck , 1987 , sid. 157–162.

Litteratur

Hill TP Determining a Fair Border // The American Mathematical Monthly. - 1983. - T. 90 , nr. 7 . - doi : 10.2307/2975720 . — .
Beck A. Constructing a Fair Border // The American Mathematical Monthly. - 1987. - T. 94 , nr. 2 . - doi : 10.2307/2322417 . — .
För andra lösningar på problemet, se Webb WA A Combinatorial Algorithm to Establish a Fair Border // European Journal of Combinatorics. - 1990. - T. 11 , nr. 3 . — S. 301–304 . - doi : 10.1016/s0195-6698(13)80129-1 .