Egyezés irigység nélkül

Az irigységmentes párosítás ( EFM) az emberek és a "tárgyak" közötti  párosítás, amelyben nincs irigység abban az értelemben, hogy egyik embernek sem vágyik átváltani egy másik személyhez tartozó "tárgyra". A kifejezést többféle összefüggésben használják. Az alábbiakban az OZ rövidítés azt jelenti , hogy nincs irigység , a PbZ pedig azt, hogy irigység nélkül felel meg .

A piacon pénzzel

Vegyünk egy olyan piacot, ahol több vevő és több tárgy is van, és minden tárgynak lehet ára. Adott egy árvektor, minden ügyfélnek van egy kéréskészlete – azon halmazok halmaza, amelyek maximalizálják az ügyfél hasznosságát a többi készlethez képest (ez a halmaz tartalmazhat üres halmazt, ha az ügyfél úgy gondolja, hogy az összes készlet túl drága).

Az irigységmentes párosítás (adott árvektor) olyan egyeztetés, amelyben minden ügynök egy halmazt kap a halmazaiból. Ez azt jelenti, hogy egyetlen ügyintéző sem akarja megkapni egy másik ügynök csomagját ugyanazon az áron [1] . Példa az ilyen feltételekre a méltányos bérleti díj problémája – a bérlők (ügynökök) és a lakás (tárgyak) összeegyeztetése minden egyes lakás árának megléte mellett.

Az irigységmentes árak az árak azon vektora, amelyeknél létezik irigységmentes párosítás. Ez a walras-i egyensúly gyengülése – a walras-i egyensúly a PV költségből és a megfelelő CV-ből áll, és ezen felül minden objektumnak vagy szerepelnie kell az egyeztetésben, vagy nulla árat kell tartalmaznia. Ismeretes, hogy a Walras-féle egyensúlyban az illesztés maximalizálja az értékek összegét, vagyis ez a maximális súly illesztése . Az eladó jövedelme azonban alacsony lehet. Ez árcsökkentést indukál az OZ-ban, amelyben az eladó az elfogadható minimális árakat felhasználhatja a bevétel növelésére [2] [3] [4] [5] [6] [7] .

Pénz nélküli piacon

Fontolja meg az orvosok és a klinikákon végzett munka kombinálásának problémáját. Minden orvos előnyben részesíti a klinikákat (összehasonlító véleménye van a klinikákról a rossztól a jóig), és minden klinikán előnyben részesíti az orvosokat (az orvosokat a legjobbtól a legrosszabbig rangsorolja). Minden orvosnak legfeljebb egy klinikán kell dolgoznia, és minden klinika meghatározott számú orvost alkalmazhat (ezt a klinika kapacitásának nevezik). Orvosokat kell szerveznünk a klinikákra. Pénzváltás nem megengedett. Két eset van, amikor egy ilyen elrendezés "rossz" lehet:

  1. Egy megfelelő irigység akkor van, ha van egy d orvos és egy h klinika , ahol d jobban szereti h a jelenlegi állást, és h klinika d orvost részesíti előnyben az egyik jelenlegi alkalmazottal szemben.
  2. Az egyezés üres , ha van egy d orvos és egy h klinika, ahol d inkább a h klinikát részesíti előnyben a jelenlegi állásnál, és h klinikán van néhány üresedés, és h inkább felveszi d , mint üresen hagyja a helyet.

Az irigység nélküli párosítás jogos irigység nélküli párosítás. Az ilyen egyeztetés az illesztési stabilitási feltétel gyengülését jelenti – a stabil egyezés mentes az irigységtől, és nincsenek benne űrök.

Rácsszerkezet

A több az egyhez illesztési problémában léteznek stabil egyezések, amelyek a Gale-Shapley algoritmussal találhatók meg . Ezért az OZ is létezik. Általánosságban elmondható, hogy sok különböző OD egyezés létezhet. Az összes OD illesztés halmaza egy rács . A stabil illesztések halmaza (ami az OD illesztések egy részhalmaza) a Tarski-operátor fix pontja ezen a rácson [8] .

Felső és alsó kvóták

A klinikáknak gyakran nemcsak felső kvótája (kapacitása), hanem alacsonyabb kvótái is vannak - minden klinikának meghatározott minimális számú orvost kell felvennie [9] . Ilyen problémák esetén előfordulhat, hogy nem léteznek stabil párosítások (bár könnyen ellenőrizhető, hogy létezik-e stabil párosítás a vidéki klinikák tételével , amely szerint az egyes klinikákhoz rendelt orvosok száma minden stabil párosításban azonos). Ilyen körülmények között természetes annak ellenőrzése, hogy létezik-e OD egyezés. Szükséges feltétel, hogy az összes alacsonyabb kvóta összege ne haladja meg az orvosok számát (ellenkező esetben egyáltalán nincs megvalósítható megoldás). Ebben az esetben, ha minden orvos-klinika pár elfogadható (minden orvos inkább dolgozik valahol, és nem munkanélküli, és minden klinika inkább felvesz néhány orvost, hogy ne legyen személyzethiány), akkor az OD-illesztés mindig létezik [9 ] .

Ha nem minden pár elfogadható, akkor lehet, hogy nem létezik OD egyezés. A PbZ létezéséről a következő módon tájékozódhat. Hozzunk létre egy új feladatot, amelyben a felső kvóták megegyeznek az eredeti feladat alsó kvótáival, az alsó kvóták pedig 0-val. Ebben az új feladatban mindig létezik és hatékonyan megtalálható egy stabil illeszkedés. Az eredeti problémának akkor és csak akkor van OD egyezése, ha bármelyik klinikán ki van töltve az új probléma [10] .

Az algoritmus továbbfejleszthető, hogy megtaláljuk az illesztés maximális EP-jét [11] .

Irigység minimalizálása

A fent meghatározottak szerint az irigység nélküli párosítás kizárja az indokolt irigységet , amikor d orvos féltékeny egy másik orvosra, akit a h klinikára osztottak be, akit d szeretne. Azonban még PbZ-ben is lehet d orvos és h klinika , ahol d inkább h -t részesíti előnyben , bár másik orvost rendelnek hozzá, de h nem látja d orvost néhány meglévő alkalmazottja helyett. Ezt nevezhetjük „indokolatlan irigységnek”. Az irigység nélküli párosítás csak ritka esetekben létezik, amikor minden orvost arra a helyre lehet kinevezni, amelyet a legjobban szeret. Ha ilyen „teljesen irigységmentes párosítás” nem létezik, ésszerű olyan párosítást találni, amely minimalizálja az „irigység mértékét”. Az irigység mértékének mérésére többféle módszer létezik, például az összes orvos irigységének összege vagy a maximális irigység [12] .

Kétrészes gráfokban

Súlyozatlan kétrészes gráfban az irigységmentes illesztés olyan illesztés , amelyben az X -ből származó illeszkedő csúcsok egyike sem szomszédos Y egyező csúcsával [13] . Képzeljük el, hogy az X csúcsok az embereket, az Y csúcsok pedig a házakat, az x személy és az y ház közötti él pedig azt a tényt jelenti, hogy x szeretne y -ben lakni . Ekkor a PbZ egy részleges házak szétosztása embereknek, úgy, hogy minden hajléktalan ne irigyelje a házat, mert nem akar a felajánlott házak egyikében sem lakni.

Bármilyen egyezés, amely telíti X -et, nem irigykedik, és minden üres egyezésnek nincs irigysége.

Sőt, ha (hol van X szomszédainak halmaza Y -ban ), akkor G beenged egy nem üres PbZ-t.

Ez a Hall-feltétel gyengülése , amely azt mondja, hogy ha egy X halmaz bármely X ' részhalmazára , akkor létezik X teljes felosztása párokra.

A torta felvágásában

Az irigységmentes párosítás kifejezést egy másik kontextusban is használták, az irigy tortavágás hatékonyságát javító algoritmusban [14] .

Lásd még

Jegyzetek

  1. ↑ Alaei, Jain, Malekian, 2010 .
  2. ↑ Guruswami, Hartline, Karlin et al., 2005 , p. 1164–1173.
  3. ↑ Briest, 2008 , p. 808–819.
  4. ↑ Chen, Ghosh, Vassilvitskii, 2011 , p. 623–645.
  5. ↑ Wang, Lu, Im, 2010 , p. 483–491.
  6. ↑ Feldman, Fiat, Leonardi, Sankowski, 2012 , p. 532–549.
  7. ↑ Chen, Deng, 2014 , p. 7:1–7:15.
  8. ↑ Wu, Roth, 2018 , p. 201–211.
  9. ↑ 1 2 Fragiadakis, Iwasaki, Troyan et al., 2016 , p. 6:1–6:40.
  10. ↑ Yokoi, 2017 .
  11. ↑ Mennyire jók a népszerű egyezések? . www.cse.iitm.ac.in. _ Letöltve: 2019. január 16. Az eredetiből archiválva : 2019. január 17.
  12. ↑ Tadenuma, 2011 , p. 155–167.
  13. ↑ Segal-Halevi, Aigner-Horev, 2019 .
  14. ↑ Sen, Nuchia, 2001 , p. 277–289.

Irodalom