Problemet med proportional kageskæring

Problemet med proportional kageskæring er en slags retfærdigt kageskæringsproblem . Dette er en opdeling af en heterogen ressource ("kage"), der opfylder kriteriet om proportionalitet , nemlig at enhver deltager mener, at den del af kagen, der er tildelt ham, ikke er værre end 1/ n af den samlede evaluering af kagen.

Når proportionalitet diskuteres , er der normalt to antagelser:

Deltagernes vurderinger er ikke atomare , det vil sige, at der ikke er nogen udelelige elementer med en positiv vurdering.
Deltagernes score er additive , det vil sige, når et stykke deles, er stykkets partitur lig med summen af dets dele.

Procedurer

For to personer er Delhi-and-Choose- proceduren en klassisk løsning. Den ene person deler ressourcen i to halvdele, som han anser for lige, og den anden person vælger den "halvdel", som han bedst kan lide. Den ikke-atomare antagelse garanterer, at kutteren kan skære (som han tror) i to lige store dele. Additivitetsantagelsen garanterer, at estimaterne for begge deltagere vil være mindst 1/2 for deres stykker.

Der er mange måder at udvide denne procedure til mere end 2 personer. Hver af disse metoder har sine egne fordele og ulemper.

Simple procedurer

Det sidste minus er den tidligste proportionaldelingsprocedure udviklet for n personer:

En af deltagerne bliver bedt om at vælge et stykke, som han vurderer til 1/ n .
Andre deltagere har til gengæld mulighed for at gøre indsigelse og erklære, at brikken er større end 1/ n . I dette tilfælde bliver han bedt om at reducere brikken, så den resterende del af brikken ifølge hans skøn er 1/ n .
Den sidste deltager, der reducerer stykket, får det.
De resterende deltagere deler resten af kagen på samme måde blandt de resterende personer. $n-1$

Ved induktion kan det bevises, at hver deltager, der overholder reglerne, er garanteret at få 1/ n af kagen, uanset de øvrige deltageres handlinger. Dette er en diskret procedure, der kan udføres i runder. I værste fald vil der være behov for handling - én handling for hver deltager i hver runde. De fleste af disse handlinger kan dog udføres på papir. Kun snit er virkelig nødvendige. Derfor, hvis kagen er forbundet, så kan det garanteres, at hvert stykke bliver forbundet. $n\ gange (n-1)/2=O(n^{2})$ $n-1$

Proceduren "Moving Knife" Dubins - Spanierer en kontinuerlig version af "Last Reducing" [1] .

Kniven bevæger sig langs torus parallelt fra den ene ende til den anden.
Deltageren siger "stop", når han mener, at værdien til venstre for kniven er nået . Et stykke kage skæres af og gives til den deltager, der sagde. ${\tfrac {1}{n))$
Denne procedure gentages med resten af kagen og de resterende deltagere. Den sidste deltager får resten af kagen.

Fink-protokollen er en algoritme, der fortsætter med at opdele i tilstrækkeligt små "lige" bidder.

Den første deltager deler ressourcen i stykker, som han anser for lige;
Den anden deltager vælger halvdelen og overlader resten til den første deltager;
Hver af disse to deltagere deler sin portion i tredjedele;
Den tredje deltager vælger to af de resulterende portioner - en hver fra den første og anden deltager;
Hvis der er fire deltagere, deler hver af de tre første deltagere sin del i kvarte, og processen fortsætter.

Fordelen ved denne protokol er, at det kan gøres online – når nye partnere kommer i spil, tilpasses den eksisterende division til det uden at skulle starte hele divisionsprocessen fra begyndelsen. Ulempen ved denne algoritme er, at hver deltager modtager et stort antal afbrudte bidder i stedet for en tilsluttet chunk.

Enkeltdeling er en procedure baseret på en ligelig opdeling, udført af en enkelt agent. Fordelen ved proceduren er, at den kan generaliseres tilsymmetrisk retfærdig udskæring af kagen.

Se også: [2] .

Rekursiv halvering

Ved at bruge divide and conquer-strategien kan proportional opdeling opnås i tide [3] . For nemheds skyld er proceduren beskrevet her givet for et lige antal deltagere, men den kan nemt tilpasses til et hvilket som helst antal deltagere: $O(n\log n)$

Hver deltager bliver bedt om at tegne en streg, der deler kagen i to stykker, som han anser for at være ækvivalente. Det kræves, at snittene ikke skærer hinanden. Den nemmeste måde at garantere dette på er kun at tillade vandrette linjer eller kun lodrette linjer.
Algoritmen sorterer de n linjer i stigende rækkefølge og skærer kagen i medianen af linjerne. For eksempel, hvis der er 4 deltagere, der tegner streger ved punkter og , skærer algoritmen kagen lodret ved punktet . $x=1,x=3,x=5$ $x=9$ $x=4$
Algoritmen tildeler hver af de to halvdele n /2 deltagere - partnere hvis linjer er inde i halvdelen. For eksempel tildeles medlemmerne, der tegnede streger ved prikkerne , til den vestlige halvdel, mens de resterende medlemmer tildeles den østlige halvdel. Hver halvdel er opdelt rekursivt blandt de n /2 deltagere, der er tildelt den halvdel. $x=1$ $x=3$

Det kan vises ved induktion, at enhver spiller, der spiller efter reglerne, er garanteret en brik med en værdi på mindst 1/ n , uanset hvordan de andre spillere opfører sig.

Takket være divide and conquer-strategien vil antallet af iterationer kun være O(log n ), i modsætning til O( n )-værdien i den sidste faldende procedure. Ved hver iteration er hver deltager pålagt at lave en note. Derfor vil det samlede antal karakterer være lig med . $O(n\log n)$

Algoritmen har en randomiseret version, der kan bruges til at reducere antallet af krydser. Se artiklen " Even-Paz Algorithm ".

Udvælgelsesprocedurer

En anden tilgang til at skære kagen er at lade hver deltager udtrække et eller andet antal stykker afhængigt af antallet af deltagere, p ( n ), og give hver deltager en af sine valgte stykker, så stykkerne ikke overlapper hinanden.

Som et simpelt eksempel på en udvælgelsesprocedure kan du forestille dig en kage som et endimensionelt segment, og hver deltager ønsker at få et separat forbundet segment. Vi bruger følgende protokol:

Hver deltager deler kagen privat op i n intervaller, som han anser for lige store, lad os kalde disse brikker for kandidater .
Protokollen arrangerer kandidaterne i rækkefølge efter deres østlige grænser (fra vest til øst) og vælger segmentet med den vestligste østlige ende. Dette segment kaldes det sidste stykke . $n^{2}$
Protokollen giver slutstykket til sin ejer og fjerner alle kandidater, der krydser det. Trin #2 gentages derefter for de resterende segmenter af resten af deltagerne. $n-1$

Udvælgelsesreglen i trin #2 sikrer, at der ved hver iteration højst fjernes ét segment af hver deltager. Derfor forbliver antallet af segmenter per deltager efter hver iteration lig med antallet af deltagere, og processen kan fortsætte indtil alle deltagere modtager et segment [4] .

Denne protokol kræver, at hver part besvarer n forespørgsler, så forespørgslens kompleksitet svarer til proceduren for sidste nedgang. $O(n^{2})$

Randomiserede versioner

Du kan bruge randomisering til at reducere antallet af forespørgsler. Tanken er, at hver deltager ikke indberetter hele sættet af n kandidater, men kun et konstant antal d kandidater valgt tilfældigt. Forespørgselskompleksiteten er O( n ), hvilket naturligvis vil være bedst muligt. I mange tilfælde er det fortsat muligt at give hver deltager en enkelt kandidat, der ikke overlapper med andre. Der er dog scenarier, hvor en sådan fordeling ikke er mulig.

Vi kan skære kagen med O( n ) forespørgsler, hvis vi går på kompromis:

I stedet for at garantere fuld proportionalitet, garanterer vi delvis proportionalitet , det vil sige, at hver deltager modtager en vis konstant brøkdel f ( n ) af den samlede værdi, hvor . $f(n)<{\tfrac {1}{n))$
I stedet for at give hver deltager en separat forbundet brik, giver vi foreningen af en eller flere ikke-skærende brikker til deltageren.

Den generelle ordning er som følger [5] :

Hver deltager deler kagen privat i lige store stykker efter hans subjektive vurdering. Disse stykker vil blive kaldt kandidater . $n\cdot an$
Hver deltager vælger 2 d kandidater ensartet tilfældigt med et afkast. Kandidater grupperes i d -par, som deltageren rapporterer til algoritmen. Disse par vil blive kaldt kvartfinalesæt . $n\cdot d$
Fra hvert kvartfinalesæt udvælger algoritmen en enkelt brik, den der krydser det mindste antal andre kandidater. Disse brikker vil blive kaldt semifinale . $n\cdot d$
For hver deltager vælger algoritmen et enkelt stykke, lad os kalde det endeligt . De sidste stykker udvælges således, at hvert punkt på kagen er dækket af højst to sidste stykker (se nedenfor). Hvis dette lykkes, skal du gå til trin nummer 5. Hvis det mislykkes, skal du vende tilbage til trin nummer 1.
Hvert stykke af kagen, der kun tilhører et sidste stykke, gives til ejeren af det stykke. Hver del af kagen, der hører til de sidste to stykker, divideres proportionalt med enhver deterministisk proportional divisionsalgoritme.

Algoritmen garanterer, at hver deltager med sandsynlighed vil modtage mindst halvdelen fra et af sine kandidatstykker, hvilket indebærer (hvis estimaterne er additive), at estimatet ikke vil være mindre end 1/2 an . Der er O( n ) kandidatbidder og O( n ) ekstra divisioner i trin #5, som hver tager O(1) tid. Derfor er den samlede køretid for algoritmen O( n ). $O(1a^{2})$

Hovedproblemet i denne ordning er udvælgelsen af de sidste stykker i trin #4. Se Edmonds-Prus-protokollen for detaljer .

Resultater efter sværhedsgrad

Resultaterne om kompleksitet er formuleret i form af "standard Robertson-Webb-modellen", det vil sige, at de refererer til procedurer, der bruger to typer handlinger: "Estimate" og "Cut".

Enhver deterministisk proportional divisionsprocedure for deltagere skal bruge mindst n handlinger, selvom alle scoringsfunktionerne er identiske [3] . $n\geqslant 3$

Desuden skal enhver deterministisk eller randomiseret (sandsynlighed) proportional divisionsprocedure, der tildeler hver deltager en tilsluttet brik, bruge handlinger [6] . $\Omega (n\log n)$

Desuden skal enhver deterministisk proportional divisionsprocedure udføre handlinger, selvom proceduren har tilladelse til at tildele hver deltager en brik, der er foreningen af segmenter, og selvom proceduren kun har lov til at garantere omtrentlig retfærdighed . Beviset er baseret på en nedre grænse for kompleksiteten i at finde et stykke kage for individuelle spillere, der er af stor værdi og tyndt i bredden [7] [8] . $\Omega (n\log n)$

Det følger af disse vanskelighedsresultater, at rekursiv halvering er den hurtigste algoritme til at opnå fuld proportionalitet med forbundne stykker, og det er den hurtigst mulige deterministiske algoritme til at opnå delvis proportionalitet selv med afbrudte stykker. Det eneste tilfælde, hvor det kan forbedres, er i randomiserede algoritmer, der garanterer delvis proportionalitet med afbrudte stykker.

Hvis spillere kun er i stand til at skære med begrænset præcision, så inkluderer den nedre grænse også randomiserede protokoller [7] [8] . $\Omega (n\log n)$

Følgende tabel indeholder kendte resultater [5] :

Proportionalitet ( helt / delvist)	Stykker (tilsluttet/ frakoblet)	Protokoltype (deterministisk / randomiseret )	Forespørgsler (præcis/ omtrentlig)	Antal anmodninger
komplet	budbringere	deterministisk	nøjagtig	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
komplet	budbringere	deterministisk	omtrentlig	$\Omega (n\log n)$ [6]
komplet	budbringere	randomiseret	nøjagtig	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
komplet	budbringere	randomiseret	omtrentlig	$\Omega (n\log n)$ [6]
komplet	usammenhængende	deterministisk	nøjagtig	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
komplet	usammenhængende	deterministisk	omtrentlig	$\Omega (n\log n)$ [7] [8]
komplet	usammenhængende	randomiseret	nøjagtig	$O(n\log n)$ [3]
komplet	usammenhængende	randomiseret	omtrentlig	$\Omega (n\log n)$ [7] [8]
delvis	budbringere	deterministisk	nøjagtig	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
delvis	budbringere	deterministisk	omtrentlig	$\Omega (n\log n)$ [7] [8]
delvis	budbringere	randomiseret	nøjagtig	$\Omega (n\log n)$ [3]
delvis	budbringere	randomiseret	omtrentlig	$\Omega (n\log n)$ [7] [8]
delvis	usammenhængende	deterministisk	nøjagtig	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
delvis	usammenhængende	deterministisk	omtrentlig	$\Omega (n\log n)$ [7] [8]
delvis	usammenhængende	randomiseret	nøjagtig	O( n ) [5]
delvis	usammenhængende	randomiseret	svagt tilnærmet (uafhængig af estimeringsfejl )	O( n ) [5]
delvis	usammenhængende	randomiseret	omtrentlig	$\Omega (n\log n)$ [7] [8]

Indstillinger

Forskellige delinger forfalder

Proportionalitetstesten kan generaliseres til en situation, hvor deltagernes forfaldne andele ikke er lige store. For eksempel kan en ressource ejes af to aktionærer, Alice ejer aktier og George ejer . Dette fører til et vægtet proportionalitetskriterium (WPR) - der er nogle vægte w i , hvis sum er 1, og enhver deltager i skal mindst modtage en andel w i af ressourcen efter hans egen vurdering. Flere algoritmer kan bruges til at finde WPR-delingen. Hovedproblemet er, at antallet af klip kan være stort, selvom der kun er to deltagere. Se Forholdsmæssig udskæring af kagen med forskellige dele på grund af . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

Superproportional inddeling

En super-proportional division er en division, hvor hver deltager modtager strengt taget mere end 1/ n af ressourcen ifølge sin egen subjektive vurdering.

En sådan opdeling eksisterer naturligvis ikke altid - hvis alle deltagere har nøjagtig de samme evalueringsfunktioner, er det bedste, vi kan gøre, at give alle præcis 1/ n . En nødvendig betingelse for eksistensen af en superproportional opdeling er således kravet om, at ikke alle partnere har samme værdiansættelse.

Overraskende, hvis evalueringsfunktionerne er additive og ikke atomare, er denne betingelse også tilstrækkelig. Det vil sige, at hvis der er mindst to deltagere, hvis evalueringsfunktioner kun er lidt forskellige, så er der en superproportional division, hvor alle deltagere får mere end 1/ n . Se Super Proportional Division for detaljer.

Naboskabsbegrænsninger

Ud over den sædvanlige begrænsning, at alle brikker skal tilsluttes, er der yderligere begrænsninger i nogle tilfælde. Især når kagen , der skal deles , er et omstridt territorium, der ligger mellem flere lande, kan det kræves, at hvert stykke, der gives til et land, støder op til landets nuværende grænse. Proportional opdeling i dette tilfælde eksisterer altid og kan findes ved at kombinere Last Decrease-protokollen med geometriske teknikker ved hjælp af konforme afbildninger . Se artiklen " The Hill-Beck Land Dividing Problem ".

2D geometriske begrænsninger

Når en "kage" er opdelt i todimensionelt rum (et plan), såsom ved opdeling af jordlodder eller reklameplads i trykte eller elektroniske medier, kræves det ofte, at stykkerne opfylder nogle geometriske begrænsninger ud over tilslutningsmuligheder. For eksempel kan det kræves, at hver brik er en firkant, et tykt rektangel (det vil sige, at længden og bredden ikke afviger flere gange) eller en tyk figur af en generel form. I nærvær af sådanne restriktioner på figurer eksisterer proportional division normalt ikke, men delvis proportional division eksisterer normalt og kan findes ved hjælp af effektive algoritmer [9] .

Økonomisk effektiv opdeling

Ud over proportionalitet kræves det ofte, at opdelingen er økonomisk effektiv , dvs. maksimerer den samlede fordel (defineret som summen af alle agenters nytteværdi).

Overvej for eksempel en kage, der indeholder 500 gram chokolade og 500 gram vanilje, som deles af to deltagere, hvoraf den ene kun vil have chokolade og den anden foretrækker vanilje. Mange kage-skæringsprotokoller vil give hvert middel 250 gram chokolade og 250 gram vanilje. Denne opdeling er proportional, da hver deltager får 0,5 af den samlede værdi, så den normaliserede samlede udbytte er 1. Denne opdeling vil dog være meget ineffektiv, da vi kan give hele chokoladedelen til den første deltager og hele vaniljedelen til den anden deltager, får en normaliseret samlet fordel 2.

Det optimale proportionale divisionsproblem er problemet med at finde en proportional partition, der maksimerer den samlede fordel blandt alle mulige proportionale fordelinger. I øjeblikket har problemet kun en løsning for meget specielle kager, når det er et endimensionelt segment, og brugstæthedsfunktionerne er lineære (det vil sige ). Generelt er problemet NP-hårdt . Hvis nyttefunktionerne ikke er normaliserede (det vil sige, at vi tillader hver deltager at have forskellige estimater af kagens samlede betydning), er problemet NP-svært selv for tilnærmelse med en faktor [10] . $u(x)=Ax+B$ ${\displaystyle {\tfrac {1}{\sqrt {n))))$

Fair opdeling

Retfærdighed er ikke en egenskab ved opdelingen, men snarere en egenskab ved protokollen. Alle proportional divisionsprotokoller er svagt retfærdige i den forstand, at enhver deltager, der handler i overensstemmelse med sin sande værdi, garanteres at modtage mindst 1/ n (eller 1/ an i tilfælde af en delvis proportional protokol) uanset hvordan de andre deltagere opfører sig. Selvom de andre medlemmer danner en koalition bare for at skade ham, vil han stadig få sin garanterede andel [11] .

De fleste protokoller er dog ikke strengt fair i den forstand, at nogle deltagere kan have incitamenter til at lyve for at få endnu mere, end han er garanteret. Dette gælder selv for en simpel opdel-og-vælg- protokol - hvis fræseren kender vælgerens præferencer, kan han skære et stykke af, som vælgeren værdsætter lige under 1/2, men som skæreren selv værdsætter godt over 1/2.

Der er rimelige mekanismer til at opnå en perfekt partition . Fordi perfekt division er proportional, er disse mekanismer også rimelige proportionale divisionsmekanismer.

Disse mekanismer kan udvides til at opnå en superproportional opdeling , hvis den findes [12] :

Vi beder hver deltager om at give en fuldstændig evaluering.
Vi vælger en tilfældig partition (se artiklen af Mossel og Tamuz [12] for detaljer).
Hvis den tilfældige partition viser sig at være superproportional ifølge de rapporterede mål, udfører vi den. Ellers bruger vi en fair mekanisme for at sikre en perfekt opdeling.

Hvis der eksisterer en superproportional division, er der en positiv chance for, at den opnås i trin 2. Derfor er den forventede værdi for enhver ærlig deltager strengt taget større end 1/ n . For at forstå, at mekanismen er retfærdig, skal du overveje tre tilfælde: (a) Hvis den valgte partition virkelig er superproportional, så er det eneste mulige resultat af løgn at narre mekanismen til at tro, at partitionen ikke er superproportional. Dette vil tvinge mekanismen til at anvende en perfekt opdeling, hvilket er værre for alle involverede, inklusive knugeren. (b) Hvis den valgte partition ikke er superproportional, kun fordi løgneren angiver 1/ n eller mindre, er den eneste effekt af at lyve at få motoren til at tro, at skillevæggen er superproportional og bruge den, hvilket kun vil skade løgneren selv. (c) Hvis den valgte opdeling faktisk ikke er superproportional, hvilket giver den anden part en værdi på 1/ n eller mindre, så vil falsk ikke have nogen effekt, da opdelingen slet ikke vil blive brugt.

Forholdsmæssig opgavefordeling

Hvis den ressource, der skal deles, er uønsket (svarende til en opgavefordeling ), defineres en proportional opdeling som en opdeling, der giver hver person højst 1/ n af ressourcen (dvs. ulighedstegnet i den anden retning).

De fleste proportional divisionsalgoritmer kan tilpasses til at dele opgaver uden problemer.

Se også

Præcis opdeling . Se også "Perfekt opdeling"

Noter

↑ Dubins og Spanier, 1961 , s. 1-17.
↑ Tasnadi, Attila. En ny procedure proportional for n-personers kageskæringsproblem . researchgate. Hentet: 24. september 2015. (ubestemt)
↑ 1 2 3 4 5 6 7 8 9 Even, Paz, 1984 , s. 285.
↑ Dette afsnit af proceduren ligner den grådige polynomieløsning )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , s. 623-634.
↑ 1 2 3 4 5 Woeinger, 2007 , s. 213-220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , s. 271-278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , s. 1-12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , s. 1-28.
↑ Bei, Chen, Hua et al., 2012 .
↑ Steinhaus, 1948 , s. 101-4.
↑ 1 2 Mossel, Tamuz, 2010 , s. 288-299.

Litteratur

En oversigt over proportionale og andre opdelinger dukkede op i artiklen:
Austin AK deler en kage // The Mathematical Gazette. - 1982. - T. 66 , no. 437 . — S. 212–215 . - doi : 10.2307/3616548 . — .
Lester Eli Dubins, Edwin Henry Spanier. Sådan skærer du en kage retfærdigt // The American Mathematical Monthly. - 1961. - T. 68 , no. 1 . - doi : 10.2307/2311357 . — .
Even S., Paz A. En note om kageskæring // Diskret anvendt matematik. - 1984. - T. 7 , no. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Balanced Allocations of Cake // 2006 47. årlige IEEE Symposium on Foundations of Computer Science (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Gerhard J. Woeinger. Om kompleksiteten ved kageskæring // Diskret optimering. - 2007. - T. 4 , no. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Kageskæring er virkelig ikke et stykke kage // Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Kageskæring er virkelig ikke et stykke kage // ACM Transactions on Algorithms. - 2011. - T. 7 , no. 4 . - doi : 10.1145/2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Fair and square: Kageskæring i to dimensioner // Journal of Mathematical Economics. - 2017. - T. 70 . - doi : 10.1016/j.jmateco.2017.01.007 . - arXiv : 1409.4511 .
Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Optimal proportional kageskæring med forbundne stykker // AAAI-konferenceforløb. – 2012.
Hugo Steinhaus. Problemet med retfærdig opdeling // Econometrica. - 1948. - T. 16 , Nr. 1 . — .
Elchanan Mossel, Omer Tamuz. Truthful Fair Division // . - 2010. - T. 6386. - (Lecture Notes in Computer Science). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .