Abstract:

Strategic behavior in a finite market can cause inefficiency in the market's allocation, and market mechanisms differ in how successfully they limit this inefficiency. A method for ranking algorithms in computer science is adapted here to rank market mechanisms according to how quickly inefficiency vanishes as the size of the market increases. It is shown that trade at a single market-clearing price in the k-double auction is "worst-case asymptotic optimal" among all incentive compatible, interim individually rational and ex ante budget balanced mechanisms.

This result is now explained. An independent, private value model of trade is considered in which the values for m buyers are independently drawn from a distribution G and the costs of m sellers are independently drawn from a distribution F. The number m measures the size of the market. The error of a mechanism for a specific value of m and for a specific choice of G and F is the fraction of the potential gains from trade that are inefficiently not achieved by the traders in the mechanism because of their strategic behavior. For each value of m, the worst-case error of a mechanism is the maximum value of this error over a range of G and F.

"Asymptotic" refers to the ranking of mechanisms according to the rates at which their worst-case errors coverge to zero as m increases. The main result of the paper is that no mechanism can dominate the k-double auction in the sense that its worst-case converges to zero at a faster rate than the worst-case error in the k-double auction.

The significance and meaning of this result is discussed in the paper. The asymptotic, worst-case approach leaves open the possibility that either for small values of m or for some determination of G and F a mechanism might exist that outperforms the k-double auction. We dispel the significance of this possibility through a numerical investigation in which the error in the k-double auction is compared to that of the "constrained efficient" mechanism, which is the mechanism that maximizes the achieved gains from trade subject to the constraints of incentive compatibility, interim individual rationality, and ex ante budget balance. The two mechanisms are compared for a variety of choices of G and F and for m = 2, 4 and 8. The numerical results suggest that even for such small sizes of markets the error of the k-double auction is at most marginally larger than that of the constrained efficient mechanism. The k-double auction thus appears to be almost "second best" in even very small markets.