Necessarily Optimal One-Sided Matchings
We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects. We focus on two popular desiderata from the matching literature: Pareto optimality and rank-maximality. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences, specifically a matching that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM) under any completion of the partial preferences. We focus on the top-$k$ model in which agents reveal a prefix of their preference rankings. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences. We also study online algorithms for eliciting partial preferences adaptively, and prove bounds on their competitive ratio.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time ste…
Stable Matching with Ties: Approximation Ratios and Learning
We study the problem of matching markets with ties, where one side of the market does not necessarily have strict preferences over members at its other side. For example, workers do not always have strict preferences ove…
Yogurts Choose Consumers? Estimation of Random-Utility Models via Two-Sided Matching
The problem of demand inversion - a crucial step in the estimation of random utility discrete-choice models - is equivalent to the determination of stable outcomes in two-sided matching models. This equivalence applies t…
Discrete Choice ModelsUnique Stable Matchings
In this paper we consider the issue of a unique prediction in one to one two sided matching markets, as defined by Gale and Shapley (1962), and we prove the following. Theorem. Let P be a one-to-one two-sided matching ma…
Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty
We consider a learning problem for the stable marriage model under unknown preferences for the left side of the market. We focus on the centralized case, where at each time step, an online platform matches the agents, an…