Fair opdeling

En retfærdig deling er opgaven med at fordele mange ressourcer mellem flere personer, der gør krav på andele af disse ressourcer, mens hver person får den del, der passer ham i en eller anden grad. Den centrale bestemmelse i en retfærdig opdeling er kravet om, at den skal udføres af deltagerne i processen selv.

Rededelingsproblemet opstår i forskellige situationer, som f.eks. deling af en arv . Det er et aktivt forskningsområde inden for matematik , økonomi (især i socialvalgsteori ), spilteori , kontroversielle spørgsmål og mange andre.

En typisk retfærdig divisionsalgoritme er del og vælg . Det viser, at to personer med forskellig smag kan dele en kage på en sådan måde, at hver af dem mener, at han fik det bedste stykke. Fair divisionsundersøgelsen kan ses som en udvidelse af denne procedure til forskellige mere komplekse forhold.

Der er mange forskellige slags retfærdige divisionsproblemer og algoritmer, afhængigt af udbyttets art, retfærdighedskriterierne, deltagernes karakter og deres præferencer og andre nødvendige egenskaber for divisionsalgoritmen.

Ting at dele

Formelt defineres fair divisionsproblemet af et sæt og en gruppe af spillere. Division er opdelingen af et sæt i ikke-overlappende delmængder: 1 delmængde pr. spiller. $x$ $n$ $x$ $n$ ${\displaystyle X=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n))$

Sættet kan være af forskellige typer: $x$

X kan være et endeligt sæt af udelelige objekter, for eksempel: X = {klaver, bil, lejlighed}, så hvert objekt skal gives til en anden deltager.
X kan være en uendelig mængde repræsenteret af delbare ressourcer , såsom penge eller kage. Matematisk modelleres en delbar ressource ofte som en delmængde af det reelle rum, for eksempel kan segmentet [0,1] repræsentere en lang, smal kage, der kan skæres i stykker af parallelle sektioner. Enhedscirklen kan repræsentere en æblekage.

Sættet, der skal opdeles, kunne også være:

homogen - såsom penge, hvor kun værdien eller mængden betyder noget;
heterogen - såsom en kage, som kan indeholde forskellige ingredienser, forskellige glasurer, cremer, frugter osv.

Endelig er det normalt nødvendigt at gøre nogle antagelser om ønskeligheden af delelige objekter - hvilken af grupperne de tilhører:

varer , såsom biler eller kage;
ubehagelige ting , såsom huslige pligter.

Baseret på disse forskelle er flere generelle typer af retfærdige divisionsproblemer blevet undersøgt:

retfærdig fordeling af genstande - opdelingen af mange udelelige og heterogene genstande;
retfærdig fordeling af ressourcer - opdelingen af mange delelige og homogene goder. Et særligt tilfælde er den retfærdige opdeling af én homogen ressource ;
en retfærdig opdeling af kagen er opdelingen af et deleligt heterogent gode . Et særligt tilfælde er kagens runde form, i hvilket tilfælde problemet kaldes en retfærdig deling af tærten ;
en retfærdig fordeling af opgaver er opdelingen af delbare heterogene ubehagelige ting.

Kombinationer og særlige tilfælde overvejes normalt også:

problemet med at leje en lejlighed i fællesskab - opdelingen af et sæt udelelige heterogene varer (for eksempel et værelse i en lejlighed) og på samme tid homogene delbare ubehagelige ting (betaling for en lejlighed);
retfærdig brug af floden - opdelingen af vand, der flyder i floder langs landegrænserne;
fair random assignment — en tilfældig tildelingsalgoritme, der i gennemsnit giver et rimeligt resultat, især velegnet til at distribuere udelelige varer.

Definitioner af retfærdighed

Det meste af det, der almindeligvis omtales som en retfærdig opdeling, er udeladt af teorien, da arbitrage bruges . Disse situationer opstår ofte med matematiske teorier, der har navnene på problemer i det virkelige liv. Beslutningerne i Talmud om aktier , når ejendom går konkurs afspejler nogle komplekse ideer om retfærdighed [1] , og de fleste mennesker anser disse beslutninger for at være retfærdige. De er dog resultatet af rabbinernes diskussioner og ikke en opdeling efter vurderinger fra deltagerne i ejendomsstriden.

Ifølge den subjektive værditeori kan der ikke være noget objektivt mål for værdien af hvert objekt. Objektiv retfærdighed er da umulig, da forskellige personer opkræver forskellige priser for hver genstand. Empiriske eksperimenter med, hvordan mennesker definerer begrebet retfærdighed [2] har ført til inkonsistente resultater.

Således fokuserer det meste af nutidig forskning om lighed på begrebet subjektiv retfærdighed . Det antages, at hver af personerne har en personlig subjektiv nyttefunktion eller signifikansfunktion , som tildeler en numerisk værdi til hver delmængde . Ofte antages funktionerne at være normaliserede, således at værdierne for hver person er 0 for det tomme sæt ( for alle i), og 1 for sættet af alle elementer ( for alle i), hvis elementerne er ønskelige, og −1 hvis elementerne er uønskede. Eksempler: $n$ $V_i$ $x$ $V_{i}(\emptyset )=0$ $V_{i}(X)=1$

Hvis er et sæt udelelige genstande {klaver, bil, lejlighed}, så kan Alice tildele en værdi på 1/3 til hver genstand, hvilket betyder, at hver genstand er lige meget værdifuld for hende. Bob kan tildele værdien 1 til sættet {bil, lejlighed} og værdien 0 til alle andre sæt undtagen X. Det betyder, at han vil have bilen og lejligheden sammen. En bil eller lejlighed, såvel som disse genstande, sammen med klaveret, er Bob ikke interesseret i. $x$
If er en lang smal kage, som kan modelleres som intervallet [0; 1], så kan Alice tildele hver delmængde en værdi, der er proportional med dens længde, hvilket betyder, at hun ønsker at få så meget kage som muligt, uanset dekorationen med glasur og cremer. Bob kan kun tildele værdier til delmængden af [0,4; 0,6], for eksempel fordi denne del af kagen kan indeholde kirsebær, og Bob bekymrer sig kun om at få kirsebær. $x$

Ud fra disse subjektive funktioner er der meget anvendte kriterier for en retfærdig opdeling. Nogle af dem er i konflikt med andre, men de kan ofte kombineres. Kriterierne beskrevet her gælder kun, når en spiller kan have det samme beløb:

Forholdsmæssig opdeling betyder, at hver deltager mindst får sin behørige andel efter sin egen værdifunktion . For eksempel, hvis tre personer deler en kage, så får hver af de tre mindst en tredjedel af deres eget skøn, det vil sige, at hver af de n deltagere får en delmængde af X , som de værdsætter mindst 1/ n :
- $V_{i}(X_{i})\geqslant 1/n$ for alle i.
En superproportional division er en, hvor hver spiller bliver strengt taget større end 1/ n (så divisionen er kun mulig, hvis spillerne har forskellige scores):
- $V_{i}(X_{i})>1/n$ for alt jeg .
En division uden misundelse [3] sikrer, at ingen ønsker, at en anden skal få mere end ham, det vil sige, at hver person modtager en andel, hvis værdi ikke er mindre end værdien af brikkerne for de andre deltagere:
- $V_{i}(X_{i})\geqslant V_{i}(X_{j})$ for alle i og j.
En division uden gruppemisundelse sikrer, at der ikke er nogen undergruppe af agenter, der er jaloux på en anden undergruppe af samme størrelse, hvilket er en meget stærkere tilstand end fraværet af misundelse.
Ligestilling i andele divisionen betyder, at hver person føler den samme tilfredshed, det vil sige, at den del af kagen, som spilleren modtager, ifølge hans egen vurdering, er den samme som for andre spillere. Dette er et vanskeligt mål, da spilleren måske ikke er sandfærdig, når han bliver spurgt om hans vurdering:
- $V_{i}(X_{i})=V_{j}(X_{j})$ for alle i og j.
En nøjagtig division (eller aftalt division ) er en division, hvor alle spillere er enige om værdien af hver brik:
- $V_{i}(X_{i})=V_{j}(X_{i})$ for alle i og j.

Alle ovenstående kriterier forudsætter, at deltagerne modtager lige store andele af . Hvis forskellige deltagere har forskellige andele (f.eks. i tilfælde af et partnerskab, hvor hver partner bidrager med forskellige midler), bør rimelighedskriteriet justeres i overensstemmelse hermed. Se artiklen Proportional opdeling af en kage med forskellige proportioner .

Yderligere krav

Ud over retfærdighed ønskes det nogle gange, at divisionen er Pareto optimal , det vil sige, at ingen anden division kan være bedre for nogen uden tab for en anden. Udtrykket "effektivitet" kommer fra den økonomiske idé om et effektivt marked . En split, hvor én spiller tager alt, er optimal efter denne definition, så det garanterer ikke i sig selv en fair split. Se også artiklerne " Effektiv kageskæring " og " Retfærdighedens pris ".

I den virkelige verden har folk nogle gange meget klare ideer om, hvordan andre spillere værdsætter indsatser, og de kan bruge det. Det tilfælde, hvor de har fuldstændig viden om, hvordan andre spillere værdsætter indsatser, kan modelleres af spilteori . Delvis viden er meget vanskelig at modellere. En stor del af den praktiske side af en retfærdig opdeling er udvikling og undersøgelse af procedurer, der fungerer godt på trods af sådan delvis viden eller små fejl.

Et yderligere krav er, at denne retfærdige opdelingsprocedure er en sandfærdig mekanisme , det vil sige, at det skal være en dominerende strategi for deltagere at vise deres gyldige scores. Dette krav er normalt meget vanskeligt at opfylde i kombination med retfærdighed og Pareto-effektivitet .

En generalisering af problemet er at lade hver interessent bestå af flere aktører, der deler det samme sæt ressourcer, men har forskellige præferencer [4] [5] .

Procedurer

Algoritmer eller procedurer [6] for en retfærdig opdeling viser spillernes handlinger i form af synlige data og deres estimater. Den korrekte procedure er den, der garanterer en retfærdig opdeling for enhver spiller, der handler rationelt efter sin egen vurdering. Mens spillerens handling afhænger af hans vurderinger, beskriver proceduren den strategi, den rationelle spiller følger. Spilleren kan opføre sig, som om brikken havde en anden score, men skal være konsekvent (forudsigelig). For eksempel, hvis proceduren siger, at den første spiller skærer kagen i to lige store dele, og den anden vælger en brik, så kan den første spiller ikke klage over, at den anden spiller fik det meste.

Hvad spilleren gør:

er enig i kriteriet om en retfærdig opdeling;
vælger den korrekte procedure og følger dens regler.

Det antages, at målet for hver spiller er at maksimere den mindste værdi, han kan få. Med andre ord nå maximin .

Procedurer kan opdeles i diskrete og kontinuerlige . En diskret procedure kan for eksempel kun involvere én tærteudskærer ad gangen. Kontinuerlige rutiner involverer ting som når en spiller flytter en kniv , og den anden spiller siger "stop". En anden form for kontinuerlig procedure involverer, at personen tildeler en værdi til hver del af kagen.

For en liste over retfærdige divisionsprocedurer, se Kategori:Retfærdige divisionsprotokoller .

Historie

Ifølge Saul Garfunkel , var kageskæringsproblemet et af de vigtigste åbne problemer i det 20. århundredes matematik [7] , og den vigtigste variant af problemet blev endelig løst ved Brahms-Taylor-proceduren udviklet af Stephen Brahms og Alan Taylor i 1995.

Kilderne til Delhi- og Vælg -protokollen er ukendte. Beslægtede aktiviteter såsom handel og byttehandel har været kendt i lang tid. Forhandlinger , der involverer mere end to deltagere, er også ret almindelige, Potsdam-konferencen er et fremragende eksempel.

Teorien om en retfærdig opdeling tælles kun fra slutningen af Anden Verdenskrig . Den blev udviklet af en gruppe polske matematikere ( Hugo Steinhaus , Bronisław Knaster og Stefan Banach ), som normalt mødtes på den skotske café i Lvov (dengang i Polen ). Proportional division for et hvilket som helst antal deltagere med navnet "sidste faldende" blev udviklet i 1944. Steinhaus tilskrev det til Banach og Knaster , da han præsenterede problemet offentligt for første gang på et møde i Econometric Society i Washington i september 1947. På dette møde foreslog han også problemet med at finde det mindste antal nedskæringer, der er nødvendige for en sådan opdeling.

For historien om misundelig skæring, se artiklen Misundelig kageskæring .

Ansøgninger

Retfærdighedsfordelingsudfordringer opstår i situationer som deling af arv, opsigelse af partnerskaber, skilsmissesag , radiofrekvensallokering , lufthavnstrafikkontrol og drift af jord-fjernmålingssatellitter .

Fair opdeling i populærkulturen

I tv-serien 4isla (sæson 3, afsnit "One Hour") fortæller Charlie om opgaven med at skære kagen i forhold til det beløb, gidseltageren kræver .
Hugo Steinhaus skrev om nogle varianter af en retfærdig opdeling i sin bog The Mathematical Kaleidoscope . I denne bog taler han om versionen af en retfærdig opdeling med tre deltagere, som blev opfundet af G. Krokhmain fra Berdichev i 1944 og en anden version opfundet af fru L. Kott [8] .
Martin Gardner og Ian Stewart udgav en bog hver med kapitler om dette problem [9] [10] . Martin Gardner foreslog at løse delingsproblemet i form af en opgavefordeling. Ian Stewart populariserede problemet med retfærdig opdeling i sine artikler i Scientific American and New Scientist .
Et uddrag fra Dinosaur Comic er baseret på kageskæringsproblemet [11] .
I den israelske film Saint Clare en russisk immigrant en israelsk matematiklærer, hvordan kan en rund kage deles retfærdigt mellem 7 personer? Hans svar: lav 4 lige snit i midten, få 8 lige store stykker. Da der kun er 7 personer, bør en brik smides væk, styret af kommunismens principper.

Se også

Noter

↑ Aumann og Maschler 1985 , s. 195-213.
↑ Yaari, Bar-Hillel, 1984 , s. en.
↑ Et ofte brugt, men noget forvirrende udtryk, da misundelse netop er det dominerende fænomen i denne opdeling. Nogle gange bruges en bogstavelig oversættelse fra engelsk "free from envy". Fraværet af misundelse betyder fravær af grunde til misundelse, det vil sige, at det er nødvendigt at opdele ressourcer på en sådan måde, at ingen har mistanke om, at han fik mindre end en anden.
↑ Manurangsi, Suksompong, 2017 , s. 100-108.
↑ Suksompong, 2018 , s. 40-47.
↑ Udtrykket protokol bruges nogle gange .
↑ Garfunkel, 1988 .
↑ Steinhaus, 1950 .
↑ Gardner, 1978 .
↑ Stewart, 2006 .
↑ Dinosaur Comics - 13. november 2008 - fantastiske sjove tider! . Hentet 8. oktober 2019. Arkiveret fra originalen 28. oktober 2019. (ubestemt)

Litteratur

Robert J. Aumann, Michael Maschler. Spilteoretisk analyse af et konkursproblem fra Talmud // Journal of Economic Theory. - 1985. - T. 36 . - doi : 10.1016/0022-0531(85)90102-4 . Arkiveret fra originalen den 20. februar 2006.
Yaari ME, Bar-Hillel M. Om retfærdig opdeling // Socialt valg og velfærd. - 1984. - T. 1 . - S. 1 . - doi : 10.1007/BF00297056 .
Pasin Manurangsi, Warut Suksompong. Asymptotisk eksistens af retfærdige opdelinger for grupper // Matematisk samfundsvidenskab. - 2017. - T. 89 . - doi : 10.1016/j.mathsocsci.2017.05.006 . - arXiv : 1706.03184 .
Warut Suksompong. Omtrentlig maksimalandele for grupper af agenter // Matematiske samfundsvidenskaber. - 2018. - T. 92 . - doi : 10.1016/j.mathsocsci.2017.09.004 . - arXiv : 1706.09869 .
Steven J. Brams, Alan D. Taylor. Fair opdeling: fra kageskæring til konfliktløsning . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 ..
Jack Robertson. Cake-Cutting Algorithms: Be Fair If You Can.. - Routledge, 1998. - ISBN 978-1-56881-076-8 .
Sol Garfunkel. Mere lige end andre: Vægtet afstemning. // Til alle praktiske formål: En introduktion til moderne matematik . - COMAP (Comsortium for Mathematics and its Applications), 1988. En serie på 26 halvtimes videolektioner på DVD
Hill TP Matematiske enheder til at få en rimelig andel // American Scientist. - 2000. - T. 88 . — S. 325–331 . - doi : 10.1511/2000.4.325 .
Vincent P. Crawford. fair division // New Palgrave: A Dictionary of Economics . - 1987. - T. 2. - S. 274-75.
- The New Palgrave: Finans. - Moskva: State University Higher School of Economics, 2008. - ISBN 978-5-7598-0588-5 .
Hal R. Varian. retfærdighed // The New Palgrave: A Dictionary of Economics. - 1987. - T. 2. - S. 275–76.
Bryan Skyrms. Udviklingen af den sociale kontrakt. - Cambridge University Press, 1996. - ISBN 978-0-521-55583-8 .
H. Steinhaus. Matematiske snapshots. - 1950. - ISBN 0-19-503267-5 .
- Steinhaus G. Matematisk Kalejdoskop . — M .: Nauka, 1981. — 160 s. - ( Bibliotek "Quantum" ). — 150.000 eksemplarer.
Martin Gardner. aha! indsigt. - 1978. - ISBN 978-0-7167-1017-2 .
Ian Stewart. Sådan skærer du en kage og andre matematiske gåder . - OUP Oxford, 2006. - ISBN 978-0-19-920590-5 .

Links

Fair division fra Discrete Mathematics Project ved University of Colorado.
Fair Divide Calculator ( Java Applet )
Fair Divider Metode: Metode til Lone Divider
Retfærdig opdeling: Markørers metode
Fair deling: Metode til forseglede bud

Spilteori
Basale koncepter	Gensidig og fælles viden Spiller Hierarki af trosretninger Irrationel forstærkning Strategi ( dominans ) Omvendt induktion
Typer af spil	Samtidig , sekventiel og gentagne Ikke -samarbejdsvillig og samarbejdsvillig Med fuldstændig , ufuldstændig , perfekt og ufuldkommen information I normal og udvidet form Antagonistisk Differential Stokastisk Kønnenes kamp Hjortejagt
Løsningskoncepter	Risiko dominans Korreleret ligevægt Balancen af en skælvende hånd Nash ligevægt Subgame perfekt ligevægt Rationaliseringsevne Sekventiel balance stærk balance Egen balance Evolutionært stabil strategi Epsilon-ligevægt Pareto effektivitet Nucleus
Eksempler på spil	Fangens dilemma Barens opgave "El Farol" Bertrand model Cournot model Stackelberg model Orlyanka Tragedien med delte ressourcer høge og duer
Epistemisk spilteori Mekanisme design Fair opdeling