Mechanism Design for the Online Allocation of Items without Monetary Payments

Book chapter (2010)
Department
Software Computer Technology (EEMCS) (TU Delft)
Copyright: The original publication is available at www.springerlink.com
More Info
expand_more

Published Date

31-12-2010

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

Lecture Notes in Business Information Processing, 59, 2010; authors version

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Computer Technology

Abstract

We consider online mechanism design without money, where agents are allowed to trade items with other agents, in an attempt to improve their own allocation. In an off-line context, this problem is known as the House Allocation Problem (HAP). We extend HAP to an online problem and call it the Online House Allocation Problem (OHAP). In OHAP, agents can choose when to arrive and depart over time and are allowed to be indifferent between items. Subsequently, we present our Agent Shifting Algorithm (ASA) for OHAP. A mechanism that uses ASA as its allocation rule is shown to be strategy-proof, individually rational and Pareto optimal. Moreover, we argue that any mechanism that obtains an outcome in OHAP that cannot be obtained by using ASA fails to be strategy-proof or is not Pareto optimal.

Files

Amec09behnam1.pdf
(pdf | 0.184 Mb)