Hill-Beck jordfordelingsproblem

Hill-Beck jorddelingsproblemet er en variant af det fair kage - skæringsproblem foreslået af Tad Hill i 1983 [1] .

Udtalelse af problemet

Der er et område D , der støder op til n lande. Hvert land estimerer (på sin egen måde) delmængder af territoriet D . Lande ønsker at dele område D retfærdigt mellem sig, hvor "retfærdighed" betyder proportional opdeling . Derudover skal de dele, der er tildelt hvert land, være forbundet med og støde op til det tildelte land . Disse geografiske begrænsninger adskiller problemet fra det klassiske problem med fair kageskæring .

Formelt skal ethvert land C i modtage usammenhængende stykker af territorium D , som vi betegner med D i , således at dele af grænsen mellem C i og D er indeholdt i . $C_{i}\cup D_{i}$

Umulighed og mulighed

Der er tilfælde, hvor problemet ikke kan løses:

Hvis der er et punkt, hvor hele jordens værdi er koncentreret (for eksempel et "helligt sted"), så er det indlysende, at området ikke kan opdeles proportionalt. For at forhindre sådanne situationer antager vi, at alle lande tildeler en værdi på 0 til alle individuelle point.
Hvis D er en firkant, er der 4 lande, der berører 4 sider af den firkant, og hvert land ser al jordværdi i grænsen af den modsatte side af firkanten, så enhver fordeling, der forbinder f.eks. et nordligt land med det ønskede sydsiden gør det umuligt at forbinde det østlige land med den ønskede vestlige side af pladsen (hvis vi taler om et todimensionalt plan). For at forhindre sådanne situationer antager vi, at alle lande antager en grænsepris på nul D .

Hill beviste i 1983, at hvis hvert enkelt punkt i D har en værdi på 0 for alle lande, og grænsen for D har en værdi på 0 for alle lande, er der en proportional division underlagt naboskabsbegrænsninger. Hans bevis vedrørte kun eksistensen, han præsenterede ikke nogen algoritme [1] .

Algoritme

Fire år senere beskrev Anatole Beck en protokol for at opnå en sådan opdeling [2] . I det væsentlige er protokollen en udvikling af " sidste-minimum "-protokollen. Protokollen giver landene mulighed for at ansøge om dele af territoriet D , giver den del med den mindste ansøgning til ansøgeren og deler resten mellem de resterende lande. Der er behov for en vis variation for at sikre, at begrænsningerne i tilknytning er opfyldt. $n-1$

Single Connected Territory

Hvis territoriet D blot er forbundet , bruges følgende algoritme:

Find Riemann-kortlægningen h , der afbilder D til enhedscirklen , så for alle lande værdien af enhver cirkel centreret ved oprindelsen er 0 og værdien af enhver radius fra oprindelsen er 0 (eksistensen af en sådan afbildning h er bevist ved at tælle argumenter).
Vi beder hvert land om at tegne på enhedens displaycirkel h ( D ) en skive centreret ved oprindelsen (diskens centrum h ( D )) og en værdi på . Dette er muligt på grund af det faktum, at alle cirkler centreret ved oprindelsen har en værdi på 0. ${\tfrac {1}{n))$
Find disken D 1 med den mindste radius r 1 .

Der er to tilfælde.

Enkelt vinder

4. Hvis D 1 kun tegnes af ét land, siger C i , så giver vi disken til land C i . Dens værdi for andre lande er strengt taget mindre end , så vi kan give land C i en lille ekstra luns ved siden af den tildelte disk. ${\tfrac {1}{n))$

For at gøre dette, lad os tegne en sektor, der forbinder D 1 med grænsen til cirklen D . Lad hvert land (bortset fra C i ) afskære denne sektor, så disk- og sektorpoolingsværdierne tilsammen ikke overstiger . Dette er muligt på grund af betingelsen om, at værdierne af alle radier fra oprindelsen er 0. Lad os give landet C i foreningen af D 1 og den trunkerede sektor. ${\tfrac {1}{n))$

Det resterende territorium er simpelthen forbundet og har en værdi i det mindste for de resterende lande, så opdelingen kan fortsættes rekursivt fra trin 1. ${\tfrac {n-1}{n))$ $n-1$

Flere vindere

Hvis del D 1 er blevet anmodet om af k >1 lande, kræves der nogle mere sofistikerede auktioner for at finde et land, som vi kan give disk- og linksektoren til.

5. Lad os vælge et vilkårligt vinderland og kalde det erklæreren , C 1 . Få hende til at tilføje en sektor, der forbinder D 1 til hendes nuværende territorium, og lad andre lande afskære fra denne sektor, så:

For ethvert tabende land har værdien af D 1 plus afskæringssektoren ikke forrang (dette er muligt, da værdien af D 1 for dem er mindre end ). ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
For ethvert vinderland er værdien af den trunkerede sektor mindre end . ${\tfrac {1}{n))$

6. Lad hvert af de vindende lande foreslå en ny radius r (mindre end deres oprindelige forslag), så værdien af den afskårne del af sektoren plus skiven med radius r værdiansættes til nøjagtigt . Vi vælger den mindste sådan disk D 2 . Igen er der to tilfælde: ${\tfrac {1}{n))$

Hvis C 1 er et af de lande, der har ansøgt om D 2 , så giver vi det blot område D 2 (som er lidt mindre end den oprindelige ansøgning D 1 ) og den forbindende sektor. C 1 er enig i, at værdien er , og andre lande er enige om, at værdien ikke er større end , så vi kan fortsætte rekursivt fra trin 1. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Ellers er C 1 enig i, at den samlede værdi af D 2 og den forbindende sektor er mindre end . Alle tabere skal også acceptere dette, da D 2 er mindre end D 1 . Dermed er C 1 og alle andre lande, der er enige i dette, fjernet fra vindersættet. ${\tfrac {1}{n))$

7. Blandt de resterende vindere vil vi vælge en ny ansøger C 2 . Lad ham tilføje en anden sektor, der forbinder D 2 til det nuværende territorium, og lad andre lande afkorte denne sektor som i trin 5.

Bemærk, at nu er territoriet D 2 forbundet med to territorier - C 1 og C 2 . Dette er et problem, da det gør resten af området usammenhængende. For at løse dette problem får C 2 lov til at vælge en anden sektor, hvis længde er mindre end 1, så den ikke afbryder forbindelsen [2] . Denne tredje sektor afkortes igen af alle lande, som i trin 5. Som svar skal C 2 give en del af sektoren tilbage, der forbinder D 2 til C 1 , hvis værdi er lig med værdien af den modtagne tredjedel sektor.

Skæringen foreslået af land C 2 indeholder nu følgende dele: D 2 , en sektor med længde 1, der forbinder D 2 til C 2 , og to korte sektorer, der ikke når grænsen til D . Værdien af denne konstruktion for C 2 er lig med , for taberne er værdien mindre end , og værdien for andre vindere overstiger ikke . ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$

Denne proces fortsætter med de resterende vindere, indtil der kun er én vinder tilbage.

Certainly Connected Territory

Hvis territoriet D er k - forbundet med endeligt k , kan opdelingen foretages ved induktion på k .

Hvis D er tilsluttet og kan opdeles ved hjælp af protokollen fra forrige afsnit. $k=1,$

Ellers skal du angive den ydre grænse for D som B 1 og de indre grænser som . $(k>1)$ ${\displaystyle B_{2},\dots ,B_{k))$

Vi finder linjen L , der forbinder den ydre grænse B 1 med den indre grænse B k , således at værdien af denne linje L for alle lande er lig med 0. Dette kan gøres i lyset af følgende argument. Der er et utalligt antal parvise ikke-skærende linjer, der forbinder B 1 og B k indeholdt i D . Men deres mål i D er endeligt, så antallet af linjer med positivt mål skal kunne tælles, og så er der en linje med nul mål.

Sættet er -tilsluttet. Lad os opdele det rekursivt og derefter tildele L vilkårligt til ethvert land, som dette område grænser op til. Dette krænker ikke opdelingens retfærdighed, da værdien af L for alle lande er 0. $D\setminus L$ $(k-1)$

Se også

Fair Cake Cutting Challenge

Noter

↑ 12 Hill , 1983 , s. 438-442.
↑ 12 Beck , 1987 , s. 157-162.

Litteratur

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