ABSTRACT Title of Document: OPEN BID AUCTIONS: A THEORETICAL AND AN EXPERIMENTAL STUDY Dipan Ghosh, Doctor of Philosophy, 2008 Directed By: Professor Peter Cramton, Department of Economics For centuries, auctions have been used as an efficient market mechanism for selling or procuring goods. Over time, auctions have evolved from its very basic price call- out form to the much more sophisticated simultaneous multi goods design, the bulk of this dramatic evolution taking place in the later part of the twentieth century. Even though the earliest use of auction dates back to around 500 B.C. in history, proper scientific research aiming at improving the effectiveness or expanding the scope of this versatile market mechanism started around the 1960?s. The pioneering work of William Vickrey in 1961 opened the floodgates for mathematicians and economists alike, to study this fascinating market mechanism, and within a very short period of time, both the understanding of the mechanism and the scope of its application improved vastly. Over these years, a huge mass of theoretical and empirical research has produced results that introduce newer auction designs and characterize the existing ones. This has also allowed scope for continued research in the field of auctions, thriving for improvements and solutions to yet-to-be answered questions. The main goal of this study is to accomplish just that; present improvements that try to address issues that have not been addressed yet. The dissertation is structured as follows. The first chapter highlights the progress that has been made in the field of auctions and introduces the advancements made in the more recent field of auction experiments. This serves as an introduction to the other chapters and briefly outlines the important findings both in the traditional theoretical literature, the more recent operational research literature and the alternative experimental literature. The second chapter introduces a new auction model designed to tackle a specific problem encountered in multiple homogeneous goods auctions, which has not been dealt with satisfactorily thus far. The last chapter presents an extension of the existing auction experiment methodologies in an attempt to reveal possible weaknesses in earlier auction experiments and to improve our understanding of important differences between open and sealed-bid auction formats. OPEN BID AUCTIONS: A THEORETICAL AND AN EXPERIMENTAL STUDY By Dipan Ghosh Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2008 Advisory Committee: Professor Peter Cramton, Chair Professor Lawrence Ausubel Professor John Rust Professor Daniel Vincent Associate Professor S. Raghavan ? Copyright by Dipan Ghosh 2008 ii Dedication To my father Mr. A. K. Ghosh, my mother Mrs. D. Ghosh, and to Dr. Gopal Tribedi. iii Acknowledgements I am extremely grateful to my advisor, Professor Peter Cramton, for providing me with immense support and invaluable guidance throughout the writing of this dissertation. I would also like to take this opportunity to thank Professor Lawrence Ausubel, Professor John Rust and Professor Daniel Vincent for their encouragement and advice. I am thankful to Dr. Andreas Lange for all the academic support and guidance he provided which made the experimental study possible. I also thank Professor S. Raghavan for kindly agreeing to serve on my dissertation committee. A heart-felt thanks to Dr. Subrata Kundu and Gopal Dhar, for useful feedback and valuable suggestions. I would also like to thank all my friends in US and back home in India, especially Jyotiska Mitra, Souvik Gupta, Abhishek Ghosh, Soma Chowdhury, Aniruddha Bagchi, Arijit Mukherjee and Sudip Gupta, who have always supported and encouraged me to achieve my goal. A very special thanks goes out to Chandrima Chatterjee, who has made this journey a fun-filled and a joyous one for me. I also take his opportunity to thank my family back in India, and my parents-in- law, for their well-wishes and continued moral support which helped me pull through difficult times. iv Lastly, and most importantly, I would like to thank the two most important people in my life without whom this would never have been a reality. I take this opportunity to thank my mother, Mrs. Dipali Ghosh, who has been a constant source of inspiration for me over these years and to whom I owe every little thing that I have achieved so far. Finally, I would like to thank my wife, Paramita Sinha, without whose constant encouragement, unconditional support, and unfaltering belief in me, this would not have been possible. I really have no words to thank her for her efforts and sacrifices. v Table of Contents Dedication.....................................................................................................................ii Acknowledgements......................................................................................................iii Table of Contents..........................................................................................................v List of Tables...............................................................................................................vi List of Figures.............................................................................................................vii Chapter 1. Introduction: Auctions and Experiments....................................................1 1.1. Progress in the field of Auctions.......................................................................1 1.2. Auction Experiments ........................................................................................5 1.3 Reconciling Theory and Experiment ????????????????9 Chapter 2: An Efficient Multi-unit Auction with Increasing Marginal Values..........12 2.1. Introduction.....................................................................................................12 2.2. A Numerical Example and Some Intuitive Insights .......................................17 2.3. The General Model.........................................................................................23 2.4. The Auction Algorithm...................................................................................27 2.4.1. Allocation................................................................................................30 2.4.2. Prices.......................................................................................................30 2.5. The Numerical Example Revisited................................................................36 2.6. Multiple Bidders with Complementarities.....................................................38 2.6.1. Single Marginal Bidder............................................................................39 2.6.1.2 Allocation ???????????????????????43 2.6.1.2 Prices...................................................................................................45 2.6.2. Multiple Marginal Bidders.......................................................................46 2.6.2.1 Allocation............................................................................................51 2.6.2.2 Prices...................................................................................................51 2.7. Linear Programming Approach.....................................................................52 2.8. Concluding Remarks.......................................................................................61 Chapter 3: Price Manipulation by the Auctioneer: An Experimental Study .............65 3.1. Introduction....................................................................................................65 3.2. Preliminary Theory........................................................................................69 3.3. Experimental Idea..........................................................................................72 3.4. Experiment Design.........................................................................................75 3.5. Results............................................................................................................78 3.6. Concluding Remarks......................................................................................83 Appendix.................................................................................................................85 Proof of Theorem 1:................................................................................................85 Proof of Theorem 2:................................................................................................87 Proof of Theorem 3.1 and 3.2:................................................................................89 Proof of Theorem 4.1 and 4.2:................................................................................90 Bibliography...............................................................................................................91 vi List of Tables 2.1 Marginal Valuations in a Spectrum License Auction ??????????.18 2.2 Possible Auction Outcome ????????????????????.18 2.3 Proposed Auction Outcome ????????????????????36 2.4 Greedy Algorithm ???????????????????????...55 2.5 KP Example 1 ?????????????????????????.55 2.6 KP Example 2 ?????????????????????????.56 2.7 KP Example 3 ?????????????????????????.57 2.8 Marginal Values ????????????????????????..58 2.9 KP Formulation ????????????????????????...58 2.10 KP Example with Complementarities ????????????????.59 2.11 Extended Greedy Algorithm Example ????????????????60 3.1 Baseline Treatment: P Values ???????????????????.79 3.2 Baseline Treatment: Summary Statistics ???????????????79 3.3 Explicit Manipulation: P Values ??????????????????.80 3.4 Explicit Manipulation: Summary Statistics ??????????????81 3.5 Implicit Manipulation: P Values ??????????????????.82 3.6 Implicit Manipulation: Summary Statistics ??????????????83 vii List of Figures 2.1. Discontinuous Demand ?????????????????????...14 2.2. Excess Demand and Excess Supply ?????????????????21 2.3. The MAP Solutions ..??????????????????????...21 2.4. Demand is equal to Supply with Complementarities ..........................................22 3.1. Bid Functions ...???????????????????????.......72 3.2. Baseline Treatment Bidding Outcome ................................................................80 3.3. Explicit Treatment Bidding Outcome .................................................................81 3.4. Implicit Treatment Bidding Outcome .................................................................83 1 Chapter 1. Introduction: Auctions and Experiments 1.1. Progress in the field of Auctions From the very early days of human civilization, auctions have been serving as an important market design, the first use of auction dating back to as early as 500 B.C. Historical accounts of auction usage are widespread, ranging from the property and estate goods auctions employed by the Romans to the fund-raising auctions used by the Chinese monks. More recent accounts would be from the late 17th and the early 18th century, when the first auction houses were created in the England. Auctions have been used extensively since then not only for selling artworks or collectibles, but also for varied purposes like century old practices of selling flowers and fish, to more modern ones like selling radio-wave spectrums, electricity and oil field drilling rights, to name a few. However, even though there are numerous accounts of auction usage throughout history as an efficient market mechanism, there is no account of any scientific research studying the working of an auction before the twentieth century. The pioneering work that opened the floodgates for mathematicians and economists alike, to study this fascinating market mechanism, would be the seminal work of William Vickrey in 1961. Since then, progress in the field of auctions has been overwhelming. Over these years, auction theorists have studied and developed designs for single unit, multiple identical units, multiple heterogeneous units and more recently, packaged units auctions. Irrespective of the auction environment, the main issues addressed by the auction-design literature have been allocative efficiency of the auction and a pricing rule consistent with the efficient allocation. 2 In a single object environment, the two most coveted auctions that take care of these two issues are the English auction and the Vickrey auction, though studies reveal the desirability and prevalence of the former over the latter (McAfee and McMillan,1987, Milgrom,1987). The rationales provided by the literature for this phenomenon are simply the strategic advantages that the open ascending bid English auction enjoy over the closed sealed bid Vickrey auction. Firstly, there is an informational advantage enjoyed by the bidders in an ascending open auction because they can observe the bids placed by the other bidders after every round and can update their future actions accordingly (Milgrom and Weber, 1982). Also, in an ascending bid auction, all that is revealed is the second highest valuation and the winner gets to preserve his own valuation for the object. This privacy preservation property of an open ascending bid auction has important implications. Since the winner does not have to reveal her own valuation, she feels insulated from any kind of manipulation by the auctioneer and feels less vulnerable for future negotiations. One of the most important and effective pricing rule prescribed by the auction literature is the one first conceptualized by Vickrey in 1961, where the price paid by a bidder is independent of that bidder?s bid. The simplest argument in favor of this simple yet effective rule is the fact that since a bidder?s bid has no effect on her price, there is every incentive for the bidder to bid truthfully. Indeed, in all the auction forms where the pricing rule satisfies this property, like the open English or the closed Vickrey auctions, the bidder?s optimum strategy is to bid truthfully and the 3 outcome is efficient. Truthful bidding is given so much importance by auction designers because it helps to achieve an efficient allocation. In a multi-unit auction, a special form of this rule is used which is also known as the Vickrey pricing rule. The price the winning bidder pays under such a rule for each unit she wins is exactly equal to the opportunity cost of assigning this unit to that bidder. In other words, the bidder gets to keep the marginal valuation she adds to the auction by being a part of it, which is better known as the bidder?s marginal product. The Vickrey prices paid by a bidder are always independent of her own bid, which encourages the bidder to bid truthfully. However, the sealed bid multiple-unit auction that Vickrey designed required the bidders to reveal their entire demand schedule. Later, Ausubel devised an open ascending auction for multiple units of the same good that mimicked Vickrey?s results and showed that prices in his auction matched that of Vickrey?s (An Efficient Ascending-Bid auction for Multiple Objects, AER). Another aspect of the auction literature, especially relevant for the multi-unit case, is the reliance on the substitutes property or the gross substitutes condition. Essentially, what it means is that each of the multiple units of the single good or the multiple goods offered for sale has to be treated like substitutes by all the bidders. This turns out to be one of the important properties that need to be satisfied in order to reach equilibrium in such auction models. In the multiple-unit single good case, this simply requires the bidders to have non-increasing marginal valuations and in the multiple goods case, this requires the valuations to be sub-additive. However, this assumption 4 is not always realistic. A simple example that illustrates this in the case of multiple- unit single good case is as follows. Suppose we have a spectrum license auction where six spectrum licenses of the same frequency are being auctioned off. There are four bidders out of which three are well- established ?big players? in that market and one firm that is a new entrant to this market. The three incumbent firms, quite understandably, treat all the licenses as substitutes, meaning they have non-increasing marginal utilities for the six licenses. However, the smaller firm, since it is a new entrant, might require a certain number of licenses, let?s suppose three, to set up a proper network needed to operate successfully. Under such circumstances, the smaller firm should treat the first three licenses as complements and thus should have increasing marginal valuations over these units. When confronted with such a situation, the existing ascending auction designs fail to produce an efficient outcome, the main reason for such a failure being the non-existence of a Walrasian equilibrium price at which demand is exactly equal to the supply. In recent times, a vastly developing field of auction theory has been combinatorial auctions, which deals with multiple goods bundled as packages. In fact, the popularity of combinatorial auctions have transcended the field of economics and crossed over to operations research and even computer science. In this area of combinatorial auctions with package bidding, Ausubel and Milgrom, 2002, have studied the results of relaxing the gross substitute property in their proxy auction. Similarly, in the field 5 of operations research, Bikhchandani and Ostroy, 2002, Bikhchandani et al, 2001, Parkes and Ungar, 2002, and Parkes and Mishra, 2004 have papers devoted to the computational solution of a similar problem in a multiple goods setting using linear programming techniques. In all of these studies, the auction problem is interpreted as a linear programming problem with the objective to compute the equilibrium outcome using primal-dual algorithms. However, the issues addressed in these studies differ not only in nature with those studied in this paper, but also in the way they are treated. Combinatorial auction models are much more complex models, which look at multiple goods auctioned off as packages. The solution techniques not only involve demanding mathematical rigor, but also tackle the problem solely from the computational aspect, especially those in operations research. Though the multiple unit single good model studied in this paper can be perceived as a special case of the broader class of combinatorial auction models, applying the linear programming techniques to solve such a model not only unnecessarily complicates matters but also is highly inefficient in terms of the technicalities involved. 1.2. Auction Experiments Even though experimental economics has been a relatively new branch of applied and behavioral economics, there has been a considerable amount of research dedicated to studying different auction design in laboratory settings. The main focus of such experiments has been to study the ?Revenue Equivalence?, ?Strategic Equivalence?, or certain behavioral aspects of different auction mechanisms. We will focus our interest on the experimental 6 studies related to sealed and open bid auction designs and will try to bring to the reader?s attention an important issue which has not be addressed so far. One of the most fundamental guidelines for designing an effective auction, as prescribed by the auction literature, has been an open structure of bidding, which maximizes the information made available to each bidder at the time of bidding1. Another important attribute of open auctions is privacy-preservation. While all the bidders are asked to reveal their entire demand schedule in a sealed bid auction, the winning bidders do not have to reveal their values in an open auction. Michael H. Rothkopf, Thomas J. Teisberg, and Edward P. Kahn (1990) pointed out that due to this fact, if the bidders apprehend cheating by the auctioneer or if there are going to be subsequent auctions or negotiations, bidders will be more reluctant to reveal their true values in sealed bid auctions. Richard Engelbrecht-Wiggans and Charles M. Kahn (1991) and Rothkopf and Harstad (1995) also provide models emphasizing the importance of protecting the privacy of winners? valuations. In fact, for single-object environments, studies have revealed the desirability and prevalence of ascending open bid English auctions over the closed sealed bid version (see, for example, the excellent surveys of R. Preston McAfee and John McMillan, 1987, and Milgrom, 1987). A considerable amount of experimental work has been done which address different issues in multiunit auction designs. Early work by Miller and Plott, 1985, compared revenue raising aspect of uniform and pay-your-bid auctions. James C. Cox et al., 1984, 1985 and Kevin A. McCabe et al., 1990, 1991, have used laboratory experiment to study multiunit auctions with single unit demand. More recent studies, like that of Paul Alsemgeest et al., 1998, address the important issue of demand reduction in multiunit auctions. List and Reiley, 2000, have studied demand reduction in multiunit auctions in a field experiment where they use naturally 1 See Milgrom and Weber, 1982a 7 occurring data from a sports card show. In their paper, they compare outcomes from a uniform auction to those from a Vickrey auction. Kagel and Levin, 2001, address this same issue of demand reduction in multiunit auctions in a laboratory setting where they compare outcomes from both a sealed bid and an open bid uniform auction to the dynamic Ausubel auction. More closely related to this study would be Kagel, Kinross and Levin, 2001, where outcomes from the sealed bid Vickrey auction are compared to those from two versions of the dynamic Ausubel auction in the absence of complementarities. To complete this list would be the studies by Grimm and Engelmann, 2002, experimentally comparing five auction formats, and Manelli, Sefton and Wilner, 1999, comparing Vickrey with Ausubel auction using bidders with interdependent values. The choice between an ascending open-bid and a closed sealed-bid auction has been one of the most debated topics in auction theory. Though the standard auction literature prescribes the ascending auction over the sealed-bid one, experimental studies have shown that the latter outperforms the former, both in laboratory and in field settings. Theoretically, the ascending auction design is more appealing compared to its sealed-bid counterpart because it does not require the bidders to reveal their entire demand, thus insulating them from any possible manipulation by the auctioneer. In addition, due to its dynamic nature, the bidders can update their information set every period to ensure more efficient bidding. However, experimental studies have shown that the sealed bid format outperforms the open bid one, both in laboratory and in field settings. In such experiments, bidders are found to be bidding more aggressively in sealed bid auctions which contradicts the theoretical predictions directly (see Kagel, 1995 and Davis and Holt, 1993 for useful surveys of auction theory and laboratory experiments). Cox et al., 1985, Kagel et al., 1987, and Kagel and Levin, 1993 have all observed overbidding in sealed bid laboratory studies. Kagel and Levin, 2001, find overbidding relative to the dominant strategy in a sealed bid uniform price auction in a 8 laboratory setting. List and Reiley, 2001, observe this same result of overbidding on the first unit in a sealed bid uniform auction, in a field experiment using data from a sports card show. Broadly speaking, these discrepancies can be categorized into three stylized facts. Firstly, subjects consistently bid more aggressively than predicted by theory in sealed bid first price auctions with independent private valuations.2 Secondly, subjects consistently bid more aggressively than predicted by theory in sealed bid second price auctions.3 Finally, strategic equivalence between English auctions and second-price sealed bid auctions fails, with far less overbidding in English auctions than in second price sealed bid auctions.4 To reconcile these anomalous results with standard theoretical predictions, a variety of explanations have been offered. For first price auctions, it can be shown theoretically that if bidders are risk averse, there would be over bidding. Riley and Samuelson, 1981, showed that bidders engage in aggressive bidding in first price auctions with risk averse preferences. Though this potentially might explain the first discrepancy, it completely fails to explain overbidding relative to the dominant strategy in second price auctions. More qualitative explanations are advanced by Kagel, Harstad and Levin, 1987, where they point out the difference in feedback from overbidding in the two auction formats as a possible source of overbidding. They argue that since the impact of overbidding is much more immediate in open auctions as compared to the closed ones, overbidding is more common in the latter. More recently, some behavioral studies have also tried to explain these discrepancies. Ettinger, 2002, and Das Varma, 2002, both study auctions where a winning bidder might exert externality on a losing bidder. In Ettinger?s paper, the winning bidder has incentive to bid more aggressively whereas the losing bidder has incentive to over bid in Das Varma?s 2 See, for example, Holt and Sherman, 2000, who give explicit graphs of measured bid functions in this case. 3 See, for example, Kagel, Harstad, and Levin, 1987. 4 Again, see Kagel, Harstad, and Levin, 1987 for a good example of clear experimental evidence of this phenomenon. 9 paper. Morgan et al., 2003, model a spite motive in bidders? preferences which successfully explains the discrepancies. In their model, the losing bidder has spiteful incentives which lead to aggressive bidding. Thus we see that there exists a wide variety of studies trying to explain the observed discrepancies. However, a seemingly important aspect has been overlooked from all of these studies. The whole premise of superiority of the ascending auction designs rests on the fact that less information is revealed in such auctions, which prevents any kind of price manipulation or other foul play by the auctioneer. Michael H. Rothkopf, Thomas J. Teisberg, and Edward P. Kahn, 1990, pointed out that if the bidders apprehend cheating by the auctioneer or if there are going to be subsequent auctions or negotiations, bidders will be more reluctant to reveal their true values in sealed bid auctions. Richard Engelbrecht- Wiggans and Charles M. Kahn (1991), and Rothkopf and Harstad (1995) also provide models emphasizing the importance of protecting the privacy of winners? valuations. However, none of the experimental studies have tried to capture this aspect of manipulation by the auctioneer. In all these experiments, the experimenter herself is the auctioneer, which right away rules out any apprehension about possible foul play by the auctioneer. With the experimenter acting as the auctioneer, this is nothing but natural. The experimenter is obligated to compute the prices and the allocation according to the rules disclosed at the beginning of the experiment. Thus, the most important rationale favoring the open auction over the sealed bid auction has not been experimentally verified yet, which also appears to be a realistic one. 1.3. Reconciling Theory and Experiment The main goal of this study is a two-pronged approach. The second chapter presents an ascending-bid auction in a multi-unit private value setting with increasing marginal 10 values. This auction mechanism is an extension of the dynamic Ausubel auction, which successfully implements the efficient outcome with non-increasing marginal values. The Ausubel auction algorithm breaks down in settings with increasing marginal values, due to the non-existence of a Walrasian equilibrium price. The proposed dynamic auction achieves efficiency in such auction environments, and like all dynamic auctions, does not require the bidders to fully express their demand curves. We use the VCG prices, inducing truthful bidding as a best response strategy. We first consider a setting in which a single bidder has increasing marginal values, and then examine the general case of several bidders with increasing marginal values. The distinguishing feature of this new auction is the fact that it is an open ascending bid auction. To the best of our knowledge, this would be the only ascending auction design that would be able to achieve efficiency even with increasing marginal values. However, since the same efficient outcome could also be achieved with a sealed bid auction, it is imperative to show how and why an open auction should be favored over a sealed bid auction. Even though the auction design literature strongly favors the open auction over the sealed bid auction, several experimental studies have produced results that are quite the opposite. Thus the second feature of this dissertation is a study that complements the first part and tries to establish the theoretical superiority of the open auction in a laboratory setting. Using a new approach to auction experiments, the main objective of the experimental study is to observe bidding behavior in sealed bid auctions and rationalize the theoretical claims by means of statistical inference. In this paper, we studied the effect of price manipulation by the auctioneer on the bidding behavior in a sealed bid auction. Our results suggest that bidding behavior in the sealed bid auction format is affected by possible price manipulation by the auctioneer. As expected, we have a much larger effect with explicit manipulation. Both with explicit and implicit manipulation, we have demand reduction compared to the no- 11 manipulation, second price auction bidding. Based on these preliminary findings, we are confident enough that our new experiment design might be applied more extensively to validate the theoretical claim of superiority of open auctions over sealed bid auctions on the premise that bidders bid sub-optimally in fear of price manipulation in sealed bid auctions. To the best of our knowledge, this is the first study that tries to analyze this experimentally. As a possible source of future research, we would ideally want to expand the scope this present study and analyze similar situations in a field experiment setting. One such possibility would be online auctions, which might be used to study this phenomenon Chapter two of this dissertation introduces the new ascending open bid auction design that could be used to achieve efficiency even with increasing marginal values. Apart from the theoretical model and the formal algorithm, it also presents an illustrative example. The third and the last chapter presents the experimental study where the new auction experiment is discussed in details and the numerical results are presented. 12 Chapter 2: An Efficient Multi-unit Auction with Increasing Marginal Values 2.1. Introduction This paper introduces an ascending price auction design for multiple homogeneous goods in a private value setting, where the bidders might exhibit complementarities. These are auctions where multiple units of the same good are sold, like spectrum license auctions of the same frequency or treasury bill auctions of the same denomination. In such auction environments, complementarities are captured by increasing marginal values. The proposed algorithm, unlike any of the existing ascending price auction designs, achieves the efficient allocation in such auctions with increasing marginal values. The contribution of this work is twofold. It allows the bidders to exhibit increasing marginal values. This is of utmost importance because the auction literature does not provide a satisfactory answer to this specific problem of complementarities in multiple homogeneous good auctions. Equally important is the fact that it is an ascending bid auction design, which several studies have revealed to be more prevalent and more desirable than its sealed-bid counterpart5. The multiunit sealed-bid Vickrey6 is the only existing auction design that can allocate the units efficiently without requiring the values to be non-increasing. Another desirable feature of the Vickrey auction is the fact that truthful bidding is an 5 See McAfee and McMillan, 1987, and Milgrom, 1987 6 See Vickrey, 1961 13 equilibrium strategy. However, being a sealed bid auction, it requires the bidders to reveal their entire demand, which has been shown to have a negative effect on the bidding behavior7. Consequently, efforts have been made to replicate the static sealed-bid Vickrey results in a dynamic setting but with very limited success. In fact, the only dynamic auction design that successfully replicated the static Vickery outcome was devised by Ausubel in 20048. This ascending price auction does not require the bidders to reveal their entire demand to compute the efficient allocation. However, the efficiency of this design is severely restricted to non-increasing marginal values only. In fact, there does not exist any dynamic multiunit auction design that would replicate the static Vickrey results in a more general increasing marginal values setting. This paper attempts to bridge this gap by introducing a multiunit auction design that extends the Vickrey results to a more general dynamic setting. Though complementarities are usually associated with heterogeneous goods, increasing marginal values cannot be ruled out in homogeneous good auctions. For example, one of the bidders in a multiunit pollution permit auction might require a minimum number of permits for optimal production; or one of the bidders in a multiunit spectrum license auction might require a minimum number of licenses to set up a proper network. In both these two cases, the aforementioned bidders would have increasing marginal values. The presence of such bidders in multiunit auctions could be a serious problem. Even with only one such bidder, there would be an indivisible 7 See Milgrom and Weber, 1982, Engelbrecht-Wiggans and Kahn , 1991, and Rothkopf and Harstad , 1995 8 See Ausubel, 2004 14 bid for the units of complementarities. This would make the aggregate demand curve discontinuous, implying that a Walrasian equilibrium price, at which demand is equal to supply, might not exist. The following figure illustrates situations like these. With a non-existent equilibrium price, the existing ascending price auctions fail to achieve the efficient allocation and might also lead to the Exposure problem9. However, this does not pose a threat for the proposed auction design because it does not require a market clearing price to compute the efficient allocation. In any auction design, prices play an extremely important role in determining the bidding strategies. One of the most important and effective pricing rule prescribed by 9 Exposure problem refers to the situation where a bidder gets only a part of her package and is asked to pay a price higher than her value Quantity Quantity Price Price Supply Supply Demand Demand Fig. 2.1.A: Continuous Case Fig. 2.1.B: Discrete Case Fig. 2.1: Discontinuous Demand. The supply curve intersects the demand curve at the discontinuous part, implying that there does not exist a price at which demand is equal to supply 15 the auction literature is the one first conceptualized by Vickrey in 1961, where the price paid by a bidder is independent of her own bid. The most convincing argument in favor of this simple yet effective rule is the fact that since a bidder?s bid has no effect on her price, there is every incentive for the bidder to bid truthfully. In a multiunit auction, a special form of this rule is used which is known as the Vickrey- Clarke-Groves (VCG)10 mechanism. The payment of the winning bidder under such a mechanism, for each unit she wins, is exactly equal to the opportunity cost of assigning this unit to that bidder. In other words, the bidder gets to keep the marginal value she adds to the auction by being a part of it, which is better known as the bidder?s marginal product. The VCG prices paid by a bidder are always independent of her own bid, which encourages the bidders to bid truthfully. The prices the winning bidders pay in the proposed auction are the VCG payments. Consequently, this implies that the bidders should bid truthfully. In recent times, a vastly developing field of auction theory has been combinatorial auctions, which deals with multiple goods bundled as packages. In fact, the popularity of combinatorial auctions have transcended the field of economics and crossed over to operations research and even computer science. In this area of combinatorial auctions with package bidding, Ausubel and Milgrom, 2002, have studied the results of relaxing the gross substitute property in their proxy auction. Similarly, in the field of operations research, Bikhchandani and Ostroy, 2002, Bikhchandani et al, 2001, Parkes and Ungar, 2002, and Parkes and Mishra, 2004 have papers devoted to the computational solution of a similar problem in a multiple goods setting using linear 10 See Vickrey, 1961, Clarke, 1971, and Groves, 1973 16 programming techniques. In all of these studies, the auction problem is interpreted as a linear programming problem with the objective to compute the equilibrium outcome using primal-dual algorithms. However, the issues addressed in these studies differ not only in nature with those studied in this paper, but also in the way they are treated. Combinatorial auction models are much more complex models, which look at multiple goods auctioned off as packages. The solution techniques not only involve demanding mathematical rigor, but also tackle the problem solely from the computational aspect, especially those in operations research. Though the multiple unit single good model studied in this paper can be perceived as a special case of the broader class of combinatorial auction models, applying the linear programming techniques to solve such a model not only unnecessarily complicates matters but also is highly inefficient in terms of the technicalities involved. The auction design presented here conforms to this need for a simpler and intuitive model without all the technical rigor, for the special case of increasing marginal values. The main model is discussed broadly in two parts. The first part deals with the case where one bidder with increasing marginal values is present. The second part deals with multiple bidders with complementarities. This is done solely to facilitate the understanding of the model, even though the first part can be treated as a special case of the second. The auctioneer does not need to know whether there is a single bidder or multiple bidders with complementarities ex ante. The single bidder algorithm can be transformed seamlessly into the multiple bidder algorithm as and when the 17 auctioneer receives the relevant information. The only reason for the above mentioned categorization is simplicity of exposition. The paper is structured as follows: Some preliminary intuitive ideas and an illustrative example are presented in the next section. The general model with single increasing value bidder is discussed in the section that follows. The auction algorithm, which shows how to compute the allocation and the prices, is presented in the next section. In the following section, the numerical example is revisited to explain how the auction works. Multiple bidders with complementarities are discussed next followed by a section on linear programming. In the concluding section, some experimental findings are presented along with the scope of future research. Proofs of theorems are relegated to the appendix at the end of the paper. 2.2. A Numerical Example and Some Intuitive Insights Let us suppose that in a spectrum license auction 6 identical blocks of licenses of the same bandwidth are being auctioned off. There are 4 bidders out of which 3 are well- established incumbent in that market. The fourth firm is a new entrant. The new entrant might require a certain number of licenses, let us suppose 3, to set up a proper network needed to operate successfully. Under such circumstances, the entrant should treat the first 3 licenses as complements and thus should have increasing marginal valuations over these units. Table 2.1 depicts such a situation where B1 is the entrant firm and the other three are the incumbent firms. 18 Table 2.1: Marginal Valuations in a Spectrum License Auction: 1st license 2nd license 3rd license 4th license 5th license 6th license B1: 0 0 18 2 2 2 B2: 13 10 2 2 2 2 B3: 12 4 2 2 2 2 B4: 11 5 2 2 2 2 When confronted with such a situation, the existing ascending auction designs fail to produce an efficient outcome, the main reason for such a failure being the non- existence of a Walrasian equilibrium price at which demand is exactly equal to the supply. Table 2.2 shows what would happen if a standard ascending price auction is used to allocate the 6 licenses among the 4 bidders. Table 2.2: Possible Auction Outcome Price B1?s demand B2?s demand B3?s demand B4?s demand Total demand 0 6 6 6 6 24 2 3 2 2 2 9 4 3 2 1 2 8 5 3 2 1 1 7 6 0 2 1 1 4 19 Clearly, there does not exist a price at which demand is equal to supply; the demand is greater than the supply for all prices equal to or less than 5 and the demand is less than supply for all prices above 5. Therefore, the standard ascending auctions break down under such situations and fail to render an equilibrium outcome. In instances like these, the non-existence of the equilibrium price can be solely attributed to the fact that the bidder with complementarities is the marginal bidder. A marginal bidder is the bidder who has the Mth highest value in an M unit auction. For example, if the top 6 values in a 6 units auction are 13, 12, 11, 10, 9, 8, then the bidder with the value 8 is the marginal bidder. If a bidder with complementarities is the marginal bidder, then her average value for the units of complementarities is the Mth highest value. For example, if the top 6 values in a 6 units auction are: 13, 12, 11, 10, 6, 6, 6, then the bidder with the average value 6 for 3 units of complementarities is the marginal bidder. This particular type of bidders would always have an all-or- nothing bid for the units of complementarities. This would lead to a multiunit reduction in demand at the margin, resulting in a shift to excess supply directly from excess demand, without demand equaling supply ever. Figure 1 depict situations like these in a continuous and a discrete framework. The allocation problem in auctions like these, with single bidder complementarities, essentially is to decide how to allocate units at the margin. In an auction where M units are being sold and the marginal bidder has complementarities over K( M. Let us suppose that at round t*, excess demand changes to excess supply for the first time. i.e., Xt* < M and Xt*-1 > M The auctioneer increases the price further. The auction ends at round t when tX = M ? K. In other words, when the auction ends, only the bidders with top M ? K values remain active. In the first half of the allocation mechanism, these M ? K units are allocated to the active bidders in the final round according to their respective demands. The second half of the allocation mechanism tackles the MAP and determines how to allocate the rest of the K units efficiently. The information collected from the bidding rounds, namely the drop out prices, are then used to calculate the prices the winning bidders should pay. To solve the MAP efficiently, the auction algorithm must provide the necessary information regarding the bidders? values that is required to compute the efficient allocation. To be more precise, it is necessary to know the average value of the K units of complementarities of the marginal bidder and the K values this bidder is competing against. Once these valuations are known, the task of determining the 28 efficient allocation becomes a simple one. It can be achieved by comparing the total value of K units (the average value times K) for the bidder with complementarities and the sum of the remaining K values13. Obviously, the one that has a higher total value is chosen. Now, as noted earlier, the only source of information in our model is the drop-out prices. If the auction mechanism could be designed such that the bidders bid truthfully, then the prices at which the bidders reduce their demand would actually be equal to their marginal value for that unit. As will be shown in later sections, wait-till-price-equals-value strategy is an equilibrium strategy and consequently, the efficient allocation could be computed using specific drop-out prices.14. Also, without any loss of generality, from now on I will just use values to mean reported and/or true values and prove that they are the same later, in Theorem 3. Before I present the allocation and pricing mechanism, I need the following preliminaries. First, I need to determine round t such that tX = M + K ? 1. Significantly, price at round t gives us the lowest amongst the top M + K values. Now, by recording prices from round t to round t and excluding round t*, I can get the bottom K values excluding the bidder with complementarities. The important 13 This is very much similar to the idea of comparing areas under the demand curve which we did in Fig. 2.3.A and Fig. 2.3.B 14 Out of the top M + K values, it is necessary to know the bottom 2K values; Out of which we have K units of complementarities and the remaining K values excluding the bidder with complementarities. The price at round t* gives the average value of the bidder with complementarities. To figure out the remaining K values, we need to look at K prices starting from the round when demand falls from M + K to M + K ? 1 all the way up to the round when demand falls from M ? K + 1 to M ? K, excluding the price at round t*. 29 assumption is that there is a single unit demand reduction in every round other than t*, where demand drops by K units. Next, for every round from round t to round t, I have to determine the set of Drop- outs Dt. i.e., find Dt ?t ? [t,t] The set of Drop-outs play an important role in the final allocation because they give us the identity of the bidder with complementarity ( *tD ) and that of the other bidders she is competing against. Finally, the clinches15 made by the bidders have to be registered. In our model, any clinch made after round t are redundant and thus are not recorded. Also, unlike the Ausubel auction, clinches in our model can be temporary. So Provisional Clinches, Ct, are determined for every round, starting from round 1 to round t . i.e., find Ct ?t ? [1,t] In the sub-sections that follow, I discuss the allocation and the pricing mechanisms. 15 For a detailed description of clinching, see Ausubel 2004. 30 2.4.1. Allocation The M ? K units that are demanded at round t are allocated to the bidders who have positive demand at round t . The algorithm for allocating the rest of the K units is as follows: ? Compare KPt* and t t t t P = ?? Pt* ? Case I: KPt* > t t t t P = ?? Pt* ; then j ? Dt* gets the remaining K units ? Case II: KPt* < t t t t P = ?? Pt* ; then i ? Dt gets 1 unit each ?t ? [t,t], t ? t*.16 For the time being, I postpone the discussion on efficiency of the proposed allocation and concentrate on the pricing mechanism used in this model. Later on, when I present Theorem 2, I will address this issue and show that the allocation is ex-post efficient. 2.4.2. Prices Arguably, the most important aspect of this model is the price. Following Vickrey?s notion of bid-independent prices, the amount a winning bidder pays in our model does not depend on her own bid. More specifically, the VCG payment mechanism for multiple units is used in this model. Thus, the price paid by bidder i is the opportunity 16 At every round t ? t*, there is a unit reduction in aggregate demand from the previous period. Now, including round t , there is 2K unit reduction in demand between round t and t , out of which K unit reduction occurs at round t*. Thus, there is a reduction of K units from rounds t to t , excluding round t* and for every such round, 1 unit is being awarded to the bidder who has reduced her demand in these rounds. Thus, K units are allocated between rounds t and t , and M - K units are allocated at round t . 31 cost of assigning those units to that particular bidder, and is computed from bids other than that of i. Mathematically, the price paid by bidder i conforms to the following formula; pi = V(N/i) ? ? ?ij jv where V(N/i) represents the total value generated by the efficient allocation without bidder i and ? ?ij jv represents the total value generated by the bidders other than i under the efficient allocation with bidder i. Thus, the important task here is to construct a pricing mechanism that conforms to the above principle. There are two price computational algorithms one for each distinct case of possible allocations. These are as follows: Case I: KPt* > t t t t P = ?? Pt* In this case, bidder j ? Dt* gets K units. The price he pays is pj = t t t t P = ?? Pt* . Bidders other than j get whatever they demand at the last round., i.e., bidder i ? j gets itx units. Now, let Ri be the sum of the prices in the last itx rounds where i ? Dt , excluding round t*. Bidder i pays Ri . Only Provisional Current Clinches made by bidder i ? j in rounds t < t are honored. 32 Case II: KPt* < t t t t P = ?? Pt* Here bidder j ? Dt* gets zero unit. Now, let yi be the number of units awarded to bidder i ? j. If yi > K then i pays KPt* for K units and the clinching prices for the rest of yi ? K units. If yi = K then i pays KPt* . Let us suppose yi < K. Let Ti be the sum of K ? yi prices in rounds where i ? Dt , starting from round t , excluding round t*. Then bidder i pays pi = KPt* ? Ti . As before, only Provisional Current Clinches made by bidder i ? j in rounds t < t are honored. Thus, the prices are indeed independent of one?s own bid and are computed solely using bids from other bidders. The next theorem uses this property of the price mechanism and shows that such prices imply that truthful bidding is an equilibrium strategy. Theorem 1: In this auction model, truthful bidding or wait-until-price-equals-value bidding strategy is a best response equilibrium strategy. Proof: See Appendix. Now, what remains is to show that the prices computed here are actually VCG prices, equal to the opportunity cost of allocating the units to that particular bidder. Using 33 Theorem 1, it can be shown that the prices computed before are indeed the VCG payments. Case I: KPt* > t t t t P = ?? Pt* In this case, bidder j ? Dt*, the bidder with complementarities, gets K units. According to the VCG principle, the price has to equal the opportunity cost of assigning these K units to bidder j, independent of her own bid. To calculate the opportunity cost of allocating these K units to bidder j, the next best alternative needs to be determined. Now, with truthful bidding or wait-until-price-equals-value bidding strategy, the K highest rejected bids (or simply, the drop-out prices) other than that of bidder j would give us the opportunity cost. Incidentally, the K highest rejected bids happen to be the K drop-out prices from round t to round t, excluding round t*.17 Thus, the VCG price for bidder j is, pj = t t t t P = ?? Pt* , which is exactly what our algorithm proposes. Bidders other than j get whatever they demand at the last round., i.e., bidder i ? j gets i tx units. Now, to calculate the VCG price for bidder i, the opportunity cost of allocating the itx units to bidder i needs to be determined. Like before, this implies that the highest rejected bids other than that of bidder i need to be considered. For example, if bidder i is awarded three units, then the chosen prices are from the last 17 Bidder j reduces demand in round t*, implying that p t* has to be ignored while calculating j?s price. 34 three rounds in which bidder i has not reduced her demand18. Also, pt* needs to be excluded because it is not a rejected bid. Now, let Ri be the sum of the prices in the last itx rounds where i ? Dt , excluding round t*. Then the VCG price bidder i ? j pays for itx units is Ri. This leads us to the next theorem. Case II: KPt* < t t t t P = ? - Pt* Here no unit is awarded to bidder j ? Dt* , the bidder with complementarities. Now, let yi be the number of units awarded to bidder i ? j. As before, to calculate VCG prices the opportunity costs need to be determined. Since the bidder with complementarities is the marginal bidder, any alternative efficient allocation should always include the marginal bidder. The important issue here is that when bidder i is awarded lesser units than the unit of complementarities, i.e., yi < K, the alternative efficient allocation would require K ? yi units to be taken away from bidders other than i who have the lowest K ? yi values amongst the allocated units. Thus, the opportunity cost of allocating these units to bidder i is the value of the K units of complementarities19 less the lowest K ? yi valuations. If yi = K, then the opportunity cost is simply the value of the K units of complementarities. Finally, for yi > K, the opportunity cost is the sum of the top yi rejected bids other than that of bidder i which includes the value of the K units of complementarities. 18 This simply means that we use prices of those periods where i does not belong to the drop-out set. 19 This can be easily computed by looking at the price at round t* and multiplying it by K 35 Thus, if yi > K then i?s VCG price should be KPt* for K units and the clinching prices for the rest of yi ? K units20. If yi = K then it is KPt* . Now, suppose yi < K. Let Ti be the sum of K ? yi prices in rounds where i ? Dt , starting from round t and excluding round t*. Then bidder i?s VCG price is pi = KPt* ? Ti. Having shown what the VCG prices should be, equivalence between these prices and the ones computed using our mechanism should be an obvious implication. Corollary 1.1: The prices computed under Case I and II are the VCG payments, which are equal to the opportunity costs of allocating units to any particular bidder. Now that I have shown that the prices in my model are actually the corresponding VCG prices, the last important issue that needs to be addressed is the efficiency of the allocation. The next Theorem proves that the allocation in both the two cases are ex- post efficient, which renders uniqueness to the proposed auction design. Theorem 2: The final allocations in both Case I and II are ex-post efficient. Proof: See Appendix. 20 If y i > K, then i has to pay the top yi rejected bids other than that of her own. This should include the value of the K units of complementarities, which are rejected under this allocation. Bidder i should already have clinched yi ? K units by the time the auction reaches round t , and thus should pay the clinching prices for these remaining yi ? K units. 36 In the next section, the example presented at the beginning of the paper is revisited to illustrate the workings of the proposed algorithm. 2.5. The Numerical Example Revisited Let us consider the example presented in section 1. Table 2.1 in section 1 gives the marginal values of each unit. Given these valuations, the efficient allocation should assign 2 units to each of bidder 2, 3 and 4, the corresponding Vickrey prices being 14, 13 and 14 respectively. The objective here is to emulate the same results by using an ascending auction and making sure that no excess information is revealed. The auction proceeds as follows. At every round, prices are announced and demands are reported. Price increases as long as there is excess demand (rounds 1,2,3,4). Excess demand changes to excess supply at round 5. Therefore, t* is 5. Price increases further to round 6 when demand is exactly equal to M ? K. Therefore,t= 6. Also, round t is round 3 where demand equals M + K ? 1 (= 8). Table 2.3: Proposed Auction Outcome: Round Price x1 x2 x3 x4 X Dt Ct 1 0 6 6 6 6 18 - - 2 2 3 2 2 2 9 1,2,3,4 - 3 4 3 2 1 2 8 3 1-1; 37 4 5 3 2 1 1 7 4 1-1;2-1 5 6 0 2 1 1 4 1 - 6 10 0 1 1 1 3 2 - Allocation: The M ? K(= 3) units that are demanded at roundt(=6) are allocated to the bidders who have positive demand at roundt; thus bidder 2 gets 1 unit, bidder 3 gets 1 unit and bidder 3 gets 1 unit. In this example KPt* (=18) < t t t t P = ? - Pt* (=19). Thus i ? Dt gets 1 unit each ?t ? [t,t], t ? t*. It is inferred from Table 2 that bidder 3 ? D3, bidder 4 ? D4 and bidder 2 ? D6. Thus bidders 3,4 and 2 get one more unit each. The final allocation therefore is as follows; bidder 1 gets 0 unit, bidders 2,3 and 4 get 2 units each. Prices: This is Case II with yi < K ?i. Using table 2, Ti?s can be calculated as follows; T2 = 4, T3 = 5 and T4 = 5. Therefore bidder 2 pays 18 ? 4 = 14, bidder 3 pays 18 ? 5 = 13 and bidder 4 pays 18 ? 4 = 14. The final outcome here is as follows; bidder 2 gets 2 units at a price of 14, bidder 3 gets 2 units at a price of 13 and bidder 4 gets 2 units at a price of 14. Thus, the new algorithm achieves the efficient allocation and the Vickrey prices without asking the bidders to reveal their entire demand schedule. In the next section, I relax the assumption that only one bidder exhibits complementarities. Now I concentrate on the case where multiple bidders might 38 exhibit complementarities and present the revised allocation and price computational algorithms. 2.6. Multiple Bidders with Complementarities There are two possibilities worth analyzing when multiple bidders exhibit complementarities. One possibility is that multiple bidders have average valuation among the top M valuations and, the bidder who has the lowest average value, is the marginal bidder. I will refer to this situation as Single Marginal Bidder. The second possibility is that multiple bidders have the same average valuation but different units of complementarity at the margin. I will refer to this situation as Multiple Marginal Bidders. In the first case, just like before, the important question to ask is whether the marginal bidder is going to be allocated any units or not. However, to address the issue, more information might be needed, which implies that the auction might have more bidding rounds. In the second case, due to the multiplicity of marginal bidders, it has to be simultaneously determined whether it is efficient to allocate units to the marginal bidder and which marginal bidder that should be. Again, more information might be needed to answer these questions, though the maximum information required in the second case is less than that required in the first case. In what follows, I discuss these two cases in details. 39 2.6.1. Single Marginal Bidder In this case, there are multiple bidders with complementarities whose average value lie in the top M valuation but there is only one marginal bidder with complementarities. Let i be the marginal bidder who has complementarity over Ki units. Thus, when price reaches bidder i?s average value, in round t*, there is a decrease in aggregate demand by Ki units, creating excess supply. Now, under normal circumstances, the price would go up till demand reaches M ? Ki. However, with multiple bidders exhibiting complementarity, the demand might never equal M ? Ki. The following list of valuations illustrates such a situation. 22, 21, 20, 19, 18, 17, 16, 16, 15, 15, 15, 14, 14, 13, 12, 11, 10, . . . (Ex. 2.6.1.1) 12 units are being auctioned off (M = 12). The underlined values represent the average values of bidders with complementarities. The marginal bidder has an average value of 14. Clearly, the aggregate demand never equals M ? Ki, which is 10. The important issue that needs to be addressed here is similar to the one dealt with before. I need to figure out whether it is efficient to allocate units to the marginal bidder or not. If, in any bidding round, demand equals M ? Ki, then the auction ends there and the efficient allocation and the prices are calculated just like the single bidder case21. 21 There might be a multiple unit drop in demand in this case after round t*. Accordingly, to calculate the efficient allocation, this has to be taken into account by multiplying the price in such rounds by the drop in demand. 40 Remark 3: If demand is equal to M ? Ki in any of the bidding rounds, then the allocation and price algorithm outlined before can be used to compute the efficient allocation and the VCG prices for the multiple bidder with complementarities case. The more interesting case is when the demand is never equal to M ? Ki, like the one illustrated in example 2.6.1.1. Let L denote the number of units that have the top M values. Due to the presence of complementarities, L has to greater than M. In example 2.6.1.1, M = 12 and L = 13. Now, if it is efficient to allocate units to the marginal bidder, then L ? M units from the top M have to be sacrificed. Similarly, if it is inefficient to allocate units to the marginal bidder, then the rejected top M ? (L ? Ki) units should be included in the top M.22 These L ? M units from the top M and the rejected top M ? (L ? Ki) units give us the total value that would be generated if the K units are not allocated to the marginal bidder. Thus, to compute the efficient allocation, the auction algorithm should be able to determine the values of these L ? M units from the top M and the rejected top M ? (L ? Ki) units. In example 2.6.1.1, if the marginal bidder is included in the final allocation, then 1 (= L ? M) unit, which has a higher value, has to be excluded. On the other hand, if the marginal bidder is excluded from the final allocation, then 1 (= M ? L + Ki) unit, which has a lower value, has to be included in the final allocation. 22 L ? K i gives the number of units in the top M without the marginal bidder. Thus, M ? (L ? Ki) gives the number of units required to complete the top M. 41 Using the auction algorithm discussed in previous sections, in round t*, there is excess supply for the first time. Thus, the aggregate demand in round t*-1, Xt*-1, should give us L. Similarly, Xt*, aggregate demand in round t*, gives us L ? Ki. Once these are known, they could be used to determine t and t, which are needed to calculate the efficient allocation and the prices. More specifically, round t should be such that Xt ? Xt*-1 = M ? (L ? Ki) ? 1. Interestingly, round t in this new algorithm is exactly similar to the one calculated before, with tX = M + Ki ? 1, and gives us the top M ? (L ? Ki) rejected bids. In example 1.4.1, tX = 12 + 2 ? 1 = 13. Thus round t is the bidding round where the bidder with marginal value 13 reduces her demand. The more challenging task is to determine t. Before the auctions ends, the value of the L ? M units need to be determined that the marginal bidder would replace from the top M, if she is included in the final allocation. Thus, after round t*, price is increased further till aggregate demand is reduced by L ? M units. Now, in the single bidder with complementarities case, this implies that Xt* ? tX = L ? M, or, tX = M ? Ki. In the multiple bidders with complementarities case, this is not that straightforward. In such situations, aggregate demand might never be reduced by exactly L ? M units due to the presence of multiple bidders with complementarities. To get around this potential problem, the following intuition is used. Let us suppose that there is a multiunit demand reduction in a round after round t* which is greater than L ? M units. Now, it follows directly from efficiency that this bidder cannot be 42 excluded from any efficient allocation. Our goal here is to determine exactly L ? M units that might be replaced by the marginal bidder. If a bidder has higher units of complementarities, she could not be replaced by the marginal bidder, and thus, she would always be a part of any efficient allocation. This is formally stated in Result 1. Result 1: If there is a reduction in demand greater than L ? M units after round t*, then efficiency requires the corresponding bidder to be awarded those many units. Consequently, these rounds do not influence the decision on how to allocate the marginal units. Thus, I ignore such rounds and concentrate on those bidding rounds only, where the aggregate reduction in demand from round t* onwards, has been less than L ? M units. Round t is reached when the aggregate reduction in demand, from round t*+1 up to round t is exactly equal to L ? M units, excluding those rounds where the reduction in demand exceeds L ? M. The worst possible situation, in terms of the length of the bidding process, would be the case where all the other bidders with complementarities have to be ignored while calculating t. In such situations, t could only be reached after all such bidders have reduced their demand, implying that the aggregate demand in round t is equal to M - ?jKj, where kj?s are the units of complementarities exhibited by the multiple bidders. Going back to example 2.6.1.1, L ? M = 1 and I have reductions of 3 and 2 units after round t*. Thus, these round have to be ignored and auction ends at round t when the bidder with marginal value 17 reduces her demand, with Xt = M ? ?jKj (= 12?2?3?2 = 5). In the following 43 example, the auction would end earlier, implying that lesser amount information would be revealed. 22, 21, 20, 19, 17, 17, 16, 16, 15, 15, 15, 14, 14, 14, 13, 12, 11, 10, . . . (Ex. 2.6.1.2) In this example, M = 12, L = 14 and M ? ?jKj = 12 ? 10 = 2. However, I have a reduction of 3 (>L ? M = 2) units when the bidder with average value 15 reduces her demand. According to the algorithm discussed above, this round is ignored and I proceed to the next round where I have a reduction of 2 units in the aggregate demand. Thus the auction ends in this round where the bidder with average value 16 reduces her demand. Therefore, in this situation, even though I do not have a bidding round where aggregate demand equals M ? Ki, the auction would end before demand equals M ? ?jKj. Thus, I see that in situations involving multiple bidders with complementarities but a single marginal bidder, more information might be needed, which calls for more bidding rounds. Consequently, to make this new auction more effective in such situations, a sufficient condition would be M >> ?jKj. 2.6.1.1. Allocation Just like before, there are two possibilities here. One possibility is that the marginal units are awarded to the bidder with complementarities. Another possibility is that the marginal bidder is excluded from the final allocation. However, in both these two cases, the bidders with positive demand in the last bidding round (round t) get the units they demand. In addition, in both these two cases, bidders who have greater than 44 L ? M units of complementarities and are in the top M, are awarded the units they demand. Now, while computing the efficient allocation, I need to make sure that I exclude bidders with greater than L ? M units of complementarities from our calculations. To this extent, I construct the set of Exclusions for every round after round t*. This set simply gives us the drop out prices of those bidders who have greater than L ? M units of complementarities. (5) Exclusions at round t>t* ; Et = { Pt ?t / Xt-1 ? Xt > L ? M ; 0 otherwise} The algorithm for allocating the remaining Ki units is as follows: ? Compare KiPt* and t t t t P = ? ? Pt* ? * 1 t t t t E = + ? ? Case I: KiPt* > t t t t P = ? ? Pt* ? * 1 t t t t E = + ? ; then i ? Dt* gets the remaining Ki units ? Case II: KiPt* < t t t t P = ? ? Pt* ? * 1 t t t t E = + ? ; then j ? Dt gets Xt-1 ? Xt ?t ? [t,t]; t ? t*and t such that Et = 0 In both the above examples, the marginal bidder would be excluded from the final allocation and the highest rejected bid would be included in the final allocation. 45 2.6.1.2 Prices Case I: KiPt* > t t t t P = ? ? Pt* ? * 1 t t t t E = + ? In this case, bidder i ? Dt* gets Ki units. The price he pays is pi = t t t t P = ? ? Pt* ? * 1 t t t t E = + ? . Bidders other than i get whatever they demand at the last round, i.e., bidder j ? i gets j tx units. Also, bidders who have greater than L ? M units of complementarities, are awarded the units they demand, i.e., if Et ? 0, then j ? Dt gets Xt-1 ? Xt units. Now, let xj be the number of units that bidder j ? i wins. Also, let Rj be the sum of the prices in the last xj rounds where j ? Dt , excluding round t*. Bidder j pays Rj. Only Provisional Current Clinches made by bidder j ? i in rounds t < t are honored. Case II: KiPt* < t t t t P = ? ? Pt* ? * 1 t t t t E = + ? Here bidder i ? Dt* gets zero unit. Now, let yj be the number of units awarded to bidder j ? i. If yj > Ki then j pays KiPt* for Ki units and the clinching prices for the rest of yj ? Ki units. If yj = Ki then j pays KiPt*. Suppose yj < Ki. Let Tj be the sum of Ki ? yj prices in rounds where j ? Dt , starting from round t , excluding round t*. Then bidder j pays pj = KiPt* ? Tj As before, only Provisional Current Clinches made by bidder j ? i in rounds t < t are honored. The following theorems summarize the results. 46 Theorem 3.1: In the multiple bidders with complementarities case, truthful bidding or wait-until- price-equals-value strategy is still a Best Response equilibrium strategy. Theorem 3.2: The prices computed are the VCG prices and the allocation is ex post efficient. Proof: See Appendix 2.6.2. Multiple Marginal Bidders In this case, multiple bidders have the same average valuation but different units of complementarities at the margin. Thus, when the price equals this average value (in round t*), there is a drop in demand by ?jKj units, where Kj?s are the units of complementarities. The following example illustrates such a situation. 22,21,20,19,18,17,17,16, 15,15,15, 15,15, 15,15,15,15, 13,12,11,. . . (Ex. 2.6.2.1) In this example, 9 units are being auctioned off and I have 3 marginal bidders with the same average value of 15. The multiplicity of the marginal bidders in situations like this presents us with a problem that cannot be solved with the algorithms developed in the previous sections. Thus, I need to make some changes to the 47 algorithm to determine how many of these marginal bidders are to be included in the final allocation, if at all, and which ones these should be. As far as efficiency is concerned, an important point to note is the fact that if it is inefficient to allocate units to one particular bidder with complementarities, then it will also be inefficient to allocate units to any other bidder who has higher units of complementarities but the same average valuation. If units are allocated to a marginal bidder with complementarities, then some values higher than her average value are excluded from the allocation. Now, if units are allocated to a bidder with higher units of complementarities but the same average value, then the only difference is that some more values higher than the common average value are being sacrificed. Thus, if including the bidder with fewer units of complementarities is inefficient, it has to be the case that the inclusion of some other bidder with higher units of complementarities but the same average value, is also inefficient. This is stated formally in the following result. Result 2: In the multiple marginal bidder with same average value case, if it is inefficient to allocate units to a particular marginal bidder, then it has to be the case that it is inefficient to allocate units to any other marginal bidder with higher units of complementarities. 48 For the simplicity of exposition, let us arrange the units of complementarities in an ascending order, K1, K2,?, and so on, where K1 is the lowest. Let bidder i be the bidder with K1 units of complementarities. After there is a multiunit demand reduction in round t*, following the initial algorithm, price is increased further till the aggregate demand equals M ? K1. Using this algorithm, it can also be figured out whether it is efficient to allocate the K1 units to bidder i. If it is inefficient to allocate these units to bidder i, then, from Result 2, it is also inefficient to allocate any unit to the other bidders who exhibit complementarities. Then the auction ends when demand equals M ? Ki and none of the bidders who exhibit complementarity gets any unit. However, if it is efficient to allocate the K1 units to bidder i, then the auction proceeds and price increases further till demand equals M ? K2, where K2 is the second lowest unit of complementarities. Again, using the algorithm from the previous section, it can be easily determined whether it is efficient to allocate the K2 units to the corresponding bidder. Just like before, if it is inefficient to allocate the K2 units to the bidder with complementarities, it would be inefficient to allocate any units to the other bidders who exhibit higher units of complementarities. Thus, bidder i is awarded K2 units and the auction ends when demand equals M ? K2. However, if it is efficient to allocate the units to the bidder with K2 units of complementarities, then the auction proceeds further. Thus, in such cases, there might be a recursive process in which units are allocated to some marginal bidder not only if it is efficient to do so, but also if it is inefficient to allocate any unit to the marginal bidder who has the next higher units of 49 complementarities. Thus, in such cases, either none of the marginal bidders are awarded any units, or, only one marginal bidder is awarded the units based on whether it is efficient to do so and whether it is inefficient to allocate any units to the marginal bidder who has the next higher units of complementarities. Here also, more information and consequently more bidding rounds might be necessary. More specifically, if it is efficient to allocate units to marginal bidder i only, then the auction ends when demand equals M ? Kl, where l is the marginal bidder with next highest units of complementarities. The worst case is when price has to go up so that the demand equals M ? Max{Kj}. Consequently, to make this new auction more effective in such situations, a sufficient condition would be M >> Max{Kj}. An interesting observation in situations like these is the fact that the final round of the auction and the efficient allocation are determined simultaneously. The auction algorithm that is used here is almost similar to the one used for the single bidder with complementarities case. At round t*, there is a reduction in demand by all the marginal bidders and there is excess supply for the first time. Using the ordering of the units of complementarities, price is increased further until demand equals M ? K1, where K1 is the lowest unit of complementarities. If it is inefficient to allocate these K1 units to the corresponding bidder, then the auction ends at this round where Xt = M ? K1. Consequently, this auction can be treated exactly like an auction with this bidder with K1 units of complementarities as the single marginal bidder. Thus, the efficient allocation and the prices could easily be computed using the algorithm discussed already. If it is efficient to allocate units to the marginal bidder with K1 units, then 50 price needs to be increased further until demand equals M ? K2, where K2 is the second lowest unit of complementarities. Now, if it is inefficient to allocate these K2 units to the corresponding bidder, then, for all practical purposes, the auction ends at the previous round where Xt = M ? K1. However, if it is efficient to allocate the K2 units, then again price have to be raised until demand equals M ? K3. Thus, the auction algorithm in such situations functions as a recursive process and stops only when it is inefficient to allocate units to a marginal bidder. If it is efficient to allocate units to all the marginal bidders before the one with the maximum units of complementarities, then this auction simply can be treated as an auction with the bidder with the maximum units of complementarities as the only marginal bidder. In example 2.6.2.1, there is a reduction of 9 units at round t*. Now, using the algorithm discussed above, I increase price further until demand equals M ? K1 = 9 ? 2 = 7, i.e., the bidder with value 16 has reduced her demand. Here, it is efficient to allocate 2 units to the corresponding marginal bidder ( 15+15 > 16+13 ). Thus auction proceeds further until the demand equals M ? K2 = 9 ? 3 = 6. It is inefficient to allocate units to the bidder with 3 units of complementarities (15+15+15 < 17+16+13). Thus, for all computational purposes, the round where demand equals M ? K1= 7 is the last round, and the efficient allocation and the prices are computed accordingly. 51 2.6.2.1 Allocation The allocation problem with multiple marginal bidders is very similar to the one with a single bidder with complementarities. The only difference here is that we might have to increase price one extra round to make sure we have the efficient allocation. However, once it has been determined which marginal bidder, if any at all, gets the units she demand, the rest of the allocation process is exactly similar to the single bidder with complementarities case. Thus, it is quite unnecessary to model a separate allocation algorithm for situations with multiple marginal bidders. 2.6.2.2 Prices The prices paid by the winning bidders in the multiple marginal bidders? case can be computed by using the same algorithm that was used to compute those paid by the bidders in the single bidder with complementarities case. Once the efficient allocation has been determined, the multiple marginal bidder problem essentially becomes a single marginal bidder problem where all but one marginal bidders are excluded from the final calculations23. Thus, to compute the prices in such situations, the same algorithm is proposed that was discussed in the section 2.4. Theorem 4.1: In the multiple marginal bidders case, truthful bidding or wait-until-price-equals- value strategy is still a Best Response equilibrium strategy. 23 Eventually, only one of the multiple marginal bidders could be allocated the units demanded. Thus, in such situations, all the other marginal bidders are excluded from the relevant computations. If none of the marginal bidders get the units they demand, then only the marginal bidder with the lowest units of complementarities would be included in the algorithm to compute the prices. 52 Theorem 4.2: The prices computed are the VCG prices and the allocation is ex post efficient. Proof: See Appendix. In the following section, a very simple Linear Programming formulation of the assignment problem in auction with single marginal bidders with complementarities is presented. 2.7. Linear Programming Approach The assignment problem that the auctioneer faces in a multiunit auction could also be modeled as a Linear Programming Problem (LPP), more specifically, as a Knapsack Problem(KP). Formally, a KP is defined as follows: We are given an item set N, which consists of n items j with profit pj and weight wj and a maximum capacity value c. The objective is to select a subset of N such that the total profit of the selected units is maximized and the total weight of the selected units do not exceed c. Alternatively, the KP can be formulated as the following linear integer programming problem: 53 { } 1 1 Maximize subject to , 0,1 , 1,...., n j j j n j j j j p x w x c x j n = = ? ? ? = ? ? (2.7.1) The optimal solution vector is often denoted by x* = ( * *1,...., nx x ) and the optimal solution value by z*. Let us suppose that the item set N consists of the entire set of reported values in an auction. Thus, an item j in this set would be a bid placed by some bidder. The associated profit pj for item j would be the value of the reported bid, bj. The weight wj of the item would be the number of units the bid was placed for. Usually, with non- increasing values, wj would just be one. The only exception to this would be the case where a bidder has increasing marginal values and places an all-or-nothing bid for a bundle of units. In that case wj would be the units of complementarities. The decision variable xj denotes whether the bid is selected in the final allocation or not; xj=0 implies exclusion and xj=1 implies inclusion. Since only M units are being auctioned off, the maximum capacity value, c, should be equal to M. With these minor adjustments, the KP can be rewritten as: { } 1 1 Maximize subject to , 0,1 , 1,...., n j j j n j j j j b x w x M x j n = = ? ? ? = ? ? (2.7.2) 54 This exactly depicts the auction allocation problem. The optimal solution in the context of auction simply refers to the efficient allocation of units. Like all LPP, the KP also has quite a few algorithmic solution techniques. The KP stands out as one of the simplest forms of LPP. A common intuitive interpretation of the problem is ?packing items into a knapsack which has a fixed capacity, so as to maximize the utility from the packed items?. Once we think of KP as a ?profitable packing of items into a knapsack problem?, an intuitive approach for a good solution algorithm would be to consider the efficiency, i.e., profit to weight ratio of each item, j j j pe w= , and put items with highest efficiency into the knapsack. Clearly, these items generate the highest profit while consuming the lowest amount of capacity. One of the algorithmic techniques used to solve a KP is called the Greedy Algorithm, which uses the exact same logic. First the items are arranged in a decreasing order of efficiency such that 1 2 1 2 ....... n n pp p w w w? ? ? The idea behind the Greedy Algorithm is to start with an empty knapsack and go through the items in this decreasing order of efficiency, adding the item under consideration if the capacity constraint is not violated. An explicit description of this algorithm is presented in the following table. 55 Table 2.4: Greedy Algorithm 0 : 0 : 1 G reedy A lgorithm : G G w w is th e to ta l w eig h t o f th e cu rren tly p a cked item s z z is th e p ro fit o f th e p a cked item s fo r j to n d o if w = = = + 1 : 0 : j j j G G j j w c th en x select item j w w w z z p else x item j is n o t selected ? = = + = + = Example: Consider a KP with c = 9 and n = 7 with the following profit and weight values: Table 2.5: KP Example 1 j 1 2 3 4 5 6 7 pj wj 6 5 8 9 5 7 3 2 3 6 8 5 9 4 If the Greedy Algorithm is applied to this KP, items 1, 2 and 7 would be selected yielding a profit zG = 14, which is the optimal solution for this problem. However, one concern regarding this particular solution algorithm is the ?quality? of the solution computed. The solution computed by the Greedy Algorithm does not necessarily have to be the optimal solution. In fact, it could be distinctly inferior to the optimal solution. For example, if we modify the above numerical example a little, we could show that the Greedy Algorithm fails to deliver the optimal solution.. 56 Table 2.6: KP Example 2 j 1 2 3 4 5 6 7 pj wj 6 5 8 9 6 7 3 2 3 6 7 5 9 4 The above table presents the previous KP with profit value for the 5th item and the weight value for the 4th item altered (the ones in red). If we apply the Greedy Algorithm to solve this problem, we will see that we have the same solution as before. However, now this solution is suboptimal because it yields a lower profit zG = 14 than the optimal profit z* = 15. Fortunately, this ?quality of the solution? issue does not affect the Greedy Algorithm solution for multiunit auctions which are modeled as KPs. We will revisit this issue shortly when we discuss how Greedy Algorithms could be used to solve multiunit auctions. To tackle the sub-optimality of the Greedy Algorithm, an extended form of the Greedy Algorithm is used sometimes to improve the ?quality? of the solution. Though this extension does not necessarily yield the optimal solution to all KPs, it is an improvement over the Greedy Algorithm in some situations. This modification is called the Extended Greedy Algorithm which consists of running Greedy first and then comparing the solution with the highest profit value of any single item. The larger of the two is finally chosen as the solution produced by Ext-Greedy Algorithm. This solution value is denoted as zEG and for the Ext-Greedy Algorithm, the following command is added at the end of the Greedy Algorithm: 57 zEG = Max {zG, Max { pj? j = 1,??.., n}} Consider the following KP with c = 6 and n = 5 with the following profit and weight values: Table 2.7: KP Example 3 j 1 2 3 4 5 pj wj 3 5 12 2 1 1 2 6 3 4 For this problem, the Greedy Algorithm would yield the solution zG = 10 with items 1, 2 and 4 being chosen. However, clearly the optimal solution is z* = 12 with item 3 being chosen only. Now, if we run the Ext-Greedy algorithm, that would give us the solution zEG = 12 which is the optimal solution for this problem. Thus, we see that for some KP, the Ext-Greedy Algorithm improves upon the Greedy Algorithm and might yield the optimal solution. As we have discussed earlier, a multiunit auction can also be interpreted as a KP; (2) above gives us the exact mathematical formulation. Let us suppose that we have a multiunit auction with 3 bidders and 4 units and the marginal values are given by the following table: 58 Table 2.8: Marginal Values Let us also suppose that there is truthful bidding so that the true values can be used as bids. The KP formulation of this problem would have n = 12 and c = 4 with the following profit and weight values: Table 2.9: KP Formulation j 1 2 3 4 5 6 7 8 9 10 11 12 pj wj 12 11 10 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 This is an auction without any complementarities which imply that the weight values of each item are 1. Thus, arranging the items in decreasing order of efficiency simply means arranging the bids in decreasing order of values. If the Greedy Algorithm is used to find the solution to this problem, items 1, 2, 3 and 4 would be chosen with zG = 42 which also happens to be the optimal solution z*. Due to the fact that all the items have unit weights and are arranged in decreasing order of true/reported values, in all auctions with non-increasing marginal values, the Greedy Algorithm solution is always the optimal solution. 1 2 3 4 B1 B2 B3 12 11 6 2 9 8 7 1 10 5 4 3 59 The more interesting case is when increasing marginal values are present. With complementarities, we could have bidders demanding package of units, which implies that some items could have non-unitary weight values. This could potentially lead to the sub-optimality of the Greedy Algorithm solution. The following example illustrates such a situation. Table 2.10: KP Example with Complementarities j 1 2 3 4 5 6 7 8 9 10 11 12 pj wj 12 11 10 19 8 7 6 5 4 3 2 1 1 1 1 2 1 1 1 1 1 1 1 1 The Greedy Algorithm would pick items 1, 2, 3 and 5 with a total profit zG = 41. The optimal solution for this problem however is to choose items 1, 2 and 4 with z* = 42. This is an auction with complementarities with the fourth bid being a package bid for 2 items. Thus we see that in auctions with complementarities or increasing marginal values, the Greedy Algorithm might yield a sub-optimal outcome. To continue our discussion on auctions with complementarities, let us consider the reduced form Marginal Auction Problem (MAP) as discussed earlier. This is a simple thought experiment where the N unit auction with a single bidder with complementarities is broken down into a hypothetical N ? K unit auction followed by a K unit auction, K being the units of complementarities. Assuming truthful bidding, N ? K units would be allocated to the top N ? K bids in the first auction. Thus, these top N ? K bids would not be present in the second auction and the problem now 60 would be to determine whether to allocate the K remaining units to the bidder with complementarities or not. This is exactly similar to the marginal allocation problem in the original N unit auction and thus is referred to as the MAP. Interestingly, in such auctions with complementarities, the important issue is to find an efficient solution for the MAP, the allocation of the remaining units being the same under any efficient allocation. Just like other auction problems, we could use 2.7.2 to express the MAP as a KP. However, the Greedy Algorithm is not the best solution algorithm for such problems because it might yield sub-optimal outcomes in some instances. Instead, a simple extension of the Greedy Algorithm that we discussed before, the Extended Greedy Algorithm, could be used to optimally solve all such problems. Let us try to explain this result with the help of the following illustrative example: Table 2.11: Extended Greedy Algorithm j 1 2 3 4 5 6 7 8 9 10 11 12 pj wj 12 11 32 8 7 7 6 5 4 3 2 1 1 1 3 1 1 1 1 1 1 1 1 1 This is a MAP with 4 bidders where the auctioneer has to decide how to allocate 3 units at the margin. If the Greedy Algorithm is used, then items 1, 2 and 4 would be picked with zG = 31. However, the optimal solution for this problem is to pick item 3 with z* = 32. If the Extended Greedy Algorithm is used instead, it would yield zEG = 32 which is simply Max {zG, Max{ pj? j = 1,??.., n}}. Thus we see that the 61 Extended Greedy Algorithm improves upon the Greedy Algorithm solution to yield the optimal outcome for all MAP. To conclude our discussion on KP and auction algorithms, we would like to point out a couple of important results. The Greedy Algorithm would give us the efficient allocation for non-increasing marginal value auctions but the same might not be so effective when complementarities are present. For auctions with increasing marginal values or complementarities, the Extended Greedy Algorithm would deliver the efficient solution for the MAP even if the Greedy Algorithm fails to do so. 2.8. Concluding Remarks The static Vickrey auction has two desirable properties. It allocates the units efficiently. Also, it induces truth telling as a dominant strategy. However, the main critique for this auction would be the fact that it requires all the bidders to reveal their entire demand. Auction theorists have pointed out that this demand revelation aspect of the static auction could potentially lead to undesirable outcomes. Using this insight, Ausubel extended the static Vickrey results in a dynamic auction setting with non-increasing marginal values. This paper also replicates the static Vickrey results in a dynamic auction setting, but it is not restricted to non-increasing marginal values only. 62 The main result of this paper states that the allocation achieved through the proposed dynamic mechanism is an efficient one, even when complementarities24 are present. Also, since VCG payments are used as prices, truthful bidding is a best response equilibrium strategy. Being an ascending price auction, demand revelation is not as extreme as the static Vickrey auction. In fact, only that much of information is revealed that is necessary to compute the efficient allocation; winning bidders with high enough values do not have to reveal their entire demand25. One possible extension of this model could be to allow for heterogeneous goods and package bids. It seems to be a formidable challenge to verify whether a mechanism like the one proposed here would work in such settings. Also, this paper solely deals with independent, private values. Another possible extension could be examining situations like these in an interdependent value setting. Perry and Reny extend the Ausubel auction to allow for interdependent values. A possibility on these lines would be to extend the Perry and Reny model to allow for increasing marginal values. Before I close, I would like to point out a set of experimental studies that are particularly relevant. Over the last couple of decades, experimental studies have shown that the sealed-bid format outperforms the open-bid one, both in laboratory and in field settings, contradicting the theoretical predictions directly26. Cox et al., 1985, Kagel et al., 1987, and Kagel and Levin, 1993 have all observed overbidding in 24 Captured by increasing marginal values. 25 Under some special circumstances, the amount of information revealed might be equal to that revealed in a closed bid auction. 26 See Davis and Holt, 1993 and Kagel 1995 for useful surveys on auction theory and laboratory experiments 63 sealed bid laboratory studies. Kagel and Levin, 2001, find overbidding relative to the dominant strategy in a sealed bid uniform price auction in a laboratory setting. List and Reiley, 2001, observe this same result of overbidding on the first unit in a sealed bid uniform auction, in a field experiment using data from a sports card show. These are particularly relevant for this paper because they provide evidences against the theoretical insights which justify the choice of an open bid auction format over a sealed bid one. However, it would be premature to denounce the theoretical predictions on account of these findings. A variety of theoretical explanations have also been offered to reconcile these anomalous findings. These would be risk aversion27, difference in feedback28, externality from winning29 and spite motive30, amongst others. However, none of these have pointed out the most serious drawback of the experimental studies. Rothkopf, et al, 1990, pointed out that if the bidders apprehend cheating by the auctioneer, they will be more reluctant to reveal their true values in sealed bid auctions. Engelbrecht-Wiggans and Kahn (1991), and Rothkopf and Harstad (1995) also provide models emphasizing the importance of protecting the privacy of winners? valuations. In all of the experimental work cited above, this important aspect of possible price manipulation by the auctioneer is overlooked. More specifically, in these experiments, the experimenter (or the computer following preset commands) played the role of the auctioneer, who had no monetary interest in the revenues 27 See Riley and Samuelson, 1981 28 See Kagel, Harstad and Levin, 1987 29 See Ettinger, 2002 and Das Varma, 2002 30 See Morgan et al, 2003 64 earned from the auction. One extension to this branch of experimental economics would be to incorporate this possible price manipulation in an experiment, which might yield results similar to the standard theoretical predictions. Ghosh and Lange, 2006, have designed such an auction experiment to study the effect price manipulation on bidding behavior, results from which are expected to improve our understanding of important differences between open and sealed-bid auction formats. Thus, to conclude, I would like to restate that to the best of my knowledge, this is the only open bid auction algorithm that deals with the problem of complementarities in a multiple homogeneous good environment. Efficiency is achieved and truthful bidding is induced as an equilibrium strategy. Though there have been some recent developments in the operational research field and more complicated mathematical models have been developed, the advantage that this new design enjoys is the simplicity of the algorithm and the intuitive and logical treatment of the problem. 65 Chapter 3: Price Manipulation by the Auctioneer: An Experimental Study Title of Chapter 3 3.1. Introduction. The choice between an ascending open-bid and a closed sealed-bid auction has been one of the most debated topics in auction theory. Though the standard auction literature prescribes the ascending auction over the sealed-bid one, experimental studies have shown that the latter outperforms the former, both in laboratory and in field settings. Theoretically, the ascending auction design is more appealing compared to its sealed-bid counterpart because it does not require the bidders to reveal their entire demand, thus insulating them from any possible manipulation by the auctioneer. In addition, due to its dynamic nature, the bidders can update their information set every period to ensure more efficient bidding. However, experimental studies have shown that the sealed bid format outperforms the open bid one, both in laboratory and in field settings. In such experiments, bidders are found to be bidding more aggressively in sealed bid auctions which contradicts the theoretical predictions directly (see Kagel, 1995 and Davis and Holt, 1993 for useful surveys of auction theory and laboratory experiments). Cox et al., 1985, Kagel et al., 1987, and Kagel and Levin, 1993 have all observed overbidding in sealed bid laboratory studies. Kagel and Levin, 2001, find overbidding relative to the dominant strategy in a sealed bid uniform price auction in a laboratory setting. List and Reiley, 2001, observe this same result of overbidding on the first unit in a sealed bid uniform auction, in a field 66 experiment using data from a sports card show. Broadly speaking, these discrepancies can be categorized into three stylized facts. Firstly, subjects consistently bid more aggressively than predicted by theory in sealed bid first price auctions with independent private valuations.31 Secondly, subjects consistently bid more aggressively than predicted by theory in sealed bid second price auctions.32 Finally, strategic equivalence between English auctions and second-price sealed bid auctions fails, with far less overbidding in English auctions than in second price sealed bid auctions.33 To reconcile these anomalous results with standard theoretical predictions, a variety of explanations have been offered. For first price auctions, it can be shown theoretically that if bidders are risk averse, there would be over bidding. Riley and Samuelson, 1981, showed that bidders engage in aggressive bidding in first price auctions with risk averse preferences. Though this potentially might explain the first discrepancy, it completely fails to explain overbidding relative to the dominant strategy in second price auctions. More qualitative explanations are advanced by Kagel, Harstad and Levin, 1987, where they point out the difference in feedback from overbidding in the two auction formats as a possible source of overbidding. They argue that since the impact of overbidding is much more immediate in open auctions as compared to the closed ones, overbidding is more common in the latter. More 31 See, for example, Holt and Sherman, 2000, who give explicit graphs of measured bid functions in this case. 32 See, for example, Kagel, Harstad, and Levin, 1987. 33 Again, see Kagel, Harstad, and Levin, 1987 for a good example of clear experimental evidence of this phenomenon. 67 recently, some behavioral studies have also tried to explain these discrepancies. Ettinger, 2002, and Das Varma, 2002, both study auctions where a winning bidder might exert externality on a losing bidder. In Ettinger?s paper, the winning bidder has incentive to bid more aggressively whereas the losing bidder has incentive to over bid in Das Varma?s paper. Morgan et al., 2003, model a spite motive in bidders? preferences which successfully explains the discrepancies. In their model, the losing bidder has spiteful incentives which lead to aggressive bidding. Thus we see that there exists a wide variety of studies trying to explain the observed discrepancies. However, a seemingly important aspect has been overlooked from all of these studies. The whole premise of superiority of the ascending auction designs rests on the fact that less information is revealed in such auctions, which prevents any kind of price manipulation or other foul play by the auctioneer. Michael H. Rothkopf, Thomas J. Teisberg, and Edward P. Kahn, 1990, pointed out that if the bidders apprehend cheating by the auctioneer or if there are going to be subsequent auctions or negotiations, bidders will be more reluctant to reveal their true values in sealed bid auctions. Richard Engelbrecht-Wiggans and Charles M. Kahn (1991), and Rothkopf and Harstad (1995) also provide models emphasizing the importance of protecting the privacy of winners? valuations. However, none of the experimental studies have tried to capture this aspect of manipulation by the auctioneer. In all these experiments, the experimenter herself is the auctioneer, which right away rules out any apprehension about possible foul play by the auctioneer. With the experimenter acting as the auctioneer, this is nothing but natural. The experimenter is obligated to compute the 68 prices and the allocation according to the rules disclosed at the beginning of the experiment. Thus, the most important rationale favoring the open auction over the sealed bid auction has not been experimentally verified yet, which also appears to be a realistic one. Consequently, in this paper we study the effect of a possibility of auctioneer price manipulation on bidding behavior. We choose a single unit sealed bid Vickrey auction and a single unit English auction to compare outcomes. There are two important reasons to choose these two particular auction formats. First of all, theoretically they are equivalent in terms of the final allocation and bidding strategies. Equally important is the fact that these are the most common and simple auction designs which eliminates any complications that could be caused by more complex designs. The experimental design is discussed in further details in the following section. However, before moving on to the following section, we would like to point out that this analysis does suffer from the risk of oversimplification. As we all know that in spite of being the most successful real world application of information economics, auction theory is plagued with some problematic technical issues like bidder collusion, bid rigging, dummy bidders, and bidding rings, among others. In this study however, we are assuming away from such technicalities and concentrating on the issue of price manipulation by the auctioneer only. Though this makes our analysis somewhat oversimplified, it allows us to isolate the probable effects of such price manipulation and study its? effect on bidding behavior. It also makes sense not to incorporate these other issues in the present analysis because most of these issues are inherent to any auction design, irrespective of it being a closed or an open one, and thus, lacks relevance for the current study. Thus, the main objective of this paper 69 is to experimentally test the effect of the possibility of price manipulation the auctioneer on the bidding behavior in both a sealed bid auction and an open bid auction. Theory suggests that the bidding behavior in an open auction should remain unaffected whereas we should observe less aggressive bidding in sealed bid auctions and we expect our experimental results to validate that. The paper is organized as follows. Some preliminary theoretical insights are presented in the next section. In the following sections the experimental design along with the actual results are presented. The final section provides some concluding remarks and scope of future research. 3.2. Preliminary Theory. The main objective of this paper is to study the effects of the possibility of price manipulation by the auctioneer on bidding behavior. In both the sealed bid Vickrey and the open bid English auction, the payments made by the winning bidders are the Vickrey payments, which do not depend on their own bids. As pointed out earlier, the auctioneer cannot manipulate price in the open bid auction because she does not have the required information. In the sealed bid auction, since the bidders submit their entire demand schedule to the auctioneer, price manipulation is definitely a possibility. One way to model price manipulation would be to assume that after all the bids are submitted, the auctioneer determines the winning allocation and then instead of charging the Vickrey prices, asks the winning bidders to pay prices slightly lower than their reported bids. The bidders in a sealed bid auction do not have any 70 information regarding the bids submitted by the other bidders. Thus, as long as the final price they are asked to pay is lower than their true value, they would be willing to pay. However, if the bidders are aware of the fact that the auctioneer is going to manipulate price and they would end up paying something that depend on the bids they submitted, they would have incentive to shed their bid and adjust their bidding behavior accordingly. Thus, truthful bidding is no longer a dominant strategy. Though this is an extreme case where the auctioneer manipulates price always, even if we model the manipulation as a probabilistic event, we should have the same result of demand reduction in sealed bid auction. For example, if we assume that the auctioneer manipulates price with a positive probability, we would still have the (expected) price dependent on one?s own bid, thus providing incentive for demand reduction. Let us suppose that the price paid by bidder i is as follows: pi = ?{V(N\i) ? ?j?i vj} + (1- ?)f(bi); 0 < ? < 1; f(bi) ? bi; f?(bi) > 0 which is the Vickrey payment with probability ? and some function of the bid submitted with probability 1- ?. Alternatively, we could also have the auctioneer charge a price which is just a positive markup over the Vickrey payments. Though this form of manipulation might seem to be independent of one?s own bid, a careful inspection would reveal quite the opposite. Here, the auctioneer needs to make sure that the markup she is going to charge is less than the bidder?s own bid. Thus, to ensure that the price charged is incentive compatible, the auctioneer has to take into consideration the bidder?s own bid. This implies that the bidders would again have 71 incentive to shed their bid because that would lower the markup. Thus, without any loss of generality, we can safely assume that the price manipulation can be modeled as above which should lead to demand reduction in sealed bid auctions. The above situation can be diagrammatically illustrated as follows. For the sake of exposition, let us assume that we have only 2 bidders and that f(bi) = bi. Then the above price equation can be rewritten as follows: pi = ?{bj} + (1- ?)bi; 0 < ? < 1, where bj is the bid submitted by the other bidder. With 2 bidders, if bidder i is the winner, then the second highest price is the bid submitted by bidder j. Let us also assume that the values are drawn from uniform distribution over [0,1]. If ? = 0, then this reduces to a first price auction and the equilibrium bid function is vi/2, where vi is bidder i?s value. On the other hand, if ? = 1, then this reduces to a second price auction and the equilibrium bid function is vi. For 0 < ? < 1, even though we do not explicitly solve for the exact mathematical form, the equilibrium bid function should be a non-increasing function of ? bounded by vi above and by vi/2 below. The following figure depicts a couple of such functions. Bid function 1 is a linear form, which is simply a linear convex combination of the two extreme equilibrium bid functions. It is represented by the solid bold line. Bid function 2 is a discontinuous function which is equal to the first price bid function for values of ? ? ?, and is equal to the second price bid function for all other values of ?. This is represented by the bold vertical disconnected lines. 72 3.3. Experimental Idea. The purpose of this experiment is to study the effects of auctioneer manipulation on bidding behavior. As pointed out in the preceding section, this sort of price manipulation affects sealed bid auctions only. With such manipulation by the auctioneer, bidders in a sealed bid auction should bid less aggressively compared to bidders in the same auction without manipulation. In this study, we have tried to capture the effects of two types of price manipulation by the auctioneer, explicit and implicit. Explicit manipulation would be the case where the bidders know at the start of the auction that the auctioneer is going to manipulate price with a certain 1 Vi Vi/2 0 1 V Bid Function 1 Bid Function 2 1/2 ? Fig. 3.1 Bid Functions. Two possible bid functions for ? ranging from 0 to 1 73 probability. Under implicit manipulation, the bidders would be aware of the fact that the auctioneer?s profits depend on the final price and the winning price would be announced by the auctioneer after observing all the bids which only she would have access to. Even though auctioneers explicitly informing the bidders about price manipulation would never occur in the real world, it serves an important purpose in our study. Our study revolves around the idea that the bidders should be aware of the fact that the auctioneer might benefit from price manipulation and take that in to account while preparing bids. Since the subjects used in our auction are undergraduate students, it can be difficult to instill this important concept of apprehension about price manipulation. By including the explicit manipulation treatment, we try to proxy for the possible lack of expertise and experience of our subjects that help real auction bidders to prepare bidding strategies. If the subjects quickly grasp the idea that the auctioneer has both incentive and scope to manipulate price, then the bidding behavior observed across the explicit and implicit manipulation treatments should be identical. If not, then the explicit manipulation treatment should produce lower bids compared to the implicit manipulation treatment. However, both these treatments should produce bids lower than the no-manipulation treatment. Also, with price manipulation, bidding in a sealed bid Vickrey auction should be less aggressive than bidding in an open English auction, which otherwise should be equivalent. Finally, bidding in an open auction should remain unaffected with or without price manipulation. Thus, the objective of this experiment is to test these three hypotheses using the data generated. 74 In our experiment, we incorporate the possibility of implicit price manipulation by randomly assigning participants as auctioneers. Since their final earnings would depend on their auction profits, they would have incentives to manipulate the final price. Interestingly, the success of this experiment does not rely on the fact that there has to be actual price manipulation. In fact, the necessary condition is that the bidders apprehend that the auctioneer has incentive and scope to manipulate price. Once the bidders become aware of the fact that the auction profit of the auctioneer is her final earnings and that she can alter that by choosing an appropriate price, they should adjust their bidding behavior accordingly. The baseline treatment is where the computer acts as the auctioneer and follows preset commands to choose the second highest bid as the winning price. We also have another treatment where a subject chosen randomly plays the auctioneer?s role but has to post the second highest bid as the final price. Any attempt to post a different price would lead to an automatic rejection by the computer program. The purpose of including this treatment is to show that the identity of the auctioneer, whether the computer or another fellow subject, does not affect the bidding behavior. This was necessary to make sure that even though two parameters (identity of the auctioneer and scope of the auctioneer) were changed across treatments, it did not affect the results. For example, it could be the case that the bidders might want to minimize the human auctioneer?s profit by bidding defensively as compared to the computer auctioneer. By comparing the results from both these two treatments, we make sure that such strategies are ruled out. 75 There are three treatments in our experiment. The first treatment is the baseline case where the subjects are chosen to participate either in a sealed bid second price auction. The second and the third treatments incorporate possible price manipulation. In the explicit manipulation treatment, the participants play a sealed-bid second price auction with the role of the auctioneer being played by the computer. In the implicit manipulation treatment, the subjects participate as bidders in a sealed-bid second price auction, with the role of the auctioneer being played by a randomly chosen subject. The subject auctioneer in this treatment would have the incentive and ability to influence price. The bidders participating in this treatment are informed about this before the auction starts. 3.4. Experiment Design Undergraduate students in the University of Maryland at College Park were used as subjects in our auction treatments. The recruitment was done through mailing lists. The treatments were run using a software called Z-Tree. Initially, three treatments were run; the baseline no-manipulation treatment, the explicit manipulation treatment and the implicit manipulation treatment. In each auction round, the bidders were competing for a single hypothetical good whose value was given to them before the start of each auction round. The bidders? values were drawn randomly from 0 and 100 whereas the auctioneer?s values were drawn randomly from 0 and 50. It was also made sure that the auctioneer announced a final price even when that price was lower than her value. The auction profits of the subjects were ten per cent of the sum of 76 their earnings from the ten actual rounds. In addition to that, each of the subjects was also paid a $10 show-up fee. Cash payments were made to the participating subjects at the end of the experiment. In the baseline treatment we have one session with twenty participants. The participants are randomly divided in to five groups of four bidders in each group. There are ten actual auction rounds preceded by two practice rounds. The instructions, which were handed out to the participants, were read out before the start of the treatment. It explained the auction rules, how the winner and the winning price are determined and a couple of illustrating examples. The bidders were informed that the computer auctioneer was pre-programmed to choose the second highest bid as the winning price. Also, the bidders were informed that their values are randomly drawn from 0 ? 100 at the beginning of every round. At the beginning of each round, the subjects log in to the bid-submit screen on their terminal and get to know their randomly assigned value and submit their bid based on that value. Once all the bids are submitted, the computer declares the winner and the second highest bid. The round ends with a result screen where the subjects get to know the highest bid, whether or not they won the round, the winning price and their profits from that round. If the subject did not win the auction they will observe a winning price and profit of zero. They subjects are asked to note down their value, their own bid, the winning price and the profit from the result screen on a separate bid record sheet. The following are screenshots of the bid-submit and the results screen. 77 In the explicit manipulation treatment, there were twelve participants divided into three groups of four bidders. For each group, a pre-programmed computer auctioneer was used to announce the winner and determine the final price. The computer auctioneer also received a randomly assigned value at each round drawn from 0 ? 50. As before, there were ten actual auction rounds preceded by two practice rounds. The instructions were handed out and read aloud by the experimenter. It was clearly mentioned in the instructions that the winning price might not be the second highest bid always. Whenever the value of the auctioneer was higher than the second highest bid, the auctioneer would manipulate price and charge ninety per cent of the highest bid instead. This was just a simple approach to incorporate explicit price manipulation. In all other cases, the winning price would be equal to the second highest bid, just like in second price auctions. Just like the baseline treatment, the bidders would submit their bids from the bid-submit screen and record their value, bid, price and profits from the results screen. In the implicit manipulation treatment, there were eight participants divided into two groups of four. In each group, there were one auctioneer and three bidders. The participants were informed at the start of the session that the bidders would have randomly assigned values drawn form 0 ? 100 and the auctioneers would have random values drawn from 0 ? 50. Also, it was announced that the auctioneers role was fixed and that the remaining subjects participating as bidders would be randomly matched with the auctioneers every round to make sure that the set of bidders were 78 continually changing across rounds. To emphasize the implicit manipulation aspect, the instructions included the following statement: ?The auctioneer?s main task is to determine the winning price which is the second highest bid. The auctioneer would declare the price after reviewing all the bids submitted by the bidders in the group. Only the auctioneer would have access to these bids and her profit would depend on the price announced; more specifically, the higher the price is, the higher is the profit.? Also, a screenshot of the auctioneer?s price-submit screen was included with the bid- submit and result screenshots. 3.5. Results The baseline treatment results are summarized in the following tables. The first table reports P which captures how far apart the actual bid is from the truthful bid, expressed as a percentage. So, a lower value of P implies that the actual bid is closer to the ruthful bid, the extreme case being p = 0 where the actual bid is equal to the truthful bid. The second table reports summary statistics for this variable P. 79 Table 3.1: Baseline Treatment: P Values P = [1 - Actual Bidding/Truthful Bidding]*100 Frequency Frequency % P = 0 127 52.92 0 < P ? 1 35 14.58 1 < P ? 5 34 14.17 5 < P ? 10 9 3.75 10 < P ? 25 14 5.83 25 < P ? 50 4 1.67 50 < P ? 75 3 1.25 75 < P < 100 9 3.75 P = 100 5 2.08 Table 3.2: Baseline Treatment: Summary Statistics Variable Obsv. Mean Std. Dev. Min Max Proportion 240 8.603987 23.652 0 100 From Table 3.1 we see that more than half of the bidders chose to bid truthfully and about sixty five percent of the bidders had bids within ten per cent of the truthful bid value. There were five outliers with bids equal to zero. The following graph compares the baseline bidding behavior with the truthful bidding outcome. 80 Fig. 3.2. Baseline Treatment Bidding Outcome 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 Value Bi ds Truthful Bidding Actual Bidding Truthful Bidding The explicit manipulation treatment results are summarized in the following tables. Table 3.3: Explicit Treatment: P Values P = [1 - Actual Bidding/Truthful Bidding]*100 Frequency Frequency % P = 0 3 2.44 0 < P ? 1 28 22.76 1 < P ? 5 30 24.39 5 < P ? 10 18 14.63 10 < P ? 25 19 15.45 25 < P ? 50 8 6.50 50 < P ? 75 5 4.07 75 < P < 100 9 7.32 P = 100 3 2.44 81 Table 3.4: Explicit Treatment: Summary Statistics Variable Obsv. Mean Std. Dev. Min Max Proportion 120 18.46377 29.31196 0 100 From Table 3.3 we see that the percentage of bidders who chose to bid truthfully have gone down drastically and a much higher percentage of bidders prefer to shed their bid. Also, from table 3.4, we see that the explicit manipulation treatment has a much higher, more than double, mean value for the proportional difference between truthful and actual bidding. The following graph compares the outcomes from the explicit manipulation treatment with the truthful bidding case. Fig. 3.3. Explicit Manipulation Treatment Bidding Outcome 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 Truthful Bidding Actual Bidding Truthful Bidding Value Bi d 82 The implicit manipulation treatment results are summarized in the following tables. Table 3.5: Implicit Treatment: P Values P = [1 - Actual Bidding/Truthful Bidding]*100 Frequency Frequency % P = 0 6 8.82 0 < P ? 1 4 5.88 1 < P ? 5 13 19.12 5 < P ? 10 10 14.71 10 < P ? 25 11 16.18 25 < P ? 50 5 7.35 50 < P ? 75 0 0.00 75 < P < 100 2 2.94 P = 100 17 25.00 Table 3.6: Implicit Treatment: Summary Statistics Variable Obsv. Mean Std. Dev. Min Max Proportion 68 34.28523 41.85321 0 100 From Table 3.5 we see that the percentage of bidders who chose to bid truthfully have increased marginally from the explicit manipulation treatment but it is still significantly smaller than the baseline treatment. Also, from table 3.6, we see that the implicit manipulation treatment has a significantly higher mean value for the proportional difference between truthful and actual bidding than both the two previous treatments. However, the high percentage of bidders submitting zero bids 83 calls for additional sessions to check for such outliers. The bidding outcome for the implicit manipulation treatment is presented in the following graph. Fig. 3.4. Implicit Manipulation Treatment Bidding Outcome 0 20 40 60 80 100 120 0 20 40 60 80 100 Actual Bidding Truthful Bidding Truthful Bidding 3.6. Concluding Remarks. In this paper, we studied the effect of price manipulation by the auctioneer on the bidding behavior in a sealed bid auction. Our results suggest that bidding behavior in the sealed bid auction format is affected by possible price manipulation by the auctioneer. As expected, we have a much larger effect with explicit manipulation. Both with explicit and implicit manipulation, we have demand reduction compared to the no-manipulation, second price auction bidding. Based on these preliminary findings, we are confident enough that our new experiment design might be applied 84 more extensively to validate the theoretical claim of superiority of open auctions over sealed bid auctions on the premise that bidders bid sub-optimally in fear of price manipulation in sealed bid auctions. To the best of our knowledge, this is the first study that tries to analyze this experimentally. As a possible source of future research, we would ideally want to expand the scope this present study and analyze similar situations in a field experiment setting. One such possibility would be online auctions, which might be used to study this phenomenon. 85 Appendix Proof of Theorem 1: In this ascending auction model, the bidding strategy of each bidder is simply an answer to the question ?when to drop out?? Thus, truthful bidding in this model simply refers to the drop-when-price-equals-value strategy. Dropping out or reducing demand at a price less than the marginal value for that unit would be a case of under- bidding in our model. Likewise, dropping out or reducing demand at a price greater than the marginal value for that unit would be a case of over-bidding in our model. Quite understandably, to answer the question ?when to drop out??, the most important thing I need to know is what price I will pay if I win any unit. I have already shown that the price a winning bidder pays is independent of her own bid, which implies that the bidder?s final price is not affected by her decision about when to drop out. The other strategic implications that remain to be explored are whether the bidders can do better by under or over bidding in terms of the number of units they win. The number of units allocated to a bidder in my model is solely determined on the basis of efficiency. In fact, the final allocation is the one that generates maximum total reported value out of all the possible allocations. Let us suppose that all the bidders are using truthful bidding strategies. Now, let us check for any incentive to under bid. Clearly, no losing bidder would want to under bid. A bidder winning multiple units could have incentive to under bid to win fewer units at a lower price. In such situations, even though her total payment has been lowered, prices being 86 independent of bids, the price she has to pay for the remaining units are unaffected. Thus, under biding to win fewer units could only lead to a loss of surplus for the bidder. Thus, even a winning bidder would not want to under bid because the only thing that could accomplish is her winning lesser number units, prices for the remaining units being unchanged. Also, a losing bidder, by over bidding, could ensure winning at least one unit but at a price higher than her value. Similarly, a winning bidder could win more units by over bidding but at prices higher than values. Another potentially problematic bidding strategy could be to place an all-or-nothing bid at the margin such that you win those many units. The worst possible case could be where the marginal bidder(without complementarities) has the highest losing bid also and by placing a package bid, is allocated both the units. For example , ?, 8, 7, 6, 5, 2, ?, depicts situations like these where the same bidder has the values 6 and 5. Let the marginal bidder?s value for the marginal unit be x and her highest losing bid be y. Also, let the second highest losing bid be t and the second lowest winning bid be s, where t + s < x + y. Without misreporting the marginal bidder wins 1 unit at price t. However, by misreporting, she can win two units at a price of t + s. To check for incentive to misreport, we compare profit from truthful bidding, which is x ? t, to that from misreporting, which is (x + y) ? (t + s), or, (x ? t) + (y ? s) . This implies that the profit from misreporting is lower because s > y. Thus there is no incentive to misreport. 87 One last thing that needs to be verified is whether a bidder, who has a winning bid but is replaced by the marginal bidder, has any incentive to misreport. For example, in a auction like this, ?, 10, 7, 6, 6, 4, ?, if 6 is the average value of the marginal bidder, bidder i with value 7 has one of the top values but is not awarded any unit. In cases like these, there could be incentive to report a bid higher than value to win. Let us suppose that bidder i has 1 top bid with a true value of x. She reports a value x? in order to win the unit. Also, y is the highest losing bid and z average value of 2 units of complementarities. Since bidder i did not win any unit with the true value, it must be the case that x + y < 2z. Also, since she wins by misreporting, it has to be the case that x? + y > 2z. Prices paid are the VCG payments. Thus, bidder i has to pay 2z ? y for the unit she wins. However, 2z ? y being greater than x, she would have no incentive to misreport. Thus, we see that no bidder has any incentive to deviate from truthful bidding. Therefore, in this model, truthful bidding or wait-till-price-equals-value strategy is an equilibrium strategy. Proof of Theorem 2: While allocating the units, the main question that needs to be answered is whether any unit is going to be allocated to the bidder with complementarities or not. We will assume throughout this proof that Theorem 1 holds, which implies that the drop-out prices are the marginal value for that unit. In round t*, the number of units of complementarities (K) and the average value of these units (Pt*) are revealed. Thus, the total value of these K units can easily be computed as KPt*. To compute the 88 efficient allocation, this value has to be compared with the total value that would be generated if these K units were allocated to bidders other than the one with complementarities. Now, between rounds t and t, excluding round t*, the marginal value of these K units are revealed through the prices in these rounds. In addition, the identities of these bidders are revealed by the set of Drop-outs from each of the bidding rounds. Thus, the total value of these K units, allocated to bidders other than the one with complementarities, can be computed by summing up these prices from round t to t, leaving out Pt*. Thus, the total value of the K units awarded to bidders other than the one with complementarities is given by t t t t P = ? ? Pt*. Therefore, it immediately follows that whenever KPt* is greater than t t t t P = ? ? Pt*, the bidder with complementarities gets the K units, the allocation referred to in Case I. The other possibility is that KPt* is lesser than t t t t P = ? ? Pt*, implying that bidders other than the one with complementarities should be allocated these remaining K units, the allocation referred to in Case II. As mentioned before, the identity of these bidders are revealed by the set of Drop-outs for rounds t through t, leaving out round t*. Each of these bidders receives a single unit out of the remaining K units. Thus, we see that the allocation mechanism used here gives us efficient outcomes. 89 Proof of Theorem 3.1 and 3.2: Using result 1, we know that the bidders who have higher units of complementarities (> L ? M), do not affect the allocation of the marginal units. The set of Exclusions groups together such bidders. Once these bidders with higher units of complementarities are accounted for, the allocation algorithm simply selects those bidding rounds over which the aggregate demand reduction has been L ? M. The presence of bidders with lower units of complementarities is not a significant issue. These bidders are incorporated into the mechanism by multiplying their drop-out price by their multiunit demand, on account of the fact that now their total value over these units are relevant and not the average one. Thus, the algorithm operates exactly as the one discussed for the single bidder case. The only difference being the presence of more bidding rounds due to bidders with higher units of complementarities. Consequently, without any changes being made to the treatment of the MAP, the multi bidder algorithm has the same efficiency and truth telling properties of the single bidder mechanism. One issue regarding truth telling needs to be addressed separately for this special multi bidder case. Since by reporting a package bid of more than L ? M units any bidder is guaranteed to win those many units, it needs to be shown that there is no incentive to do so. Let us look at the most likely case where this sort of misreporting could be a possibility. Let us suppose that a bidder is winning x units(< L ? M) with value v, at a price p. By misreporting she could win y units(>L ? M) at a price p?. Her true value for the y units is v?. Now, for profitable misreporting, it has to be the case 90 that v ? p < v? ? p?. However, the additional units that she is winning by misreporting, is actually replacing those many units with values higher than her own(simply because her bids on those units were losing bids). Since VCG prices are used, p? would charge these replaced values for the additional units she wins. Thus, for these additional values, she would end up paying more than her true value and it is always the case that v ? p > v? ? p?. This proves that there is no incentive to misreport in order to take advantage of the fact that higher units of complementarities cannot be excluded from the final allocation. Proof of Theorem 4.1 and 4.2: From Result 2 we know that only one out of the many marginal bidders would be considered to be a part of the final allocation (which is determined using the recursive process outlined above). Thus, the multiple marginal bidder case is essentially similar to the single marginal bidder case, the remaining bidders having no role in the computation of either the final allocation or the prices. Thus, for computational purposes, the multiple marginal bidder model reduces to a single marginal bidder model, and the allocation and price algorithms used here is exactly similar to those used in the single bidder case. This implies that truthful bidding, VCG prices and efficiency theorems for single marginal bidder can also be applied in multiple marginal bidder cases, which proves the above two theorems trivially. 91 Bibliography Ausubel, Lawrence M. ?An Efficient Ascending-Bid Auction for Multiple Objects.? American Economic Review, Vol. 94, No. 5, pp. 1452-1475, Dec. 2004. Ausubel, Lawrence M. and Peter C. Cramton, ?Demand Reduction and Inefficiency in Multi-Unit Auctions.? Working Paper No. 96?07, University of Maryland, Department of Economics, July 2002 revision. Ausubel, Lawrence M. and Paul Milgrom. ?Ascending Auctions with Package Bidding?. Frontiers of Theoretical Economics: Vol. 1: No. 1, Article 1, 2002. Bikhchandani, Sushil, Sven de Vries, James Schummer and Rakesh V. Vohra, Linear Programming and Vickrey Auctions.? Mimeo, UCLA and Northwestern University, May 2001. Bikhchandani, Sushil and Joseph M. Ostroy, ?Ascending Price Vickrey Auctions.? Mimeo, UCLA, September 2001. Clarke, E. ?Multipart Pricing of Public Goods?. Public Choice, 2, pp 19-33, 1971 Cox, James C., Vernon L. Smith and James M. Walker, ?Expected Revenue in Discriminative and Uniform Price sealed Bid Auctions," in Vernon L. Smith, ed., Research in Experimental Economics, Vol. 3, Greenwich, CT, JAI Press, 1985, pp. 159-81. Das Varma, G., ?Standard Auctions with Identity Dependent Externalities,? RAND Journal of Economics, 2002. Davis, D. D. and C. A. Holt, Experimental Economics, Princeton University Press, Princeton, N.J., 1993. 92 Engelbrecht-Wiggans, R., ?Auctions with Price-Proportional Benefits to Bidders,? Games and Economic Behavior, 6 (1994), pp. 339-346. Engelbrecht-Wiggans, Richard and Charles M. Kahn, ?Protecting the Winner: Second-Price versus Oral Auctions.? Economics Letters, March 1991, 35(3), pp. 243?248. Ettinger, D., ?Auctions and Shareholdings,? working paper, CREST-LEI and CERASENPC, Paris, November, 2002. Holt, C. A. and R. Sherman, ?Risk Aversion and the Winner's Curse,? Unpublished manuscript, April, 2000. Kagel, J. H., ?Auctions: a survey of Experimental Research,? in The Handbook of Experimental Economics, (J. H. Kagel and A. E. Roth, eds.), Princeton University Press, Princeton, NJ, 1995. Kagel, John H., and Dan Levin, ?Independent Private Value Auctions: Bidder Behavior in First-, Second-, and Third Price Auctions with Varying Number of Bidders.? Economic Journal, July 1993, 103(419), pp. 868?879. Kagel, John H., Ronald M. Harstad and Dan Levin, ?Information Impact and Allocation Rules in Auctions with Affiliated Private Values: A Laboratory Study.? Econometrica, November 1987, 55(6), pp. 1275?1304. List, A. John and David Lucking-Reiley. ?Demand Reduction in Multiunit Auctions: Evidence from a Sportscard field Experiment,? The American Economic Review, Vol. 90, No. 4, Sep. 2000, pp 961-972. Groves, T. ?Incentives in Teams?, Econometrica, 41, pp 617-631, 1973 93 McAfee, R. Preston and John McMillan. ?Auctions and Bidding.? Journal of Economic Literature: 25(2), pp. 699-738, June 1987. Milgrom, R. Paul. ?Auction Theory.? Advances in Economic Theory Fifth World Congress, Cambridge University Press, pp 1-32, 1987. Milgrom, R. Paul and Robert J. Weber. ?A Theory of Auctions and Competitive Bidding.? Econometrica, 50(5), pp. 1089-1122, September 1982a. Morgan, John, Ken Steiglitz and George Reis. ?The Spite Motive and Equilibrium Behavior in Auctions,? Contributions to Economic Analysis & Policy, Vol.2, Issue 1 2003. Parkes, C. David and Debasis Mishra. ?Ascending Price Vickrey Auctions for General Valuations.? Journal of Economic Theory, 2004 Parkes, C. David and Lyle H. Ungar. ?An Ascending-Price Generalized Vickrey Auction.? Harvard University Technical Report , 2002. Perry, Motty and Philip J. Reny, ?An Efficient Auction.? Econometrica, May 2002, 70(3), pp. 1199?1212. Riley, J. G. and W. F. Samuelson, ?Optimal Auctions,? American Economic Review, 71, 3(1981), pp. 381-392. Rothkopf, Michael H., and R. M. Harstad, ?Two models of bid-taker cheating in Vickrey Auctions.? Journal of Business, 68(2):257--267, 1995. Vickrey, William. ?Counterspeculation, Auctions and Competitive Sealed Tenders.? Journal of Finance, 16(1), pp. 8-37, March 1961.