A lakás megosztásának feladata

A megosztott lakbér probléma [1] [2]  egyfajta fair share -probléma , amelyben egyszerre kell oszthatatlan tárgyakat és fix pénzbeli árat megosztani. Az angol szakirodalomban ennek a problémának különböző nevei vannak, például Rental harmony , housemates problem [ 3] [4] és room- assignment -rent-division [5] [6] [7] [8] .

Tipikus feltételek mellett vannak olyan partnerek, akik a bérbeadó által kért áron bérelnek közös szobás lakást . Mindegyik partnernek megvannak a saját preferenciái – az egyik a nagy szobát részesíti előnyben, a másik a főútra néző szobát, és így tovább. A következő két problémát kell egyszerre megoldani:

Számos olyan tulajdonság van, amelynek teljesítéséhez szükségünk van.

Az irigység hiányából Pareto hatékonyság következik. Bizonyítás: (ellentmondás) tegyük fel, hogy van egy alternatív hozzárendelés ugyanazzal az árvektorral, amely szigorúan jobb legalább egy partner számára. Akkor a mostani elosztás mellett ez a partner féltékeny lesz.

A lakásmegosztás problémáját két különböző feltevés alapján vizsgálták a partnerek preferenciái alapján:

A kardinalitás magába foglalja az ordinalitást, hiszen mindig lehet preferenciarelációt építeni a becslések vektora szerint. Az ordinálisság általánosabb feltevés, és kevesebb mentális terhet ró a partnerekre.

Rendes változat

Su: szobánként egy személy

Francis Su protokollja a következő feltételezéseket tartalmazza a partnerek preferenciáit illetően:

  1. Jó ház : Bármilyen bérleti bontásban, minden embernek legalább egy szoba+díj csomag elfogadható.
  2. Minimális külső hatás : A preferencia kapcsolat a szobától és a fizetéstől függ, de nem a többi partner választásától.
  3. Fösvény leányvállalatok : Minden leányvállalat kedveli az ingyenes (nulla díjas) szobákat bármely más szobához képest.
  4. Topológiailag zárt preferenciakészlet : Az a partner, aki egy ársorozathoz szobát preferál, azt a szobát preferálja a határárnál is.

Normalizáljuk a helyiségek teljes fizetését 1-re. Ekkor bármely árséma egy pont a -dimenziós szimplexben, amelynek csúcsai . A Su-protokoll ennek a szimplexnek a kettős változatán a Simmons-Su tortavágó protokollokhoz hasonlóan működik - a duális szimplex háromszögelésének bármely olyan csúcsa esetén, amely megfelel egy bizonyos ársémának, az algoritmus megkérdezi a partnert, hogy szobát szeretne ebben az árrendszerben?". Ez a kettős szimplex Sperner-színéhez vezet, majd van egy kis alszimplex, amely megfelel a szobák és a kifizetések hozzávetőleges eloszlásának, irigység nélkül.

A Su protokoll olyan disztribúciók sorozatát adja vissza, amelyek irigység nélkül konvergálnak egy disztribúcióhoz. Az árak mindig nem negatívak. Ezért az eredmény kielégíti a nem-negativitás és az OP követelményeit.

Sun [10] és Procaccia [11] népszerű magyarázatot adott Su lakásmegosztási protokolljára.

A Francis Su Fair Division oldala [ 12] és a Divide Your Rent Fairly [13] online megvalósítással rendelkezik.

Azrieli és Shmaya megosztottak egy szobát

Azrieli és Shmaya [2] általánosította Su megoldását egy olyan helyzetre, amelyben az egyes helyiségek kapacitása nagyobb lehet, mint egy (vagyis néhány partner osztozhat ugyanazon a helyiségen).

Irigység nélkül bizonyították az elosztás létezését a következő feltételek mellett:

  1. Jó ház : Minden partnernek legalább egy szobája tetszik minden árvektornak megfelelően.
  2. Minimális külső hatás : Minden partner a szabad szobákat részesíti előnyben.
  3. Fösvény partnerek : A preferenciák árban folyamatosak.

A bizonyítás során használt fő eszközök:

Megoldásuk ugyanabban az értelemben konstruktív, mint Su megoldása – van egy eljárás, amely a megoldásokat tetszőleges pontossággal közelíti.

Az ordinális protokollok alapvető tulajdonságai

V. Mind a Su protokollban, mind az Azrieli és Shmaiya protokollban az egyes partnerek preferenciakapcsolatai megengedettek (de nem kötelezőek), hogy a teljes árvektortól függjenek. Vagyis a partner azt mondhatja: "Ha az A szoba 1000-be kerül, akkor a B szobát preferálom a C szobával szemben, de ha az A szoba csak 700-ba kerül, akkor a C szobát részesítem előnyben a B helyett."

Számos oka van annak, hogy ez az általánosítás hasznos lehet [2] .

  1. A jövő tervezése. Tegyük fel, hogy a partner úgy gondolja, hogy a legjobb szoba A, majd B, majd C. Ha A túl drága, a résztvevő elfoglalja B-t. De ha A olcsóbb, a partner megveheti C-t (a legolcsóbbat), majd pénzt takarít meg és költözik A.
  2. Hiányos információ. Az árvektor információkat adhat a partnernek a szobák minőségéről.
  3. Szomszédok. Az árvektor bizonyos mértékig meg tudja jósolni a partnernek, hogy milyen emberek fognak lakni a szomszédos szobákban.
  4. Illogikus hatások, például percepciós kereteffektusok . Ha a B és a C szoba azonos minőségű és azonos árú, akkor a partner az A-t választja. De ha a B szoba drágul, akkor a partner választhatja a C-t, gondolván "ugyanúgy, mint B, de olcsóbb...".

B. Su megoldása, valamint Azrieli és Shmaya megoldása „fukar bérlőt” feltételez – azt feltételezik, hogy a bérlő mindig előnyben részesíti az ingyenes szobát a pozitív árú szobával szemben. Ez a feltételezés erős és nem mindig reális. Ha az egyik szoba nagyon rossz, előfordulhat, hogy néhány bérlő akkor sem akar ilyen szobában lakni, ha a fizetés nulla. Ez a kardinális változatban könnyen belátható - ha figyelembe vesszük, hogy az A szoba 0, a B szoba 100, míg az A szoba ingyenes, a B szoba pedig 50, akkor határozottan a B szobát részesíti előnyben.

Su [1] ennek a feltevésnek a enyhítését a következőképpen javasolta: ha van szabad szoba, minden partner soha nem a legdrágább szobát választja. Ehhez nem kell szabad szobát választania. Ez különösen akkor érvényes, ha a személy mindig előnyben részesíti az ingyenes szobát a legalább teljes árú szobával szemben. Azonban még ez a gyengített feltevés is irreálisnak bizonyulhat, mint a fenti példában [14] .

Cardinal version

Amint azt fentebb kifejtettük, a kardinális változat bemenete egy ajánlati ármátrix – minden partnernek minden szobára licitálnia kell, jelezve, hogy mennyit értékel az adott szobára (mondjuk rubelben vagy dollárban).

A kardinális döntések kulcsfogalma a maximális összeg eloszlása. Ez a szobapartnerek elosztása, amely maximalizálja az ajánlati árak összegét. A maxsum-os eloszlás megtalálásának problémája hozzárendelési feladatként ismert, és a magyar algoritmussal időben (hol  a partnerek száma) megoldható . Bármely OZ eloszlás maxsum, és bármilyen maxsum eloszlás EP [4] .

Összeférhetetlenség az EP és a nem-negativitás között

A két követelmény, az irigység hiánya és a fizetés negativitása, nem mindig kompatibilis. Tegyük fel például, hogy a teljes ár 100, és a becslések a következők:

1. szoba 2. szoba
Partner 1 150 0
Partner 2 140 tíz

Itt csak a maximális összeg eloszlása ​​adja az 1-es szobát az 1. partnernek, a 2-es szobát pedig a 2. partnernek. Annak érdekében, hogy a 2. partner ne legyen féltékeny, az 1. partnernek 115-öt, a 2. partnernek pedig −15-öt kell fizetnie.

Ebben a példában a becslések összege nagyobb, mint a teljes költség. Ha a pontszámok összege megegyezik a teljes költséggel, és két vagy három partner van, akkor mindig létezik OD és HO eloszlás [15] . De négy vagy több partner esetén az OD és a DO ismét összeegyeztethetetlennek bizonyulhat, mint a következő példában (bizonyítást lásd Brahms cikkében [16] ):

1. szoba 2. szoba 3. szoba 4. szoba
Partner 1 36 34 harminc 0
Partner 2 31 36 33 0
Partner 3 34 harminc 36 0
Partner 4 32 33 35 0

Megjegyzendő, hogy ez a példa nem fordul elő az ordinális változatban, mivel az ordinális protokoll a "fukar partnerek" feltételezést teszi, ahol a partnerek mindig a szabad szobákat részesítik előnyben. Ha ez a feltevés igaz, mindig van egy OD+HO eloszlás. A fenti példában azonban a feltételezés meghiúsul, és az OD+HO eloszlás nem létezik. Ezért a kardinális változat protokolljainak kompromisszumot kell keresniük a DO és a DO között. Mindegyik protokoll más-más kompromisszumot köt.

Brahms és Kilgour: DE, nem OZ

Brahms és Kilgour [8] [17] megszakítási eljárást javasolt :

  1. Kiszámoljuk a maxsum eloszlást.
  2. Ha a maximális összeg kevesebb, mint a teljes ár, akkor a probléma megoldhatatlan, mert a partnerek nem akarják kifizetni a ház tulajdonosa által kiszabott teljes árat.
  3. Ha a maximális összeg pontosan megegyezik a teljes árral, akkor a szobák kiosztásra kerülnek és a partnerek kifizetik a meghirdetett áraikat.
  4. Ha a maximális összeg nagyobb, mint a teljes ár, akkor az árakat az árak és a következő (minimális) értékelés közötti különbség alapján csökkentik (a részletesebb leírást lásd a könyvben).

Az utolsó lépés mögött az az elképzelés áll, hogy a következő (minimális) pontszám a teremért folyó „versenyt” jelenti. Ha a következő legmagasabb ajánlatot tevő partner több helyet szeretne, akkor ennek többe kell lennie. Ez hasonló a Vickrey aukcióhoz . A Vickrey aukción azonban a fizetés teljes mértékben a bejelentett áraktól függ, és a gap eljárásban a kifizetések csak részben függetlenek. Ezért a break eljárás nem sérthetetlen .

A gap eljárás mindig nem negatív árakat rendel hozzá. Mivel a hozzárendelés maxsum, nyilvánvaló, hogy Pareto-hatékony is. Egyes partnerek azonban féltékenyek lehetnek. Vagyis a törési eljárás kielégíti a DE-t és az EP-t, de nem az EP-t.

Ezenkívül a megszakítási eljárás irigységgel teli eloszlást adhat vissza, még akkor is, ha létezik OD-eloszlás. Brahms ezt mondta erről a problémáról: „A rés árak figyelembe veszik a versenyt az ajánlattételi árakban, amelyek piacképessé teszik az ármechanizmust. Bár az irigység hiánya kívánatos tulajdonság, én inkább a piacszerű mechanizmust részesítem előnyben, ahol konfliktus van a két tulajdonság között; a partnereknek többet kell fizetniük, ha ajánlataik versengenek, még akkor is, ha ez irigységhez vezet” [18] .

Haake, Wraith és Su: OZ, de nem DE

Haake, Wraith és Su [7] egy kompenzációs eljárást mutatott be . A probléma, amelyet ez az eljárás megold, bizonyos szempontból általánosabb, mint a közös lakásbérlés problémája:

A partnerekkel szemben „képzettségi követelmény” van – a jelentkezések összege nem lehet kevesebb, mint a teljes költség.

Az eljárás a következő lépésekből áll.

  1. Keresse meg a maxsum (pragmatikus) eloszlást, azt a legnagyobb hasznossági összegű eloszlást, amely kielégíti az objektumkötegek korlátait. Ha nincsenek megkötések, akkor az egyes objektumok által a legmagasabb pontszámot elért partnernek adott eloszlás maxsum. Ha vannak megkötések (például „partnerenként legalább egy objektum”), akkor nehéz lehet megtalálni a maximális összeg eloszlását.
  2. Minden partnerhez hozzárendeljük a neki kiosztott csomag értékét. Ezzel létrejön a kezdeti pénztár.
  3. Az árat a kezdeti pénztárból fizetjük. Ha minden partner megfelelt a képesítési követelményeknek, akkor van elég pénz a pénztárgépben, és megjelenhet némi maradék összeg.
  4. Kizárjuk az irigységet az irigy partnereknek fizetett kompenzáció révén. Nincs több kifizetési kör. Az eljárás teljesen világos, és egyértelműen megmondja, hogy milyen kártérítést és milyen sorrendben kell fizetni. Ezenkívül ez az eljárás számítógép nélkül is könnyen végrehajtható.
  5. A minden körben teljesített kártérítés összege az irigység megszüntetéséhez szükséges legkisebb összeg, amely soha nem haladja meg a fennmaradó összeget. Ha marad valami, ezt a maradékot bármilyen módon fel lehet osztani, ami nem kelt irigységet, például egyenlő összeget kell fizetni minden partnernek (a cikkek más lehetőségeket is tárgyalnak, amelyek "méltányosabbnak" tekinthetők).

Ha sok objektum és összetett kényszer van, akkor az eloszlás maximális összegének megtalálásának kezdeti lépése számítógép nélkül nehéz lehet. Ebben az esetben a „kompenzációs eljárás” tetszőleges elosztással indulhat. Ebben az esetben az eljárás az irigység ciklusait tartalmazó eloszlással végződhet . Ezek a hurkok eltávolíthatók, ha csomagokat mozgatnak a hurok körül. Az ilyen átutalás szigorúan növeli a hasznosság teljes összegét. Ezért korlátozott számú iteráció után a rendszer megtalálja a maximális összegű eloszlást, és az eljárás a fentiek szerint folytatható az irigységmentes eloszlás eléréséhez.

A kompenzációs eljárás negatív kifizetéseket rendelhet egyes partnerekhez (vagyis pozitív pénzösszegeket ad a partnereknek). Ez azt jelenti, hogy a kompenzációs eljárás OC, de nem NA. A szerzők azt mondják:

„Nem zárjuk ki azokat a helyzeteket, amikor egy embert mások fizetnek. A tisztességes felosztás keretében ezt egyáltalán nem látjuk problémának. Sőt, ha a csoport egyik tagjától sem akar megszabadulni, nincs ok arra, hogy a csoport ne támogassa azt a tagot, aki nem kívánt (mások számára) tárgycsomagot kap. Ezenkívül a minősítési követelmény biztosítja, hogy a támogatások ne származzanak abból, hogy a játékosok alábecsülik a teljes tárgykészletet” [19] .

Más szerzők azonban azzal érvelnek, hogy egy tipikus bérleti forgatókönyv esetén

„Azt a bérlőt, akihez negatív megélhetési költséggel rendelnek szobát, több másik bérlő is támogat. Előfordulhat, hogy ilyen helyzetben inkább üresen hagyják a szobát, és megválnak a szobát elfoglaló szobatárstól, ugyanis kedvezményt kapnak a szállás árából. Az ilyen helyzetek elkerülése érdekében a helyiségek negatív díját ki kell zárni” [4] .

Abdulkadiroglu, Sönmez és Unver: OZ és DE ha lehet

Abdulkadiroglu, Sönmez és Unver [5] a piaci mechanizmuson alapuló megközelítést javasolta. Ez az angol aukció és a holland aukció kombinációja . A legegyszerűbben folyamatos árverésnek nevezik:

  1. Minden szoba árát hozzárendeljük a ház teljes költségéhez.
  2. Kiszámoljuk az egyes partnerek igényeit - egy szobát vagy szobakészletet, amelyet a partner a leginkább szeretne megkapni az aktuális áron.
  3. Olyan szobákat választunk, amelyekre nagy a kereslet (olyan szobák, amelyek több felhasználót szeretnének, mint ahány szoba; pontos meghatározást lásd a cikkben).
  4. A megnövekedett keresletű szobák árát ugyanazzal az együtthatóval emeljük;
  5. Ugyanakkor a többi szoba árát ugyanennyivel csökkentjük, így az összes szoba árának összege megegyezik a teljes árral.
  6. Azonnal frissítjük partnereink igényeit és számos helyiséget, ahol megnövekedett az igény.
  7. Amikor a nagy igényű szobák halmaza üres, megállunk, és a Hall esküvői tételét alkalmazzuk , hogy minden partnernek az igényeinek megfelelő szobát rendeljünk.

A gyakorlatban nem szükséges folyamatosan változtatni az árakat, hiszen csak azok az árak érdekesek, amelyeknél egy vagy több partner követelményrendszere megváltozik. Előzetesen meghatározhatunk egy számunkra érdekes árkészletet, és a folyamatos árakat tartalmazó aukciót diszkrét áras aukcióvá alakíthatjuk. Az ilyen diszkrét árakkal rendelkező aukció véges számú lépés után leáll [20] .

Az így létrejött elosztás mindig mentes az irigységtől. Az árak negatívak lehetnek, mint Haake, Wraith és Su eljárásában. Ezzel az eljárással ellentétben azonban az árak nem negatívak, ha van egy OD eloszlás nem negatív árakkal.

Alvás és Vlah: OZ és DE, ha lehetséges

Son és Vlah [4] az eloszlások következő általános tulajdonságát bizonyították:

  1. Az irigység hiánya maxsum összeget von maga után: ha egy x eloszlás esetén létezik olyan p árvektor, amelyre nincs irigység az x eloszlásban , akkor x a maxsum.
  2. Az irigység hiánya a maxsumból következik: ha egy adott p árvektor esetén van olyan x eloszlás , amelyre a p árvektor nem kelt irigységet , akkor erre a p árvektorra egyetlen maxsum eloszlásban sem lesz irigység.

Ezen tulajdonságok alapján a szerzők a következő algoritmust javasolták:

  1. A maxsum eloszlás megkeresése.
  2. Az irigység hiányának feltételét figyelembe véve megtaláljuk az árak minimumvektorát (azt a vektort, amelyen az árak összege minimális). Egy ilyen árvektor egy lineáris programozási megoldás , és a Bellman-Ford algoritmussal kereshető meg .
  3. Ha a minimális ár megegyezik a teljes árral, hajtsa végre a maxsum eloszlást a minimum árakkal és lépjen ki.
  4. Ha a minimális összeg kisebb, mint a teljes ár, akkor az összes árat megemeljük úgy, hogy az összeg egyenlő legyen a teljes árral (azaz minden árhoz hozzáadjuk az értéket ). Az árak azonos mértékű változtatása biztosítja az irigység hiányát.
  5. Ha a minsum nagyobb, mint a teljes ár, akkor nincs olyan megoldás, amely egyszerre elégíti ki a HO és az OR követelményeit. Az eljárás folytatására több lehetőség is van
    • Minden árat ugyanannyival csökkentünk, amíg az összeg egyenlővé nem válik a teljes árral (azaz minden árból kivonjuk az értéket ). Egyes árak negatívak lesznek, mint például a Haake, Wraith és Su megoldásban.
    • Csak a pozitív árakat addig csökkentjük, amíg az árak összege egyenlővé nem válik a teljes árral. Itt az árak nem ugyanúgy változnak, ami óhatatlanul irigységhez vezet, mint Brahms és Kilgour megoldásában. Ebben a megoldásban azonban az irigy partnerek ingyen kapják meg a szobáikat .

A maxsum eloszlás és a minimális árak végrehajtásának bonyolultsága egyenlő .

Úgy tűnik, a Son and Vlach megoldása rendelkezik az előző protokollok összes kívánt tulajdonságával, azaz OZ, NO (ha lehetséges), polinomiális futási idővel, és ráadásul garantálja, hogy minden irigy partner kap egy szabad szobát. A "Szobák hozzárendelése és bérbeadása" [21] cikk egy hasonló megoldás megvalósítását tartalmazza, amely szintén egy lineáris programozási probléma megoldásán alapul, de a cikk más munkákra hivatkozik.

Mash, Gal, Procaccia és Zeke: OZ és maximin

Gal, Mash, Procaccia és Zeke [22] megfigyelték a www.spliddit.org webhelyen található bérelosztó alkalmazással kapcsolatos tapasztalataik alapján, hogy az irigység hiánya önmagában nem elég a résztvevők vágyainak kielégítéséhez. Ezért építettek egy lineáris programozáson alapuló algoritmikus apparátust olyan eloszlás kiszámítására, amelyben nincs irigység, és amely bizonyos kritériumokat optimalizál. Elméleti és kísérleti tesztek alapján arra a következtetésre jutottak, hogy a maximin kritérium  - egy szer minimális hasznosságának maximalizálása, figyelembe véve az irigység hiányát - optimális eredményt ad.

Vegye figyelembe, hogy mivel megoldásuk mindig OZ, negatív árakat adhat vissza.

Költségvetési megállapodások

A legtöbb kardinális modellt használó cikk azt feltételezi, hogy az ágensek kvázi lineáris hasznossági függvényekkel rendelkeznek  – hasznosságuk egyenlő a szoba értékével mínusz az ár. A valóságban azonban az ügynököknek költségvetési korlátai vannak – ha egy szoba ára magasabb, mint a költségvetésük, a hasznosság sokkal gyorsabban csökken, mint a linearitás. Procaccia, Vélez és Yu [23] tanulmányozták ezt a modellt, és bemutattak egy algoritmust annak meghatározására, hogy van-e olyan OD eloszlás, amely kielégíti a költségvetési korlátokat, és ha igen, akkor az algoritmus talál egy további igazságossági kritériumot kielégítő eloszlást.

Stratégiai megállapodások

Az összes áttekintett protokoll feltételezi, hogy a partnerek őszinték a becsléseiket illetően. A stratégiák nem sebezhetetlenek  – a partner hibás érték megadásával nyerhet. Ráadásul a stratégia sebezhetetlensége összeegyeztethetetlen az irigység hiányával  – nincs protokoll egy olyan determinisztikus sebezhetetlen stratégiához, amely mindig irigységmentes elosztást ad. Ez akkor is igaz, ha csak két partner van, és az árak negatívak is lehetnek. Bizonyítás : Tegyük fel, hogy a teljes ár 100, és a partnerek becslései a következők (hol vannak a paraméterek és ):

1. szoba 2. szoba
Partner 1 100 x
Partner 2 100 y

Csak a maximális kiosztás ad az 1. szobát az 1. partnernek és a 2. szobát a 2. partnernek. Legyen a 2. szoba ára (tehát az 1. szoba ára ). Annak érdekében, hogy a partner 1 ne irigykedjen, el kell végezni . Annak érdekében, hogy ne irigyeljük a 2. partnert, végre kell hajtani .

Tegyük fel, hogy a determinisztikus protokoll az árat az intervallumból valamilyen értékre állítja be . Ha az ár nagyobb, mint , akkor a 2. partnert arra ösztönzi, hogy alacsonyabb értéket adjon meg , amely nagyobb marad , hogy a fizetését közelebb csökkentse . Hasonlóképpen, ha az ár alacsonyabb, mint , akkor az 1. partnernek van oka magasabb árat felszámítani a -ra , amely alacsonyabb marad , hogy oldalirányban növelje a 2. partner fizetését (és ezáltal csökkentse saját befizetéseit). Ezért a mechanizmus nem lehet sebezhetetlen stratégia.

A kutatók kétféleképpen kezelik ezt a lehetetlenséget.

Sun és Yang: Feladatcsere

A problémának van egy olyan változata, ahol ahelyett, hogy azt feltételeznénk, hogy egy ház összköltsége fix, azt feltételezzük, hogy minden helyiségre van egy maximális költség. Ebben a változatban létezik egy sebezhetetlen stratégia mechanizmusa - egy determinisztikus elosztási szabály, amely az összegben kiválasztja a minimális árat, egy sebezhetetlenségi stratégia [24] .

Ez az eredmény általánosítható az oszthatatlan tárgyakra való nagyobb rugalmasság és a koalíciós stratégia stabilitásának bizonyítása érdekében [25] [26] .


Dufton és Larson: A véletlen felhasználása

Visszatérve a lakások tisztességes felosztásának eredeti problémájához, szóba jöhet a véletlen mechanizmusa . A véletlenszerűségi mechanizmus egy valószínűségi eloszlást ad vissza a szobák eloszlására és a fizetés eloszlására. A véletlenszerűségi mechanizmus tisztességes elvárás , ha egyetlen partner sem növeli a hasznosság várható értékét azzal, hogy hamisan adja meg a szobák értékelését. A véletlenszerűségi mechanizmus méltányossága többféleképpen mérhető [6] :

1. Az irigység előzetes hiánya azt jelenti, hogy nincs olyan partner, aki irigyelné a sorshúzással bármely másik partner szobáját. Ez a feltétel triviális teljesítése: minden eloszlást egyenlő valószínűséggel választunk ki, és minden partnerhez összköltségdíjat rendelünk. De ennek a feltételnek nem sok haszna van, mivel nagy az esély arra, hogy sok partner féltékeny lesz a végső elosztásnál. Lehet, hogy nem elégedettek azzal, hogy a lottó tisztességes volt.

2. Az irigységmentesség garantált valószínűsége ( GPEF  ) azt jelenti, hogy van egy bizonyos valószínűség , amelynél a résztvevők értékelésétől függetlenül legalább nem lesz irigység a végső döntésben. A GVOZ-t a következő módon lehet megszerezni: irigység nélkül megtaláljuk a terjesztést; véletlenszerűen kiválasztunk egy egész számot , és a ciklus partnereit áthelyezzük a jobb oldali helyiségbe. Ez a véletlenszerű mechanizmus méltányos, mivel minden partner azonos valószínűséggel tartózkodik minden szobában, és egy várható ár a teljes költségben, függetlenül a partner bejelentett áraitól. Az eloszlás CV megszerzésének valószínűsége egyenlő annak valószínűségével, hogy , ami pontosan egyenlő . Ez nem különösebben biztató, mivel a partnerek számának növekedésével annak valószínűsége, hogy nem lesz féltékeny, 0-ra hajlik, de nincs mód arra, hogy jobb legyen, mivel a GVOA egyetlen becsületes elvárás mechanizmusában sem haladja meg a .

3. Az irigységmentes partnerek várható száma ( ENEF ) azt jelenti, hogy van valamilyen egész szám , így ha meghatározzuk azoknak a partnereknek a számát, akik nem irigylik a mechanizmus összes lehetséges kimenetelét, a becslésektől függetlenül a partnerek nem haladják meg a várakozást . A POCH teszt alkalmasabbnak tűnik, mint a HLOT teszt, mert nemcsak az irigység teljes hiányának valószínűségét méri, hanem azon esetek minőségét is, amikor a terjesztés nem teljesen mentes az irigységtől. Egy becsületes függőben lévő mechanizmus maximális OCHBZ értéke nem haladja meg a . Lehetőség van erre a szegélyre . Létezik ugyanis egy őszinte várakozási mechanizmus, amely majdnem eléri ezt a határt – a TWBZ egyenlő a . A fő gondolat a következő. A Vickrey-Clark-Groves mechanizmus segítségével kiszámítjuk a megbízást a maximális összeggel és a kifizetések összegével. Véletlenszerűen válasszon partnert. Hagyja figyelmen kívül ezt a partnert, és használja újra a Vickrey-Clark-Groves mechanizmust. Az eredményeket úgy kombináljuk, hogy garantáljuk a teljes költség teljes kifizetésének egyenlőségét (a részleteket lásd a cikkben). Meg lehet mutatni, hogy  

a) a mechanizmus tisztességes folyamatban van (b) minden partner, kivéve azt, akit figyelmen kívül hagynak, nem lesz féltékeny

Ezért az OCHBZ egyenlő . A modellezés azt mutatja, hogy az esetek körülbelül 80%-ában a HLH nem haladja meg ezt a mechanizmust .

Andersson és Svensson: Részleges sebezhetetlenség megszerzése

A sérthetetlenségi követelmény lehetséges enyhítése a "manipulálhatóság fokának" minimalizálására tett kísérlet [27] . Ezt úgy határozzák meg, hogy minden esetben megszámolják a szabályokat manipulálni képes ügynökök számát. A legelőnyösebb igazságos elosztási szabályokat minimálisan manipulálják (egyénileg és koalícióban egyaránt), mind a méltányosság, mind a költségvetési egyensúly szempontjából. Az ilyen szabályok az összes igazságos és kiegyensúlyozott eloszlás közül azt a disztribúciót választják ki, amelynek maximális számú ügynöke a maximális hasznosság.

Lásd még

Jegyzetek

  1. ↑ 1 2 Su, 1999 , p. 930–942.
  2. ↑ 1 2 3 Azrieli, Shmaya, 2014 , p. 128.
  3. ↑ Potthoff, 2002 , p. 405.
  4. ↑ 1 2 3 4 Sung, Vlach, 2004 .
  5. ↑ 1 2 Abdulkadiroğlu, Sönmez, Ünver, 2004 , p. 515.
  6. ↑ 1 2 Dufton, Larson, 2011 , p. 34–39.
  7. ↑ 1 2 Haake, Raith, Su, 2002 , p. 723.
  8. ↑ 1 2 Brams, 2008 , p. 305–328.
  9. ↑ Itt a gyengén szó azt jelenti, hogy a partner esetleg nem különböztet meg egy másik szoba + fizetési preferencia csomagot a megadotttól. Ha a partner nem tekinti egyenlőnek a csomagokat, akkor a szigorúan jobb kifejezést használják.
  10. ↑ Sun Albert . A bérleti díj felosztásához kezdje egy háromszöggel . Archiválva : 2020. november 11. Letöltve: 2014. augusztus 26.
  11. ↑ Ariel Procaccia. Tisztességes megosztottság és a nyafogó filozófusok problémája . Turing láthatatlan keze (2012. augusztus 15.). Letöltve: 2014. augusztus 26. Az eredetiből archiválva : 2014. szeptember 3..
  12. ↑ Francis Su's Fair Division oldal (a hivatkozás nem elérhető) . Math.hmc.edu . Letöltve: 2017. január 5. Az eredetiből archiválva : 2018. október 27.. 
  13. ↑ Oszd meg igazságosan a lakbért . Az eredetiből archiválva : 2019. december 31. Letöltve: 2017. január 5.
  14. ↑ Brams, 2008 , p. 320–321.
  15. ↑ Sung, Vlach, 2004 , p. 110–111.
  16. ↑ Brams, 2008 , p. 318–319.
  17. ↑ Brams, Kilgour, 2001 , p. 418.
  18. ↑ Brams, 2008 , p. 321.
  19. ↑ Haake, Raith, Su, 2002 , p. 746.
  20. ↑ Abdulkadiroğlu, Sönmez, Ünver, 2004 , p. 525-528.
  21. ↑ Szobák hozzárendelése és bérbeadás megosztása - Spliddit . Letöltve: 2016. március 5. Az eredetiből archiválva : 2016. március 5..
  22. ↑ Gal, Mash, Procaccia, Zick, 2016 , p. 67–84.
  23. ↑ Procaccia, Velez, Yu, 2018 .
  24. ↑ Sun, Yang, 2003 , p. 73.
  25. ↑ Andersson, Svensson, 2008 , p. 350.
  26. ↑ Andersson, 2009 , p. 1719–1724
  27. ↑ Andersson, Ehlers, Svensson, 2014 , p. 753.

Irodalom