Competitive Query Minimization for Stable Matching with One-Sided Uncertainty

Bampis, Evripidis; Dogeas, Konstantinos; Erlebach, Thomas; Megow, Nicole; Schlöter, Jens; Trehan, Amitabh

Abstract

We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algorithm can make queries to reveal information about the preferences of the agents in B. We examine three query models: comparison queries, interviews, and set queries. Using competitive analysis, our aim is to design algorithms that minimize the number of queries required to solve the problem of finding a stable matching or verifying that a given matching is stable (or stable and optimal for the agents of one side). We present various upper and lower bounds on the best possible competitive ratio as well as results regarding the complexity of the offline problem of determining the optimal query set given full information.

Citation

Bampis, E., Dogeas, K., Erlebach, T., Megow, N., Schlöter, J., & Trehan, A. (2024, August). Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. Presented at International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024), London, UK

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
• Start Date: Aug 28, 2024
• End Date: Aug 30, 2024
• Acceptance Date: Jul 1, 2024
• Online Publication Date: Sep 16, 2024
• Publication Date: Sep 16, 2024
• Deposit Date: Jul 16, 2024
• Publicly Available Date: Jul 18, 2024
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Peer Reviewed: Peer Reviewed
• Volume: 317
• Pages: 17:1-17:21
• Series Title: Leibniz International Proceedings in Informatics
• Series ISSN: 1868-8969
• Book Title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024
• DOI: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.17
• Public URL: https://durham-repository.worktribe.com/output/2600577