Rättvis uppdelning

En rättvis uppdelning är uppgiften att fördela många resurser på flera personer som gör anspråk på andelar av dessa resurser, samtidigt som varje person får den del som passar honom i en eller annan grad. Den centrala bestämmelsen för en rättvis uppdelning är kravet att den ska utföras av deltagarna i processen själva.

Skäldelningsproblemet uppstår i olika situationer, som till exempel delning av ett arv . Det är ett aktivt forskningsområde inom matematik , ekonomi (särskilt inom sociala valteori ), spelteori , kontroversiella frågor och många andra.

En typisk rättvis divisionsalgoritm är dividera och välj . Det visar att två personer med olika smak kan dela en tårta på ett sådant sätt att var och en av dem tror att han fick den bästa biten. Rättvis divisionsstudien kan ses som en utvidgning av denna procedur till olika mer komplexa förhållanden.

Det finns många olika typer av rättvis divisionsproblem och algoritmer, beroende på utdelningens karaktär, rättvisekriterierna, deltagarnas karaktär och deras preferenser och andra nödvändiga egenskaper hos divisionsalgoritmen.

Saker att dela

Formellt definieras problemet med rättvis division av en uppsättning och en grupp spelare. Division är uppdelningen av en uppsättning i icke-överlappande delmängder: , en delmängd per spelare. $X$ $n$ $X$ $n$ ${\displaystyle X=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n))$

Uppsättningen kan vara av olika typer: $X$

X kan vara en ändlig uppsättning odelbara objekt, till exempel: X = {piano, bil, lägenhet}, så varje objekt måste ges till en annan deltagare.
X kan vara en oändlig mängd representerad av delbara resurser , som pengar eller kaka. Matematiskt modelleras en delbar resurs ofta som en delmängd av det verkliga rummet, till exempel kan segmentet [0,1] representera en lång, smal kaka som kan skäras i bitar av parallella sektioner. Enhetscirkeln kan representera en äppelpaj.

Uppsättningen som ska delas kan också vara:

homogen - som pengar, där bara värdet eller kvantiteten spelar roll;
heterogen - såsom en kaka, som kan innehålla olika ingredienser, olika glasyrer, krämer, frukter, etc.

Slutligen är det vanligtvis nödvändigt att göra några antaganden om önskvärdheten av delbara objekt - vilken av grupperna de tillhör:

varor , såsom bilar eller tårtor;
obehagliga saker , som hushållssysslor.

Baserat på dessa skillnader har flera generella typer av rättvis divisionsproblem studerats:

rättvis fördelning av objekt - uppdelningen av många odelbara och heterogena objekt;
rättvis fördelning av resurser - uppdelningen av många delbara och homogena varor. Ett specialfall är rättvis uppdelning av en homogen resurs ;
en rättvis uppdelning av kakan är uppdelningen av en delbar heterogen vara . Ett specialfall är kakans runda form, i vilket fall problemet kallas en rättvis uppdelning av pajen ;
en rättvis fördelning av arbetsuppgifter är uppdelningen av delbara heterogena obehagliga saker.

Kombinationer och specialfall övervägs vanligtvis också:

problemet med att gemensamt hyra en lägenhet - uppdelningen av en uppsättning odelbara heterogena varor (till exempel ett rum i en lägenhet) och samtidigt homogena delbara obehagliga saker (betalning för en lägenhet);
rättvis användning av floden - uppdelningen av vatten som strömmar i floder längs länders gränser;
fair random assignment — en slumpmässig allokeringsalgoritm som ger ett rättvist resultat i genomsnitt, särskilt lämplig för att distribuera odelbara varor.

Definitioner av rättvisa

Det mesta av det som vanligtvis kallas en rättvis uppdelning utelämnas från teorin eftersom arbitrage används . Dessa situationer uppstår ofta med matematiska teorier som har namn på verkliga problem. Besluten i Talmud om aktier när egendom går i konkurs återspeglar några komplexa idéer om rättvisa [1] och de flesta anser att dessa beslut är rättvisa. De är dock resultatet av rabbinernas diskussioner och inte en uppdelning enligt uppskattningar från deltagarna i egendomstvisten.

Enligt den subjektiva värdeteorin kan det inte finnas något objektivt mått på varje objekts värde. Objektiv rättvisa är då omöjlig, eftersom olika personer tar olika priser för varje objekt. Empiriska experiment om hur människor definierar begreppet rättvisa [2] har lett till inkonsekventa resultat.

Sålunda fokuserar den mesta nutida forskningen om rättvisa på begreppet subjektiv rättvisa . Det antas att var och en av personerna har en personlig subjektiv nyttofunktion eller signifikansfunktion , som tilldelar varje delmängd ett numeriskt värde . Ofta antas funktionerna vara normaliserade, så att värdena för varje person är 0 för den tomma uppsättningen ( för alla i), och 1 för uppsättningen av alla element ( för alla i) om elementen är önskvärda, och −1 om elementen är oönskade. Exempel: $n$ $V_i$ $X$ $V_{i}(\emptyset )=0$ $V_{i}(X)=1$

Om det är en uppsättning odelbara föremål {piano, bil, lägenhet}, kan Alice tilldela ett värde på 1/3 till varje föremål, vilket betyder att varje föremål är lika värdefullt för henne. Bob kan tilldela värdet 1 till mängden {bil, lägenhet} och värdet 0 till alla andra uppsättningar utom X. Det betyder att han vill ha bilen och lägenheten tillsammans. En bil eller lägenhet, samt dessa föremål, tillsammans med pianot, är Bob inte intresserad. $X$
If är en lång, smal kaka, som kan modelleras som intervallet [0; 1], så kan Alice tilldela varje delmängd ett värde som är proportionellt mot dess längd, vilket betyder att hon vill få så mycket tårta som möjligt, oavsett dekoration med glasyr och krämer. Bob kan bara tilldela värden till delmängden [0,4; 0,6], till exempel, eftersom den här delen av kakan kan innehålla körsbär, och Bob bryr sig bara om att få körsbär. $X$

Baserat på dessa subjektiva funktioner finns det ofta använda kriterier för en rättvis uppdelning. Vissa av dem står i konflikt med andra, men de kan ofta kombineras. Kriterierna som beskrivs här gäller endast när en spelare kan ha samma summa:

Proportionell uppdelning innebär att varje deltagare får minst sin förfallna andel enligt sin egen värdefunktion . Till exempel, om tre personer delar på en tårta, får var och en av de tre minst en tredjedel av sin egen uppskattning, det vill säga var och en av de n deltagarna får en delmängd av X som de värderar minst 1/ n :
- $V_{i}(X_{i})\geqslant 1/n$ för alla i.
En superproportionell division är en där varje spelare blir strikt större än 1/ n (så divisionen är endast möjlig om spelarna har olika poäng):
- $V_{i}(X_{i})>1/n$ för allt jag .
En division utan avund [3] säkerställer att ingen vill att någon annan ska få mer än honom, det vill säga att varje person får en andel vars värde inte är mindre än värdet av bitarna för de andra deltagarna:
- $V_{i}(X_{i})\geqslant V_{i}(X_{j})$ för alla i och j.
En division utan gruppavund säkerställer att det inte finns någon undergrupp av agenter som är avundsjuka på en annan undergrupp av samma storlek, vilket är ett mycket starkare tillstånd än frånvaron av avund.
Jämställdhet i andelar divisionen innebär att varje person känner samma tillfredsställelse, det vill säga den del av kakan som spelaren får, enligt hans egen bedömning, är densamma som för andra spelare. Detta är ett svårt mål, eftersom spelaren kanske inte är sanningsenlig när han frågas om sin bedömning:
- $V_{i}(X_{i})=V_{j}(X_{j})$ för alla i och j.
En exakt division (eller överenskommen division ) är en division där alla spelare är överens om värdet av varje pjäs:
- $V_{i}(X_{i})=V_{j}(X_{i})$ för alla i och j.

Alla ovanstående kriterier förutsätter att deltagarna får lika andelar av . Om olika deltagare har olika andelar (till exempel vid ett partnerskap där varje partner bidrar med olika medel), bör skälighetskriteriet justeras därefter. Se artikeln Proportionell uppdelning av en kaka med olika proportioner .

Ytterligare krav

Förutom rättvisa önskar man ibland att divisionen är Pareto optimal , det vill säga ingen annan division kan vara bättre för någon utan förlust för en annan. Termen "effektivitet" kommer från den ekonomiska idén om en effektiv marknad . En split där en spelare tar allt är optimal enligt denna definition, så den garanterar inte i sig en rättvis split. Se även artiklarna " Effektiv kakskärning " och " Rättvisans pris ".

I den verkliga världen har människor ibland väldigt tydliga idéer om hur andra spelare värderar insatser, och de kan använda det. Fallet där de har fullständig kunskap om hur andra spelare värderar insatser kan modelleras av spelteori . Delkunskap är mycket svårt att modellera. En stor del av den praktiska sidan av en rättvis uppdelning är utvecklingen och studien av procedurer som fungerar bra trots sådan ofullständig kunskap eller små fel.

Ett ytterligare krav är att denna rättvisa uppdelningsprocedur är en sanningsenlig mekanism , det vill säga att det måste vara en dominerande strategi för deltagarna att visa sina giltiga poäng. Detta krav är vanligtvis mycket svårt att uppfylla i kombination med rättvisa och Pareto-effektivitet .

En generalisering av problemet är att låta varje intressent bestå av flera aktörer som delar samma uppsättning resurser men har olika preferenser [4] [5] .

Procedurer

Algoritmer , eller procedurer [6] för en rättvis uppdelning listar spelarnas handlingar i form av synliga data och deras uppskattningar. Det korrekta förfarandet är det som garanterar en rättvis uppdelning för alla spelare som agerar rationellt enligt sitt eget omdöme. Medan spelarens agerande beror på hans bedömningar, beskriver proceduren den strategi som den rationella spelaren följer. Spelaren kan agera som om pjäsen hade en annan poäng, men måste vara konsekvent (förutsägbar). Till exempel, om proceduren säger att den första spelaren skär kakan i två lika delar, och den andra väljer en bit, så kan den första spelaren inte klaga på att den andra spelaren fick den största delen.

Vad spelaren gör:

instämmer i kriteriet om en rättvis uppdelning.
väljer rätt förfarande och följer dess regler.

Det antas att målet för varje spelare är att maximera det lägsta värde som han kan få. Med andra ord, nå maximin .

Procedurer kan delas in i diskreta och kontinuerliga . En diskret procedur kan till exempel endast involvera en pajskärare åt gången. Kontinuerliga rutiner involverar saker som när en spelare flyttar en kniv och den andra spelaren säger "stopp". En annan typ av kontinuerlig procedur innebär att personen tilldelar varje del av kakan ett värde.

För en lista över förfaranden för rättvis delning, se Kategori: Rättvis delningsprotokoll .

Historik

Enligt Saul Garfunkel , var kakskärningsproblemet ett av de viktigaste öppna problemen i 1900-talets matematik [7] , och den viktigaste varianten av problemet löstes slutligen genom Brahms-Taylor-förfarandet utvecklat av Stephen Brahms och Alan Taylor 1995.

Källorna till Delhi- och Choose- protokollen är okända. Närliggande aktiviteter som handel och byteshandel har varit kända sedan länge. Förhandlingar som involverar fler än två deltagare är också ganska vanliga, Potsdamkonferensen är ett enastående exempel.

Teorin om en rättvis uppdelning räknas först från slutet av andra världskriget . Den utvecklades av en grupp polska matematiker ( Hugo Steinhaus , Bronisław Knaster och Stefan Banach ) som vanligtvis träffades på Scottish Café i Lvov (då i Polen ). Proportionell uppdelning för valfritt antal deltagare med namnet "senast minskande" utvecklades 1944. Steinhaus tillskrev det till Banach och Knaster när han presenterade problemet offentligt för första gången vid ett möte med Econometric Society i Washington i september 1947. Vid detta möte föreslog han också problemet med att hitta det minsta antal nedskärningar som behövs för en sådan uppdelning.

För historien om avundsjuk skärning, se artikeln Avundsjuk kakskärning .

Applikationer

Rättvisa uppdelningsutmaningar uppstår i situationer som delning av arv, uppsägning av partnerskap, skilsmässaförfaranden , radiofrekvenstilldelningar , flygplatstrafikkontroll och drift av jordfjärranalyssatelliter .

Rättvis uppdelning i populärkulturen

I tv-serien 4isla (säsong 3, avsnitt "One Hour"), berättar Charlie om uppgiften att skära kakan som tillämpas på den summa pengar som gisslantagaren kräver .
Hugo Steinhaus skrev om några varianter av en rättvis uppdelning i sin bok The Mathematical Kaleidoscope . I den här boken talar han om versionen av en rättvis division med tre deltagare, som uppfanns av G. Krokhmain från Berdichev 1944 och en annan version som uppfanns av fru L. Kott [8] .
Martin Gardner och Ian Stewart publicerade varsin bok med kapitel om detta problem [9] [10] . Martin Gardner föreslog att lösa uppdelningsproblemet i form av en arbetsfördelning. Ian Stewart populariserade problemet med rättvis uppdelning i sina artiklar i Scientific American and New Scientist .
Ett utdrag ur Dinosaur Comic är baserat på problemet med att skära kakor [11] .
I den israeliska filmen Saint Clare en rysk invandrare en israelisk mattelärare hur kan en rund tårta delas rättvist mellan 7 personer? Hans svar: gör 4 raka snitt i mitten, få 8 lika stora bitar. Eftersom det bara är 7 personer bör en bit slängas, vägledd av kommunismens principer.

Se även

Anteckningar

↑ Aumann och Maschler 1985 , sid. 195–213.
↑ Yaari, Bar-Hillel, 1984 , sid. ett.
↑ En ofta använd, men något förvirrande term, eftersom avund är just det dominerande fenomenet i denna division. Ibland används en bokstavlig översättning från engelska "free from envy". Frånvaron av avund betyder frånvaro av skäl till avund, det vill säga det är nödvändigt att dela resurser på ett sådant sätt att ingen misstänker att han fick mindre än någon annan.
↑ Manurangsi, Suksompong, 2017 , sid. 100–108.
↑ Suksompong, 2018 , sid. 40–47.
↑ Termen protokoll används ibland .
↑ Garfunkel, 1988 .
↑ Steinhaus, 1950 .
↑ Gardner, 1978 .
↑ Stewart, 2006 .
↑ Dinosaur Comics - 13 november 2008 - fantastiskt roliga tider! . Hämtad 8 oktober 2019. Arkiverad från originalet 28 oktober 2019. (obestämd)

Litteratur

Robert J. Aumann, Michael Maschler. Spelteoretisk analys av ett konkursproblem från Talmud // Journal of Economic Theory. - 1985. - T. 36 . - doi : 10.1016/0022-0531(85)90102-4 . Arkiverad från originalet den 20 februari 2006.
Yaari ME, Bar-Hillel M. Om att dela rättvist // Socialt val och välfärd. - 1984. - T. 1 . - S. 1 . - doi : 10.1007/BF00297056 .
Pasin Manurangsi, Warut Suksompong. Asymptotisk existens av rättvisa divisioner för grupper // Matematisk samhällsvetenskap. - 2017. - T. 89 . - doi : 10.1016/j.mathsocsci.2017.05.006 . - arXiv : 1706.03184 .
Warut Suksompong. Ungefärliga maximala andelar för grupper av agenter // Matematisk samhällsvetenskap. - 2018. - T. 92 . - doi : 10.1016/j.mathsocsci.2017.09.004 . - arXiv : 1706.09869 .
Steven J. Brams, Alan D. Taylor. Rättvis uppdelning: från tårtskärning till tvistlö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. Mer jämställda än andra: viktad röstning. // För alla praktiska ändamål: En introduktion till samtida matematik . - COMAP (Comsortium for Mathematics and its Applications), 1988. En serie med 26 halvtimmars videolektioner på DVD
Hill TP Matematiska enheter för att få en rättvis andel // American Scientist. - 2000. - T. 88 . — S. 325–331 . - doi : 10.1511/2000.4.325 .
Vincent P. Crawford. rättvis 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. rättvisa // The New Palgrave: A Dictionary of Economics. - 1987. - T. 2. - S. 275–76.
Bryan Skyrms. Utvecklingen av det sociala kontraktet. - Cambridge University Press, 1996. - ISBN 978-0-521-55583-8 .
H. Steinhaus. Matematiska ögonblicksbilder. - 1950. - ISBN 0-19-503267-5 .
- Steinhaus G. Matematiskt Kalejdoskop . — M .: Nauka, 1981. — 160 sid. - ( Bibliotek "Quantum" ). — 150 000 exemplar.
Martin Gardner. a ha! insikt. - 1978. - ISBN 978-0-7167-1017-2 .
Ian Stewart. Hur man skär en tårta och andra matematiska problem . - OUP Oxford, 2006. - ISBN 978-0-19-920590-5 .

Länkar

Rättvis division från Discrete Mathematics Project vid University of Colorado.
Fair Divide Calculator ( Java Applet )
Fair Divider Method: Metod för Lone Divider
Rättvis indelning: Method of Markers
Rättvis uppdelning: Metod för förseglade bud

Spel teori
Grundläggande koncept	Ömsesidig och gemensam kunskap Spelare Hierarki av tro Irrationell förstärkning Strategi ( dominans ) Omvänd induktion
Typer av spel	Samtidigt , sekventiellt och repetitivt Icke -samarbetsvillig och samarbetsvillig Med fullständig , ofullständig , perfekt och ofullständig information I normal och utökad form Antagonistisk Differentiell Stokastisk Kampen mellan könen Rådjursjakt
Lösningskoncept	Riskdominans Korrelerad jämvikt Balansen av en darrande hand Nash jämvikt Subgame perfekt jämvikt Rationaliserbarhet Sekventiell balans stark balans Egen balans Evolutionärt stabil strategi Epsilon-jämvikt Pareto effektivitet Kärna
Spelexempel	Fångens dilemma Uppgiften för baren "El Farol" Bertrand modell Cournot modell Stackelberg modell Orlyanka Tragedin med delade resurser hökar och duvor
Epistemisk spelteori Mekanism design Rättvis uppdelning