Abstrakt. Vi studerar okoordinerade matchande marknader med ytterligare lokala begränsningar som fångar upp t.ex. begränsad information, synlighet eller externa effekter på marknaderna. Varje agent är en nod i ett fast matchande nätverk och strävar efter att matchas med en annan agent. Varje agent har en komplett preferenslista över alla andra agenter det kan matchas med. Men, beroende på begränsningar och det nuvarande läget i spelet, inte alla möjliga partners är tillgängliga för matchning hela tiden. För korrelerade preferenser föreslår och studerar vi en allmän klass av hedoniska koalitionsformationsspel som vi kallar koalitionsformationsspel med begränsningar. Denna klass omfattar och utökar många nyligen studerade varianter av stabil matchning, såsom lokalt stabil matchning, socialt stabil matchning, eller vänskapsmatchning. Kanske överraskande visar vi att alla dessa varianter är inneslutna i en klass av "konsistenta" instanser som alltid tillåter en polynom förbättring sekvens till ett stabilt tillstånd. Dessutom visar vi att för konsekventa fall finns det alltid en polynom sekvens till varje nåbart tillstånd. Vår karakterisering är snäv i den meningen att vi ger exponentiella lägre gränser när var och en av kraven för konsekvens kränks. Vi analyserar även matchning med okorrelerade preferenser, där vi får ett större utbud av resultat. Medan socialt stabil matchning alltid tillåter en polynom sekvens till ett stabilt tillstånd, för andra klasser är olika ytterligare antaganden tillräckliga för att garantera samma resultat. För problemet med att nå ett givet stabilt tillstånd, visar vi NP-hårdhet i nästan alla anses klasser av matchande spel.
Vårt senaste arbete REF visar att beslut Path-To-Stability till en given stabil matchning blir NP-hård.
Matching Dynamics with Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}