Yhteensopiva ilman kateutta

Envy - free matching ( EFM) on  ihmisten ja "objektien" välinen sovitus, jossa ei ole kateutta siinä mielessä, että kenelläkään ihmisistä ei ole halua vaihtaa "esineeseen", joka kuuluu toiselle henkilölle. Termiä käytetään useissa eri yhteyksissä. Alla lyhenne OZ tarkoittaa Ei kateutta ja PbZ tarkoittaa Matching without Envy .

Markkinoilla rahalla

Harkitse markkinoita, joilla on useita ostajia ja useita esineitä, ja jokaisella esineellä voi olla hinta. Kun hintavektori on annettu, jokaisella asiakkaalla on pyyntöjoukko – joukko sarjoja, jotka maksimoivat asiakkaan hyödyllisyyden muihin sarjoihin verrattuna (tämä joukko voi sisältää tyhjän joukon, jos asiakkaan mielestä kaikki sarjat ovat liian kalliita).

Kateeton sovitus (hintavektorin mukaan) on sovitus, jossa jokainen agentti saa joukon joukostaan. Tämä tarkoittaa, että yksikään agentti ei halua saada toisen agentin pakettia samaan hintaan [1] . Esimerkki tällaisista ehdoista on oikeudenmukaisen vuokran ongelma – vuokralaisten (agenttien) ja asunnon (kohteiden) yhdistäminen siten, että jokaisesta asunnosta on hinta.

Kadeteettomat hinnat ovat hintojen vektori, joille on olemassa kateudeton vastaavuus. Tämä on Walrasian tasapainon heikkeneminen — Walrasian tasapaino koostuu kustannus-PV:stä ja vastaavasta CV:stä, ja lisäksi jokaisen kohteen on joko sisällytettävä vastaavuuteen tai sen hinta on nolla. Tiedetään, että walrasilaisessa tasapainossa sovitus maksimoi arvojen summan, eli tämä on maksimipainon sovitus . Myyjän tulot voivat kuitenkin olla pienet. Tämä saa aikaan hintojen keventämisen OZ:ssa, jolloin myyjä voi käyttää hyväksyttäviä vähimmäishintoja tulojen lisäämiseen [2] [3] [4] [5] [6] [7] .

Markkinoilla ilman rahaa

Harkitse ongelmaa yhdistää lääkärit työskentelemään klinikoilla. Jokainen lääkäri suosii klinikoita (hänellä on vertaileva mielipide klinikoista huonoista hyviin), ja jokainen klinikka suosii lääkäreitä (lääkäreiden luokittelu parhaista huonoimpaan). Jokaisen lääkärin on työskenneltävä enintään yhdessä klinikalla, ja jokainen klinikka voi työllistää kiinteän määrän lääkäreitä (kutsutaan klinikan kapasiteetiksi ). Meidän on järjestettävä lääkärit klinikoille. Rahanvaihto ei ole sallittua. On olemassa kaksi tapausta, joissa tällainen järjestely voi olla "huono":

  1. Vastaaminen on kohtuullista kateutta , jos on lääkäri d ja klinikka h siten, että d pitää h nykyistä työtä parempana ja klinikka h suosii lääkäriä d jonkin nykyisen työntekijän sijaan.
  2. Vastaavuus on tyhjä , jos siellä on lääkäri d ja klinikka h siten, että d suosii klinikkaa h nykyiseen työpaikkaan, ja klinikalla h on avoimia työpaikkoja ja h mieluummin palkkaa d kuin jättää paikan tyhjäksi.

Sovittelu ilman kateutta on sovitus ilman perusteltua kateutta. Tällainen yhteensopivuus heikentää yhteensopivuuden vakausehtoa – vakaa yhteensopivuus on sekä kateudeton että siinä ei ole tyhjiä kohtia.

Hilarakenne

Useita yhteen -sovitusongelmassa on olemassa stabiileja vastaavuuksia, ja ne voidaan löytää käyttämällä Gale-Shapley-algoritmia . Siksi myös OZ on olemassa. Yleisesti ottaen voi olla monia erilaisia ​​OD-sovituksia. Kaikkien OD-sovitusten joukko on hila . Stabiilisovitusten joukko (joka on OD-sovitusten osajoukko) on Tarski-operaattorin kiinteä piste tässä hilassa [8] .

Ylä- ja alakiintiöt

Usein klinikoilla ei ole vain yläkiintiöitä (kapasiteettia), vaan myös pienempiä kiintiöitä - jokaisen klinikan on palkattava tietty vähimmäismäärä lääkäreitä [9] . Tällaisissa ongelmissa stabiileja vastaavuuksia ei välttämättä ole olemassa (vaikka on helppo tarkistaa, onko stabiili vastaavuus olemassa maaseutuklinikan lauseella , jonka mukaan jokaiselle klinikalle määrättyjen lääkäreiden määrä on sama kaikissa stabiileissa vastaavuuksissa). Tällaisissa olosuhteissa on luonnollista tarkistaa, onko OD-sovitus olemassa. Välttämätön edellytys on, että kaikkien alempien kiintiöiden summa ei saa olla suurempi kuin lääkäreiden lukumäärä (muuten ei ole mitään toteuttamiskelpoista ratkaisua). Tässä tapauksessa, jos kaikki lääkäri-klinikka-parit ovat hyväksyttäviä (jokainen lääkäri haluaa mieluummin työskennellä jossain eikä olla työttömänä, ja jokainen klinikka haluaa palkata jonkun lääkärin, jotta henkilöstöstä ei ole pulaa), OD-sovitus on aina olemassa [9 ] .

Jos kaikki parit eivät ole hyväksyttäviä, OD-sovitusta ei ehkä ole olemassa. Voit saada selville PbZ:n olemassaolosta seuraavalla tavalla. Tehdään uusi ongelma, jossa yläkiintiöt ovat yhtä suuret kuin alkuperäisen ongelman alemmat kiintiöt ja alemmat 0. Tässä uudessa tehtävässä vakaa vastaavuus on aina olemassa ja se voidaan löytää tehokkaasti. Alkuperäisellä ongelmalla on OD-sovitus silloin ja vain, jos jokin klinikka täytetään uudessa tehtävässä [10] .

Algoritmia voidaan parantaa vastaavuuden maksimi EP:n löytämiseksi [11] .

Envy Minimization

Kuten edellä on määritelty, sovittaminen ilman kateutta sulkee pois oikeutetun kateuden , jossa lääkäri d on mustasukkainen toiselle lääkärille, joka on määrätty klinikalle h , jota d suosii. Kuitenkin jopa PbZ:ssä voi olla lääkäri d ja klinikka h siten, että d suosii h :ta, vaikka sille on määrätty toinen lääkäri, mutta h ei näe lääkäriä d joidenkin nykyisten työntekijöiden sijaisena. Tätä voidaan kutsua "kohtuuttomaksi kateudeksi". Täsmäys ilman kateutta on olemassa vain harvoissa tapauksissa, jolloin jokainen lääkäri voidaan nimittää siihen paikkaan, jota hän eniten haluaa. Kun tällaista "täysin kateudetonta vastaavuutta" ei ole olemassa, on järkevää löytää vastineita, jotka minimoivat "kateuden määrän". On olemassa useita tapoja mitata kateuden suuruutta, kuten kaikkien lääkäreiden kateuden summa tai kateuden enimmäismäärä [12] .

Kaksiosaisissa kaavioissa

Painottamattomassa kaksiosaisessa graafissa kateudeton sovitus on sovitus , jossa mikään X :n sovituspisteistä ei ole Y :n sovituspisteen vieressä [13] . Kuvittele, että X -pisteet edustavat ihmisiä ja Y -pisteet taloja, ja henkilön x ja talon y välinen reuna edustaa sitä, että x haluaisi asua y :ssä . Silloin PbZ on talojen osittainen jako ihmisille siten, että jokainen koditon ei kadehdi asukkaalle, koska hän ei halua asua missään tarjotuista taloista.

Missään X :ää tyydyttävässä vastaavuudessa ei ole kateutta, eikä millään tyhjällä vastaavuudella ole kateutta.

Lisäksi, jos (missä on X : n naapureiden joukko Y :ssä ), niin G hyväksyy ei-tyhjän PbZ:n.

Tämä on Hallin ehdon heikkeneminen , joka sanoo, että jos jollekin joukon X osajoukolle X ' on olemassa X :n täydellinen osiointi pareiksi.

Kakun leikkaamisessa

Termiä kateudeton sovitus käytettiin myös toisessa yhteydessä, algoritmissa, jolla parannettiin kateellisen kakun leikkaamisen tehokkuutta [14] .

Katso myös

Muistiinpanot

  1. ↑ Alaei, Jain, Malekian, 2010 .
  2. ↑ Guruswami, Hartline, Karlin et ai., 2005 , s. 1164-1173.
  3. ↑ Briest, 2008 , s. 808–819.
  4. ↑ Chen, Ghosh, Vassilvitskii, 2011 , s. 623–645.
  5. ↑ Wang, Lu, Im, 2010 , s. 483–491.
  6. ↑ Feldman, Fiat, Leonardi, Sankowski, 2012 , s. 532–549.
  7. ↑ Chen, Deng, 2014 , s. 7:1–7:15.
  8. ↑ Wu, Roth, 2018 , s. 201–211.
  9. ↑ 1 2 Fragiadakis, Iwasaki, Troyan et ai., 2016 , s. 6:1–6:40.
  10. ↑ Yokoi, 2017 .
  11. ↑ Kuinka hyviä ovat Popular Matchings? . www.cse.iitm.ac.in. _ Haettu 16. tammikuuta 2019. Arkistoitu alkuperäisestä 17. tammikuuta 2019.
  12. ↑ Tadenuma, 2011 , s. 155-167.
  13. ↑ Segal-Halevi, Aigner-Horev, 2019 .
  14. ↑ Sen, Nuchia, 2001 , s. 277-289.

Kirjallisuus