Separation between second price auctions with personalized reserves and the revenue optimal auction

When buyer valuations are drawn IID from a known regular distribution, a second price auction with a symmetric reserve price is the revenue-optimal single-item auction. When this distribution is irregular, we provide the first separation result showing that a second price auction with reserves earns at most 0.778 times the revenue of Myerson’s optimal auction, even when the reserves can be asymmetric. Since the lower bound is 0.745 for i.i.d. buyers, our result is nearly tight.     

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.     

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.     

Strategic bidding in continuous electricity auctions: an application to the Spanish electricity market

In this paper we introduce an asymmetric model of continuous electricity auctions with limited production capacity and bounded supply functions. The strategic bidding is studied with this model by means of an electricity market game. We prove that for every electricity market game with continuous cost functions a mixed-strategy Nash equilibrium always exists. In particular, we focus on the behavior of producers in the Spanish electricity market. We consider a very simple form for the Spanish electricity market: an oligopoly consisting just of independent hydro-electric power production units in a single wet period. We show that a pure-strategy Nash equilibrium for the Spanish electricity market game always exists.     

基于权值编码的组合拍卖竞胜标确定启发式算法研究

针对较大规模组合拍卖竞胜标确定问题(WDP),提出了基于权值编码的竞胜标确定启发式算法.改进了算法编码机制并嵌入基于WDP本质特点的启发式搜索规则,极大地提高了算法进化能力和求解效率.模拟实验结果表明该算法能够在较短时间内求出WDP最优解或满意近似解,为较大规模网上组合拍卖竞胜标确定问题提供了切实可行的求解算法.     

A multicriteria perspective on reverse auctions

This is a summary of the main contributions of the author’s PhD thesis. The thesis is written in English. It was supervised by Philippe Vincke and was defended on 20 December 2005 at the Université Libre de Bruxelles. A copy is available from the author upon request. The aim of this work is to investigate the use of a partial relations for bids’ comparisons in the context of multi-attribute auctions. At first a theoretical framework is developed. Then a specific model referred to as the butterfly model is presented. Finally the concept of bidding niches is formalized and related to the aforementioned model.      

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.     

Bid Evaluation in Procurement Auctions with Piecewise Linear Supply Curves

Consider a marketplace operated by a buyer who wishes to procure large quantities of several heterogeneous products. Suppliers submit price curves for each of the commodities indicating the price charged as a function of the supplied quantity. The total amount paid to a supplier is the sum of the prices charged for the individual commodities. It is assumed that the submitted supply curves are piecewise linear as they often are in practice. The bid evaluation problem faced by the procurer is to determine how much of each commodity to buy from each of the suppliers so as to minimize the total purchase price. In addition to meeting the demand, the buyer may impose additional business requirements that restrict which contracts suppliers may be awarded. These requirements may result in interdependencies between the commodities which lead to suboptimal results if the commodities are traded in independent auctions rather than simultaneously. Even without the additional business constraints the bid evaluation problem is NP-hard. The main contribution of our study is a flexible column generation based heuristics that provides near-optimal solutions to the procurer’s bid evaluation problem. Our method scales very well due to the Branch-and-Price technology it is built on. We employ sophisticated rounding and local improvement heuristics to obtain quality solutions. We also developed a test data generator that produces realistic problems and allows control over the difficulty level of the problems using parameters.     

Selecting optimal selling format of a product in B2C online auctions with boundedly rational customers

The advancement of Internet technology has enabled new formats for selling products in the B2C online auctions. At present, on the major online auction sites, there exist three popular selling formats, namely, the posted price, pure auction and buy-price auction formats. It is an important decision problem for a firm to select the most profitable format to sell its products through the Internet. The customer behavior is of course a crucial element of the decision process. To the best of our knowledge, most models available today assume that customers are perfectly rational. To better understand the decision process, in this paper, we incorporate the concept of bounded rationality into consideration. We first present a “behavior choice function” to characterize the behavior of the customers with bounded rationality. Then corresponding to each selling format, we construct a revenue model based on the bounded rationality for analysis. Finally, we conduct some elaborate computational experiments to investigate the performance of each revenue model for developing new managerial insights. Our computational results clearly demonstrate how the bounded rationality of customer behavior affects the choice of a preferable selling format for a B2C firm in an online auction.     

Optimal bidding in auctions of mixed populations of bidders

A mixed population of bidders consists of two asymmetric groups. Members of the first group are game-theoretic players, who maximize their expected profit and incorrectly believe that their opponents act similarly. The second group of bidders adopts an irrational strategy: they either choose their bids randomly following a given probability distribution, in a “naïve” form of bidding, or follow a decision-theoretic approach, maximizing their expected profit under the assumption that all other bids are random. In a sealed bid private-value procurement auction we examine the optimal strategy of a new player, who has perfect knowledge of the structure of the mixed bidder population and enters the auction. The optimal bid of the new bidder is derived when the cost and mark-up follow a uniform distribution in [0, 1]. The effect of the relative size of the group of game-theoretic bidders and the population size on the optimal bid price is established.