Matchande utan avundsjuka

Avundsfri matchning ( EFM) är en  matchning mellan människor och "objekt" där det inte finns någon avund i den meningen att ingen av personerna har en önskan att byta till ett "objekt" som tillhör en annan person. Termen används i flera olika sammanhang. Nedan betyder förkortningen OZ No Envy , och PbZ betyder Matching without Envy .

På marknaden med pengar

Tänk på en marknad där det finns flera köpare och flera objekt, och varje objekt kan ha ett pris. Givet en prisvektor har varje kund en förfrågningsuppsättning — uppsättningen uppsättningar som maximerar kundens användbarhet jämfört med andra uppsättningar (denna uppsättning kan innehålla en tom uppsättning om kunden tycker att alla uppsättningar är för dyra).

En avundsfri matchning (med en prisvektor) är en matchning där varje agent får en uppsättning från sin uppsättning uppsättningar. Det betyder att ingen agent vill ta emot en annan agents paket för samma pris [1] . Ett exempel på sådana villkor är problemet med rimlig hyra — matchning av hyresgäster (ombud) med bostäder (objekt) i närvaro av ett pris för varje bostad.

Avundsfria priser är vektorn av priser för vilka det finns en avundsfri matchning. Detta är en försvagning av den walrasiska jämvikten — den walrasiska jämvikten består av kostnaden PV och den matchande CV:n, och dessutom måste varje objekt antingen inkluderas i matchningen eller ha ett nollpris. Det är känt att i den walrasiska jämvikten maximerar matchningen summan av värdena, det vill säga detta är matchningen av maximal vikt . Säljarens inkomst kan dock vara låg. Detta inducerar en prislättnad i OZ, där säljaren kan använda de lägsta acceptabla priserna för att öka intäkterna [2] [3] [4] [5] [6] [7] .

På en marknad utan pengar

Tänk på problemet med att kombinera läkare för att arbeta på kliniker. Varje läkare har en preferens för kliniker (han har en jämförande uppfattning om kliniker från dåliga till bra), och varje klinik har en preferens för läkare (rankar läkare från bäst till sämst). Varje läkare måste arbeta på högst en klinik och varje klinik kan anställa ett fast antal läkare (kallas klinikens kapacitet ). Vi måste ordna läkare till kliniker. Växling av pengar är inte tillåtet. Det finns två fall där ett sådant arrangemang kan vara "dåligt":

  1. En matchning har rimlig avund om det finns en läkare d och en klinik h så att d föredrar h framför det nuvarande jobbet och klinik h föredrar läkare d framför en av de nuvarande anställda.
  2. En matchning är tom om det finns en läkare d och en klinik h så att d föredrar klinik h framför det nuvarande jobbet, och klinik h har några lediga platser och h föredrar att anställa d än att lämna platsen tom.

En matchning utan avund är en matchning utan berättigad avund. En sådan matchning är en försvagning av matchningsstabilitetsvillkoret - en stabil matchning är både fri från avund och har inga tomrum.

Gitterstruktur

I många-till-en-matchningsproblemet finns stabila matchningar och kan hittas med hjälp av Gale-Shapley-algoritmen . Därför finns OZ också. I allmänhet kan det finnas många olika OD-matchningar. Uppsättningen av alla OD-matchningar är ett gitter . Uppsättningen av stabila matchningar (som är en delmängd av OD-matchningar) är en fast punkt för Tarski-operatorn på detta gitter [8] .

Övre och undre kvoter

Ofta har kliniker inte bara övre kvoter (kapacitet), utan även lägre kvoter - varje klinik måste anställa ett visst minsta antal läkare [9] . I sådana problem kan det hända att stabila matchningar inte existerar (även om det är lätt att kontrollera om det finns en stabil matchning genom lantklinikernas teorem , enligt vilket antalet läkare som tilldelats varje klinik är detsamma i alla stabila matchningar). Under sådana förhållanden är det naturligt att kontrollera om det finns en OD-matchning. En nödvändig förutsättning är att summan av alla lägre kvoter inte får vara större än antalet läkare (annars finns det ingen genomförbar lösning alls). I det här fallet, om alla läkare-mottagningspar är acceptabla (varje läkare föredrar att arbeta någonstans och inte vara arbetslös, och varje klinik föredrar att anställa någon läkare så att det inte råder brist på personal), så existerar alltid OD-matchningen [9 ] .

Om inte alla par är acceptabla, kanske en OD-matchning inte existerar. Du kan få reda på existensen av PbZ på följande sätt. Låt oss skapa ett nytt problem där de övre kvoterna är lika med de lägre kvoterna för det ursprungliga problemet, och de lägre kvoterna är lika med 0. I detta nya problem finns alltid en stabil matchning och kan hittas effektivt. Det ursprungliga problemet har en OD-matchning om och endast om någon klinik fylls i det nya problemet [10] .

Algoritmen kan förbättras för att hitta den maximala EP för matchningen [11] .

Avundsminimering

Som definierats ovan utesluter matchning utan avund berättigad avund , där läkare d är avundsjuk på en annan läkare som har blivit tilldelad klinik h som d föredrar. Men även i PbZ kan det finnas en läkare d och en klinik h så att d föredrar h , även om en annan läkare är anvisad till den, men h ser inte läkare d som en ersättning för vissa av sina befintliga anställda. Detta kan kallas "orimlig avundsjuka". Matchning utan avund alls existerar endast i sällsynta fall, när varje läkare kan utses till den plats som han föredrar mest. När en sådan "helt avundsfri matchning" inte existerar är det rimligt att hitta matchningar som minimerar "avundsmängden". Det finns flera sätt att mäta avundens storlek, som summan av alla läkares avundsjuka eller maximal avund [12] .

I tvådelade grafer

I en oviktad tvådelad graf är en avundsfri matchning en matchning där ingen av de matchande hörnen från X är intill en matchande vertex från Y [13] . Föreställ dig att X -punkten representerar människor och Y -punkten representerar hus, och kanten mellan person x och hus y representerar det faktum att x skulle vilja bo i y . Då är PbZ en partiell fördelning av hus för människor, så att varje hemlös person inte avundas personen med huset, eftersom han inte vill bo i något av de erbjudna husen.

All matchning som mättar X har ingen avundsjuka, och all tom matchning har ingen avund.

Dessutom, om (var är uppsättningen av grannar till X i Y ), så medger G en icke-tom PbZ.

Detta är en försvagning av Halls tillstånd , som säger att om för någon delmängd X ' av en mängd X , så finns det en fullständig uppdelning av X i par.

När du skär kakan

Termen avundsfri matchning användes också i ett annat sammanhang, i en algoritm för att förbättra effektiviteten av en avundsjuk kakskärning [14] .

Se även

Anteckningar

  1. ↑ Alaei, Jain, Malekian, 2010 .
  2. ↑ Guruswami, Hartline, Karlin et al., 2005 , sid. 1164–1173.
  3. ↑ Briest, 2008 , sid. 808–819.
  4. ↑ Chen, Ghosh, Vassilvitskii, 2011 , sid. 623–645.
  5. ↑ Wang, Lu, Im, 2010 , sid. 483–491.
  6. ↑ Feldman, Fiat, Leonardi, Sankowski, 2012 , sid. 532–549.
  7. ↑ Chen, Deng, 2014 , sid. 7:1–7:15.
  8. ↑ Wu, Roth, 2018 , sid. 201–211.
  9. ↑ 1 2 Fragiadakis, Iwasaki, Troyan et al., 2016 , sid. 6:1–6:40.
  10. ↑ Yokoi, 2017 .
  11. ↑ Hur bra är populära matchningar? . www.cse.iitm.ac.in. _ Hämtad 16 januari 2019. Arkiverad från originalet 17 januari 2019.
  12. ↑ Tadenuma, 2011 , sid. 155–167.
  13. ↑ Segal-Halevi, Aigner-Horev, 2019 .
  14. ↑ Sen, Nuchia, 2001 , sid. 277–289.

Litteratur