Sammanfattning Historiskt har analysen av matchning centrerat sig på att utforma algoritmer för att producera stabila matchningar samt på att analysera incitamentkompatibiliteten hos matchningsmekanismer. Mindre uppmärksamhet har ägnats åt frågor som rör social välfärd för stabila matchningar i kardinal nyttomodeller. Vi undersöker den förlust i social välfärd som uppstår genom att kräva matchningar för att vara stabil, det naturliga jämviktsbegreppet under individuell rationalitet. Även om denna förlust kan vara godtyckligt dålig under allmänna preferenser, när det finns någon struktur till den underliggande grafen som motsvarar naturliga villkor på preferenser, vi bevisa värsta fall gränser på priset på anarki. Förvånansvärt nog, under enkla distributioner av verktyg, visar sig den genomsnittliga fallförlusten vara betydligt mindre än den värsta analysen skulle tyda på. Dessutom har vi förutsättningar för att det ska finnas ungefär stabila matchningar som också är nära socialt optimala, vilket visar att tillägg av små växlingskostnader kan göra socialt (nära) optimala matchningar stabila. Vår analys leder till flera samtidiga resultat av intresse för konvergensen av decentraliserade partnerskiftande algoritmer, och på inverkan av heterogenitet av smaker på social välfärd.
I REF tillhandahölls priset på anarki och stabilitetsgränser för ungefärliga korrelerade stabila matchningar.
Anarchy, stability, and utopia: creating better matchings
{'venue': 'Autonomous Agents and Multi-Agent Systems', 'journal': 'Autonomous Agents and Multi-Agent Systems', 'mag_field_of_study': ['Computer Science']}