Adapting Stable Matchings to Evolving Preferences

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00341903" target="_blank" >RIV/68407700:21240/20:00341903 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1609/aaai.v34i02.5550" target="_blank" >https://doi.org/10.1609/aaai.v34i02.5550</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/aaai.v34i02.5550" target="_blank" >10.1609/aaai.v34i02.5550</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Adapting Stable Matchings to Evolving Preferences

Popis výsledku v původním jazyce

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

Název v anglickém jazyce

Adapting Stable Matchings to Evolving Preferences

Popis výsledku anglicky

Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the AAAI Conference on Artificial Intelligence

ISBN

—

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

8

Strana od-do

1830-1837

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

New York

Datum konání akce

7. 2. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—