Truthful approximation mechanisms for restricted combinatorial auctions

When attempting to design a truthful mechanism for a computationally hard problem such as combinatorial auctions, one is faced with the problem that most efficiently computable heuristics can not be embedded in any truthful mechanism (e.g. VCG-like payment rules will not ensure truthfulness).We develop a set of techniques that allow constructing efficiently computable truthful mechanisms for combinatorial auctions in the special case where each bidder desires a specific known subset of items and only the valuation is unknown by the mechanism (the single parameter case). For this case we extend the work of Lehmann, O'Callaghan, and Shoham, who presented greedy heuristics. We show how to use If-Then-Else constructs, perform a partial search, and use the LP relaxation. We apply these techniques for several canonical types of combinatorial auctions, obtaining truthful mechanisms with provable approximation ratios.     

Competitive auctions

We study a class of single-round, sealed-bid auctions for an item in unlimited supply, such as a digital good. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e. encourages bidders to bid their true valuations) and on all inputs yields profit that is within a constant factor of the profit of the optimal single sale price. We justify the use of optimal single price profit as a benchmark for evaluating a competitive auctions profit. We exhibit several randomized competitive auctions and show that there is no symmetric deterministic competitive auction. Our results extend to bounded supply markets, for which we also give competitive auctions.     

Informational limitations of ascending combinatorial auctions

We study the inherent limitations of natural widely-used classes of ascending combinatorial auctions. Specifically, we show that ascending combinatorial auctions that do not use both non-linear prices and personalized prices cannot achieve social efficiency with general bidder valuations. We also show that the loss of efficiency can be severe and that only a diminishing fraction of the social welfare may be captured. This justifies the added complexity in the auctions suggested by, e.g., Parkes and Ungar (2000) [29] and Ausubel and Milgrom (2002) [2].     

Exploring pricing rules in combinatorial sealed-bid auctions

The allocation of public goods such as the radio spectrum is a difficult task that the government must face. Currently, auctions are becoming an important tool to deal with this duty. In this context, the rules that the auctioneer establishes are particularly relevant, as the final outcome depends on them. When auctioning many related items, such as spectrum licenses, the bidders’ values for one item may depend on the number of items already obtained (complements and substitutes items). In such circumstances, combinatorial auctions are the most appropriate alternative for allocating lots. This paper analyzes the implications of selecting a particular pricing mechanism on the final result in a combinatorial sealed-bid auction. The following pricing rules are selected: the first-price mechanism, the Vickrey–Clarke–Groves (VCG) mechanism, and the bidder–Pareto–optimal (BPO) core mechanism, a core-selecting auction. To test these pricing rules, a simulator of the auction model has been developed. Then, to tackle the complex problem of simulating bidders’ behavior, a co-evolutionary system has been designed to identify improved strategies. The results revealed that the first-price mechanism yields inefficient outcomes and a notable reduction in the seller's revenues. Both the VCG and BPO mechanisms yield outcomes that are closer to the efficient allocation, and differences in revenues are affected by the presence of asymmetries.     

Optimal collusion-resistant mechanisms with verification

We present the first general positive result on the construction of collusion-resistant mechanisms, that is, mechanisms that guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments). This is a much stronger solution concept as compared to truthful or even group strategyproof mechanisms, and only impossibility results were known for this type of mechanisms in the “classical” model.We describe collusion-resistant mechanisms with verification that return optimal solutions for a wide class of mechanism design problems (which includes utilitarian ones as a special case). Note that every collusion-resistant mechanism without verification must have an unbounded approximation factor and, in general, optimal solutions cannot be obtained even if we content ourselves with truthful (“non-collusion-resistant”) mechanisms. All these results apply to problems that have been extensively studied in the algorithmic mechanism design literature like, for instance, task scheduling and inter-domain routing.     

Combinatorial auctions with decreasing marginal utilities

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.     

Truthful mechanism design for multidimensional scheduling via cycle monotonicity

We consider the makespan-minimization problem on unrelated machines in the context of algorithmic mechanism design. No truthful mechanisms with non-trivial approximation guarantees are known for this multidimensional domain. We study a well-motivated special case (also a multidimensional domain), where the processing time of a job on each machine is either “low” or “high.” We give a general technique to convert any c-approximation algorithm (in a black-box fashion) to a 3c-approximation truthful-in-expectation mechanism. Our construction uses fractional truthful mechanisms as a building block, and builds upon a technique of Lavi and Swamy [Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595–604]. When all jobs have identical low and high values, we devise a deterministic 2-approximation truthful mechanism. The chief novelty of our results is that we do not utilize explicit price definitions to prove truthfulness. Instead we design algorithms that satisfy cycle monotonicity [Rochet, J., 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16, 191–200], a necessary and sufficient condition for truthfulness in multidimensional settings; this is the first work that leverages this characterization.     

Ascending prices and package bidding: Further experimental analysis

We explore the performance of multi-round, price-guided combinatorial auctions for a previously untested class of value profiles in which synergies arise from shared fixed costs. We find that, in many cases, a simulator that bids straightforwardly does well in predicting auction performance, but exceptions arise because human bidders sometimes rely on cues besides prices to guide their package selection and because they sometimes bid aggressively on items for which they have no value in order to increase payments by bidders seeking complementary packages. In our experiments, this latter behavior not only raises prices, but can also improve efficiency by mitigating the threshold problem. Comparisons between a combinatorial clock auction (CCA) and a simultaneous ascending auction (SAA) are reported.     

Robustness of the Incentive Compatible Combinatorial Auction

Goods are said to be combinatorial when the value of a bundle of goods is not equal to the sum of the values of the same goods unbundled. Investigations of combinatorial allocation problems should recognize that there are two separate aspects of such problems: anenvironmental distinction between multiple-unit allocation problems which involve combinatorial goods and those which do not do so, and aninstitutional distinction between auctions in which combinatorial values can be expressed as part of the bidding rules and those in which they cannot. Forsythe and Isaac (Research in Experimental Economics, Vol. 2 (1982). Greenwich, Conn.: JAI Press, Inc.) reports the extension of the Vickrey auction into a demand-revealing, multiple unit, private goods auction that can incorporate combinatorial values. This current paper places that theoretically demand-revealing institution in a series of experimental environments in order to generate results (e.g. efficiencies) which may serve as a benchmark for other auctions (combinatorial or otherwise) whose implementation characteristics may be more favorable. To aid in interpretation of our Vickrey experimental results, we also provide results of alternatives to Vickrey allocations from both institutional and heuristic sources, as well as a discussion of the source of the Vickrey auctions high efficiencies even in the presence of misrevelation.     

Asymptotic Revenue Equivalence in Auctions

We study the revenue in auctions of a single object when the number of bidders becomes large. We show that all sequences of auctions belonging to a class of mechanisms have limiting expected revenue equal to the expected best-use value of the object. An important special case that is covered is common value auctions, but more generally not even affiliation of values is assumed. This provides an asymptotic revenue equivalence result for settings beyond that of private values. Journal of Economic Literature Classification Numbers: D44, C72.     

Mixed bundling auctions

We study multi-object auctions where agents have private and additive valuations for heterogeneous objects. We focus on the revenue properties of a class of dominant strategy mechanisms where a weight is assigned to each partition of objects. The weights influence the probability with which partitions are chosen in the mechanism. This class contains efficient auctions, pure bundling auctions, mixed bundling auctions, auctions with reserve prices and auctions with pre-packaged bundles. For any number of objects and bidders, both the pure bundling auction and separate, efficient auctions for the single objects are revenue-inferior to an auction that involves mixed bundling.     

Worst-case optimal redistribution of VCG payments in multi-unit auctions

For allocation problems with one or more items, the well-known Vickrey–Clarke–Groves (VCG) mechanism (aka Clarke mechanism, Generalized Vickrey Auction) is efficient, strategy-proof, individually rational, and does not incur a deficit. However, it is not (strongly) budget balanced: generally, the agents' payments will sum to more than 0. We study mechanisms that redistribute some of the VCG payments back to the agents, while maintaining the desirable properties of the VCG mechanism. Our objective is to come as close to budget balance as possible in the worst case. For auctions with multiple indistinguishable units in which marginal values are nonincreasing, we derive a mechanism that is optimal in this sense. We also derive an optimal mechanism for the case where we drop the non-deficit requirement. Finally, we show that if marginal values are not required to be nonincreasing, then the original VCG mechanism is worst-case optimal.     

Unique Implementation of the Full Surplus Extraction Outcome in Auctions with Correlated Types

In auctions with correlated types it is possible to design mechanisms such that full surplus extraction can be obtained as the outcome of an equilibrium in which agents use (weakly) dominant strategies. However, it is not assured that the outcome is unique. We present an example in which no mechanism can yield the full surplus extraction outcome as the unique Bayesian equilibrium outcome. Next we show that in the standard auction model the multiplicity problem can be fully resolved using sequential mechanisms, i.e., we show that it is possible to obtain the full surplus extraction outcome as the unique perfect Bayesian equilibrium outcome.Journal of Economic LiteratureClassification Numbers: D44; D70.     

Standard Auctions with Financially Constrained Bidders

We develop a methodology for analyzing the revenue and efficiency performance of auctions when buyers have private information about their willingness to pay and ability to pay. We then apply the framework to scenarios involving standard auction mechanisms. In the simplest case, where bidders face absolute spending limits, first-price auctions yield higher expected revenue and social surplus than second-price auctions. The revenue dominance of first-price auctions over second-price auctions carries over to the case where bidders have access to credit. These rankings are explained by differences in the extent to which financial constraints bind in different auction formats.     

Cardinal Bayesian allocation mechanisms without transfers

In allocating goods with no use of monetary transfers, random allocation mechanisms can be designed in order to elicit information on preference intensities. I study the nontransfer allocation of two ex-ante identical objects under Bayesian incentive compatibility, with symmetric agents and independent private valuations. I find the ex-ante utilitarian-optimal mechanism, in which the probability of receiving a specified object is used as “numeraire” to purchase probability units of the other object. I characterize this mechanism as an appropriate combination of lotteries, auctions and insurance. The latter element ensures that efficient auctions are feasible. If the problem is constrained to guarantee exactly one object per agent, then the optimal mechanism uses no information other than the agents? ordinal preferences.     

Optimal shill bidding in the VCG mechanism

This paper studies shill bidding in the Vickrey?CClarke?CGroves (VCG) mechanism applied to combinatorial auctions. Shill bidding is a strategy whereby a single decision-maker enters the auction under the guise of multiple identities (Yokoo et?al. Games Econ Behav, 46?pp. 174?C188, 2004). I formulate the problem of optimal shill bidding for a bidder who knows the aggregate bid of her opponents. A key to the analysis is a subproblem??the cost minimization problem (CMP)??which searches for the cheapest way to win a given package using shills. An analysis of the CMP leads to several fundamental results about shill bidding: (i) I provide an exact characterization of the aggregate bids b such that some bidder would have an incentive to shill bid against b in terms of a new property Submodularity at the Top; (ii) the problem of optimally sponsoring shills is equivalent to the winner determination problem (for single minded bidders)??the problem of finding an efficient allocation in a combinatorial auction; (iii) shill bidding can occur in equilibrium; and (iv) the problem of shill bidding has an inverse, namely the collusive problem that a coalition of bidders may have an incentive to merge (even after competition among coalition members has been suppressed). I show that only when valuations are additive can the incentives to shill and merge simultaneously disappear.     

Collusion in one-shot second-price auctions

Summary. Most of the literature on collusive behavior in auctions ignores two important issues that make collusion difficult to sustain at least in one-shot interactions: the detection of cheating and the verification of bids. Colluding bidders may deceive each other by using shill bidders. Also, if the identities of the bidders and their bids are not published then it would be difficult to verify the bid of a colluding bidder. This paper addresses these problems in one shot second price auctions where one bidder offers another bidder a side payment in exchange for not participating in the auction, while the number of other bidders is stochastic. In spite of the barriers to collusion mentioned above, a simple side payment mechanism which depends only on the auction price is introduced. It induces a successful collusion, eliminates the verification problem, provides no incentive for the use of shill bidders and guarantees that the proponent obtains ex-post non-negative payoff. The colluding bidders are ex-ante strictly better off compared with the competitive case, irrespective of their types.Received: 27 November 2002, Revised: 28 January 2005, JEL Classification Numbers: C72, D44, D82.Yair Tauman: Correspondence toWe would like to thank an anonymous referee for very valuable comments and suggestions that significantly improved the paper. We thank Shmuel Zamir for a helpful discussion.     

Optimal combinatorial mechanism design

We consider an optimal mechanism design problem with several heterogenous objects and interdependent values. We characterize ex post incentives using an appropriate monotonicity condition and reformulate the problem in such a way that the choice of an allocation rule can be separated from the choice of the payment rule. Central to the analysis is the formulation of a regularity condition, which gives a recipe for the optimal mechanism. If the problem is regular, then an optimal mechanism can be obtained by solving a combinatorial allocation problem in which objects are allocated in a way to maximize the sum of virtual valuations. We identify conditions that imply regularity using the techniques of supermodular optimization.     

Bidder collusion

We analyze bidder collusion at first-price and second-price auctions. Our focus is on less than all-inclusive cartels and collusive mechanisms that do not rely on auction outcomes. We show that cartels that cannot control the bids of their members can eliminate all ring competition at second-price auctions, but not at first-price auctions. At first-price auctions, when the cartel cannot control members’ bids, cartel behavior involves multiple cartel bids. Cartels that can control bids of their members can suppress all ring competition at both second-price and first-price auctions; however, shill bidding reduces the profitability of collusion at first-price auctions.     

Valuation structure in first-price and least-revenue auctions: an experimental investigation

In many auctions the valuation structure involves both private and common value elements. Existing experimental evidence (e.g. Goeree and Offerman in Am. Econ. Rev. 92(3):625–643, 2002) demonstrates that first-price auctions with this valuation structure tend to be inefficient, and inexperienced subjects tend to bid above the break-even bidding threshold. In this paper, we compare first-price auctions with an alternative auction mechanism: the least-revenue auction. This auction mechanism shifts the risk regarding the common value of the good to the auctioneer. Such a shift is desirable when ex post negative payoffs for the winning bidder results in unfulfilled contracts, as is often the case in infrastructure concessions contracts. We directly compare these two auction formats within two valuation structures: (1) pure common value and (2) common value with a private cost. We find that, relative to first-price auctions, bidding above the break-even bidding threshold is significantly less prevalent in least-revenue auctions regardless of valuation structure. As a result, revenue in first-price auctions is higher than in least-revenue auctions, contrary to theory. Further, when there are private and common value components, least-revenue auctions are significantly more efficient than first-price auctions.