A solution to the random assignment problem on the full preference domain

• 成果类型: Article; Proceedings Paper
• 署名作者: Katta, Akshay-Kumar; Sethuraman, Jay
• 署名单位: Columbia University
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2005.05.001
• 发表日期: 2006
• 页码: 231-250
• 关键词: assignment; randomization; Indifferences; ordinal efficiency; fairness; Envy-freeness; strategy-proofness; maximum flows

摘要

We consider the problem of allocating a set of indivisible objects to agents in a fair and efficient manner. In a recent paper, Bogomolnaia and Moulin consider the case in which all agents have strict preferences, and propose the probabilistic serial (PS) mechanism; they define a new notion of efficiency, called ordinal efficiency, and prove that the probabilistic serial mechanism finds an envy-free ordinally efficient assignment. However, the restrictive assumption of strict preferences is critical to their algorithm. Our main contribution is an analogous algorithm for the full preference domain in which agents are allowed to be indifferent between objects. Our algorithm is based on a reinterpretation of the PS mechanism as an iterative algorithm to compute a flow in an associated network. In addition we show that on the full preference domain it is impossible for even a weak strategyproof mechanism to find a random assignment that is both ordinally efficient and envy-free. (c) 2005 Elsevier Inc. All rights reserved.