REAL

Popular and Dominant Matchings with Uncertain and Multimodal Preferences

Csáji, Gergely Kál (2024) Popular and Dominant Matchings with Uncertain and Multimodal Preferences. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI, California, pp. 2740-2747. ISBN 9781956792041

[img]
Preview
Text
0303.pdf - Published Version

Download (163kB) | Preview

Abstract

We study the Popular Matching (PM) problem in multiple models, where the preferences of the agents in the instance may change or may be unknown or uncertain. In particular, we study an Uncertainty model, where each agent has a possible set of preference lists, a Multilayer model, where there are layers of preference profiles, and a Robust popularity model, where any agent may move some other agents up or down some places in his preference list. Our goal is always to find a matching that is popular in any possible preference profile.We study both one-sided (only one class of the agents have preferences) and two-sided bipartite markets. In the one-sided model, we show that all our problems can be solved in polynomial time by utilizing the structure of popular matchings. We also obtain nice structural results. With two-sided preferences, we show that all three above models lead to NP-hard questions for popular matchings. By using the connection between dominant matchings and stable matchings, we show that in the robust and uncertainty models, a certainly dominant matching in all possible preference profiles can be found in polynomial time, whereas in the multilayer model, the problem remains NP-hard for dominant matchings too. We also answer an open question about d-robust stable matchings.

Item Type: Book Section
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 15 Aug 2024 11:14
Last Modified: 15 Aug 2024 11:18
URI: https://real.mtak.hu/id/eprint/202595

Actions (login required)

Edit Item Edit Item