Simmons Protocols - Su

Simmons-Su protokollerne er et sæt protokoller til misundelig opdeling. Protokollerne er baseret på Sperners lemma . Fordelene ved disse protokoller er, at de pålægger få begrænsninger for deltagernes præferencer og stiller deltagerne i divisionen enkle spørgsmål, såsom "hvilket stykke foretrækker du?".

Der er udviklet protokoller til at løse flere relaterede problemer.

Kageskæring

I det misundelige kageskæringsproblem bør en heterogen delbar ressource ("kage") opdeles i n deltagere med forskellige præferencer i dele af kagen. Kagen skal deles i n stykker, så (a) hver deltager får et enkelt tilsluttet stykke og (b) hver deltager mener, at hans stykke (i svag forstand) er bedre end alle de andre stykker. Problemløsningsprotokollen blev udviklet af Forest Simmons i 1980 med hjælp fra Michael Starbird. Protokollen blev første gang udgivet af Francis Su i 1999 [1] .

Givet et snit af kagen (i n stykker), siger vi, at deltageren foretrækker et bestemt stykke af det snit, hvis han mener, at dette stykke er bedre end alle andre stykker. "I svag forstand" betyder, at deltageren ikke må skelne mellem den modtagne brik og en eller flere andre brikker, således at han kan "foretrække" mere end én brik.

Protokollen gør følgende antagelser om præferencerne for deltagerne i divisionen

Uafhængighed af andre deltagere - præference afhænger af deltageren og den specifikke udskæring af hele kagen, men ikke af andre deltageres valg.
Sultne deltagere - En deler foretrækker aldrig en tom brik.
Topologisk lukkede præferencesæt - ethvert stykke, der foretrækkes under en konvergent snitsekvens, vil blive foretrukket som grænsen for sekvensen. For eksempel, hvis konkurrenten foretrækker det første stykke i alle snit, når det første snit blev lavet på et punkt,og foretrækker det andet stykke i alle snit, når snittet er lavet ved, såvil deltageren i tilfælde af et pointcutforetrækker begge dele. $x>0,2$ $x<0,2$ $x=0.2$

Disse betingelser er meget svage, og i modsætning til andre fair kageskæringsprotokoller kræves det ikke , at hjælpefunktioner er additive eller monotone .

Protokollen tager hensyn til endimensionelle sektioner. For eksempel kan en kage være et endimensionelt segment [0; 1] og hvert stykke er et interval . Kagen kan være rektangulær og udskæringerne laves langs den længere side (parallelt med den korte side), så alle stykker er rektangulære. Hvert snit kan repræsenteres af n tal , hvor er længden af det i -te stykke. Vi antager, at den samlede længde af kagen er 1, så . Rummet af mulige udskæringer er så en dimensionel simpleks med n hjørner i rummet . Protokollen fungerer på denne simpleks som følger: $x_{i},i=1,\dots ,n$ $x_{i}$ $x_{1}+\dots +x_{n}=1$ $(n-1)$ $\mathbb {R} ^{n}$

Vi triangulariserer den afskårne simplex til mindre simplices af den ønskede størrelse.
Vi tildeler et medlem til hvert vertex af triangulariseringen, så hver subsimplex har n forskellige etiketter.
For hvert hjørne af triangulariseringen spørger vi dens ejer: "Hvilket stykke ville du foretrække, hvis snittet blev lavet i henhold til dette punkt?". Vi markerer toppunktet med nummeret på det foretrukne stykke.

Den resulterende markering opfylder kravene i Sperners farvelemma :

Hvert hjørne af den originale simplex svarer til et snit af kagen, hvor et stykke indeholder hele kagen, og alle andre stykker er tomme. Ifølge de "sultne deltagere"-tilstanden for opdelingen skal ejeren af toppunktet foretrække dette stykke, og derfor er alle hjørner i den store simplex forskellige.
Hver side/flade af den originale simplex svarer til et snit af kagen, hvor nogle stykker er tomme, og ikke-tomme stykker svarer til hjørner på siden. Ved betingelsen "sultne medlemmer" må ejerne kun foretrække ikke-tomme stykker, så trianguleringsspidserne på disse sider kan kun have en af etiketterne, der vises ved de tilsvarende spidser.

Derfor skal der ifølge Sperners lemma være mindst ét subsimplex, hvor alle etiketter er forskellige. I trin #2 tildeler vi hvert hjørne af dette subsimplex til et andet medlem. Derfor har vi fundet n meget ens sæt udskæringer, hvor forskellige deltagere foretrækker forskellige stykker af kagen.

Vi kan nu opdele subsimplexet i et gitter af mindre subsimplexes og gentage processen. Vi får en sekvens af mindre og mindre simplices, der konvergerer til et enkelt punkt. Dette punkt svarer til et sæt snit. Ved at antage, at "præferencesæt er lukkede", i dette sæt af snit foretrækker alle deltagere forskellige stykker, så dette snit har ingen misundelse.

Eksistensen af at skære uden misundelse er blevet bevist før [2] , men Simmons' bevis giver en konstruktiv omtrentlig algoritme . Antag for eksempel, at en del jordbeholdning skal deles, og partnerne er enige om, at en forskel på 1 centimeter ikke er signifikant for dem. Derefter kan den originale simplex trianguleres til simplices med sidestørrelser mindre end 1 cm. I dette tilfælde svarer et punkt i enhver subsimplex med alle forskellige etiketter til et (omtrentligt) misundelsesfrit snit.

I modsætning til andre misundelige delingsprotokoller, hvor hver deltager kan få en enorm mængde krummer, giver Simmons-protokollen hver deltager en tilsluttet brik. Desuden, hvis den originale kage er rektangulær, vil alle udvalgte stykker være rektangulære.

Et par år efter offentliggørelsen af algoritmen blev det bevist, at enhver udskæring uden misundelse med forbundne stykker ikke kan findes ved endelige protokoller [3] . Derfor er tilnærmelsesalgoritmen den bedste, vi kan håbe på at opnå på begrænset tid. I øjeblikket er Simmons' algoritme den eneste algoritme til at tilnærme en misundelig kageskæring med forbundne stykker.

Simmons' algoritme er en af de få fair divisionsalgoritmer, der er implementeret og tilgængelig online [4] .

En god ting ved algoritmen er, at forespørgslerne fra deltagerne er meget enkle - de skal bare beslutte for hver opdeling, hvilket stykke de foretrækker. Dette er forskelligt fra andre algoritmer, der stiller forespørgsler såsom "klip et stykke med en værdi på 1/3" eller lignende forespørgsler.

Beregningsmæssig kompleksitet

Mens den jaloux opdeling med forbundne brikker kan tilnærmes til enhver præcision ved hjælp af ovenstående protokol, kan selve tilnærmelsen tage lang tid. Især [5]

Hvis hjælpefunktionerne kun er tilgængelige ved hjælp af et orakel (prædiktor), er antallet af anmodninger om at opnå misundelsesgrænsen mindre end . $\varepsilon$ $\Theta ({\frac {1}{\varepsilon ^{n))})$
Hvis hjælpefunktionerne er givet eksplicit af en polynomiel-tidsalgoritme, har det misundelige kageskæringsproblem den samme kompleksitet som at finde Brouwer fikspunkt , det vil sige, at problemet er PPAD-komplet .

Harmonisk leje

I dette problem beslutter n venner at leje et hus med n soveværelser til en leje bestemt af ejeren af huset. Hver af vennerne kan have forskellige præferencer – én foretrækker måske et stort værelse, en anden foretrækker måske et værelse med udsigt til naturen, og så videre. Følgende to opgaver skal løses samtidigt: (a) tildele et soveværelse til hver deltager, (b) bestemme det honorar, som hver deltager skal betale, således at beløbet for betalte bidrag svarer til det fulde lejebeløb. Tildelingen må ikke have misundelse , dvs. hver deltager skal (i løs forstand) foretrække sit eget værelse + honorar frem for andre deltagere. Det vil sige, at ingen af deltagerne bør foretrække et andet værelse mod et gebyr, der er tildelt det pågældende lokale. Protokollen til at løse dette problem blev udviklet af Francis Su i 1999 [1] .

Ideen er følgende. Normaliser den samlede leje til 1. Så er hver betalingsfordelingsordning et punkt i det -dimensionelle simpleks med hjørner ved . Su-protokollen kører på den dobbelte version af denne simplex ligesom Simmons-Su-kageskæringsprotokollerne - for ethvert hjørne af triangulariseringen af det dobbelte simpleks, der svarer til en bestemt betalingsfordelingsordning, spørger protokollen ejeren "hvilket rum gør du foretrækker i denne betalingsordning?". Dette fører til en Sperner-farvning i dual simplex, og så er der et lille subsimplex, der svarer til en omtrentlig fordeling af værelser og gebyrer uden misundelse. $(n-1)$ $n$ $\mathbb {R} ^{n}$

Papirerne af Sun [6] og Procaccia [7] giver en populær forklaring af Harmonious Renting-protokollen [8] , og side [9] giver en online implementering af protokollen.

Se artiklen Problemet med at dele en lejlighed for andre løsninger på dette problem.

Opdeling af rutinearbejde

I denne opgave er der nogle rutineopgaver, som bør fordeles på n deltagere, for eksempel klipning af en stor græsplæne (plæne).

"Harmonisk leje"-protokollen kan bruges til at opnå en fordeling af rutineopgaver uden misundelse, blot ved at behandle husleje som en opgave og ignorere lokalerne. Delbarhed af rutinearbejde kan opnås ved at dividere den tid brugt på arbejde [1] .

Skæring af flere kager

I denne opgave skal to eller flere kager deles samtidigt mellem to eller flere deltagere, hvilket giver hver deltager et enkelt stykke fra hver kage. Selvfølgelig, hvis præferencerne er uafhængige (det vil sige, at værktøjet fra skæring er lig med summen af forsyningerne af de valgte stykker fra hver kage), så kan problemet løses ved metoder til at skære en kage - vi udfører bare en misundelig opdeling af hver kage for sig. Spørgsmålet bliver mere interessant, når deltagerne har relaterede kagepræferencer, når den del af en kage, en deltager foretrækker, har indflydelse på evalueringen af et stykke af en anden kage givet til en deltager. For eksempel, hvis "kagerne" er arbejdsskift på to sammenhængende dage, foretrækker en medarbejder typisk det samme skift hver dag (f.eks. morgen+morgen eller aften+aften) frem for to forskellige vagter (f.eks. aften+morgen) ).

Løsningen på dette problem for tilfældet med 2 deledeltagere og 2 eller 3 kager blev offentliggjort i 2009 [10] . Hvis antallet af kager er m , og hver kage er delelig i k stykker, så kan det udskårne rum repræsenteres som et d - dimensionelt polyeder med n hjørner, hvor og . En generalisering af Sperners lemma til polytoper [11] garanterer, at hvis denne polytop er triangulariseret og mærket på passende måde, er der i det mindste fuldt mærkede subsimplexer. Hver af disse simplices svarer til en (omtrentlig) misundelsesfri distribution, hvor hver deltager får en forskellig kombination af bidder. Kombinationerne kan dog overlappe hinanden - den ene deltager kan modtage "morgen" og "aften" vagterne, mens den anden får "aften" og "morgen" vagterne. Selvom dette er et andet valg, er det ikke kompatibelt. Afsnit 4 i papiret af Cloutier, Nyman og Su [10] beviser, at division uden misundelse med to med usammenhængende stykker kan være umuligt, hvis , men altid muligt, hvis og (det vil sige, mindst en kage er opdelt i tre dele og hver deltager modtager et stykke fra hver kage, og mindst et stykke kage kasseres). Lignende resultater blev bevist for tre kager. $d=m(k-1)$ ${\displaystyle n=k^{m))$ $nd$ $m=k=2$ $m=2$ $k=3$

Se også

Topologisk kombinatorik

Noter

↑ 1 2 3 Su, 1999 , s. 930-942.
↑ Stromquist, 1980 , s. 640-644.
↑ Stromquist, 2008 .
↑ En implementering af Francis Su, Elisha Peterson og Patrick Winograd er tilgængelig på: https://www.math.hmc.edu/~su/fairdivision/ Arkiveret 27. oktober 2018 på Wayback Machine
↑ Deng, Qi, Saberi, 2012 , s. 1461.
↑ Albert Sun. Start med en trekant for at dele lejen . NY Times . Hentet 26. august 2014. Arkiveret fra originalen 11. november 2020. (ubestemt)
↑ Ariel Procaccia. Retfærdig opdeling og de klynkende filosoffers problem . Turings usynlige hånd . Hentet 26. august 2014. Arkiveret fra originalen 3. september 2014. (ubestemt)
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 31. december 2019. Arkiveret fra originalen 27. oktober 2018. (ubestemt)
↑ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Arkiveret 31. december 2019 på Wayback Machine Divide Your Rent Fairly
↑ 1 2 Cloutier, Nyman, Su, 2010 , s. 26-37.
↑ De Loera, Peterson, Su, 2002 , s. 1-26.

Litteratur

Su FE Rental Harmony: Sperners Lemma i Fair Division // The American Mathematical Monthly. - 1999. - T. 106 , udg. 10 . - doi : 10.2307/2589747 . — .
Cloutier J., Nyman KL, Su FE To-spiller misundelsesfri multi-cake division // Matematisk Samfundsvidenskab. - 2010. - T. 59 . - doi : 10.1016/j.mathsocsci.2009.09.002 . - arXiv : 0909.0301 .
De Loera JA, Peterson E., Su FE En polytopal generalisering af Sperners Lemma // Journal of Combinatorial Theory, Series A. - 2002. - V. 100 . - doi : 10.1006/jcta.2002.3274 .
Walter Stromquist. Sådan skærer du en kage retfærdigt // The American Mathematical Monthly. - 1980. - T. 87 , no. 8 . - doi : 10.2307/2320951 . — .
Walter Stromquist. Misundelsesfrie kageopdelinger kan ikke findes af endelige protokoller // Electronic Journal of Combinatorics (januar 2008) Nøgle: Stromquist2008Envyfree. - 2008. Arkiveret 11. marts 2016.
Deng X., Qi Q., Saberi A. Algoritmiske løsninger til misundelsesfri kageskæring // Operations Research. - 2012. - T. 60 , no. 6 . doi : 10.1287 / opre.1120.1116 .