Hill–Beck landdelningsproblem

Följande variant av det rättvisa kakskärningsproblemet introducerades av Ted Hill 1983.

Det finns ett territorium D i anslutning till n länder. Varje land värderar de olika delmängderna av D olika. Länderna skulle vilja dela D rättvist mellan sig, där "rättvis" betyder en proportionell uppdelning . Dessutom måste andelen som tilldelas varje land vara ansluten till och gränsa till det landet . Denna geografiska begränsning skiljer detta problem från klassisk rättvis tårtskärning .

Formellt måste varje land C i få en osammanhängande bit av D , märkt D i , så att en del av gränsen mellan C i och D finns i det inre av C i ∪ Di .

Omöjlighet och möjlighet

Det finns fall där problemet inte kan lösas:

  1. Om det finns en enda punkt till vilken två länder tilldelar allt sitt värde (t.ex. en helig plats), så kan territoriet uppenbarligen inte delas proportionellt. För att förhindra sådana situationer antar vi att alla länder tilldelar värdet 0 till alla singulära punkter.
  2. Om D är en kvadrat, finns det 4 länder intill kvadratens 4 sidor, och varje land tilldelar hela dess värde till gränsen på motsatt sida, då varje allokering som förbinder, säg, det norra landet med dess önskade södra gräns kommer att göra det omöjligt att koppla samman östlandet med dess önskade västra gräns (så länge vi befinner oss i ett tvådimensionellt plan). För att förhindra sådana situationer antar vi att alla länder tilldelar ett värde på 0 till gränsen för D .

1983 bevisade Hill 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, så finns det en proportionell division med angränsande begränsning. Hans bevis var bara existentiella – ingen algoritm beskrevs.

Algoritm

4 år senare beskrev Anatole Beck ett protokoll för att uppnå en sådan uppdelning. I huvudsak är protokollet en utarbetning av Last diminisher -protokollet. Den låter länderna bjuda på delar av D , ger det minsta budet till sin budgivare och delar upp resten mellan de återstående n − 1 länderna. Vissa variationer behövs för att garantera att grannskapsbegränsningen är uppfylld.

Enkelt sammankopplat territorium

När D är helt enkelt ansluten används följande algoritm.

1. Hitta en Riemann-mappning h som mappar D till enhetsskivan , så att för alla länder är värdet av varje cirkel centrerad vid origo 0 och värdet för varje radie från origo är 0 (förekomsten av ett sådant h bevisas med ett räkneargument).

2. Be varje land att rita, på enhetsskivans karta h ( D ), en skiva centrerad vid origo med värdet 1/ n . Detta är möjligt tack vare villkoret att värdet på alla cirklar centrerade vid origo är 0.

3. Hitta skivan D 1 med den minsta radien, r 1 .

Det finns två fall.

Ensam vinnare

4. Om D 1 bara ritades av ett enda land, säg C i , ge denna skiva till C i . Dess värde för de andra länderna är strikt mindre än 1/ n , så vi kan ge till C i en liten extra bit som kopplar den till dess tilldelade skiva.

För att göra detta, rita en sektor som ansluter D 1 till bilden av gränsen mellan C i och D . Låt varje land (utom C i ) trimma denna sektor så att alla länder värderar föreningen mellan skivan och sektorn som högst 1/ n . Detta är möjligt tack vare villkoret att värdet på alla radier från origo är 0. Tilldela C i föreningen av D 1 och den trimmade sektorn.

Resten är helt enkelt kopplad och har ett värde på minst ( n − 1)/ n till de återstående n − 1 länderna, så uppdelningen kan fortsätta rekursivt i steg 1.

Många vinnare

Om D 1 drogs av k >1 länder, krävs det några mer sofistikerade auktioner för att hitta ett land som vi kan ge en skiva och en anslutande sektor till.

5. Välj ett godtyckligt vinnarland och kalla det deklaranten , C 1 . Låt den lägga till en sektor som ansluter D 1 till dess nuvarande territorium och låt de andra länderna trimma den sektorn så att:

  • För varje icke-vinnande land är värdet på D 1 plus den trimmade sektorn högst 1/ n (detta är möjligt eftersom värdet på D 1 för dem är mindre än 1/ n ).
  • För varje vinnande land är värdet på enbart den trimmade sektorn mindre än 1/ n .

6. Låt vart och ett av de vinnande länderna bjuda en ny radie r (mindre än dess första bud), så att värdet på den trimmade sektorn plus skivan med radie r är exakt 1/ n . Välj den minsta skivan, D 2 . Återigen finns det två fall:

Om C 1 är ett av länderna som bjuder D 2 , ge det bara D 2 (som är något mindre än den ursprungliga D 1 ) och den anslutande sektorn. C 1 höll med om att värdet är 1/ n och de andra länderna var överens om att det är högst 1/ n , så vi kan fortsätta rekursivt i steg 1.

I annat fall håller C 1 med om att det totala värdet av D 2 plus den anslutande sektorn är mindre än 1/ n . Alla icke-vinnare måste också acceptera detta eftersom D 2 är mindre än D 1 . Så C 1 och alla andra länder som går med på detta tas bort från uppsättningen av vinnare.

7. Bland de återstående vinnarna, välj en ny deklarator C 2 . Låt den lägga till en annan sektor som ansluter D 2 till sitt nuvarande territorium och låt de andra länderna trimma den sektorn som i steg 5.

Observera att nu är D 2 kopplad till två olika territorier – C 1 och C 2 . Detta är ett problem eftersom det gör det återstående territoriet frånkopplat. För att lösa detta tillåts C 2 ta en annan sektor, denna tid av längd mindre än 1 så att den inte skadar anslutningen. Den tredje sektorn trimmas återigen av alla länder som i steg 5. I gengäld måste C2 ge upp någon del av sektorn som förbinder D2 till C1 , vars värde är lika med värdet av den tredje sektorn som den mottog .

C 2 :s kandidatallokering innehåller nu följande delar: D 2 , en enda sektor av längden 1 som förbinder D 2 till C 2 , och två korta sektorer som inte når gränsen till D . Värdet av denna konstruktion för C 2 är 1/ n , dess värde för icke-vinnarna är mindre än 1/ n , och dess värde för de återstående vinnarna är högst 1/ n .

Denna process fortsätter med de återstående vinnarna, tills endast en enda vinnare återstår.

Ändligt förbundet territorium

Om territoriet D är k- förbundet med ett ändligt k , så kan divisionen fortsätta genom induktion på k .

När k = 1 är D enkelt anslutet och kan delas med protokollet i föregående avsnitt.

Annars ( k > 1), markera den yttre gränsen för D med B 1 och dess inre gränser med B 2 , ..., B k .

Hitta en linje L som förbinder den yttre gränsen B 1 med den inre gränsen B k , så att alla länder värderar L som 0. Detta är möjligt med följande räkneargument. Det finns en oräknelig oändlighet av parvis-disjunkta linjer som förbinder B 1 och Bk och ingår i D . Men måttet på D är ändligt, så antalet linjer med ett positivt mått måste vara ändligt.

Mängden D \ L är ( k − 1)-ansluten. Dela det rekursivt och tilldela sedan L godtyckligt till valfritt land som gränsar till det. Detta påverkar inte fördelningens rättvisa eftersom värdet på L är 0 för alla länder.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Hill–Beck_land_division_problem&oldid=1033881845 "