Combinatorial Games under Auction Play

ARichman gameis a combinatorial game in which, rather than alternating moves, the two players bid for the privilege of making the next move. The theory of such games is a hybrid between the classical theory of games (von Neumann, Morgenstern, …) and the combinatorial theory of games (Berlekamp, Conway, Guy, …). We expand upon our previous work by considering games with infinitely many positions as well as several variants including thePoorman variantin which the high bidder pays a third party (rather than the other player).Journal of Economic LiteratureClassification Number: C7.     

A Sealed-Bid Auction That Matches the English Auction

This paper analyzes a two-stage sealed-bid auction that is frequently employed in privatization, takeover, and merger and acquisition contests. This auction format yields the same expected revenue as the open ascending (English) auction, yet is less susceptible to preemptive bidding and collusion. Journal of Economic Literature Classification Number: D44.     

The Endowment Effect and Repeated Market Trials: Is the Vickrey Auction Demand Revealing?

The difference between people's valuations of gains and losses has been widely observed in both single trial and repeated trial experiments, as well as in survey responses and in commonplace behavior. However, the results of some Vickrey auction experiments indicate that the disparity may decrease, or even disappear, over repeated trials. This paper reports the results of two further repeated Vickrey auction experiments that test the impact of both a second price and a ninth price auction rule on valuations. Although valuations should be independent of this variation in the exchange price rule, the manipulation had a dramatic impact on subjects' stated values of a common market good. The results suggest that the endowment effect remains robust over repeated trials, and that contrary to common understanding, the Vickrey auction may elicit differing demands dependent on the context of the valuation.     

成本分担博弈与维克里拍卖机制研究

成本分担博弈中的平均分担机制往往导致参与人低报自己的收益率,从而导致博弈结果的无效率。笔者通过在成本分担博弈中引入维克里机制,利用参与人的占优策略——说真话,使成本分担博弈的结果实现了帕累托最优配置。     

Vickrey auctions with reserve pricing

Summary. We generalize the Vickrey auction to allow for reserve pricing in a multi-unit auction with interdependent values. In the Vickrey auction with reserve pricing, the seller determines the quantity to be made available as a function of the bidders' reports of private information, and then efficiently allocates this quantity among the bidders. Truthful bidding is a dominant strategy with private values and an ex post equilibrium with interdependent values. If the auction is followed by resale, then truthful bidding remains an equilibrium in the auction-plus-resale game. In settings with perfect resale, the Vickrey auction with reserve pricing maximizes seller revenues.Received: 31 December 2002, Revised: 5 May 2003, JEL Classification Numbers: D44, C78, D82.Correspondence to: Lawrence M. AusubelThe authors gratefully acknowledge the generous support of National Science Foundation Grants SES-97-31025, SES-01-12906 and IIS-02-05489. We appreciate valuable comments from Ilya Segal. Special thanks go to Mordecai Kurz, who served as Larry's dissertation advisor and who introduced both authors to the economics profession back at IMSSS at Stanford. Congratulations and best wishes are extended to Mordecai and his family on the happy occasion of the publication of Assets, Beliefs, and Equilibria in Economic Dynamics: Essays in Honor of Mordecai Kurz, in which this article also appears.     

Optimality and Robustness of the English Auction

In Milgrom and Weber's (1982, Econometrica50, 1089–1122) “general symmetric model,” under a few additional regularity conditions, the English auction maximizes the seller's expected profit within the class of all posterior-implementable trading procedures and fails to do so among all interim incentive-compatible procedures in which “losers do not pay.” These results suggest that appropriate notions of robustness and simplicity which imply the optimality of the English auction for a risk-neutral seller must impose “bargaining-like” features on the set of feasible trading mechanisms. Journal of Economic Literature Classification Numbers: D44, D82.     

Laboratory Behavior in Spot and Forward Auction Markets

Auctions that require advance production increase seller costs because inventories must be held. This cost does not exist in production-to-demand markets for which production follows trading, and sales exactly match quantities produced. Data from laboratory computerized double auction markets show that advance-production prices are significantly higher and quantities traded are significantly lower than they are in production-to-demand auctions. Price convergence patterns show advance-production sellers moving toward 9% higher prices and 22% greater earnings.     

Auction Design for the Allocation of Emission Permits in the Presence of Market Power

To the extent that emission permits have been allocated using market mechanisms, this has been done using a sealed-bid auction design, typically with discriminatory prices. However, several authors have recommended the ascending auction format. Basically, two competing ascending auction designs have been suggested, the standard ascending auction (with clock or demand schedules), or an alternative ascending-clock implementation of Vickrey-pricing. The latter design was introduced as a response to problems of bid shading under the sealed-bid and the standard ascending auction format. The purpose of this paper is to investigate the allocation of permits under these two alternative mechanisms. The auction process and the resulting market outcome in the presence of oligopolistic competition are simulated. In this setting, it is not obvious that bid shading is the optimal strategy under the standard design, nor is it obvious that sincere bidding is the optimal strategy under the alternative ascending auction design. The alternative auction format makes it less costly to pursue a strategy to increase market shares through the acquisition of emission permits, thus increasing the competitor's costs, leading to overbidding as the optimal strategy.     

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.     

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.     

Numerical Computation of Equilibrium Bid Functions in a First-Price Auction with Heterogeneous Risk Attitudes

We use numerical methods to compute Nash equilibrium (NE) bid functions for four agents bidding in a first-price auction. Each bidderi is randomly assigned:r _i [0,r _max], where 1 –r _i is the Arrow-Pratt measure of constant relative risk aversion. Eachr _i is independently drawn from the cumulative distribution function (·), a beta distribution on [0,r _max]. For various values of the maximum propensity to seek risk,r _max, the expected value of any bidder's risk characteristic,E (r _i ), and the probability that any bidder is risk seeking,P (r _i > 1), we determine the nonlinear characteristics of the (NE) bid functions.     

Auction prices, market share, and a common agent

The primary pro-competitive justification for multiple principals to hire a common bidding agent is efficiency. The efficiency gained by doing so increases the advantage of the common bidding agent. Almost common value auction theory predicts that an advantaged bidder is able to reduce competition by credibly enhancing the ‘winner's curse’ of disadvantaged rivals. The credible threat results in disadvantaged rivals exiting the bidding process early, leaving the advantaged bidder to purchase most, if not all, units at lower prices than when rivals have common values. The results of our empirical study of a common bidding agent are consistent with this theory.     

Cartels and the Incentive to Cheat: Evidence from the Classroom

Several points about cartel behavior are illustrated, using the curve on an exam.     

The Effect of Bidder Heterogeneity on Combinatorial Conservation Auction Designs

In an iterative combinatorial auction, bidders can submit bids on individual and/or on combinations of projects in a series of intermediate rounds, where bid prices are revised before a final allocation is made. The iterative format is useful for conservation service procurement as landholders can rely on market information revealed through the rounds to evaluate their choices of projects and bid prices. However, there is no single way of providing the market information. Different designs for generating price information have been proposed. Little is known about the performance of iterative combinatorial auction designs when heterogeneous bidders, with different cost structures, participate in an auction. Using an agent based model, we evaluate a selected set of designs under different bidder heterogeneity scenarios. We observe that higher degrees of heterogeneity lead to lower auction efficiency and that auction outcomes are highly sensitive to price feedback design choices.     

Quantal Response Equilibrium and Overbidding in Private-Value Auctions

This paper applies the quantal response equilibrium (QRE) model to study overbidding in private-values auctions. Experimental evidence shows that the prevalence of overbidding depends on the cost of overbidding relative to underbidding, as predicted theoretically. We use QRE as an error structure to estimate parameters of several competing models of overbidding. A QRE model based on risk averse bidders closely tracks the exact distribution of bids. The estimated parameters are significant and consistent across treatments. Journal of Economic Literature Classification Numbers: C72, C92, D44.     

The Design of ``Smart' Water Market Institutions Using Laboratory Experiments

One of the problems with proposals for substantialinstitutional change in water systems is thatmodification and irreversibility make the processslow, cautious and costly to society. In this paper,we discuss the role that experimental economics canplay in evaluating proposed institutional changes tohelp facilitate a more rapid and smooth adoption ofchanges in the water system. Experimental economicsyields a formal and replicable system for analyzingalternative market structures before they are actuallyimplemented. For example, a water market can bedeveloped and tested in the laboratory under supplyand demand constraints that reflect drought conditionsthat might occur in California, or other arid regionsin the world. We present a prototype of a Californiawater transfer model and the results from a series ofwater market experiments. Results include realizedmarket efficiency and surplus distribution, as well asan analysis of market price volatility. Theimplications of this research extend well beyondCalifornia water markets, not only to water markets inother arid regions, but also to the design of marketsfor other environmental goods, including tradablepollution permits and fishery ITQs.     

不同一口价组合拍卖机制下的卖方收益比较研究

随着电子商务的发展,作为网上拍卖方式之一的一口价拍卖逐渐盛行起来。网上一口价拍卖打破了时间和空间的限制,因而被广泛应用于组合拍卖中。笔者针对目前拍卖网站所采用的两种不同拍卖规则:固定一口价和持久一口价,在独立私人估价模型下分析比较了上述两种规则下的卖方期望收益。     

模拟植物生长算法在组合优化问题中的应用:研究进展

首先介绍了系统文献综述方法论与操作流程,从不同维度给出了文献分类标准;然后基于行政机构和出版来源分类标准,梳理了模拟植物生长算法(PGSA)的研究现状;接着分别针对电力系统、应急管理、设施选址、斯坦纳树、车间调度和旅行商等组合优化问题,对PGSA应用的代表性研究进行了综述,重点介绍了PGSA在若干领域的应用;最后从不同视角总结了已有研究成果,并指出PGSA解决组合优化问题的未来研究方向和具体内容。     

An Improved Reverse Auction for Addressing Water Quality in Agricultural Watersheds Using Coupled Simulation-Optimization Models

As nutrients and sediment in agricultural watersheds continue to degrade water quality, attention is increasingly given to reverse auctions to cost-effectively address these pollutants. Typically, reverse auctions include a selection process which depends on both the monetary bid and a ranking of the environmental benefit, where the latter is often approximated using simple models, such as the Universal Soil Loss Equation （USLE）. When the environmental objective is to improve water quality, the cost-effectiveness of such ranking methods cannot always be assured since simple models may poorly approximate the effects on downstream water quality. In this paper, we introduce an alternative reverse auction approach that takes advantage of richer watershed process models and optimization tools that are now much more commonly available. This ＂improved＂ reverse auction allows decision-makers to better consider the cost-effective assignment of conservation practices and to address water quality or other environmental objectives. In a spatially detailed simulation, we demonstrate how this approach can improve the design of a reverse auction for the Raccoon River Watershed in Iowa, and estimate the potential gains from using the simulation-optimization approach relative to simpler ranking methods for selecting bids. We also point out that simple bid ranking schemes may not yield sufficient nutrient reductions to achieve water quality goals but bids areeasily selected to achieve any feasible water quality improvement in the ＂improved＂ auction process.     

Auction theory adaptations for real life applications

We develop extensions to auction theory results that are useful in real life scenarios.1. Since valuations are generally positive we first develop approximations using the log-normal distribution. This would be useful for many finance related auction settings since asset prices are usually non-negative.2. We formulate a positive symmetric discrete distribution, which is likely to be followed by the total number of auction participants, and incorporate this into auction theory results.3. We develop extensions when the valuations of the bidders are interdependent and incorporate all the results developed into a final combined realistic setting.4. Our methods can be a practical tool for bidders and auction sellers to maximize their profits. The models developed here could be potentially useful for inventory estimation and for wholesale procurement of financial instruments and also non-financial commodities.All the propositions are new results and they refer to existing results which are stated as Lemmas.