Fair Cake Cutting Challenge

Den retfærdige udskæring af kagen er en slags retfærdig opdelingsproblem . Problemet involverer en heterogen ressource, såsom en kage med forskellige dekorationer (fra fløde , bær, chokolade ), som antages at være delelig - det vil sige, at et vilkårligt lille stykke kan skæres fra det uden at ødelægge den fulde værdi. Ressourcen skal deles mellem flere partnere, som har forskellige præferencer for forskellige dele af kagen. Nogle foretrækker for eksempel chokoladepynt, andre foretrækker kirsebær, mens andre bare vil have et større stykke. Opdelingen skal være subjektivt retfærdig, hver deltager skal modtage et stykke, som han/hun betragter som en rimelig andel.

Udtrykket "kage" er kun en metafor , kageskæringsprocedurer kan bruges til at adskille forskellige slags ressourcer, såsom jordejerskab , reklameplads eller sendetid.

Kageskæringsproblemet blev foreslået af Hugo Steinhaus efter Anden Verdenskrig [1] og er forblevet et genstand for intense studier i matematik , datalogi , økonomi og statskundskab [2] .

Antagelser

Der er en kage , som normalt antages at være et endeligt endimensionelt segment, en todimensionel polygon eller en endelig delmængde af et højeredimensionelt euklidisk rum . $C$ $\mathbb{R}^d$

Der er en person med lige rettigheder til [3] . $n$ $C$

$C$ skal skæres i sådanne usammenhængende undergrupper , at hver deltager vil modtage et separat undersæt. Det stykke, der er beregnet til deltageren , er betegnet som , og . $n$ $jeg$ $X_{i}$ ${\displaystyle C=X_{1}\sqcup \cdots \sqcup X_{n))$

Hver deltager skal modtage et stykke med en "fair" værdi. Retfærdighed bestemmes ud fra subjektive værdifunktioner . Hvert ansigt har en subjektiv værdifunktion, der kortlægger delmængder til tal. $jeg$ $V_i$ $C$

Funktionerne antages at være absolut kontinuerlige i længde, areal eller (generelt) Lebesgue-målet [4] . Det betyder, at der ikke er nogen "atomer", det vil sige entalspunkter, der tildeles en positiv værdi af en eller flere agenter. Således er alle dele af kagen delbare.

I nogle tilfælde antages evalueringsfunktionerne også at være sigma-additive .

Et eksempel på en kage

Vi vil bruge følgende kage som illustration:

Kagen består af to dele - chokolade og vanilje.
Der er to deltagere - Alice og George.
Alice vurderer chokoladeportionen til 9 enheder og vaniljeportionen til 1 enhed.
George vurderer chokoladeportionen til 6 enheder og vaniljeportionen til 4.

Krav om retfærdighed

Det oprindelige og mest generelle retfærdighedskriterium er proportionalitet (PR, engelsk proportionality , PR). I den forholdsmæssige opdeling af kagen modtager hver deltager et stykke, hvis værdi han vurderer mindst i den samlede værdi af hele kagen. I eksemplet ovenfor kan en proportional opdeling opnås ved at give hele vaniljeportionen og 4/9 af chokoladeportionen til George (med en samlet score på 6,66), og de resterende 5/9 af chokoladeportionen gives til Alice (med en samlet score på 5). Symbolsk: $1/n$

\forall {i}:\ V_{i}(X_{i})\geqslant 1/n

Proportionalitetskriteriet kan generaliseres til situationer, hvor menneskers rettigheder ikke er lige. For eksempel, når man forholdsmæssigt deler en kage med forskellige andele , tilhører kagen aktionærerne, så en af dem ejer 20 % og den anden 80 % af kagen. Dette fører til et kriterium om vægtet proportionalitet :

\forall i:V_{i}(X_{i})\geqslant w_{i}

hvor w i er vægte, hvis sum er 1.

Et andet typisk kriterium er fraværet af misundelse (OZ, engelsk envy-freeness , EF). Med en misundelig opdeling [5] modtager hver person en brik, hvis værdi ifølge denne person ikke er mindre end værdien af de andre brikker. Formelt sprog:

\forall i,j:\ V_{i}(X_{i})\geqslant V_{i}(X_{j})

I nogle tilfælde er der et implikationsforhold (konsekvens) mellem proportionalitet og misundelsesfrihed, hvilket afspejles i følgende tabel:

Agenter	Bedømmelser	fra OZ følger PR?	fra PR følger OZ?
2	tilsætningsstof	Ja	Ja
2	generel	Ikke	Ja
3+	tilsætningsstof	Ja	Ikke
3+	generel	Ikke	Ikke

Det tredje, mindre brugte kriterium er upartiskhed ( engelsk equitability , EQ). I en uvildig division spiser hver person et stykke med nøjagtig den samme evalueringsværdi. I kageeksemplet kan en upartisk udskæring opnås ved at give hver deltager halvdelen af chokoladen og halvdelen af vaniljestykkerne, så hver deltager får en værdi på 5. Symbolsk:

\forall i,j:\ V_{i}(X_{i})=V_{j}(X_{j})

Det fjerde kriterium er nøjagtighed . Hvis andelen af hver partner i er lig med w i , så er en nøjagtig division en division, hvor:

\forall {i,j}:\ V_{i}(X_{j})=w_{j}

Hvis alle vægte er ens (1/ n ), så kaldes snittet perfekt og

\forall i,j:\ V_{i}(X_{j})=1/n

Geometriske krav

I nogle tilfælde skal de stykker, der er beregnet til deltagerne, opfylde nogle geometriske begrænsninger ud over retfærdighed.

Den mest almindelige begrænsning er tilslutning . I tilfælde af en endimensionel kage udmønter dette krav sig til et krav om, at stykkerne skal være intervaller. I det tilfælde, hvor kagen er en endimensionel cirkel ("tærte"), udmønter dette sig i kravet om, at hvert stykke skal være en bue. Se artiklen " Problemet med retfærdig udskæring af kagen ".
En anden begrænsning er naboskab . Denne begrænsning gælder i det tilfælde, hvor "kagen" er et omstridt område, der skal opdeles mellem grænselande. I dette tilfælde kan det kræves, at de brikker, der gives til landet, grænser op til landets nuværende territorium. Denne begrænsning håndteres af Hill-Beck-landdelingsproblemet .
Når man deler land, er der ofte todimensionelle begrænsninger, såsom at hver brik er en firkant eller (mere generelt) en fed genstand [6] [7] .

Yderligere krav

I retspraksis overvejes omkostningseffektiviteten ved opdeling ofte. Se artiklen " Effektiv kageskæring ".

Ud over de ønskelige egenskaber ved endelige snit er der også ønskelige egenskaber ved delingsprocessen. En sådan egenskab er sandfærdighed (også kendt som stimuluskompatibilitet ), som kan være på to niveauer.

Svag sandfærdighed betyder, at hvis en partner afslører sin sande værdi for algoritmen, er han garanteret at få en rimelig andel (for eksempel værdierne af hele kagen i tilfælde af proportional opdeling), uanset hvad de andre partnere gør . Selvom alle de andre partnere danner en koalition for at påføre ham maksimal skade, vil han stadig modtage sin garanterede andel. De fleste kageskæringsalgoritmer er sande i denne forstand [1] . $1/n$
Stærk sandfærdighed betyder, at ingen af partnerne kan opnå en fordel ved at lyve. Det vil sige, at sandfærdig adfærd er den dominerende strategi . De fleste kage-skæringsprotokoller er ikke strengt sandfærdige. At bygge en strengt sandfærdig divisionsprotokol er en vanskelig opgave [8] .

Resultater

2 personer - en proportional og misundelsesfri opdeling

For mennesker eksisterer OD-delingen altid og kan findes ved hjælp af opdel-og-vælg- protokollen . Hvis evalueringsfunktionerne er additive, vil dette snit også være PR, ellers er proportionalitet ikke garanteret. $n=2$

Proportional inddeling

For n personer med additive scores er der altid en proportional nedskæring. Mest brugte protokoller:

Last-Minimum Procedure , en protokol, der kan sikre, at chunks er forbundet (dvs. ingen deltager får to eller flere separate chunks). Især hvis kagen er et endimensionelt interval, vil hver deltager modtage et interval. Protokollen er diskret og kan udføres i omgange. Det kræver handling. $n$ $O(n^{2})$
Dubins-Spenier Moving Knife proceduren er en tidskontinuerlig version af Last Decreasing-protokollen [9] .
Fink-protokollen (også kendt som konsekutive par eller enkeltvælger ) er en diskret protokol, der kan bruges til at klippe online - hvis det proportionale snit for partnere er kendt, når en ny partner kommer ind i spillet, ændrer protokollen det eksisterende snit, så den indkommende deltager og allerede deltagere i delingen modtager . Ulempen ved protokollen er, at hver partner modtager et stort antal individuelle stykker. $n-1$ $1/n$
Even-Paz-protokollen , baseret på kontinuerlig opdeling af en kage og en gruppe af midler, og som kræver allehandlinger. Dette er den hurtigst mulige deterministiske protokol for proportional division, og den hurtigst mulige protokol for proportional division, som garanterer, at alle brikker er forbundet. $O(n\log n)$
Edmonds-Prus- protokollen er en randomiseret protokol, der kræver alle handlinger, men som kun garanterer delvist proportional klipning (hver deltager får mindst , hvor er en konstant), og kan give hver deltager et sæt krummer i stedet for et sammenhængende stykke. $På)$ $1/an$ $-en$
Beck landdelingsprotokollen kan give en proportional opdeling af det omstridte territorium mellem flere nabolande. I dette tilfælde modtager hvert land en andel, der både er forbundet og grænser op til landets nuværende territorium.
Woodalls superproportionale divisionsprotokol giver en division, hvor hver deltager modtager strengt taget mere end , givet at mindst to deltagere har forskellige meninger om værdien af mindst et stykke. $1/n$

Se artiklen " Proportional opdeling af en kage med forskellige proportioner " for detaljer og en komplet bibliografi.

Ovenstående algoritmer fokuserer hovedsageligt på agenter med en lige stor andel af ressourcekravene. Du kan dog generalisere dem og få proportional opdeling af kagen med forskellige delinger .

Misundelig division

PO-delingen for en person eksisterer, selvom vurderingerne ikke er additive, så længe de er repræsenteret af konsistente præferencesæt. OD-inddelingen blev undersøgt separat for det tilfælde, hvor stykkerne skal forbindes, og for det tilfælde, hvor stykkerne kan bestå af separate adskilte dele. $n$

For tilsluttede stykker er de vigtigste resultater:

Stromquists "Moving Knife"-procedure producerer en misundelsesfri opdeling for 3 personer ved at tildele hver af dem en kniv og bede dem bevæge deres knive løbende over kagen i henhold til den foreskrevne procedure.
Simmons -protokollen kan give en misundelsesfri udskæringstilnærmelse for mennesker med vilkårlig præcision. Hvis evalueringsfunktionerne er additive, vil opdelingen også være proportional. Ellers forbliver opdelingen fri for misundelse, men ikke nødvendigvis proportional. Algoritmen giver en hurtig og praktisk måde at løse nogle retfærdige divisionsproblemer [10] [11] . $n$

Begge disse algoritmer er uendelige: den første er kontinuerlig, mens den anden kan tage uendelig lang tid at konvergere. Faktisk kan misundelsesfrie snit i forbundne intervaller for 3 eller flere personer ikke findes af nogen endelig protokol.

For (muligvis) afbrudte bidder er hovedresultaterne:

Den diskrete Selfridge-Conway-procedure giver et misundelsesfrit snit til tre deltagere i højst 5 snit.
Brahms-Taylor-Zwicker "Moving Knife"-proceduren giver et misundelsesfrit snit til fire deltagere i højst 11 snit.
En variant af " Last Reducer " -protokollen med genbrug finder en additiv tilnærmelse til skæring uden misundelse på en begrænset tid. Specifikt for enhver konstant giver protokollen et udsnit, hvor værdien for hvert medlem er mindst større end den største værdi minus over tid . $\epsilon >0$ $\epsilon$ $O(n^{2}/\epsilon )$
Tre forskellige procedurer, en af Brahms og Taylor (1995) , en anden af Robertson og Webb (1998) og endnu en, Pikurko-proceduren (2000) giver misundelsesfri skæring for mennesker. Begge algoritmer kræver et begrænset, men ubegrænset antal klip. $n$
Aziz og McKenzies (2016) procedure finder misundelsesfri cutting for folk til et begrænset antal forespørgsler. $n$

Det negative resultat i det generelle tilfælde er meget svagere end i tilfælde af forbundethed. Alt, hvad vi ved, er, at enhver misundelsesfri udskæringsalgoritme skal bruge mindst forespørgsler. Der er en stor kløft mellem dette resultat og den beregningsmæssige kompleksitet af kendte procedurer. $\Omega (n^{2})$

Se misundelsesfri kageskæring [ 5 ] for detaljer og en komplet bibliografi .

Effektiv opdeling

Når evalueringsfunktionerne er additive, er der en utility cut ( Utilitarian-maximal , UM) . For at skabe et RP-snit skal vi intuitivt give hver deltager et stykke kage med en værdi, der er maksimal for ham. I RP- kageeksemplet vil udskæring give al chokoladen til Alice og al vaniljen til George, hvilket opnår nytteværdi . $9+4=13$

Denne proces er nem at implementere, hvis evalueringsfunktionerne er stykkevis konstante, det vil sige, at kagen kan opdeles i stykker, således at pristætheden på hvert stykke er konstant for alle deltagere. Når estimatorfunktionerne ikke er stykkevis konstante, er eksistensen af RP-snit baseret på en generalisering af denne procedure for estimatorfunktioner ved hjælp af Radon-Nikodim- sætningen, se sætning 2 i Dubins og Spanier [9] .

Når kagen er endimensionel, og brikkerne skal forbindes (det vil sige kontinuerlige segmenter), virker den simple algoritme til at tildele brikken til den agent, der er mest signifikant, ikke. I dette tilfælde er opgaven med at finde RP af snittet NP-hård, og desuden er intet FPTAS- skema muligt, medmindre P = NP. Der er en 8-fold tilnærmelsesalgoritme og en parameteriseret kompleksitetsalgoritme , der er eksponentiel i antallet af spillere [12] .

For ethvert sæt af positive vægte kan den vægtede RP-partition findes ved lignende metoder. Derfor eksisterer der altid Pareto- effektive ( PE) partitioner .

Procedurel retfærdighed

På det seneste har der ikke kun været interesse for retfærdigheden af den endelige opdeling, men også for retfærdigheden af delingsproceduren – der bør ikke være forskel på forskellige roller i proceduren. Nogle proceduremæssige retfærdighed er blevet undersøgt:

Anonymitet kræver, at hver agent i tilfælde af permutation af agenter og gentagelse af proceduren modtager nøjagtig det samme stykke som i den oprindelige division. Dette er en streng betingelse. I øjeblikket er den anonyme procedure kun kendt for 2 agenter.
Symmetrien kræver, at i det tilfælde, hvor agenterne er permuteret, og proceduren gentages for de permuterede agenter, modtager hver agent samme værdi som i den oprindelige division. Dette er en svagere betingelse end anonymitet. På nuværende tidspunkt er symmetriske og proportionale procedurer kendt for et vilkårligt antal agenter, og de kræver forespørgsler. En symmetrisk og misundelsesfri procedure er kendt for et vilkårligt antal agenter, men kræver meget længere eksekveringstid - det kræver udførelse af den eksisterende misundelsesfri procedure. $O(n^{3})$ $n!$
Aristotelianity kræver, at hvis to agenter har identiske mål for betydning, vil de modtage den samme værdi. Dette er svagere end symmetri og opfyldes af enhver misundelsesfri procedure. Desuden er aristoteliske og proportionelle procedurer kendt for et vilkårligt antal agenter og kræver forespørgsler. $O(n^{3})$

Se artiklen " Symmetrisk Fair Cake Cutting " for detaljer og links.

Effektiv retfærdig opdeling

For n personer med additive værdifunktioner er der altid en EPOS-inddeling [13] .

Hvis kagen er et endimensionelt interval, og hver deltager skal opnå et sammenhængende interval, så gælder følgende generelle resultat: hvis evalueringsfunktionerne er strengt monotone (hver deltager foretrækker stærkt et stykke og ikke nogen af hans egne delmængder), så enhver OZ-afdeling vil også være en EP [14] . Derfor giver Simons-protokollen i dette tilfælde EPOS-opdeling.

Hvis kagen er en endimensionel cirkel (for eksempel et interval, hvor to endepunkter er topologisk identificeret), og hver flade skal modtage en forbundet bue, så er det tidligere resultat ikke korrekt - OD-delingen vil ikke nødvendigvis være en EP. Derudover er der par af (ikke-additive) estimatorfunktioner, for hvilke der ikke findes nogen EPOS-deling. Men hvis der er 2 agenter, og mindst én af dem har en additiv evalueringsfunktion, så eksisterer EPOS-divisionen [15] .

Hvis kagen er endimensionel, men enhver person kan få en diskontinuerlig delmængde af den, vil OD-inddelingen ikke nødvendigvis være EP. I dette tilfælde kræves der mere komplekse algoritmer for at finde divisionens EPOS.

Hvis evalueringsfunktionerne er additive og stykkevis konstante, så er der en algoritme, der finder EPOS-divisionen [16] . Hvis estimatordensitetsfunktionerne er additive og Lipschitz-kontinuerlige , så kan de tilnærmes ved stykkevis konstante funktioner "så tæt på som vi vil", så denne algoritme tilnærmer EPOS-divisionen "så tæt som vi vil" [16] .

OD-divisionen er ikke nødvendigvis RP [17] [18] . En af tilgangene til at håndtere denne vanskelighed er at søge efter opdelingen med den maksimale nytteværdi blandt alle mulige OC'er af OC'er. Dette problem blev undersøgt for en kage, som er et endimensionelt interval, hvorfra hver person kan få diskontinuerlige dele, og evalueringsfunktionerne er additive [19] .

Ikke-additive procedurer

De fleste af de eksisterende procedurer for retfærdig deling, der er skitseret ovenfor, forudsætter additiv nytte for spillerne. Med andre ord, hvis en spiller får noget nytte af 25 g chokoladekage, så antages det, at han vil få præcis den dobbelte nytteværdi fra 50 g af den samme chokoladekage.

I 2013 viste Rishi S. Mirchandani, at de fleste eksisterende fair division algoritmer er inkompatible med ikke-additive hjælpefunktioner [20] . Han beviste også, at det særlige tilfælde med fair division-problemet, hvor spillerne har ikke-additive hjælpefunktioner, ikke kan have proportionale løsninger.

Mirchandani foreslog, at problemet med retfærdig division kunne løses ved hjælp af ikke-lineære optimeringsteknikker. Spørgsmålet er dog stadig, om der er bedre algoritmer til specifikke undersæt af ikke-additive hjælpefunktioner.

Se også

Problemet med retfærdig fordeling af objekter er et lignende problem, hvor opdelingens objekter er udelelige.

Noter

↑ 1 2 Steinhaus, 1948 , s. 101-4.
↑ Procaccia, 2016 .
↑ Menneskerettigheder diskuteres ikke her, opgaven er at dele kagen op, så hver person får en rimelig andel.
↑ Hill, Morrison, 2010 , s. 281.
↑ 1 2 Ofte oversat med "division uden misundelse" (sporerpapir fra engelsk), selvom det er tilstedeværelsen af misundelse, der spiller hovedrollen i denne opdeling.
↑ Altså, så dens længde og bredde er tæt på.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , s. 1-28.
↑ Chen, Lai, Parkes, Procaccia, 2013 , s. 284-297.
↑ 1 2 Dubins, Spanien, 1961 , s. 1-17.
↑ The Fair Division Calculator (downlink) . Hentet 12. oktober 2019. Arkiveret fra originalen 28. februar 2010. (ubestemt)
↑ Ivars Peterson. En fair aftale for husfæller . MathTrek (13. marts 2000). Hentet 12. oktober 2019. Arkiveret fra originalen 20. september 2012. (ubestemt)
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Weller, 1985 , s. 5-17.
↑ Berliant, Thomson, Dunz, 1992 , s. 201.
↑ Thomson, 2006 , s. 501-521.
↑ 1 2 Reijnierse, Potters, 1998 , s. 291-311.
↑ Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, 2011 , s. 589.
↑ Aumann, Dombb, 2010 , s. 26.
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Mirchandani, 2013 , s. 78-91.

Litteratur

Ariel Procaccia. Kapitel 13: Cake Cutting Algorithms // Handbook of Computational Social Choice / Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. - Cambridge University Press, 2016. - ISBN 9781107060432 .
Hugo Steinhaus. Problemet med retfærdig opdeling // Econometrica. - 1948. - T. 16 , Nr. 1 . — .
Hill TP, Morrison KE Cutting Cakes Carefully // The College Mathematics Journal. - 2010. - T. 41 , no. 4 . doi : 10.4169 / 074683410x510272 .
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 .
Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia. Sandhed, retfærdighed og kageskæring // Spil og økonomisk adfærd. - 2013. - T. 77 , no. 1 . - doi : 10.1016/j.geb.2012.10.009 .
Lester Dubins. Sådan skærer du en kage retfærdigt // The American Mathematical Monthly. - 1961. - T. 68 , no. 1 . - doi : 10.2307/2311357 . — .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Databehandling af socialt effektive kagedivisioner . - 2013.
Weller D. Fair opdeling af et målbart rum // Journal of Mathematical Economics. - 1985. - T. 14 . - doi : 10.1016/0304-4068(85)90023-0 .
Berliant M., Thomson W., Dunz K. Om den retfærdige opdeling af en heterogen vare // Journal of Mathematical Economics. - 1992. - T. 21 , no. 3 . - doi : 10.1016/0304-4068(92)90001-n .
Thomson W. Børn, der græder ved fødselsdagsfester. Hvorfor? // Økonomisk teori. - 2006. - T. 31 , no. 3 . - doi : 10.1007/s00199-006-0109-3 .
Reijnierse JH, Potters JAM Om at finde en misundelsesfri Pareto-optimal division // Matematisk programmering. - 1998. - T. 83 , no. 1-3 . - doi : 10.1007/bf02680564 .
Caragiannis I., Kaklamanis C., Kanellopoulos P., Kyropoulou M. The Efficiency of Fair Division // Theory of Computing Systems. - 2011. - T. 50 , no. 4 . - doi : 10.1007/s00224-011-9359-y .
Aumann Y., Dombb Y. The Efficiency of Fair Division with Connected Pieces // Internet- og netværksøkonomi . - 2010. - T. 6484. - (Lecture Notes in Computer Science). — ISBN 978-3-642-17571-8 . - doi : 10.1007/978-3-642-17572-5_3 . Registrering påkrævet for at downloade
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Optimal misundelsesfri kageskæring, konference AAAI . – 2011.
Rishi Mirchandani. Superadditivitet og Subadditivitet i Fair Division // Journal of Mathematics Research. - 2013. - August ( bind 5 , hæfte 3 ). doi : 10.5539 / jmr.v5n3p78 .