Opgaven med at dele lejlighed

Delt huslejeproblemet [1] [2]  er en slags fair deleproblem , hvor udelelige genstande og en fast pengepris skal deles på samme tid. I den engelske litteratur har dette problem forskellige navne, såsom Rental harmony , housemates problem [ 3] [4] og room- assignment -rent-division [5] [6] [7] [8] .

Under typiske forhold er der samarbejdspartnere, der er villige til at leje en bofællesskab til den pris, som udlejer ønsker. Hver af partnerne har deres egne præferencer - den ene foretrækker et stort værelse, den anden foretrækker måske et værelse med udsigt over hovedvejen, og så videre. Følgende to problemer skal løses på samme tid:

Der er flere egenskaber, som vi vil kræve for at blive opfyldt.

Fra fraværet af misundelse følger Pareto effektivitet. Bevis: (modsigelse) antag, at der er en alternativ tildeling med den samme prisvektor, som strengt taget er bedre for mindst én partner. Så, med den nuværende distribution, vil denne partner være jaloux.

Problemet med at dele en lejlighed blev undersøgt under to forskellige antagelser om partnernes præferencer:

Kardinalitet indebærer ordinalitet, da det altid er muligt at opbygge en præferencerelation i henhold til vektoren af ​​estimater. Ordinalitet er en mere generel antagelse og lægger mindre psykisk belastning på partnere.

Ordinær version

Sø: én person pr. værelse

Francis Su 's protokol gør følgende antagelser om partneres præferencer:

  1. Godt hus : Ved enhver lejeopdeling finder hver person, at mindst én værelse+gebyrpakke er acceptabel.
  2. Minimum ekstern indflydelse : Præferenceforholdet afhænger af værelse og betaling, men ikke af valg af andre partnere.
  3. Nærige tilknyttede selskaber : Alle tilknyttede selskaber kan lide gratis (nul gebyr) værelser sammenlignet med ethvert andet rum.
  4. Topologisk lukket præferencesæt : En partner, der foretrækker et værelse til en prissekvens, foretrækker også dette rum til den marginale pris.

Vi normaliserer den samlede betaling for lokalerne til 1. Så er ethvert prisskema et punkt i det -dimensionelle simpleks med toppunkter ved . Su-protokollen fungerer på den dobbelte version af denne simplex på samme måde som Simmons-Su -kageskæringsprotokollerne - for ethvert hjørne af trianguleringen af ​​det dobbelte simpleks, der svarer til et bestemt prisskema, spørger algoritmen partneren "hvilket værelse foretrækker du i denne prisordning?". Dette fører til en Sperner-farvning af dual simplex, og så er der et lille subsimplex, der svarer til en omtrentlig fordeling af værelser og udbetalinger uden misundelse.

Su-protokollen returnerer en sekvens af distributioner, der konvergerer til en distribution uden misundelse. Priserne er altid ikke-negative. Derfor opfylder resultatet kravene til ikke-negativitet og OP.

Sun [10] og Procaccia [11] har givet en populær forklaring på Sus lejlighedsdelingsprotokol.

Francis Su's Fair Division Page [ 12] og Divide Your Rent Fairly [13] har onlineimplementeringer.

Azrieli og Shmaya delte et værelse

Azrieli og Shmaya [2] generaliserede Su's løsning til en situation, hvor kapaciteten af ​​hvert værelse kan være større end et (det vil sige, at nogle partnere kan dele det samme rum).

De beviste eksistensen af ​​distribution uden misundelse under følgende forhold:

  1. Godt hus : Hver partner kan lide mindst et værelse i henhold til hver prisvektor.
  2. Minimum ekstern indflydelse : Alle partnere foretrækker gratis værelser.
  3. Nærige partnere : Præferencer er løbende i pris.

De vigtigste midler brugt i beviset:

Deres løsning er konstruktiv i samme forstand som Su's løsning - der er en procedure, der tilnærmer løsninger til enhver given nøjagtighed.

Grundlæggende egenskaber for ordinære protokoller

A. I både Su-protokollen og Azrieli- og Shmaiya-protokollen er hver partners præferencerelationer tilladt (men ikke påkrævet) at afhænge af den fulde prisvektor. Det vil sige, at partneren kan sige: "Hvis værelse A koster 1000, så vil jeg foretrække værelse B frem for værelse C, men hvis værelse A kun koster 700, så vil jeg foretrække værelse C frem for B."

Der er flere grunde til, at en sådan generalitet kan være nyttig [2] .

  1. Planlægning for fremtiden. Antag, at partneren mener, at det bedste værelse er A, så B, så C. Hvis A er for dyrt, indtager deltageren B. Men hvis A er billigere, kan partneren købe C (det billigste) og så spare penge og flytte til EN.
  2. Ufuldstændige oplysninger. Prisvektoren kan give partneren information om rummenes kvalitet.
  3. Naboer. Prisvektoren kan til en vis grad forudsige en partner, hvilken slags mennesker der vil bo i naborummene.
  4. Ulogiske effekter, såsom perceptuelle rammeeffekter . Hvis rum B og C har samme kvalitet og samme pris, så vælger partneren A. Men hvis værelse B bliver dyrere, kan partneren vælge C, og tænker "det er det samme som B, men billigere..".

B. Su's løsning og Azrieli's og Shmayas løsning antager en "nærlig lejer" - de antager, at en lejer altid foretrækker et ledigt værelse frem for et positivt prissat værelse. Denne antagelse er stærk og ikke altid realistisk. Hvis et værelse er meget dårligt, kan det ske, at nogle lejere ikke vil bo i et sådant værelse, selvom betalingen er nul. Dette er nemt at se i kardinalversionen - hvis du tænker på, at værelse A koster 0,- og værelse B koster 100,-, mens værelse A er gratis og værelse B koster 50,- vil du helt sikkert foretrække værelse B.

Su [1] foreslog en lempelse af denne antagelse som følger: hver partner vælger aldrig det dyreste værelse, hvis der er et ledigt værelse. Dette kræver ikke, at personen vælger et ledigt værelse. Dette gælder især, hvis personen altid foretrækker et ledigt værelse frem for et værelse til en værdi af mindst fuld pris. Men selv denne svækkede antagelse kan vise sig at være urealistisk, som i eksemplet ovenfor [14] .

Kardinal version

Som forklaret ovenfor er input til kardinalversionen en budprismatrix - hver partner skal byde for hvert værelse, hvilket angiver, hvor meget de værdsætter dette værelse (f.eks. i rubler eller dollars).

Nøglekonceptet i kardinalbeslutninger er maxsum- fordelingen. Dette er fordelingen af ​​værelsespartnere, der maksimerer summen af ​​budpriser. Problemet med at finde en fordeling med maxsum er kendt som opgaveproblemet og kan løses af den ungarske algoritme i tide (hvor  er antallet af partnere). Enhver OZ-fordeling er en maxsum og enhver maxsum-fordeling er en EP [4] .

Inkompatibilitet mellem EP og ikke-negativitet

De to krav, fravær af misundelse og ikke-negativitet af betalinger, er ikke altid kompatible. Antag for eksempel, at den fulde pris er 100, og estimaterne er:

Værelse 1 Værelse 2
Partner 1 150 0
Partner 2 140 ti

Her er det kun maxsum-fordelingen, der giver rum 1 til makker 1, og rum 2 til makker 2. For at forhindre, at makker 2 bliver jaloux, skal makker 1 betale 115,- og makker 2 skal betale -15.

I dette eksempel er summen af ​​estimaterne større end de samlede omkostninger. Hvis summen af ​​scorerne er lig med de samlede omkostninger, og der er to eller tre partnere, så er der altid en OD- og HO-fordeling [15] . Men i tilfælde af fire eller flere partnere kan OD og DO igen vise sig at være uforenelige, som i følgende eksempel (se artiklen af ​​Brahms [16] for bevis):

Værelse 1 Værelse 2 Værelse 3 Værelse 4
Partner 1 36 34 tredive 0
Partner 2 31 36 33 0
Partner 3 34 tredive 36 0
Partner 4 32 33 35 0

Bemærk, at dette eksempel ikke forekommer i den ordinære version, da ordinære protokollen gør antagelsen om "nære partnere", hvor partnere altid foretrækker gratis værelser. Hvis denne antagelse er sand, er der altid en OD+HO-fordeling. Men i eksemplet ovenfor fejler antagelsen, og OD+HO-fordelingen eksisterer ikke. Derfor bør protokollerne i kardinalversionen søge et kompromis mellem DO og DO. Hver protokol gør forskellige afvejninger.

Brahms og Kilgour: MEN, ikke OZ

Brahms og Kilgour [8] [17] foreslog en pauseprocedure :

  1. Vi beregner maxsumfordelingen.
  2. Hvis max-summen er mindre end den fulde pris, så er problemet uløseligt, fordi partnerne ikke ønsker at betale den fulde pris, som husets ejer har tildelt.
  3. Hvis maxsum er nøjagtigt lig med den fulde pris, så tildeles værelserne og partnerne betaler deres annoncerede priser.
  4. Hvis maxsum er større end den fulde pris, så sænkes priserne baseret på forskellen mellem disse priser og den næste (minimum) værdiansættelse (se bogen for en mere detaljeret diskussion).

Tanken bag det sidste trin er, at den næste (minimum) score repræsenterer "konkurrencen" om rummet. Hvis partneren med det næsthøjeste bud ønsker mere plads, så burde det koste mere. Dette svarer i ånden til Vickrey-auktionen . På en Vickrey-auktion er betalingen dog helt afhængig af de angivne priser, og i gap-proceduren er betalingerne kun delvist uafhængige. Derfor er pauseproceduren ikke usårbar .

Gab-proceduren tildeler altid ikke-negative priser. Da opgaven er maxsum, er det indlysende, at den også er Pareto-effektiv. Nogle partnere kan dog være jaloux. Det vil sige, at pauseproceduren opfylder MEN og EP, men ikke PP.

Desuden kan pauseproceduren returnere en misundelsesfyldt fordeling, selv når der eksisterer en OD-fordeling. Brahms sagde om dette problem: "Gap-priser tager højde for konkurrence i udbudspriser, der gør prismekanismen salgbar. Selvom fraværet af misundelse er en ønskværdig egenskab, foretrækker jeg en markedslignende mekanisme, hvor der er en konflikt mellem de to egenskaber; partnere bør betale mere, hvis deres bud konkurrerer, selvom dette fører til misundelse” [18] .

Haake, Wraith og Su: OZ men ikke MEN

Haake, Wraith og Su [7] præsenterede en kompenserende procedure . Problemet, som denne procedure løser, er i nogle henseender mere generelt end problemet med at leje en lejlighed sammen:

Der er et "kvalifikationskrav" for partnere - antallet af ansøgninger må ikke være mindre end de samlede omkostninger.

Proceduren tager følgende trin.

  1. Find den maxsum (pragmatiske) fordeling, fordelingen med den højeste nyttesum, der opfylder begrænsningerne på objektbundterne. Hvis der ikke er nogen begrænsninger, er fordelingen, som hvert objekt giver til partneren med den højeste score, maxsum. Hvis der er begrænsninger (såsom "mindst ét ​​objekt pr. partner"), så kan maxsum-fordelingen være svær at finde.
  2. Vi tildeler hver partner værdien af ​​den pakke, der er distribueret til ham. Dette skaber en indledende checkout.
  3. Vi betaler prisen fra den første kasse. Hvis alle partnere har opfyldt kvalifikationskravene, så er der penge nok i kasseapparatet, og der kan dukke et restbeløb op.
  4. Vi udelukker misundelse ved kompensationsbetalinger til misundelige partnere. Der er ikke flere udbetalingsrunder. Proceduren er helt klar og siger tydeligt, hvilken erstatning der skal udbetales og i hvilken rækkefølge. Desuden er denne procedure let at udføre uden en computer.
  5. Kompensationsbeløbet i alle runder er det mindste beløb, der kræves for at eliminere misundelse, og det overstiger aldrig restbeløbet . Hvis der er noget tilbage, kan den resterende del opdeles på en hvilken som helst måde, der ikke skaber misundelse, såsom at betale et lige stort beløb til hver partner (artiklerne diskuterer andre muligheder, der kan betragtes som mere "fair").

Hvis der er mange objekter og komplekse begrænsninger, kan det indledende trin med at finde fordelingens maksimumsum være svært at beregne uden en computer. I dette tilfælde kan "kompensationsproceduren" starte med en vilkårlig fordeling. I dette tilfælde kan proceduren ende med en distribution, der indeholder cyklusser af misundelse . Disse løkker kan fjernes ved at flytte pakker rundt i løkken. En sådan overførsel øger strengt den samlede mængde nytte. Derfor vil maxsum distributionen blive fundet efter et begrænset antal iterationer, og proceduren kan fortsætte som ovenfor for at opnå en misundelsesfri distribution.

Kompensationsproceduren kan tildele negative udbetalinger til nogle partnere (det vil sige give partnere positive beløb). Det betyder, at kompensationsproceduren er en OC, men ikke en NA. Forfatterne siger:

»Vi udelukker ikke situationer, hvor én person bliver betalt af andre. I sammenhæng med en retfærdig opdeling ser vi det overhovedet ikke som et problem. Desuden, hvis gruppen ikke ønsker at slippe af med nogen af ​​medlemmerne, er der ingen grund til, at gruppen ikke skal støtte et medlem af gruppen, som modtager en uønsket (til andre) pakke af objekter. Desuden sikrer kvalifikationskravet, at tilskud ikke skyldes, at aktørerne undervurderer det fulde sæt af objekter” [19] .

Men andre forfattere hævder, at i et typisk leje scenarie

”En lejer, der får anvist et værelse med negative leveomkostninger, får tilskud fra flere af de andre lejere. I sådan en situation foretrækker de måske at lade værelset stå tomt og skille sig af med den værelseskammerat, der indtager værelset, da de får rabat på overnatning. For at undgå sådanne situationer bør det negative gebyr for lokalerne udelukkes” [4] .

Abdulkadiroglu, Sönmez og Unver: OZ og MEN hvis muligt

Abdulkadiroglu, Sönmez og Unver [5] foreslog en tilgang baseret på markedsmekanismen. Det er en kombination af den engelske auktion og den hollandske auktion . Det beskrives enklest som en auktion med løbende priser:

  1. Vi tildeler prisen for hvert værelse i den fulde pris for huset.
  2. Vi udregner kravsættet for hver partner - et værelse eller et sæt værelser, som partneren mest ønsker at modtage til den aktuelle pris.
  3. Vi udvælger lokaler, der er meget efterspurgte (rum, der ønsker flere brugere end antallet af værelser; se artiklen for en præcis definition).
  4. Vi hæver prisen på værelser med øget efterspørgsel med samme koefficient;
  5. Samtidig reducerer vi prisen på andre værelser med samme beløb, så summen af ​​priserne på alle værelser forbliver lig den fulde pris.
  6. Vi opdaterer straks kravene fra partnere og mange lokaler med øget efterspørgsel.
  7. Når sættet af værelser med stor efterspørgsel er tomt, stopper vi og anvender Halls bryllupssætning for at tildele hver partner et værelse i henhold til hans krav.

I praksis er det ikke nødvendigt at ændre prisen løbende, da kun priser er interessante, hvor kravene fra en eller flere partnere ændres. Vi kan definere et sæt priser af interesse for os på forhånd og gøre en auktion med løbende priser til en auktion med diskrete priser. En sådan auktion med diskrete priser stopper efter et begrænset antal trin [20] .

Den resulterende distribution er altid fri for misundelse. Priserne kan være negative som i proceduren for Haake, Wraith og Su. Men i modsætning til denne procedure er priserne ikke-negative, hvis der er en OD-fordeling med ikke-negative priser.

Søvn og Vlah: OZ og MEN, hvis det er muligt

Son og Vlah [4] beviste følgende generelle ejendom af distributioner:

  1. Fraværet af misundelse indebærer maxsum: givet en fordeling x , hvis der eksisterer en prisvektor p sådan, at der ikke er misundelse i x fordeling , så er x maxsum.
  2. Fraværet af misundelse følger af maxsum: for en given prisvektor p , hvis der er en fordeling x , for hvilken prisvektoren p ikke skaber misundelse, vil der for denne prisvektor p ikke være nogen misundelse i nogen maxsumfordeling.

Baseret på disse egenskaber foreslog forfatterne følgende algoritme:

  1. At finde maxsum-fordelingen.
  2. Vi finder minsum-vektoren af ​​priser (vektoren, hvor summen af ​​priser er minimal) under hensyntagen til betingelsen om fravær af misundelse. En sådan prisvektor er en lineær programmeringsløsning og kan findes ved hjælp af Bellman-Ford-algoritmen .
  3. Hvis minimumsprisen er lig med den fulde pris, implementer maxsum distributionen med minimumspriser og exit.
  4. Hvis minsum er mindre end den fulde pris, forhøjer vi alle priser, så summen bliver lig med den fulde pris (det vil sige vi tilføjer værdien til hver pris ). Ændring af priser med samme beløb sikrer fravær af misundelse.
  5. Hvis minsum er større end den samlede pris, så er der ingen løsning, der samtidig opfylder kravene til HO og OR. Der er flere mulige måder at fortsætte proceduren på
    • Vi sænker alle priser med det samme beløb, indtil summen bliver lig med den fulde pris (det vil sige, vi trækker værdien fra hver pris ). Nogle priser er bundet til at blive negative, som i Haake-, Wraith- og Su-løsningen.
    • Vi sænker kun positive priser med det samme beløb, indtil summen af ​​priser bliver lig med den fulde pris. Her ændres priserne ikke på samme måde, hvilket uundgåeligt vil føre til misundelse, som i løsningen af ​​Brahms og Kilgour. Men i denne løsning vil misundelige partnere få deres værelser gratis .

Kompleksiteten ved at udføre maxsum distribution og minsum priser er lig med .

Son og Vlachs løsning ser ud til at have alle de ønskede egenskaber fra de tidligere protokoller, dvs. OZ, NO (hvis muligt), polynomisk køretid, og desuden garanterer den, at enhver misundelig partner får et gratis værelse. Artiklen "Tildel værelser og del leje" [21] giver en implementering af en lignende løsning, også baseret på løsning af et lineært programmeringsproblem, men artiklen citerer andet arbejde.

Mash, Gal, Procaccia og Zeke: OZ og maximin

Gal, Mash, Procaccia og Zeke [22] observerede , baseret på deres erfaringer med udlejningsdistributionsappen på www.spliddit.org, at fraværet af misundelse alene ikke er nok til at tilfredsstille deltagernes forhåbninger. Derfor byggede de et algoritmisk apparat baseret på lineær programmering til at beregne en fordeling, der ikke har misundelse, og som optimerer nogle kriterier. Baseret på teoretiske og eksperimentelle tests konkluderede de, at maximin -kriteriet  - maksimering af den minimale nytteværdi af et middel under hensyntagen til fraværet af misundelse - giver optimale resultater.

Bemærk, at da deres løsning altid er OZ, kan den returnere negative priser.

Budgetkonventioner

De fleste artikler med en kardinalmodel antager, at agenter har kvasi-lineære nyttefunktioner  - deres nytte er lig med rummets værdi minus prisen. Men i virkeligheden har agenter budgetmæssige begrænsninger - hvis prisen på et værelse er højere end deres budget, falder nytten meget hurtigere end lineariteten. Procaccia, Vélez og Yu [23] studerede denne model og præsenterede en algoritme til at bestemme, om der er en OD-fordeling, der opfylder budgetbegrænsningerne, og hvis det er tilfældet, finder algoritmen en fordeling, der opfylder et yderligere retfærdighedskriterium.

Strategiske aftaler

Alle de gennemgåede protokoller antager, at partnerne er ærlige om deres estimater. Strategier er ikke usårbare  - en partner kan vinde ved at angive en forkert værdi. Desuden er strategiens usårlighed uforenelig med fraværet af misundelse  - der er ingen protokol for en deterministisk usårbar strategi, der altid giver en misundelsesfri distribution. Dette gælder, selvom der kun er to partnere, og priserne kan være negative. Bevis : Antag, at den samlede pris er 100, og partnernes estimater er som følger (hvor er parametrene og ):

Værelse 1 Værelse 2
Partner 1 100 x
Partner 2 100 y

Kun den maksimale tildeling giver værelse 1 til partner 1 og værelse 2 til partner 2. Lad være prisen på værelse 2 (så prisen på værelse 1 er ). Så at partner 1 ikke misunder, skal udføres . For ikke at misunde partner 2, skal det udføres .

Lad os antage, at den deterministiske protokol sætter prisen til en vis værdi fra intervallet . Hvis prisen er større end , så har partner 2 et incitament til at indtaste en lavere værdi på , som forbliver større end , for at reducere sine betalinger tættere på . Ligeledes, hvis prisen er mindre end , så har partner 1 grund til at opkræve en højere pris for , som forbliver lavere , for at øge partner 2s betalinger sidelæns (og derved reducere deres egne betalinger). Derfor kan mekanismen ikke være en usårbar strategi.

Forskere håndterer denne umulighed på to måder.

Sun og Yang: Opgaveerstatning

Der er en variant af problemet, hvor vi i stedet for at antage, at den samlede pris for et hus er fast, antager, at der er en maksimal omkostning for hvert værelse. I denne variant er der en mekanisme for en usårbar strategi - en deterministisk fordelingsregel, der vælger minimumsprisen i summen, er en usårbarhedsstrategi [24] .

Dette resultat kan generaliseres for større fleksibilitet til udelelige objekter og bevis for stabiliteten af ​​koalitionsstrategien [25] [26] .


Dufton og Larson: Using chance

Vender vi tilbage til det oprindelige problem med en retfærdig opdeling af boliger, kan vi overveje tilfældighedsmekanismen . Tilfældighedsmekanismen returnerer en sandsynlighedsfordeling over fordelingen af ​​værelser og fordelingen af ​​betaling. Tilfældighedsmekanismen er rimelig i forventning, hvis ingen partner øger den forventede værdi af hans nytte ved at misrepræsentere hans vurdering af værelserne. Tilfældighedsmekanismens retfærdighed kan måles på forskellige måder [6] :

1. Fraværet af misundelse på forhånd betyder, at der ikke er nogen partnere, der misunder en anden partners værelse trukket ved lodtrækning. Denne betingelse er triviel at opfylde: vi vælger alle distributioner med lige stor sandsynlighed og tildeler et samlet omkostningsgebyr til hver partner. Men denne betingelse er af ringe nytte, da der er en stor chance for, at mange partnere vil være jaloux i den endelige distribution. De er måske ikke tilfredse med, at lotteriet var retfærdigt.

2. Guaranteed Probability of Envy-Freeness ( GPEF  ) betyder, at der er en vis sandsynlighed for, at der uanset deltagernes vurderinger i det mindste ikke vil være misundelse i den endelige beslutning. Det er muligt at opnå GVOZ på følgende måde: vi finder distributionen uden misundelse; vi vælger et heltal tilfældigt og flytter partnerne i cyklussen til rummet til højre. Denne tilfældige mekanisme er rimelig i forventning, da enhver partner har lige stor sandsynlighed for at være i hvert værelse og en forventet pris i de samlede omkostninger, uanset partnerens deklarerede priser. Sandsynligheden for at få fordelings-CV er lig med sandsynligheden for at , som er nøjagtigt lig med . Dette er ikke specielt opmuntrende, da sandsynligheden for ikke at være jaloux har en tendens til 0, efterhånden som antallet af partnere vokser, men der er ingen måde at gøre det bedre på, da GVOA ikke overstiger .

3. Forventet antal  misundelsesfrie partnere ( ENEF ) betyder, at der er et eller andet heltal , sådan at hvis vi bestemmer antallet af partnere, der ikke misunder alle mulige resultater af mekanismen, uanset skøn, partnere ikke overstiger forventningen . POCH-testen ser ud til at være mere egnet end HLOT-testen, fordi den måler ikke kun sandsynligheden for fuldstændig fravær af misundelse, men også kvaliteten af ​​de tilfælde, hvor distributionen ikke er fuldstændig fri for misundelse. Den maksimale OCHBZ for en ærlig afventende mekanisme overstiger ikke . Det er muligt at få denne grænse for . For der er en ærlig ventemekanisme, der næsten når denne grænse - TWBZ er lig med . Hovedideen er følgende. Vi bruger Vickrey-Clark-Groves-mekanismen til at beregne tildelingen med det maksimale beløb og dets betalingsbeløb. Vælg tilfældigt en partner. Ignorer denne partner og brug Vickrey-Clark-Groves-mekanismen igen. Vi kombinerer resultaterne for at garantere ligheden af ​​den fulde betaling af de fulde omkostninger (se artiklen for detaljer). Det kan man vise

(a) mekanismen er ærlig afventende (b) alle partnere, undtagen den der ignoreres, vil ikke være jaloux

Derfor er OCHBZ lig med . Modellering viser, at i omkring 80% af tilfældene overskrider HLH ikke denne mekanisme .

Andersson og Svensson: At opnå delvis usårbarhed

En mulig lempelse af usårbarhedskravet er et forsøg på at minimere "grader af manipulerbarhed" [27] . Det bestemmes ved at tælle for hvert tilfælde antallet af agenter, der kan manipulere reglerne. De mest foretrukne regler for retfærdig fordeling manipuleres minimalt (både individuelt og i koalition) både med hensyn til retfærdighed og med hensyn til budgetbalance. Sådanne regler vælger fordelingen med det maksimale antal agenter, for hvem nytten er maksimal blandt alle retfærdige og afbalancerede distributioner.

Se også

Noter

  1. ↑ 1 2 Su, 1999 , s. 930-942.
  2. ↑ 1 2 3 Azrieli, Shmaya, 2014 , s. 128.
  3. ↑ Potthoff, 2002 , s. 405.
  4. ↑ 1 2 3 4 Sung, Vlach, 2004 .
  5. ↑ 1 2 Abdulkadiroğlu, Sönmez, Ünver, 2004 , s. 515.
  6. ↑ 1 2 Dufton, Larson, 2011 , s. 34-39.
  7. ↑ 1 2 Haake, Raith, Su, 2002 , s. 723.
  8. ↑ 1 2 Brams, 2008 , s. 305-328.
  9. ↑ Her betyder ordet svagt , at partneren ikke må skelne et andet værelse + betalingspræferencepakke fra det angivne. Hvis partneren ikke anser pakkerne for lige, bruges udtrykket strengt taget bedre.
  10. ↑ Albert Sun. Start med en trekant for at dele lejen . Arkiveret 11. november 2020. Hentet 26. august 2014.
  11. ↑ Ariel Procaccia. Retfærdig opdeling og de klynkende filosoffers problem . Turings usynlige hånd (15. august 2012). Hentet 26. august 2014. Arkiveret fra originalen 3. september 2014.
  12. ↑ Francis Su's Fair Division-side (link ikke tilgængeligt) . Math.hmc.edu . Hentet 5. januar 2017. Arkiveret fra originalen 27. oktober 2018. 
  13. ↑ Fordel din husleje retfærdigt . Arkiveret fra originalen den 31. december 2019. Hentet 5. januar 2017.
  14. ↑ Brams, 2008 , s. 320-321.
  15. ↑ Sung, Vlach, 2004 , s. 110-111.
  16. ↑ Brams, 2008 , s. 318-319.
  17. ↑ Brams, Kilgour, 2001 , s. 418.
  18. ↑ Brams, 2008 , s. 321.
  19. ↑ Haake, Raith, Su, 2002 , s. 746.
  20. ↑ Abdulkadiroğlu, Sönmez, Ünver, 2004 , s. 525-528.
  21. ↑ Tildel værelser og del leje - Spliddit . Hentet 5. marts 2016. Arkiveret fra originalen 5. marts 2016.
  22. ↑ Gal, Mash, Procaccia, Zick, 2016 , s. 67-84.
  23. ↑ Procaccia, Velez, Yu, 2018 .
  24. ↑ Sun, Yang, 2003 , s. 73.
  25. ↑ Andersson, Svensson, 2008 , s. 350.
  26. ↑ Andersson, 2009 , s. 1719–1724
  27. ↑ Andersson, Ehlers, Svensson, 2014 , s. 753.

Litteratur