Employing Mechanism Design for the Online Allocation of Items

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.Electrical Engineering, Mathematics and Computer Scienc