A note on the assignment problem with uniform preferences

DOI10.1016/J.ORL.2015.02.010MaRDI QIDQ1785360zbMATH OpenOpenAlexFDO

Authors Jay Sethuraman, Chun Ye

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.6078

zbMATH Keywords

efficiencyfairnessprobabilistic serial mechanismrandom assignment

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80)

Abstract: Motivated by a problem of scheduling unit-length jobs with weak preferences over time-slots, the random assignment problem (also called the house allocation problem) is considered on a uniform preference domain. For the subdomain in which preferences are strict except possibly for the class of unacceptable objects, Bogomolnaia and Moulin characterized the probabilistic serial mechanism as the only mechanism satisfying equal treatment of equals, strategyproofness, and ordinal efficiency. The main result in this paper is that the natural extension of the probabilistic serial mechanism to the domain of weak, but uniform, preferences fails strategyproofness, but so does every other mechanism that is ordinally efficient and treats equals equally. If envy-free assignments are required, then any (probabilistic or deterministic) mechanism that guarantees an ex post efficient outcome must fail even a weak form of strategyproofness.

Recommendations

• A solution to the random assignment problem on the full preference domain
• A simple random assignment problem with a unique solution
• A new solution to the random assignment problem.
• Random assignment under weak preferences
• Strategy-proof assignment on the full preference domain

Cites work

• A new solution to the random assignment problem.
• A simple random assignment problem with a unique solution
• A solution to the random assignment problem on the full preference domain
• Consistency in the probabilistic assignment model
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Incentive compatibility in a market with indivisible goods
• On a conjecture by Gale about one-sided matching problems
• Pairwise kidney exchange
• Queue allocation of indivisible goods
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Scheduling with Opting Out: Improving upon Random Priority

Cited in

(7)

• Uncertain random assignment problem
• Random assignments with uniform preferences: an impossibility result
• On slots' scheduling
• Corrigendum to: ``Random assignment: redefining the serial rule
• A simple random assignment problem with a unique solution
• A solution to the random assignment problem on the full preference domain
• Random scheduling with deadlines under dichotomous preferences

This page was built for publication: A note on the assignment problem with uniform preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785360)