Pricing in multiple-item procurement auctions with a common to all items fixed cost

In a sealed bid multiple-item procurement auction, bidders may incur a fixed cost, which is common to all items. The paper develops pricing methods which ensure that a preset percentage profit level is always realized and the fixed cost is completely recovered, even if the eventual order is for some of the items at reduced quantities. One approach sets constraints and determines acceptable orders. Another alternative is to provide appropriate discounts. Finally, a third method considers fixed prices and imposes constraints that address the exposure problem of recovering the fixed cost. These methods may also be used for pricing combinatorial auctions.     

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.     

Auctions with bidder-determined allowable combinations

Combinatorial auctions are desirable as they enable bidders to express the synergistic values of a group of assets and thus may lead to better allocations. Compared to other types of auctions, they keep bidders from being exposed to risks (of receiving only parts of combinations that would be valuable to them) or from being overly cautious (in order to minimize such risks). However, computation time needed to determine the set of optimal winning combinations in a general combinatorial auction may grow exponentially as the auction size increases, and this is sometimes given as a reason for not using combinatorial auctions. To determine the winning allocation in a reasonable time, a bid taker might try to limit the kinds of allowable combinations, but bidders may disagree on what combinations should be allowed, and this may make limiting the allowable combinations politically infeasible.This paper proposes and tests successfully a new approach to managing the computational complexity of determining the set of winning combinations. The main idea is to let bidders themselves determine and prioritize the allowable combinations. Using bidder-determined combinations has two nice properties. First, by delegating the decision on what is biddable to the bidders who know what combinations are important to them, the bid taker is able to be (and appear) fair. Second, since bidders know their economics and have the incentive to get important combinations included, bidder prioritization of combinations will tend to assure that the most economically-important combinations are included in determining the winning set of bids if the bid taker is not able to consider all of the combinations submitted by bidders. The proposed auction process is useful in situations, such as government auctions, in which the bid taker is reluctant to limit the allowable combinations.     

Exact methods for combinatorial auctions

This is a summary of the author’s PhD thesis supervised by Frits Spieksma and defended on 20 December 2006 at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/dries.goossens/public). This work deals with combinatorial auctions, i.e., auctions where bidders can bid on sets of items. We study two special cases, namely the total quantity discount auction and the matrix bid auction.      

Anonymous sealed bid auction protocol based on a variant of the dining cryptographers’ protocol

Sealed bid auctions are a popular means of high-stakes bidding, as they eliminate the temporal element from the auction process, allowing participants to take less emotional, more thoughtful decisions. In this paper, we propose a digital communication protocol for conducting sealed bid auctions with high stakes, where the anonymity of bids as well as other aspects of fairness must be protected. The Dining Cryptographers?? Protocol (denoted by DC) was presented by David Chaum in 1988. The protocol allows the participants to broadcast a message anonymously. In a recent paper (Another Twist in the Dining Cryptographers?? Protocol, submitted to the Journal of Cryptology) the authors propose a variant of the original DC eliminating its main disadvantages. In this paper we present a cryptographic protocol realizing anonymous sealed bid auctions, such as first price or Vickrey auction, based on this variant. The proposed scheme allows to identify at least one dishonest participant violating the protocol without using of Trusted Third Parties. Additionally, we require that bids are binding. It is achieved by enabling all participants acting in concert (the so-called ??angry mob??) to find out the identity of the winner, in case the winner fails to make the purchase.     

A market-based multi-agent system model for decentralized multi-project scheduling

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.     

An efficient local search algorithm for the winner determination problem

Combinatorial auction, which allows bidders to bid on combinations of items, is an important type of market mechanism. The winner determination problem (WDP) has extensive applications in combinatorial auctions, and attracts more and more attention due to its strong relevance to business. However, this problem is intractable in theory as it has been proven to be NP-hard, and is also a challenging combinatorial optimization problem in practice. This paper is devoted to designing an efficient heuristic algorithm for solving the WDP. This proposed heuristic algorithm dubbed abcWDP is based on an effective yet simple local search framework, and equipped with three novel strategies, i.e., configuration checking, free-bid exploiting, and pseudo-tie mechanism. Extensive computational experiments on a broad range of benchmarks demonstrate that abcWDP performs much better than state-of-the-art algorithms and CPLEX in terms of both revenue and running time. More encouragingly, our abcWDP algorithm as a sequential algorithm even achieves better computational results than the multi-thread implemented algorithm \(\hbox {CA}_\mathrm{RA}\), which confirms its efficiency.     

Revenue-maximizing Dutch auctions with discrete bid levels

This paper is concerned with setting a predetermined number of bid levels in a Dutch auction to maximize the auctioneer’s expected revenue. As a departure from the traditional methods used by applied economists and game-theorists, a novel approach is taken in this study to tackle the problem by formulating the auctioning process as a constrained nonlinear program and applying standard optimization techniques to solve it. Aside from proposing respective closed-form formulae for computing the optimal bid levels and the auctioneer’s maximum expected revenue, we also show that the bid decrements should be increasing if there are two or more bidders in the Dutch auction. Additionally, the auctioneer’s maximum expected revenue increases with the number of bidders as well as the number of bid levels. Finally, managerial implications of the key findings as well as limitations of this research work are discussed.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

The stochastic bid generation problem in combinatorial transportation auctions

In this paper, we deal with the generation of bundles of loads to be submitted by carriers participating in combinatorial auctions in the context of long-haul full truckload transportation services. We develop a probabilistic optimization model that integrates the bid generation and pricing problems together with the routing of the carrier’s fleet. We propose two heuristic procedures that enable us to solve models with up to 400 auctioned loads.     

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.     

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.     

Design issues for 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.Received: April 2003, Revised: July 2003, AMS classification: 91B26, 90BXX, 90C27All correspondence to:Jawad Abrache     

Dominance or maximin: How to solve an English auction

It is widely believed that the English auction is solved after the dominated strategies are eliminated. This paper demonstrates that the dominance criterion is not very effective in many English auction models. To bid more than the true willingness to pay is dominated but a stronger solution concept is needed to deduce that the buyers increase the price in small steps up to their valuation. An iterated application of the dominance criterion does not solve the problem, but if it is assumed that the buyers use their maximin strategies the usual argument holds. Received May 1995/Final version May 1998     

Bidding under price uncertainty in multi-unit pay-as-bid procurement auctions for power systems reserve

In this paper a methodology for profit maximized bidding under price uncertainty in a day-ahead, multi-unit and pay-as-bid procurement auction for power systems reserve is proposed. Within this novel methodology a bidder is considered to follow a Bayes-strategy. Thereby, one bidder is assumed to behave strategically and the behavior of the remaining is summarized in a probability distribution of the market price and a reaction function to price dumping by the strategic bidder. With this approach two problems arise: First, as a pay-as-bid auction is considered, no uniform price and therefore no single probability distribution of the market price is readily available. Second, if historic bidding data of all participants are used to estimate such a distribution and market power is a relevant factor, the bid of the strategically behaving bidder is likely to influence the distribution. Within this paper for both of the problems solutions are presented. It is shown that by estimating a probability of acceptance the optimal bidding price with respect to a given capacity can be calculated by maximizing a stochastic non-linear objective function of expected profit. Taking the characteristics of recently established markets in Germany into account, the methodology is applied using exemplary data. It is shown that the methodology helps to manage existing price uncertainties and hence supports the trading decisions of a bidder. It is inferred that the developed methodology may also be used for bidding on other auction markets with a similar market design.     

Multi-mode resource constrained multi-project scheduling and resource portfolio problem

This paper introduces a multi-project problem environment which involves multiple projects with assigned due dates; activities that have alternative resource usage modes; a resource dedication policy that does not allow sharing of resources among projects throughout the planning horizon; and a total budget. Three issues arise when investigating this multi-project environment. First, the total budget should be distributed among different resource types to determine the general resource capacities, which correspond to the total amount for each renewable resource to be dedicated to the projects. With the general resource capacities at hand, the next issue is to determine the amounts of resources to be dedicated to the individual projects. The dedication of resources reduces the scheduling of the projects’ activities to a multi-mode resource constrained project scheduling problem (MRCPSP) for each individual project. Finally, the last issue is the efficient solution of the resulting MRCPSPs. In this paper, this multi-project environment is modeled in an integrated fashion and designated as the resource portfolio problem. A two-phase and a monolithic genetic algorithm are proposed as two solution approaches, each of which employs a new improvement move designated as the combinatorial auction for resource portfolio and the combinatorial auction for resource dedication. A computational study using test problems demonstrated the effectiveness of the solution approach proposed.     

Modeling first bid in retail secondary market online auctions: A Bayesian approach

We propose a Bayesian framework to model bid placement time in retail secondary market online business‐to‐business auctions. In doing so, we propose a Bayesian beta regression model to predict the first bidder and time to first bid, and a dynamic probit model to analyze participation. In our development, we consider both auction‐specific and bidder‐specific explanatory variables. While we primarily focus on the predictive performance of the models, we also discuss how auction features and bidders' heterogeneity could affect the bid timings, as well as auction participation. We illustrate the implementation of our models by applying to actual auction data and discuss additional insights provided by the Bayesian approach, which can benefit auctioneers.     

Characterization and computation of nash-equilibria for auctions with incomplete information

We consider a continuous sealed-bid auction model for an indivisible object with two bidders and incomplete information on both sides where the bidders' evaluations are assumed to be independently distributed on some real intervals. The price the winner (the highest bidder) has to pay is a given convex combination of the highest and the second highest (lowest) bid. It is shown that, for all but the second highest bid-price auction, all equilibrium-strategies are continuously differentiable and strictly monotonically increasing, and moreover, that the set of Nash-equilibria is completely characterized by a boundary value problem for a system of singular differential equations. In the case of symmetric data (independently and identically distributed true values) and for a particular class of asymmetric distributions (including uniform distributions), the boundary value problem is solved explicitly and uniquely.     

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.     

组合拍卖在门户网站广告机会分配中的应用

目前门户网站的广告机会销售主要通过价格协商的方式,这种方式不仅导致大量的中间交易成本而且分配结果常常无法达到最优.针对该情形,本文结合门户网站广告机会的特点,建立了广告机会分配的组合拍卖模型.该模型能让广告主自由的表达广告机会之间的无差异及互补效用.通过将该模型的特例转化为一般背包问题,文中证明了该问题求解的NP难特性.因此本文针对标的本身的结构提出了四种启发式信息及两种求解器:二元蚁群算法及贪婪算法.最后通过数值实验给出了在不同情况下,不同启发信息的性能并表明了在任何情况下二元蚁群算法比贪婪算法的寻优性更强.