Huis toewijzing probleem - House allocation problem

In de economie en informatica is het huistoewijzingsprobleem het probleem van het toewijzen van objecten aan mensen met verschillende voorkeuren , zodat elke persoon precies één object ontvangt. De naam "huistoewijzing" komt van de belangrijkste motiverende toepassing, namelijk het toewijzen van slaapzalen aan studenten. Andere veelgebruikte termen zijn toewijzingsprobleem en eenzijdige matching . Bij huistoewijzingsproblemen wordt aangenomen dat geldoverdrachten niet zijn toegestaan; de variant waarin geldoverdrachten zijn toegestaan, staat bekend als huurharmonie .

definities

Er zijn n mensen (ook wel: agenten ), en m objecten (ook wel: huizen ). De makelaars kunnen verschillende voorkeuren hebben boven de huizen. Ze kunnen hun voorkeuren op verschillende manieren uiten:

• Binaire waarderingen : elke makelaar waardeert elk huis op 1 (wat betekent dat de makelaar het huis leuk vindt), of 0 (wat betekent dat de makelaar het huis niet leuk vindt).
• Voorkeursrangschikking : elke makelaar rangschikt de huizen van goed naar slecht. De rangschikking kan streng (geen onverschilligheden) of zwak (onverschilligheden toegestaan) zijn.
• Kardinaal nut : elke agent kent een niet-negatieve numerieke waarde toe aan elk huis.

Verschillende overwegingen kunnen van belang zijn bij het ontwerpen van algoritmen voor huistoewijzing.

• Pareto-efficiëntie (PE) - geen enkele andere toewijzing is beter voor sommige agenten en niet slechter voor alle agenten.
• Eerlijkheid - kan op verschillende manieren worden gedefinieerd, bijvoorbeeld afgunstvrijheid (EF) - geen enkele agent mag jaloers zijn op een andere agent.
• Strategyproofness (SP) - elke agent heeft een prikkel om zijn/haar ware voorkeuren aan het algoritme te melden.
• Individuele rationaliteit (IR) - geen enkele agent mag verliezen door deelname aan het algoritme.

Efficiënte toewijzingen

In de economie is PE de primaire efficiëntievereiste in huistoewijzing. Er zijn verschillende algoritmen die een PE-toewijzing in verschillende instellingen bereiken.

Waarschijnlijk is het eenvoudigste algoritme voor het toewijzen van huizen de seriële dictatuur : de agenten worden in een willekeurige volgorde gerangschikt (bijvoorbeeld op basis van anciënniteit), en elke agent kiest op zijn beurt het best overblijvende huis volgens zijn/haar voorkeuren. Dit algoritme is duidelijk SP. Als de voorkeuren van de agenten strikt zijn, vindt het een PE-toewijzing. Het kan echter erg oneerlijk zijn tegenover de agenten die als laatste kiezen. Het kan (in verwachting) eerlijker worden gemaakt door de volgorde uniform willekeurig te kiezen; dit leidt tot het mechanisme dat willekeurige seriële dictatuur wordt genoemd . Het mechanisme is PE ex-post, maar het is niet PE ex-ante; zie eerlijke willekeurige toewijzing voor andere gerandomiseerde mechanismen die ex-ante PE zijn.

Wanneer elke makelaar al een huis bezit, zijn billijkheidsoverwegingen minder belangrijk, het is belangrijker om makelaars te garanderen dat ze niet zullen verliezen door deelname (IR). Het beste handelscyclusalgoritme is het unieke algoritme dat IR, PE en SP garandeert. Met strikte voorkeuren vindt TTC de unieke kernstabiele toewijzing.

Abdulkadiroglu en Sonmez beschouwen een uitgebreide setting waarin sommige agenten al een huis hebben, terwijl andere geen huis hebben. Hun mechanisme is IR, PE en SP. Ze presenteren twee algoritmen die dit mechanisme implementeren.

Ergin beschouwt regels die ook consistent zijn , dat wil zeggen dat hun voorspellingen niet afhankelijk zijn van de volgorde waarin de opdrachten worden gerealiseerd.

In informatica en operationeel onderzoek is de primaire efficiëntievereiste het maximaliseren van de som van hulpprogramma's. Het vinden van een huistoewijzing die de som van nutsvoorzieningen maximaliseert, is gelijk aan het vinden van een maximale gewichtsovereenkomst in een gewogen tweedelige grafiek; het wordt ook wel het toewijzingsprobleem genoemd .

Eerlijke toewijzingen

Algoritmische problemen met betrekking tot de eerlijkheid van de matching zijn in verschillende contexten bestudeerd.

Wanneer agenten binaire waarderingen hebben, definiëren hun "achtige" relaties een bipartiete grafiek op de sets van agenten en huizen. Een afgunstvrije woningtoewijzing komt overeen met een afgunstvrije matching in deze grafiek. De volgende algoritmische problemen zijn bestudeerd.

• Beslissen of er een volledige EF- toewijzing bestaat. Dit geldt als er een matching bestaat die alle agenten verzadigt; dit kan in polynomiale tijd worden bepaald door gewoon een maximale kardinaliteitsovereenkomst te vinden in de tweedelige grafiek.
• Het vinden van een gedeeltelijke EF- toewijzing van maximale kardinaliteit. Dit kan in polynomiale tijd.
• Het vinden van een gedeeltelijke EF- toewijzing van maximale kardinaliteit en minimale kosten (waarbij elke rand vooraf gespecificeerde kosten voor de samenleving heeft). Ook dit kan in polynomiale tijd.
• Het vinden van een volledige EF- toewijzing, waarbij het aantal niet-jaloerse agenten wordt gemaximaliseerd. Dit probleem is NP-moeilijk. Het bewijs is door reductie van het probleem met de minimale dekking (ook bekend als bipartiete expansie ).

Wanneer agenten kardinale waarderingen hebben , wordt de grafiek van agenten en huizen een gewogen bipartiete grafiek . De volgende algoritmische problemen zijn bestudeerd.

• Beslissen of er een volledige EF- toewijzing bestaat.
  • Als m = n , moeten alle huizen worden toegewezen, dus een toewijzing is EF als elke makelaar een huis met de hoogste waarde krijgt. Daarom is het mogelijk om de oorspronkelijke grafiek te herleiden tot een ongewogen grafiek, waarin elke makelaar alleen aan zijn hoogst gewaardeerde huizen grenst, en in deze grafiek naar een perfecte overeenkomst te zoeken.
  • Wanneer m > n , werkt het bovenstaande algoritme mogelijk niet, aangezien niet alle huizen moeten worden toegewezen: zelfs als een enkel huis de meeste voorkeur heeft van alle agenten, kan er een volledige EF-toewijzing bestaan ​​waarin dit specifieke huis niet is toegewezen. Gan, Suksompong en Voudouris presenteren een polynomiaal-tijdalgoritme dat in polynomiale tijd beslist of er een volledige EF-toewijzing bestaat voor elke m ≥ n .
• Beslissen of er een volledige lokale afgunstvrije toewijzing bestaat. Lokale jaloezie-vrijheid betekent dat de agenten zich op een sociaal netwerk bevinden en alleen hun buren in dat netwerk benijden. Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet en Wilczynski bestuderen het probleem om te beslissen of er een volledige lokale afgunstvrije toewijzing bestaat voor m = n , voor verschillende netwerkstructuren.
• Het vinden van een volledige EF- toewijzing, waarbij het aantal niet-jaloerse agenten wordt gemaximaliseerd. Onder gemeenschappelijke complexiteit theoretische veronderstelling, dit probleem is moeilijk te benaderen. In het bijzonder, als NP niet kan worden opgelost in subexponentiële tijd, dan kan het voor sommigen niet worden benaderd binnen een factor van ; als de hypothese van de uitbreiding van de kleine verzameling waar is, kan deze niet worden benaderd tot binnen een factor van voor elk (want het is triviaal om te benaderen: geef één agent zijn favoriete huis en verdeel de andere agenten willekeurig). Het bewijs is door reductie van het maximale gebalanceerde biclique- probleem.${\displaystyle n^{\gamma}}$${\displaystyle \gamma >0}$${\displaystyle n^{\gamma}}$${\displaystyle \gamma <1}$${\displaystyle \gamma =1}$
• Beslissen of er sprake is van een volledige proportionele allocatie . Dit probleem is NP-compleet, door reductie van exacte 3-set dekking .
• Beslissen of er sprake is van een volledige billijke allocatie . Dit probleem kan worden opgelost in polynomiale tijd.
• Het vinden van een gedeeltelijke EF- toewijzing van maximale kardinaliteit. De runtime-complexiteit van dit probleem is open.

Gerelateerde problemen

• Toewijzingsprobleem - elke agent moet een enkel object krijgen. Het doel is om de som van de waarderingen te maximaliseren, of de som van de kosten te minimaliseren.
• Eerlijke willekeurige toewijzing - elke agent moet een enkel object krijgen. Randomisatie is toegestaan. De toewijzing moet in de verwachting eerlijk en efficiënt zijn.
• Huurharmonie - elke agent moet een enkel object krijgen en een prijs betalen; de toewijzing van objecten + prijzen moet vrij van jaloezie zijn.
• Matching zonder afgunst - sommige agenten kunnen niet-toegewezen blijven, zolang ze geen van de toegewezen huizen leuk vinden.
• Eerlijke toewijzing van items - elke agent kan een willekeurig aantal objecten krijgen.

Referenties