Abstract:

We consider two problems from the area of algorithmic mechanism design: finite support single-item auctions and shortest path auctions. The two parts of this thesis are tied together by the common theme of optimality, and, more generally, maximization of the auctioneer's utility under various restrictions on the computational model.

First, we show how to design a revenue-maximizing auction for finite support distributions. In doing so, we introduce a novel class of mechanisms for finite support auctions, which we call order-based auctions ; we believe that this concept may be of independent interest.

Next we consider the situation when the mechanism designer knows each bidder's valuation support, but does not know the probability of each value. We study two cases that differ in the amount of information available to the mechanism designer and describe polynomial-time algorithms for both of these cases.

A shortest path auction is a mechanism for buying an inexpensive path in a network, where edges are owned by selfish agents. We investigate the payments the buyer must make in order to buy a path.

We show that any mechanism with (weakly) dominant strategies can force the buyer to make very large payments. Namely, for every such mechanism, the buyer can be forced to pay c (P ) + ? k (c (Q ) - c ( P )), where c (P ) is the cost of the shortest path, c (Q ) is the cost of the second-shortest path, and k is the number of edges in P .

Furthermore, we find the optimal mechanism for this problem and show that under various natural distributions of edge costs, the optimal mechanism pays at most logarithmic factors more than the actual cost, whereas the classical VCG mechanism must pay [Special characters omitted.] times the actual cost.

Finally, we show that by deleting some of the edges of the graph, one can reduce the total payment of the VCG mechanism by a factor of ?( n ). While we prove that finding the optimal set of edges to delete is hard, we describe a pseudopolynomial time algorithm for series-parallel graphs and fixed edge costs and discuss the applicability of this algorithm for the case of general (probabilistic) costs.