Husfordelingsproblem - House allocation problem
I økonomi og informatikk er husfordelingsproblemet problemet med å tilordne objekter til mennesker med forskjellige preferanser , slik at hver person mottar nøyaktig ett objekt. Navnet "husfordeling" kommer fra den viktigste motiverende applikasjonen, som er å tildele hybelhus til studenter. Andre vanlige termer er oppgaveproblem og ensidig matching . I husfordelingsproblemer antas det at monetære overføringer ikke er tillatt; varianten der monetære overføringer er tillatt er kjent som utleieharmoni .
Definisjoner
Det er n mennesker (også kalt: agenter ) og m -objekter (også kalt: hus ). Agentene kan ha forskjellige preferanser fremfor husene. De kan uttrykke sine preferanser på forskjellige måter:
- Binære verdivurderinger : hver agent verdsetter hvert hus til enten 1 (som betyr at agenten liker huset), eller 0 (som betyr at agenten misliker huset).
- Preferanserangering : hver agent rangerer husene fra de beste til de verste. Rangeringen kan være streng (ingen likegyldigheter) eller svak (likegyldighet tillatt).
- Kardinalverktøy : hver agent tildeler en ikke-negativ numerisk verdi til hvert hus.
Flere hensyn kan være viktige ved utformingen av algoritmer for husfordeling.
- Pareto -effektivitet (PE) - ingen annen tildeling er bedre for noen agenter og ikke verre for alle agenter.
- Rettferdighet - kan defineres på forskjellige måter, for eksempel misunnelsesfrihet (EF) - ingen agent skal misunne en annen agent.
- Strategiproofness (SP) - hver agent har et insentiv til å rapportere sine sanne preferanser til algoritmen.
- Individuell rasjonalitet (IR) - ingen agent bør tape på å delta i algoritmen.
Effektive tildelinger
Innen økonomi er det primære effektivitetskravet i husallokering PE. Det er forskjellige algoritmer som oppnår en PE -tildeling i forskjellige innstillinger.
Sannsynligvis den enkleste algoritmen for husfordeling er seriell diktatur : agentene blir ordnet i en vilkårlig rekkefølge (f.eks. Etter ansiennitet), og hver agent velger igjen det beste gjenværende huset etter hans/hennes preferanser. Denne algoritmen er åpenbart SP. Hvis agentenes preferanser er strenge, finner den en PE -tildeling. Imidlertid kan det være veldig urettferdig overfor agenter som velger sist. Det kan gjøres mer rettferdig (i forventning) ved å velge rekkefølgen jevnt og tilfeldig; dette fører til mekanismen som kalles tilfeldig seriediktatur . Mekanismen er PE ex-post, men det er ikke PE ex-ante; se rettferdig tilfeldig tildeling for andre randomiserte mekanismer som er forhånds-PE.
Når hver agent allerede eier et hus, er rettferdighetshensyn mindre viktig, det er viktigere å garantere overfor agenter at de ikke vil tape på å delta (IR). Den beste handelssyklusalgoritmen er den unike algoritmen som garanterer IR, PE og SP. Med strenge preferanser finner TTC den unike kjernestabile tildelingen.
Abdulkadiroglu og Sonmez vurderer en utvidet setting der noen agenter allerede eier et hus mens noen andre er husløse. Mekanismen deres er IR, PE og SP. De presenterer to algoritmer som implementerer denne mekanismen.
Ergin vurderer regler som også er konsistente , det vil si at deres spådommer ikke avhenger av rekkefølgen oppgavene blir utført i.
I datavitenskap og driftsforskning er det primære effektivitetskravet å maksimere summen av verktøy. Å finne en husallokering som maksimerer summen av verktøy tilsvarer å finne en maksimalvekt i en vektet todelt graf; det kalles også oppgaveproblemet .
Rettferdige tildelinger
Algoritmiske problemer knyttet til rettferdighet i matchingen har blitt studert i flere sammenhenger.
Når agenter har binære verdivurderinger, definerer deres "like" -forhold en todelt graf over settene med agenter og hus. En misunnelsesfri husallokering tilsvarer en misunnelsesfri matching i denne grafen. Følgende algoritmiske problemer er studert.
- Avgjør om det finnes en fullstendig EF -tildeling. Dette holder iff det finnes en matching som metter alle agentene; Dette kan avgjøres i polynomisk tid ved bare å finne en maksimal kardinalitetstilpasning i den topartige grafen.
- Finne en delvis EF -tildeling av maksimal kardinalitet. Dette kan gjøres på polynomtid.
- Finne en delvis EF- tildeling av maksimal kardinalitet og minimumskostnad (der hver kant har en forhåndsspesifisert kostnad for samfunnet). Dette kan også gjøres på polynomtid.
- Finne en fullstendig EF- tildeling, der antallet ikke-misunnelige agenter er maksimert. Dette problemet er NP-hardt. Beviset er ved reduksjon fra minimum dekning (aka bipartite ekspansjon ) problem.
Når agenter har kardinal verdivurderinger , blir grafen over agenter og hus en vektet todelt graf . Følgende algoritmiske problemer er studert.
- Avgjør om det finnes en fullstendig EF -tildeling.
- Når m = n , må alle hus tildeles, så en tildeling er EF hvis hver agent får et hus med den høyeste verdien. Derfor er det mulig å redusere den opprinnelige grafen til en uvektet graf, der hver agent bare ligger ved siden av sine høyest verdsatte hus, og se etter en perfekt matchning i denne grafen.
- Når m > n , fungerer kanskje ikke ovennevnte algoritme, siden ikke alle hus må tildeles: selv om et enkelt hus er mest foretrukket av alle agenter, kan det eksistere en fullstendig EF-tildeling der dette spesifikke huset ikke er tilordnet. Gan, Suksompong og Voudouris presenterer en polynom-tid-algoritme som i polynomtid avgjør om det finnes en fullstendig EF-tildeling for noen m ≥ n .
- Avgjør om det finnes en fullstendig lokal misunnelsesfri tildeling. Lokal misunnelse betyr at agentene er lokalisert på et sosialt nettverk , og de misunner bare naboene i nettverket. Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet og Wilczynski studerer problemet med å avgjøre om det finnes en fullstendig lokal misunnelsesfri tildeling for m = n , for ulike nettverksstrukturer.
- Finne en fullstendig EF- tildeling, der antallet ikke-misunnelige agenter er maksimert. Under vanlig kompleksitetsteoretisk antagelse er dette problemet vanskelig å tilnærme. Spesielt hvis NP ikke kan løses på en undereksponentiell tid, kan den ikke tilnærmes til en faktor på for noen ; Hvis den lille ekspansjonshypotesen er sann, kan den ikke tilnærmes til en faktor på for noen (for det er trivielt å tilnærme: bare gi en agent favoritthuset sitt, og fordel de andre agentene vilkårlig). Beviset er ved reduksjon fra det maksimalt balanserte biclique -problemet.
- Avgjør om det finnes en fullstendig proporsjonal tildeling . Dette problemet er NP-komplett, ved reduksjon fra eksakt 3-setts deksel .
- Avgjøre om det finnes en fullstendig rettferdig tildeling . Dette problemet kan løses på polynomtid.
- Finne en delvis EF -tildeling av maksimal kardinalitet. Kjøretidskompleksiteten til dette problemet er åpen.
Relaterte problemer
- Tildelingsproblem - hver agent må få et enkelt objekt. Målet er å maksimere summen av verdsettelser, eller minimere summen av kostnader.
- Rettferdig tilfeldig tildeling - hver agent må få et enkelt objekt. Randomisering er tillatt. Tildelingen bør være rettferdig og effektiv i forventning.
- Leie harmoni - hver agent må få et enkelt objekt og betale en pris; tildeling av objekter+priser bør være misunnelsesfri.
- Misunnelsesfri matching - noen agenter kan forbli uallokerte, så lenge de ikke liker noen av de tildelte husene.
- Rettferdig varetildeling - hver agent kan få et hvilket som helst antall objekter.
