Combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research. An earlier version of this paper appeared in 4OR 2, 1–33, 2004.     

Designing sniping agents

Sniping agents are increasingly being deployed to assist bidders in acquiring items in online auctions. This paper reviews the extant auction literature and proposes an overarching sniping agent design framework that could potentially increase the commercial viability of snipping agents. For better alignment between the functions of sniping agents and the needs of human bidders, we review existing literature based on three fundamentals: (1) knowledge about human bidder behavior, (2) awareness of the product(s) desired by a bidder, and (3) an understanding of the research on bidding agents and auction design. The output of this review is the explicit consideration of iterative combinatorial auction agent design, fuzzy set representation of the bidder’s preferences and dynamic derivation of bidding strategies according to the progress of ongoing auctions.     

Allocative efficiency in simulated multiple-unit combinatorial auctions with quantity support

We study the behavior of the Quantity Support Mechanism, a support tool, which suggests new bids for bidders in semi-sealed-bid combinatorial auctions. The support tool gives bidders a shortlist of provisionally winning bids (price–quantity combinations) they can choose from. We conducted a series of simulations to test the efficiency of the final allocations in the auctions. Our results indicate that quantity support auctions are more efficient than auctions without it, although the theoretical optimum is not always reached. Also, in our experiments, quantity support auctions led to a lower total cost to the buyer than non-combinatorial auctions, where the items were auctioned individually. The simulation results also show that the QSM cannot entirely overcome the threshold problem and what we call the “puzzle problem”.     

Non-linear anonymous pricing combinatorial auctions

In combinatorial auctions the pricing problem is of main concern since it is the means by which the auctioneer signals the result of the auction to the participants. In order for the auction to be regarded as fair among the various participants the price signals should be such that a participant that has won a subset of items knows why his bid was a winning bid and that agents that have not acquired any item easily can detect why they lost. The problem in the combinatorial auction setting is that the winner determination problem is a hard integer programming problem and hence a linear pricing scheme supporting the optimal allocation might not exist.     

Home-grown values and incentive compatible auction design

The behavioral properties of several auctions designed to elicit individual valuations for an object are studied using controlled laboratory experiments. Our experiments lead us to conclude that there are some behavioral differences between alternative incentive-compatible institutions for eliciting home-grown values, contrary to the theoretical expectation that these institutions are isomorphic. These results are consistent with earlier experimental results using induced values. The most important finding is that English auctions appear to elicit lower bids than Vickrey auctions, after controlling for observable socio-economic characteristics. Moreover, English auction bids also exhibit significantly less residual variance and may be sensitive to the number of rival bidders. It appears that the real-time learning allowed in the English auction significantly affects subject behavior. We also find that values elicited with the Becker, DeGroot and Marshak institution differ from those in both English and Vickrey auctions. Received November 1993/Final version May 1995     

Using bid data for the management of sequential,multi-unit,online auctions with uniformly distributed bidder valuations

Internet auctions for consumers’ goods are an increasingly popular selling venue. We have observed that many sellers, instead of offering their entire inventory in a single auction, split it into sequential auctions of smaller lots, thereby reducing the negative market impact of larger lots. Information technology also makes it possible to collect and analyze detailed bid data from online auctions. In this paper, we develop and test a new model of sequential online auctions to explore the potential benefits of using real bid data from earlier auctions to improve the management of future auctions. Assuming a typical truth-revealing auction model, we quantify the effect of the lot size on the closing price and derive a closed-form solution for the problem of allocating inventory across multiple auctions when bidder valuation distributions are known. We also develop a decision methodology for allocating inventory across multiple auctions that dynamically incorporates the results of previous auctions as feedback into the management of subsequent auctions, and updating the lot size and number of auctions. We demonstrate how information signals from previous auctions can be used to update the auctioneer’s beliefs about the customers’ valuation distribution, and then to significantly increase the seller’s profit potential. We use several examples to reveal the benefits of using detailed transaction data for the management of sequential, multi-unit, online auctions and we demonstrate how these benefits are influenced by the inventory holding costs, the number of bidders, and the dispersion of consumers’ valuations.     

Monotonicity in asymmetric first-price auctions with affiliation

I study monotonicity of equilibrium strategies in first-price auctions with asymmetric bidders, risk aversion, affiliated types, and interdependent values. Every mixed-strategy equilibrium is shown to be outcome-equivalent to a monotone pure-strategy equilibrium under the “priority rule” for breaking ties. This provides a missing link to establish uniqueness in the “general symmetric model” of Milgrom and Weber (Econometrica 50:1089–1122, 1982). Non-monotone equilibria can exist under the “coin-flip rule” but they are distinguishable: all non-monotone equilibria have positive probability of ties whereas all monotone equilibria have zero probability of ties. This provides a justification for the standard empirical practice of restricting attention to monotone strategies. Hendricks et al. (2003) provide an overview of recent empirical work. For a survey of experimental work, see Kagel and Levin (2002).     

Hats,auctions and derandomization

We investigate derandomizations of digital good randomized auctions. We propose a general derandomization method which can be used to show that for every random auction there exists a deterministic auction having asymptotically the same revenue. In addition, we construct an explicit optimal deterministic auction for bi‐valued auctions. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 478–493, 2015     

基于有穷损害优先法求解组合拍卖竞胜标问题研究

迄今为止,组合拍卖竞胜标问题并不存在一个多项式时间复杂度的算法,其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。它是一个NP难问题,也是组合拍卖机制设计中的难题之一。而有穷损害优先方法是纯粹递归论中的一个十分重要的现代方法,特别对NP难问题求解算法的设计,对研究依复杂度决定的偏序结构的构造是一个很基本的有用工具。因此,本文提出根据组合拍卖的内在特性,将各不同的拍卖商品按照拍卖机制的要求,并结合其自身的协同价值等因素,设定一个优先序,然后采用有穷损害优先法有效有序地解决。     

How to bid in unified second-price auctions when requests are duplicated

In display advertising auctions, a unique display opportunity may trigger many bid requests being sent to the same buyer. Bid request duplication is an issue: programmatic bidding agents might bid against themselves. In a simplified setting of unified second-price auctions, the optimal solution for the bidder is to randomize the bid, which is quite unusual. Our results motivate the recent switch to a unified first-price auction by showing that a unified second-price auction could have been detrimental to all participants.     

A double-sided multiunit combinatorial auction for substitutes: Theory and algorithms

Combinatorial exchanges have existed for a long time in securities markets. In these auctions buyers and sellers can place orders on combinations, or bundles of different securities. These orders are conjunctive: they are matched only if the full bundle is available. On business-to-business (B2B) exchanges, buyers have the choice to receive the same product with different attributes; for instance the same product can be produced by different sellers. A buyer indicates his preference by submitting a disjunctive order, where he specifies the quantity he wants of each particular good and what limit price he is willing to pay for each good, thus providing a subjective valuation of each attribute. Only the goods with the best prices will be traded. This article considers a doubled-sided multiunit combinatorial auction for substitutes, that is, a uniform price auction where buyers and sellers place both types of orders, conjunctive (AND orders) and disjunctive (XOR orders). We show that linear competitive prices exist. We also propose an algorithm to clear the market, which is particularly efficient when the number of traders is large, and the goods are divisible.     

车辆牌照拍卖模型

提出多个相同物品(如车辆牌照)同时密封拍卖的模型，给出对称均衡竞标策略；证明了该拍卖方式与第一价格密封连续拍卖产生相同的预期收益；对估价为均匀分布的拍卖预期收益进行了研究。     

Vickrey–Dutch procurement auction for multiple items

We consider a setting where there is a manufacturer who wants to procure multiple items from a set of suppliers each of whom can supply one or more of these items (bundles). We design an ascending price auction for such a setting which implements the Vickrey–Clarke–Groves outcome and truthful bidding is an ex post Nash equilibrium. Our auction maintains non-linear and non-anonymous prices throughout the auction. This auction has a simple price adjustment step and is easy to implement in practice. As offshoots of this auction, we also suggest other simple auctions (in which truthful bidding is not an equilibrium by suppliers) which may be suitable where incentives to suppliers are not a big concern. Computer simulations of our auction show that it is scalable for the multi-unit case, and has better information revelation properties than its descending auction counterpart.     

Multi-criteria auctions without full comparability of bids

The emergence of auction mechanisms that support bids characterized by several attributes is one of the most recent evolutions within auction theory. These mechanisms, referred to as multi-attribute, multiple issue or multi-dimensional auctions, are at the intersection between multi-criteria decision and auction theories. The purpose of this paper is to introduce multi-criteria auctions the originality of which is not to require full comparability between bids. We claim that this distinctive feature is of great interest, especially in procurement situations. Furthermore, the existence of potential incomparability between multi-dimensional offers will permit us to manage different bidding niches coexisting within the same bidding space. A theoretical framework based on a general preference structure will be introduced and then referenced to existing approaches such as multi-attribute auctions or new ones such as dominance based multi-criteria auctions or butterfly auctions.     

Block order restrictions in combinatorial electric energy auctions

In Europe, the auctions organized by “power exchanges” one day ahead of delivery are multi-unit, double-sided, uniformly priced combinatorial auctions. Generators, retailers, large consumers and traders participate at the demand as well as at the supply side, depending or whether they are short or long in electric energy. Because generators face nonconvex costs, in particular startup costs and minimum run levels, the exchanges allow “block orders” that are all-or-nothing orders of a given amount of electric energy in multiple consecutive hours, while the standard order consists of an amount for a single hour that can be curtailed. All exchanges restrict the size (MWh/h), the type (span in terms of hours) or the number (per participant per day) of blocks that can be introduced. This paper discusses the rationale of block order restrictions. Based on simulations with representative scenarios, it is argued that the restrictions could be relaxed, which some exchanges have already started doing.     

Nonparametric identification and estimation of score auctions in multi-attribute procurement

Score auctions are used in procurement to incorporate other attributes beyond price. We establish nonparametric econometric identification of bidders' pseudotypes (a measure of bidder's private cost), when bids are evaluated using a preannounced quasi-linear score, calculated on the basis of the submitted levels of the attributes. Hence, we extend the standard nonparametric method for independent private costs sealed-bid, first price auctions, to multi-attribute quasi-linear score auctions. We illustrate the result with an application to scoring bid data.     

基于内生投标人的拍卖

讨论了参与者是内生性的第一价格和第二价格密封拍卖的均衡报价策略 ,两种不同的拍卖形式产生相同的预期收入 ;由于中止值的存在 ,卖方预期收入可能随着潜在参与者的增加而减少 .对拍卖商来说 ,如果投标人是风险回避的 ,那么第一价格密封拍卖比第二价格密封拍卖产生更高的预期收益 .     

All-pay auctions with risk-averse players

We study independent private-value all-pay auctions with risk-averse players. We show that: (1) Players with low values bid lower and players with high values bid higher than they would bid in the risk neutral case. (2) Players with low values bid lower and players with high values bid higher than they would bid in a first-price auction. (3) Players’ expected utilities in an all-pay auction are lower than in a first-price auction. We also use perturbation analysis to calculate explicit approximations of the equilibrium strategies of risk-averse players and the seller’s expected revenue. In particular, we show that in all-pay auctions the seller’s expected payoff in the risk-averse case may be either higher or lower than in the risk neutral case.     

Compact bidding languages and supplier selection for markets with economies of scale and scope

Combinatorial auctions have been used in procurement markets with economies of scope. Preference elicitation is already a problem in single-unit combinatorial auctions, but it becomes prohibitive even for small instances of multi-unit combinatorial auctions, as suppliers cannot be expected to enumerate a sufficient number of bids that would allow an auctioneer to find the efficient allocation. Auction design for markets with economies of scale and scope are much less well understood. They require more compact and yet expressive bidding languages, and the supplier selection typically is a hard computational problem. In this paper, we propose a compact bidding language to express the characteristics of a supplier’s cost function in markets with economies of scale and scope. Bidders in these auctions can specify various discounts and markups on overall spend on all items or selected item sets, and specify complex conditions for these pricing rules. We propose an optimization formulation to solve the resulting supplier selection problem and provide an extensive experimental evaluation. We also discuss the impact of different language features on the computational effort, on total spend, and the knowledge representation of the bids. Interestingly, while in most settings volume discount bids can lead to significant cost savings, some types of volume discount bids can be worse than split-award auctions in simple settings.     

Comparing the Spanish and the discriminatory auction formats: A discrete model with private information

The Spanish Treasury is the only Treasury in the world that uses a hybrid system of discriminatory and uniform price auctions to sell government debt: winning bidders pay their bid price for each unit if this is lower than the weighted average price of winning bids (WAP), and pay the WAP otherwise. Following Gordy [Gordy, M., 1996. Multiple bids in a multiple-unit common-value auction. Board of Governors of the Federal Reserve System], we model the Spanish auction as a common value auction of multiple units with private information, allowing for multiple bids. Numerical analysis shows that bidders spread their bids more in the Spanish than in the discriminatory auction and bid higher for the first unit, and that the expected seller’s revenue is higher in the Spanish than in the discriminatory auction within a reasonable set of parameter values.