Simmons Protocols - Su

Simmons-Su- protokollen är en uppsättning protokoll för avundsjuk uppdelning. Protokollen bygger på Sperners lemma . Fördelarna med dessa protokoll är att de sätter få restriktioner på deltagarnas preferenser och ställer enkla frågor till deltagarna i divisionen, som "vilken bit föredrar du?".

Protokoll har utvecklats för att lösa flera relaterade problem.

Tårtskärning

I det avundsjuka kakskärningsproblemet bör en heterogen delbar resurs ("kaka") delas upp i n deltagare med olika preferenser i delar av kakan. Tårtan bör delas i n bitar så att (a) varje deltagare får en enda sammankopplad bit och (b) varje deltagare anser att hans bit är (i svag mening) bättre än alla andra bitar. Problemlösningsprotokollet utvecklades av Forest Simmons 1980 med hjälp av Michael Starbird. Protokollet publicerades första gången av Francis Su 1999 [1] .

Med tanke på ett snitt av kakan (i n bitar) säger vi att deltagaren föredrar en viss bit av det snittet om han anser att denna bit är bättre än alla andra bitar. "I svag bemärkelse" betyder att den tävlande inte får skilja mellan den mottagna pjäsen och en eller flera andra pjäser, så att han kan "föredra" mer än en pjäs.

Protokollet gör följande antaganden om preferenser för deltagarna i divisionen

  1. Oberoende från andra deltagare - preferenser beror på deltagaren och den specifika skärningen av hela kakan, men inte på valet som gjorts av andra deltagare.
  2. Hungriga deltagare - En deltagare föredrar aldrig en tom pjäs.
  3. Topologiskt slutna preferensuppsättningar - varje del som föredras under en konvergent klippsekvens kommer att föredras som gränsen för sekvensen. Till exempel, om den tävlande föredrar den första biten i alla snitt när det första snittet gjordes vid en punktoch föredrar den andra biten i alla snitt när snittet görs vid, då i fallet med ett punktsnitt,kommer den tävlande lika föredrar båda delarna.

Dessa förhållanden är mycket svaga och, till skillnad från andra rättvisa kakskärningsprotokoll , krävs det inte att verktygsfunktioner är additiva eller monotona .

Protokollet tar hänsyn till endimensionella sektioner. Till exempel kan en kaka vara ett endimensionellt segment [0; 1] och varje bit är ett intervall . Kakan kan vara rektangulär och snitten görs längs den längre sidan (parallellt med den kortare sidan) så att alla bitar blir rektangulära. Varje snitt kan representeras av n siffror , där är längden på den i -te biten. Vi antar att tårtans totala längd är 1, så . Utrymmet för möjliga skärningar är då en dimensionell simplex med n hörn i rymden . Protokollet fungerar på detta simplex enligt följande:

  1. Vi triangulariserar den skurna simplexen till mindre förenklingar av önskad storlek.
  2. Vi tilldelar en medlem till varje vertex av triangulariseringen så att varje subsimplex har n olika etiketter.
  3. För varje vertex av triangulariseringen frågar vi dess ägare: "Vilken bit skulle du föredra om snittet gjordes enligt denna punkt?". Vi markerar spetsen med numret på den föredragna biten.

Den resulterande markeringen uppfyller kraven för Sperners färglemma :

Därför, enligt Sperners lemma, måste det finnas minst ett subsimplex där alla etiketter är distinkta. I steg #2 tilldelar vi varje vertex i detta subsimplex till en annan medlem. Därför har vi hittat n väldigt lika uppsättningar av snitt där olika deltagare föredrar olika delar av kakan.

Vi kan nu dela upp subsimplexet i ett rutnät av mindre subsimplex och upprepa processen. Vi får en sekvens av mindre och mindre förenklingar som konvergerar till en enda punkt. Denna punkt motsvarar en uppsättning snitt. Genom antagandet att "preferensuppsättningar är stängda", i denna uppsättning av snitt föredrar alla deltagare olika bitar, så detta snitt har ingen avund.

Förekomsten av skärning utan avund har bevisats tidigare [2] , men Simmons bevis ger en konstruktiv ungefärlig algoritm . Anta till exempel att en del markinnehav måste delas och partnerna är överens om att en skillnad på 1 centimeter inte är signifikant för dem. Sedan kan den ursprungliga simplexen trianguleras till simplicerar med sidostorlekar mindre än 1 cm.I detta fall motsvarar en punkt i valfri subsimplex med alla olika etiketter ett (ungefärligt) avundsfritt snitt.

Till skillnad från andra avundsjuka delningsprotokoll, där varje deltagare kan få en enorm mängd smulor, ger Simmons-protokollet varje deltagare en ansluten del. Dessutom, om den ursprungliga kakan är rektangulär, kommer alla utvalda bitar att vara rektangulära.

Några år efter publiceringen av algoritmen bevisades det att någon skärning utan avund med sammankopplade bitar inte kan hittas av finita protokoll [3] . Därför är approximationsalgoritmen det bästa vi kan hoppas på att uppnå på ändlig tid. För närvarande är Simmons algoritm den enda algoritmen för att approximera en avundsjuk kakskärning med sammankopplade bitar.

Simmons algoritm är en av de få rättvisa divisionsalgoritmerna som är implementerade och tillgängliga online [4] .

En trevlig sak med algoritmen är att frågorna från deltagarna är väldigt enkla - de måste bara bestämma för varje delning vilken bit de föredrar. Detta skiljer sig från andra algoritmer som ställer frågor som "klipp ut en bit med ett värde på 1/3" eller liknande frågor.

Beräkningskomplexitet

Även om den svartsjuka divisionen med anslutna bitar kan approximeras till vilken precision som helst med hjälp av ovanstående protokoll, kan själva approximationen ta lång tid. I synnerhet [5]

Harmonisk hyra

I det här problemet bestämmer sig n vänner för att hyra ett hus med n sovrum för en hyra som bestäms av husets ägare. Var och en av vännerna kan ha olika preferenser – en kanske föredrar ett stort rum, en annan kanske föredrar ett rum med utsikt över naturen och så vidare. Följande två uppgifter måste lösas samtidigt: (a) tilldela ett sovrum till varje deltagare, (b) bestämma den avgift som varje deltagare ska betala, så att beloppet av inbetalda bidrag motsvarar hela hyran. Tilldelningen får inte ha avund , d.v.s. varje deltagare måste (i lös mening) föredra sitt eget rum + avgift framför andra deltagare. Det vill säga att ingen av deltagarna ska föredra ett annat rum mot en avgift som tilldelas det rummet. Protokollet för att lösa detta problem utvecklades av Francis Su 1999 [1] .

Tanken är följande. Normalisera den totala hyran till 1. Sedan är varje betalningsfördelningsschema en punkt i det -dimensionella simplexet med hörn vid . Su-protokollet körs på den dubbla versionen av denna simplex som Simmons-Su-katskärningsprotokollen - för varje vertex av triangulariseringen av det dubbla simplexet som motsvarar ett visst betalningsfördelningssystem frågar protokollet ägaren "vilket rum vill du föredra i detta betalningssystem?". Detta leder till en Sperner-färgning i den dubbla simplexen, och sedan finns det ett litet subsimplex som motsvarar en ungefärlig fördelning av rum och avgifter utan avund.

Tidningarna av Sun [6] och Procaccia [7] ger en populär förklaring av Harmonious Renting-protokollet [8] , och sidan [9] ger en online-implementering av protokollet.

Se artikeln Problemet med att dela lägenhet för andra lösningar på detta problem.

Uppdelning av rutinarbete

I detta problem finns det några rutinuppgifter som bör fördelas på n deltagare, till exempel att klippa en stor gräsmatta (gräsmatta).

Protokollet "Harmonious Renting" kan användas för att få en fördelning av rutinjobb utan avundsjuka, helt enkelt genom att behandla hyran som en syssla och ignorera lokalerna. Delbarhet av rutinarbete kan uppnås genom att dividera tiden som läggs på arbete [1] .

Skär flera kakor

I det här problemet ska två eller flera kakor delas samtidigt mellan två eller flera deltagare, vilket ger varje deltagare en enskild bit från varje tårta. Naturligtvis, om preferenserna är oberoende (det vill säga nyttan från skärning är lika med summan av verktygen för de utvalda bitarna från varje kaka), kan problemet lösas med metoder för att skära en kaka - vi utför bara en avundsjuk uppdelning av varje tårta för sig. Frågan blir mer intressant när deltagarna har relaterade tårtpreferenser, när den del av en tårta som en deltagare föredrar har en inverkan på utvärderingen av en del av en annan tårta som ges till en deltagare. Till exempel, om "kakorna" är arbetsskift på två angränsande dagar, kan vanligtvis en anställd föredra samma skift varje dag (till exempel morgon+morgon eller kväll+kväll) snarare än två olika skift (till exempel kväll+morgon ).

Lösningen på detta problem för fallet med 2 deltagare och 2 eller 3 kakor publicerades 2009 [10] . Om antalet kakor är m och varje kaka är delbar i k bitar, kan det skurna utrymmet representeras som en d - dimensionell polyeder med n hörn, där och . En generalisering av Sperners lemma till polytoper [11] garanterar att om denna polytop triangulariseras och märks på lämpligt sätt, finns det åtminstone helt märkta subsimplexer. Var och en av dessa förenklingar motsvarar en (ungefärlig) avundsfri distribution där varje deltagare får en annan kombination av bitar. Kombinationerna kan dock överlappa varandra - en deltagare kan få "morgon" och "kväll" skift, medan den andra kommer att få "kväll" och "morgon" skift. Även om detta är ett annat val, är det inte kompatibelt. Avsnitt 4 i tidningen av Cloutier, Nyman och Su [10] bevisar att division utan avund med två med osammanhängande bitar kan vara omöjligt om , men alltid möjligt om och (det vill säga minst en tårta är uppdelad i tre delar och varje deltagaren får en bit från varje tårta, och minst en tårtbit kasseras). Liknande resultat visades för tre kakor.

Se även

Anteckningar

  1. ↑ 1 2 3 sö, 1999 , sid. 930–942.
  2. ↑ Stromquist, 1980 , sid. 640–644.
  3. ↑ Stromquist, 2008 .
  4. ↑ En implementering av Francis Su, Elisha Peterson och Patrick Winograd finns tillgänglig på: https://www.math.hmc.edu/~su/fairdivision/ Arkiverad 27 oktober 2018 på Wayback Machine
  5. ↑ Deng, Qi, Saberi, 2012 , sid. 1461.
  6. ↑ Albert Sun. För att dela hyran, börja med en triangel . NY Times . Hämtad 26 augusti 2014. Arkiverad från originalet 11 november 2020.
  7. ↑ Ariel Procaccia. Rättvis splittring och gnällfilosofernas problem . Turings osynliga hand . Hämtad 26 augusti 2014. Arkiverad från originalet 3 september 2014.
  8. ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 31 december 2019. Arkiverad från originalet 27 oktober 2018. 
  9. ↑ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Arkiverad 31 december 2019 på Wayback Machine Divide Your Rent Fairly
  10. ↑ 1 2 Cloutier, Nyman, Su, 2010 , sid. 26–37.
  11. ↑ De Loera, Peterson, Su, 2002 , sid. 1–26.

Litteratur