Unit-demand auctions : fast algorithms for special cases and a connection to stable marriage with indifferences

Unit-demand auctions have been heavily studied, in part because this model allows for a mechanism enjoying a remarkably strong combination of game-theoretic properties: efficiency, stability (or envy-freeness), and strategyproofness. One way to derive this mechanism is to specialize the Vickrey-Clarke-Groves (VCG) mechanism to the setting of unit-demand auctions.

In the first part of this dissertation, we focus on developing fast algorithms for implementing the VCG mechanism for compactly representable special cases of unit-demand auctions. We first consider the model with the following special structure: there are n bids, each having two associated real values, a "slope" and an "intercept"; there are m items, each having an associated real value, a "quality"; for each bid u and item v, u offers on v an amount that is equal to the slope of u times the quality of v plus the intercept of u. Within this model, we present a data structure that processes the bids one-by-one in arbitrary order and maintains an efficient representation of a VCG outcome for the set of processed bids; each bid is processed in O(√m log^2 m) time. Thus, we solve the problem of computing a VCG outcome of an auction with this form in O(n √m log^2 m) time. We also present an O(n log n)-time algorithm for computing the VCG prices, given a VCG allocation of an auction with this form.

Next, we study the special case of the aforementioned model where the qualities of the items are evenly-spaced, i.e., the qualities form an arithmetic sequence. This special case is motivated by the following application to the scheduling domain. Consider the problem of scheduling unit jobs on a single machine with a common deadline where some jobs may be rejected. Each job has a weight and a profit, and the objective is to minimize the sum of the weighted completion times of the scheduled jobs plus the sum of the profits of the rejected jobs. It is not hard to see that this problem is equivalent to finding a VCG allocation of an auction with this special form, where we interpret each job as a bid by setting the slope to the negated weight and the intercept to the profit, and we interpret the time slots as items by setting the qualities to 1 through the deadline. We first present an O(n log n)-time algorithm for computing a VCG allocation of an auction with this special form. Then, we describe how to use our algorithm to compute within the same time bound, a VCG allocation of an auction for the case where the item qualities form a nondecreasing sequence that is the concatenation of two arithmetic sequences. This allows us to incorporate weighted tardiness penalties with respect to a common due date into the aforementioned scheduling problem. We also show that certain natural variations of the scheduling problems we study are NP-hard.

In the second part of this dissertation, we explore a connection between unit-demand auctions and the stable marriage model (and more generally, the college admissions model). We present a framework based on two variants of unit-demand auctions: the first variant, a unit-demand auction with priorities (UAP), extends a unit-demand auction by associating a "priority" with each bidder; the second variant, an iterated UAP (IUAP), extends a UAP by associating a sequence of unit-demand bids (instead of a single unit-demand bid) with each bidder. We present a nondeterministic algorithm that generalizes the well-known "deferred acceptance" algorithm for the stable marriage model by iteratively converting an IUAP to a UAP while maintaining a special kind of a maximum-weight matching. Using this framework, we develop a mechanism for the stable marriage model with indifferences that is Pareto-optimal, weakly stable, and group strategyproof for the men. Our results generalize to the college admissions model with indifferences.