Employing Mechanism Design for the Online Allocation of Items

Employing Mechanism Design for the Online Allocation of Items

Jalilzadeh, B.

Witteveen, C. (mentor)
De Weerdt, M.M. (mentor)
Planken, L.R. (mentor)
Geers, H.J.A.M. (mentor)

Electrical Engineering, Mathematics and Computer Science

2009-02-04

A fundamental problem in online mechanism design is how to deal with agents that arrive and depart over time. Possible approaches that deal with this problem can roughly be split up into two parts: online mechanism design with and without monetary payments. By far, most research until now has focussed on the former of the two. Our main contribution is to the field of 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 present a general framework that extends HAP to an online problem, and call it the Time Slot Reservation Problem (TSRP). A key issue in both HAP and TSRP is that we want to reallocate items that are owned by agents, rather than the mechanism. As a consequence, agents are capable of blocking the outcome of a mechanism by not relinquishing their allocation. We present an algorithm, called the Time Slot Shifting Algorithm (TSSA), that takes this intricacy into account. A mechanism that uses TSSA 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 TSRP that cannot be obtained by using TSSA fails to be either strategy-proof or Pareto optimal.

house allocation
mechanism design
online dynamic
top trading cycle
pareto optimailty

http://resolver.tudelft.nl/uuid:8ef36410-06c2-4372-a9fe-e0e45b264a73

TU Delft, Electrical Engineering, Mathematics, Computer Sci, Computer Science

Student theses

master thesis

(c) 2009 Jalilzadeh, B.