The Assignment Problem: Theory and Experiments

Citation

Olson, Mark Allen (1991) The Assignment Problem: Theory and Experiments. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/8ZCK-E373. https://resolver.caltech.edu/CaltechETD:etd-07232007-145323

Abstract

In this thesis I consider the problem of assigning a fixed and heterogeneous set of goods or services to a fixed set of individuals. I analyze this allocation problem with and without the use of monetary transfers to allocate good.

There are many applications in the literature associated with this problem. The usual approach to this problem has been to discuss the properties of individual mechanisms (variously called procedures, algorithms, or rules) to solve the problem, often ignoring the incentive properties. In this thesis I take a different approach, that is, to look at a large class of mechanisms and to determine the conditions necessary to induce mechanisms with desired optimality and incentive properties. This analytic technique is augmented by an experimental examination of some of the mechanisms that have been proposed to solve this problem. Mechanisms that use transfers and consider incentive properties exist in the literature, but mechanisms that do not use transfers do not. None of these mechanisms has been tested or compared. The thesis is divided into two chapters; in chapter I, I examine the class of nontransfer dominant and Nash strategy mechanisms, and in chapter II, I discuss the experimental tests of the known transfer mechanisms and of the nontransfer mechanisms discussed in chapter I.

In the first chapter of this thesis, I characterize the conditions necessary for a nontransfer mechanism to be implementable in dominant and Nash strategies. This characterization is an extension of the Gibbard-Satterthwaite theorem. One of the conditions, ordinality, explains a distinction that is observed in the mechanisms described in the literature, that is, the use of cardinal information when transfers are used, and the use of ordinal information when transfers are not used. In addition, I apply a little-known concept for strategic behavior, nonbossiness, which is a necessary condition for implementability.

In the second chapter of this thesis, I use experimental methods to explore some procedures that could be used to assign individuals to slots. I look at four mechanisms, two transfer mechanisms, a sealed-bid auction and a progressive auction, and two nontransfer mechanisms, a choice mechanism and a chit mechanism (which are also studied in part I of this thesis). The mechanisms were compared to their theoretical predictions and to each other. For the chit mechanism a genetic algorithm was used to compute the predicted outcome; since this is a new use for the technique, I discuss the methodology that I used.

The experimental results for the transfer auctions are similar to the results found for single and multiple unit auctions; that is, progressive auctions tend to be more efficient and extract higher revenue from the bidders. While the transfer mechanisms studied had the properties that they are efficient and extract surplus (in terms of revenue) from the bidders, nontransfer mechanisms retain most of the surplus for bidders but tend to be less efficient. The difference between the two classes of mechanisms was most apparent in a high-contention environment where the use of nontransfer mechanisms resulted in a much larger surplus to the individual bidders, and the transfer mechanisms resulted in slightly higher efficiencies (the differences in efficiencies were small in comparison to the differences in consumer surplus). In a low-contention environment the use of either a transfer or a nontransfer mechanism had little effect on either the efficiencies or the consumer surplus.

The results of this study are a first step to understanding the assignment problem and to understanding more difficult allocation problems with heterogeneous goods. Two simple results are evident from our results. In the low-contention environment the planner can choose among the mechanisms discussed and not be concerned about their relative merits, since there is little difference in the outcomes of these mechanisms; in the high-contention environment the planner must determine whether efficiency or consumer surplus is more important; if efficiency or revenue is most important then, the progressive auction is clearly superior, if consumer welfare is most important then the chit mechanism is superior.

Thesis Files