2014/10/16 by Jay Sethuraman, Chun Ye, Sethuraman, Jay +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1412.6078
openalex publication_date 2014/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.