Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Simultaneous pooled auctions

Suppose a seller wants to sell k similar or identical objects and there are n > k potential buyers. Suppose that each buyer wants only one object. In this case, we suggest the use of a simultaneous auction that would work as follows. Players are asked to submit sealed bids for one object. The individual with the highest bid chooses an object first; the individual with the second-highest bid chooses the next object; and this process continues until the individual with the kth highest bid receives the last object. Each individual pays the equivalent to his or her bid. When objects are identical, we show that the proposed auction generates the same revenue as a first-price sealed-bid sequential auction. When objects are perfectly correlated, there is no known solution for sequential auctions, whereas we can characterize bidding strategies in the proposed auction. Moreover, the proposed auction is optimal (given an appropriately chosen reserve price), and it may be easier and cheaper to run than a sequential auction.

A simple analysis of the US emission permits auctions

We examine a stylized version of EPA auctions when agents know the list of values of sellers and buyers. There are inefficient equilibria where no goods are traded and efficient equilibria where all exchange occurs at a uniform price. We also provide examples under incomplete information when the uniform price equilibrium holds and when it does not hold. (C) 1999 Elsevier Science S.A. All rights reserved. JEL classification: D44; Q29.

Hybrid auctions

In this paper we analyze a hybrid auction that combines a first-price and a Vickrey auction. We show that this auction may generate more expected revenue than a standard first-price auction. (C) 2002 Elsevier Science B.V. All rights reserved.

Auction price anomalies: Evidence from wool auctions in Australia

Using detailed Australian wool auction data we test for further evidence of pricing anomalies at sequential auctions. We find that an anomaly frequently exists and order is frequently endogenously determined. Moreover, prices increase through some sales and decrease through others. We examine whether it is possible to explain the variation in the anomaly across sales and conclude that there is no systematic relationship between the direction of the price anomaly and the characteristics of the wool or the auction. We do, however, find evidence that an anomaly, is more likely in longer sales.

Auctions with synergies and asymmetric buyers

In this paper we consider sequential auctions with synergies where one player wants two objects and the remaining players want one object each. We show that expected prices may not necessarily decrease as predicted by Branco [Econ. Lett. 54 (1997) 159]. Indeed we show that expected prices can actually increase. (C) 2004 Elsevier B.V All rights reserved.

Reserve price commitments in auctions

It is well known that the optimal auction-one that maximizes the seller's expected revenue-can be implemented using a standard auction format with a suitably chosen reserve price. This reserve price is above the seller's value of retaining the object and the mechanism requires a commitment not to sell the object below the reserve. This commitment is what makes the reserve valuable to the seller. However, in practice, a reserve price commits the seller to sell the object if the reserve is reached, but does not commit her to withhold the object from sale if bidding falls short of the reserve. In this note we investigate whether reserve prices remain valuable for the seller when she may negotiate with the highest bidder if the reserve is not met. We show that the value of the reserve price may be completely undermined if the seller is a sufficiently weak bargainer. (c) 2004 Elsevier B.V. All rights reserved.

Corruption and auctions

We investigate how corruption affects the outcome of a first-price auction (bidding behavior, efficiency and the seller's expected revenue). The auctioneer approaches the winner to offer the possibility of a reduction in his bid in exchange for a bribe. The bribe can be a percentage of the difference between the winning and the second-highest bid or a fixed amount. We show that there exists a symmetric bidding strategy equilibrium that is monotone, i.e., higher valuation buyers bid higher. Corruption does not affect efficiency but both the auctioneer's expected bribe and the seller's expected revenue depend on the format of the bribe payments. We also find the optimal bribe scheme.

Sequential asymmetric auctions with endogenous participation

In this paper we suggest a model of sequential auctions with endogenous participation where each bidder conjectures about the number of participants at each round. Then, after learning his value, each bidder decides whether or not to participate in the auction. In the calculation of his expected value, each bidder uses his conjectures about the number of participants for each possible subgroup. In equilibrium, the conjectured probability is compatible with the probability of staying in the auction. In our model, players face participation costs, bidders may buy as many objects as they wish and they are allowed to drop out at any round. Bidders can drop out at any time, but they cannot come back to the auction. In particular we can determine the number of participants and expected prices in equilibrium. We show that for any bidding strategy, there exists such a probability of staying in the auction. For the case of stochastically independent objects, we show that in equilibrium every bidder who decides to continue submits a bid that is equal to his value at each round. When objects are stochastically identical, we are able to show that expected prices are decreasing.

Chinese wool auctions: Failed agribusiness reform or future marketing channel?

The spectacular though short-lived operation of China's wool auctions graphically illustrates problems in reforming China's agribusiness sector. A selective coverage of product type and participants, a highly contrived process of price discovery, and an urgent need for parallel reform in related areas all led to the demise of the auctions and are a barrier to their re-emergence as a viable wool marketing channel. Despite the challenges facing wool auctions, this paper argues that they still have much to offer the marketing of wool in China.

High or low initial setting price?: Initial setting price as prediction of intention to bid in on line auctions

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Tacit collusion and capacity withholding in repeated uniform price auctions

This paper contributes to the study of tacit collusion by analyzing infinitely repeated multiunit uniform price auctions in a symmetric oligopoly with capacity constrained firms. Under both the Market Clearing and Maximum Accepted Price rules of determining the uniform price, we show that when each firm sets a price-quantity pair specifying the firm's minimum acceptable price and the maximum quantity the firm is willing to sell at this price, there exists a range of discount factors for which the monopoly outcome with equal sharing is sustainable in the uniform price auction, but not in the corresponding discriminatory auction. Moreover, capacity withholding may be necessary to sustain this out-come. We extend these results to the case where firms may set bids that are arbitrary step functions of price-quantity pairs with any finite number of price steps. Surprisingly, under the Maximum Accepted Price rule, firms need employ no more than two price steps to minimize the value of the discount factor

Elicited bid functions in (a)symmetric first-price auctions

We report on a series of experiments that examine bidding behavior in first-price sealed bid auctions with symmetric and asymmetric bidders. To study the extent of strategic behavior, we use an experimental design that elicits bidders' complete bid functions in each round (auction) of the experiment. In the aggregate, behavior is consistent with the basic equilibrium predictions for risk neutral or homogenous risk averse bidders (extent of bid shading, average seller's revenues and deviations from equilibrium). However, when we look at the extent of best reply behavior and the shape of bid functions, we find that individual behavior is not in line with the received equilibrium models, although it exhibits strategic sophistication.

Bidding at sequential first-price auctions with(out) supply uncertainty: a laboratory analysis

We report on a series of experiments that test the effects of an uncertain supply on the formation of bids and prices in sequential first-price auctions with private-independent values and unit-demands. Supply is assumed uncertain when buyers do not know the exact number of units to be sold (i.e., the length of the sequence). Although we observe a non-monotone behavior when supply is certain and an important overbidding, the data qualitatively support our price trend predictions and the risk neutral Nash equilibrium model of bidding for the last stage of a sequence, whether supply is certain or not. Our study shows that behavior in these markets changes significantly with the presence of an uncertain supply, and that it can be explained by assuming that bidders formulate pessimistic beliefs about the occurrence of another stage.

Auctions for government securities: a laboratory comparison of uniform, discriminatory and spanish designs

The Bank of Spain uses a unique auction format to sell government bonds, which can be seen as a hybrid of a uniform and a discriminatory auction. For winning bids above the average winning bid, buyers are charged the average winning bid, otherwise they pay their respective bids. We report on an experiment that compares this auction format to the discriminatory format, used in most other countries, and to the uniform format. Our design is based on a common value model with multi-unit supply and two-unit demand. The results show significantly higher revenue with the Spanish and the uniform formats than with the discriminatory one, while volatility of prices over time is significantly lower in the discriminatory format than in the Spanish and uniform cases. Actual price dispersion is significantly larger in the discriminatory than in the Spanish. Our data also exhibit the use of bid-spreading strategies in all three designs.