INCOMPLETELY SPECIFIED COMBINATORIAL AUCTION: AN ALTERNATIVE ALLOCATION MECHANISM FOR BUSINESS-TO-BUSINESS NEGOTIATIONS By JONI LYNNE JONES A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2000 Copyright 2000 by Joni Lynne Jones ACKNOWLEDGMENTS This dissertation, the culmination of my graduate education, could not have been completed without the support, patience and guidance of a multitude of people. One individual is overwhelmingly responsible for my success, Dr. Gary Koehler, my dissertation chair. His willingness to patiently share his expertise coupled with a gentle guiding hand and high expectations inspired me to seek excellence. I would also like to express my appreciation to the members of my committee for freely sharing their time and for their insightful comments. I am especially grateful to Dr. Selcuk Erenguc, my department chair, for recognizing my potential, giving me the opportunity and providing the resources necessary to achieve my goals. I'd like to extend my thanks to Dr. Jacquelyn Rees for providing a well-lit path to follow on the quest for my Ph.D. Let me also acknowledge my colleagues in the Ph.D program for their unwavering moral support and friendship throughout my years in the program, especially Dr. Lawrence Nicholson, Ms. Pauline Chin, Ms. Cheryl Aasheim and Mr. Kutsal Dogan. Thanks go to my friends who have been patient, understanding and always encouraging during the many triumphs and failures along the way. I especially appreciate my dear friend, Mr. Thomas Standridge, for his tireless support. Finally, I am forever indebted to my family, particularly my mother, Rose Patton, for always believing in me. m TABLE OF CONTENTS page ACKNOWLEDGMENTS iii ABSTRACT viii CHAPTERS 1 INTRODUCTION 1 1.1 Introduction 1 1.2 The Research Problem 3 1.3 Motivation 4 1 .4 Expected Contributions of this Research 7 1.5 Summary 7 2 AUCTION THEORY 9 2.1 Introduction 9 2.2 Overview 9 2.3 Auction Types 12 2.3.1 Single Item Auctions 12 2.3.2 Multiple Item Auctions 14 2.4 Framework: The Benchmark Model 19 2.5 Modifying The Benchmark Model Assumptions 21 2.6 Electronic Auctions 27 2.7 Summary 30 3 APPLICATION ENVIRONMENT AND MODEL 31 3.1 Network Television Practices 31 3.1.1 Environmental Constraints 34 3.1.2 Negotiation Strategies 35 3.2 Auction Description 37 3.2.1 Notation 38 3.2.2 Objective Function 39 3.2.3 Constraints 39 3.2.3.1 Reservation requirement 40 3.2.3.2 Maximum seller coverage 40 3.2.3.3 Maximum spot availability 41 3.2.3.4 Buyer selection indicator 41 3.2.3.5 Campaign commercial length constraint 42 3.2.3.6 Anti-Clutter Control 43 3.2.3.7 Frequency: Max commercials per show 43 3.2.3.8 Demographic gross impression guarantee 44 3.2.3.9 Show placement requirement 45 3.2.3.10 Pod protection constraints 46 3.2.3.1 1 Bid specification and ordering 48 3.2.3.12 Bidder reservation price 48 3.3 Summary 49 CONSTRAINT PROGRAMMING 50 4.1 Introduction 50 4.2 Constraint Satisfaction Problems 51 4.3 Arc Consistency 53 4.4 Systematic Search Algorithms 55 4.4.1 Look Back Algorithms 56 4.4.1.1 Chronological Backtracking (BT) 56 4.4.1.2 Backjumping (BJ) 57 4.4.1.3 Conflict-Directed Backjumping (CBJ) 58 4.4.2 Look Ahead Algorithms 58 4.4.2.1 Forward Checking (FC) 59 4.4.2.2 Maintaining Arc-Consistency (MAC) 60 4.4.3 Hybrid Backtracking/Forward Checking Algorithms 60 4.4.4 Improving Performance 61 4.5 Arc-Consistency Algorithms 62 4.6 Stochastic Search Algorithms 63 4.7 Constraint Programming 64 4.8 Advertising Sales Application 65 4.9 Summary 66 HUERISTIC DEVELOPMENT 67 5.1 Introduction 67 5.2 Overview 68 5.3 Aggregate Sub-Problems 70 5.4 Domain Management - Constraint Programming 73 5.5 Master Problem 76 5.5.1 Sorting Criteria 1 78 5.5.2 Sorting Criteria 2 79 5.5.3 Sorting Criteria 3 79 5.6 Branch and Bound 80 5.6.1 Breadth First Search (BFS) 80 5.6.2 Depth First Search (DFS) 81 5.6.3 Fathoming Criteria 81 5.7 Determining an Upper Bound to PI: 82 5.8 Summary 82 6 SIMULATED BIDDING AGENT DEVELOPMENT 84 6.1 Introduction 84 6.2 Data Analysis 86 6.3 Number of Buyers 87 6.4 Demographic Category and Total Gross Rating Points 87 6.5 Bidder Reservation Price 89 6.6 Commercial Lengths and Frequency 91 6.7 Limits on Number of Commercials 92 6.8 Selection of Product Type 93 6.9 Selection of Desired Shows 93 6.10 Bidding Strategy 96 6.11 Summary 101 7 EXPERIMENTAL DESIGN 103 7.1 Introduction 103 7.2 Performance Measures 103 7.2.1 Efficiency 104 7.2.2 Optimality 107 7.2.3 Auction Length 108 7.2.4 Solution Methodology Performance 109 7.3 The Experiments 109 7.3.1 Modification of Bidder Types 110 7.3.2 Modification of Bid Increment Ill 7.3.3 Modification of Stopping Rule Ill 7.3.4 Modification of Maximum Round Time 112 7.3.5 Heuristic Methods versus Integer Programming 113 7.4 Summary 114 8 EXPERIMENTAL RESULTS 115 8.1 Introduction 115 8.2 Agent Summary Statistics 115 8.3 Bidder Type Impact 118 8.3.1 Summary of Impact of Various Bidder Types 118 8.3.2 Analysis of Bidder Type Results 120 8.4 Bid Increment Impact 121 8.4.1 Analysis of Bid Increment Results 122 8.4.2 Summary of Bid Increment Findings 126 8.5 Analysis of Stopping Rule Effect 127 8.5.1 Trickle Effect 128 8.5.2 Summary of Stopping Rule Influence 129 8.6 Influence of Seller Reservation Price 129 8.7 Heuristic Performance: Changing Computing Time 132 8.7.1 Standard Heuristic Performance 132 8.7.2 FastMode Heuristic Performance 134 8.8 Heuristic Performance Versus Integer Program 135 VI 8.9 Summary 137 9 CONCLUSION 139 9.1 Introduction 139 9.2 Project Overview 139 9.3 Conclusions 140 9.4 Limitations 141 9.5 Direction for Future Research 142 9.5.1 Expansion of the Mechanism 142 9.5.2 Empirical Investigations 144 9.5.3 Game Theory Studies 145 9.6 Summary 145 APPENDICES A DISTRIBUTION OF DEMOGRAPHIC REQUIRMENTS BY CATEGORY 146 B REGRESSION OF PRICE AND DEMOGRAPHICS 149 C EXPERIMENTAL RESULTS 155 LIST OF REFERENCES 178 BIOGRAPHICAL SKETCH 188 vn Abstract of Dissertation Presented to the Graduate School of the University of Florida in Partial Fulfillment of the Requirements for the Doctor of Philosophy INCOMPLETELY SPECIFIED COMBINATORIAL AUCTION: AN ALTERNATIVE ALLOCATION MECHANISM FOR BUSINESS-TO-BUSINESS NEGOTIATIONS By Joni Lynne Jones August 20000 Chairman: Gary J. Koehler Major Department: Decision and Information Sciences The popularity of auctions has increased dramatically with their introduction to the Internet. The migration has provided a unique opportunity to harness the power of computing to create new auction forms that were previously unworkable. This research presents a new auction mechanism designed to accommodate the potentially large and often complex problems that are commonly reflected in negotiated sales. I describe a new and innovative way of using an auction mechanism by modifying a combinatorial auction to accept inexact multi-criteria package bids. The bids are incompletely specified yet provide enough of a framework to guide, rather than dictate, the choice of goods to satisfy stated needs. The ability of the bidder to prescribe various aspects of the sale, beyond her willingness to purchase goods at a particular price, makes it possible to use this type mechanism to replace or enhance negotiated sales. vin IX The allocation of goods requires solving a complex combinatorial problem in real- time. In the past this has been considered completely impractical in a conventional auction setting. Utilizing computing resources an online auction of this nature is not only feasible but may provide a way to optimally allocate a given set of bids while satisfying bidder preferences. This auction is applicable to any collection of goods but is most appropriate for complementary goods. As expected, the proposed model becomes computationally intractable as the number of bidders increase, I therefore present simplifying heuristics to make large problems manageable. Television advertising sales provides an interesting arena in which to investigate the use of the incompletely specified auction. The auction will be employed to accommodate sales where approximately 300 to 350 buyers compete for a finite amount of commercial airtime in the upcoming season. Several constraints unique to media buying are included in the model increasing its complexity significantly which include separation of competing ads, meeting bidder's demographic group exposure requirements while ensuring the seller receives her reservation prices, allowing for a variety of commercial lengths, and accommodating specific show placement requests. CHAPTER 1 INTRODUCTION 1 . 1 Introduction , — _ Electronic or Internet based auctions have garnered a great deal of interest in recent years. The renewed popularity of auctions stems from various characteristics unique to this form of commerce. Web based auctions enjoy a much broader audience due to their accessibility to anyone with an Internet connection, thereby growing the buyer pool, increasing competition and thus enhancing profits. The expense and logistics of gathering at one location, a major deterrent to conventional auctions, has been replaced with inexpensive websites. Barriers to entering the electronic auction market have been lowered for all participants. Finally, electronic auctions provide us an opportunity, through harnessing the power of computing, to establish more complex trading rules and handle more complex goods. It is this opportunity upon which we attempt to capitalize in this research. Recent progress in utilizing computing and networking power includes a variety of new auction designs to facilitate the simultaneous sale of multiple items. Various mechanisms have emerged such as the popular Internet based Yankee Auction (Vakrat & Seidman, 1998) and the Groves/Vickery design (Bapna, Goes & Goupta, 1998) in which a specified number of identical items are offered for sale simultaneously with the items going to the top bidders whose aggregate demand equals the number of items for sale. Alternatively, the FCC Spectrum license sales of the early 1990s showed that by executing single items auctions simultaneously, buyers could aggregate a desired collection of goods (Crampton, 1995; McMillan, 1994). None of the above designs allow the bidder to submit a single bid for a combination of heterogeneous items, although it has been shown that in the non-auction environment the value of a bundle of positively correlated goods can be greater than the sum of the individual item values (Bakos & Brynjolfsson, 1998). Allowing the bidder to create a unique bundle of desired goods for which a single bid is submitted, referred to as a package bid, would seem like a logical way to improve the efficiency of auctioning complementary goods by capturing the synergies between product offerings. The most recent advance in auction design, the combinatorial auction, acknowledges this need and profits from the use of computing power. In the past bidding on a group of objects has been considered completely impractical in a conventional setting due to the complexity of winner determination, however utilizing computing resources an online auction of this nature is not only feasible but has proven superior to other multi-object sales mechanisms (DeMartini, Kwasnica, Ledyard & Porter, 1999). All of the auction forms mentioned so far suffer from the fact that the buyer supplies a bid restricted to item and price information. For example, most combinatorial auctions assume the bidders desire multiple goods and have a reservation price for each, thus their package bid consists of the desired quantity of each item and a per unit price, or a single price for a designated collection of items. In either case a price-item vector is the sole basis for allocating winning bids. Constraints limiting the allocation, within the current combinatorial formats, are generally restricted to meeting reservation prices and product availability. In many cases this does not adequately reflect the needs of either the buyer or seller. Negotiated sales is a prime example of a business process that could benefit from the use of auctions as they provide an effective means of price discovery, especially for products hard to price a priori or when information asymmetries are present (Englbrecht-Wiggans, 1980; Milgrom, 1989; Choi & Whinston, 1998). However, incorporating the negotiation process into an auction mechanism requires the bid to contain extended specifications. The complexities generated by the required modifications to existing auctions have discouraged widespread use of electronic negotiation models (Choi, Stahl & Whinston, 1997). This research attempts to develop a new auction mechanism that captures the intricacies necessary to enhance or replace a negotiated environment. In this chapter we provide an overview of our thesis, including a brief description of the mechanism and application environment, our motivation and the research contributions. The research problem is presented in Section 1.2, the motivation for developing the particular model is discussed in Section 1 .3 and the anticipated impact of this study is provided in Section 1 .4. 1 .2 The Research Problem This research attempts to develop an auction mechanism as an alternative to sales usually accomplished through negotiation. The mechanism will need to provide the buyers with an opportunity to constrain the allocation of goods through a multi-criteria package bid. To impart flexibility, the mechanism must allow bids that are incompletely 4 specified yet provide enough of a framework to guide the allocation. The ability of the bidder to dictate various aspects of the sale, beyond her willingness to purchase units at a particular price, makes it possible to use this type of mechanism to replace or enhance a negotiated environment. Our research problem is to design an auction mechanism to accommodate the potentially large and often complex problems that are commonly reflected in the negotiated environment. We address this problem by modifying a combinatorial auction to accept inexact multi-criteria bids. The bids must extend beyond the current price-item vector and allow the bidder to guide, rather than dictate, the choice of goods to satisfy stated needs. We address this problem by carefully constructing a mechanism to accommodate the requirements of an industry whose sales are currently conducted exclusively through negotiation. The selection of winning bids in a combinatorial auction is an extremely complex problem, in fact it has been shown to be NP-complete (Rothkopf, Pekec and Harstad, 1998). Therefore, another question addressed in this study is to ascertain if a heuristic allocation engine can be developed to determine a satisficing solution in real time and if so how effective is it? 1 .3 Motivation The primary motivation for studying this problem was an acknowledgement of the need for an auction mechanism that more accurately reflects the demands of the market. Rarely are purchase decisions predicated solely on the price of an item, yet current auction mechanisms make allocation decisions based on this limited criterion. Secondly, the ability to harness computing power has made possible more complex auction mechanisms opening an exciting area of research and we want to expand the models available through this endeavor. Finally, we have identified an industry that may benefit from changing their current business process. We design our auction mechanism to sell commercial airtime for the Network Television Industry. Television advertising airtime is a commodity product that is currently sold through negotiations that are "frequently based on long-term relationships and editorial and demographic synergies, not just getting the lowest price (Weaver, pp.1, 1999)." Units are typically allocated on a first come first serve basis as opposed to being dictated by competitive forces that could enhance the network's ability to achieve an equilibrium based distribution of goods. The complexity of determining an allocation that simultaneously satisfies the market participants' demands restricts the seller's ability to promote competitive bargaining. This complexity is evidenced by advertising agencies widespread use of "optimizer," decision support software to assist in planning and buying media. Optimizers are purported to give knowledge and real-time information to the buyers to help them determine the best mix of media, i.e. network (including various daypart decisions), cable, syndication, billboard and print (Ross, 1998). Some suggest that if networks do not embrace technology they will get left behind (Stewart, 2000). The major networks have already seen an erosion of their market share with cable and syndication among the beneficiaries (Ross, 1998). Further evidence of the need for change in this industry is the appearance of alternative selling mechanisms. A number of web-based auctions have appeared selling excess last minute advertising inventory. These sites, such as AdOutlet.com and Adauction.com, are simplistic in nature selling single units of time that are considered "fire sale" spots or unsold airtime within close proximity to airdate. Airtime is similar to airline seats, at the end of each day unsold commercial airtime can never be recovered. These sites have been criticized for their limited offerings and their focus on "distressed" inventory (Stewart, 2000; Coleman, 1999). Proponents point out the advantage of 24- hour access and price discovery afforded by the sites (Kuchinskas, 1999). Current online advertising auctions are designed for scatter and opportunistic sales that handle short-term campaigns and or supplemental purchases throughout the year. There is no mechanism designed to assist in "upfront sales," the large onetime sale of spots encompassing annual campaigns. This market provides an interesting arena in which to extend the current design of the combinatorial auction. The combinatorial auction is appropriate for this environment to accommodate synergies between products and consumers' desires for a collection or bundle of goods to meet their annual campaign exposure requirements. In this environment there are also ample substitutes so buyers are not restricted to obtaining a specific item but may be satisfied with any number of the substitutes available. The current versions of combinatorial auctions do not allow for substitutes or bids that do not precisely specify the desired objects. Therefore, a new mechanism needs to be developed to accommodate these market characteristics. Chapter 3 explores this industry in greater detail, including a discussion of constraints imposed on the placement of ads that must be conveyed through the mechanism. 1 .4 Expected Contributions of this Research Two major contributions are expected from this research. First, we hope to develop a new business-to-business auction mechanism, the generalized model will be germane to environments were the purchase decision criteria extends beyond the price of the item or items desired. This multi-dimension combinatorial auction will accommodate business models that currently use negotiations as their primary sales mechanism and sales for products and or services that require multi-criteria decisions. The other major result from this study is the development of a heuristic designed to determine auction winners and efficiently allocate inventory. We hope the heuristic will provide an optimal or near optimal allocation and thus provide a methodology applicable to other combinatorial optimization problems. 1.5 Summary This chapter has briefly introduced the research project and discussed the merits of the study as well as its anticipated contribution. The remainder of this dissertation is organized as follows. Chapter 2 will present the background literature for auctions, including an overview of classical theory as well as recent discoveries propagated by the changes wrought by the migration of auctions to the Internet. Chapter 3 will introduce the application environment and define the problem using an integer programming model. We review constraint programming, a methodology effective in solving the type of problem represented by our auction in Chapter 4. The fifth chapter describes the heuristic development in detail. We intend to test our mechanism's performance through 8 simulation and in Chapter 6 we present the characteristics of the artificial agents that will represent bidders in our experiments. The agents are modeled to be representative of the industry participants, their characteristics reflect patterns discovered from data provided by a major corporation in the television industry. In Chapter 7 we outline the experiments that will be conducted to judge the performance of the mechanism. Details of experimental results as well as an interpretation of the findings are given in Chapter 8. Finally, conclusions from the research and identification of future directions for this study encompass the remainder if this dissertation. CHAPTER 2 AUCTION THEORY 2.1 Introduction This chapter presents a general overview of Auctions. The goal of this chapter is to review classic auction theory and various extensions that have originated from it. Section 2.2 will provide a general overview of auction theory, specifically defining an auction, its players, various auction categories and the settings that favor their use. Section 2.3 describes various auction types, both single item and multiple object formats. Section 2.4 will present the well accepted classical or "benchmark" auction model. Section 2.5 looks at modeling issues that must be considered and broadens our perspective by reviewing several auction situations that either extend or restrict the benchmark model. Section 2.6 reviews the impact of the Internet on auctions. 2.2 Overview "An auction is a market institution with an explicit set of rules determining resource allocation and prices on the basis of bids from the market participants" (McAfee & McMillan, 1987, pp.701). It attempts to match a buyer with a seller to achieve a market clearing equilibrium price (Engelbrecht-Wiggans, 1980). Formalized trading procedures govern the players' interaction based on specific rules for competitive bidding and trade execution (Klein & O'Keefe, 1998). Choi and Whinston (1998) describe an 10 auction as simply posted prices where the price movements are more rapid and the number of participants greater. Auctions are the simplest and most familiar means of price discovery (Engelbrecht-Wiggans, 1980). Thus, they are effective when items are hard to price (Beam & Segev, 1998), for instance when demand for an item is difficult to determine a priori or when a product's value varies greatly (as with time sensitive products or services, which tend to lose their value rapidly) ( Chio & Whinston, 1998; Bapna et al.,1998; Milgrom, 1989). Auctions are commonly classified by the goods traded or the rules used that determine the final price (Lengwiler, 1999). Some auctions are performed in real time while others accept bids over time to be matched at a specified later date (Klein & O'Keefe, 1998). A typical auction consists of four major components: players, objects, payoff functions and strategies (Engelbrecht- Wiggins, 1980). Players include the bidders, the seller and the auctioneer. Most literature views auctions from the perspective of the seller who owns the item(s) for sale and is attempting to maximize his profit. Conversely, the bidder attempts to minimize the price, thereby maximizing her utility. The seller, as the Stackelberg leader or first mover, normally precommits to a set of policies, choosing the auction form and rules (McAfee and McMillan, 1987). A Stackelberg leader is implicitly assumed to commit first to his chosen action and not change that action after receiving additional information, even though changing might be profitable ex post (Rasmusen, 1989). This seeming advantage is tempered by information asymmetries. The seller and buyers do not know the other player's valuation of the object to be auctioned (Choi & 11 Whinston, 1998). The auctioneer, in the traditional setting, is simply a facilitator bringing together the buyer and seller. The number of items offered, value information, physical characteristics and type characterize objects (Engelbrecht-Wiggins, 1980). Single objects are the common focus of classical auction theory, however objects may be single divisible or indivisible items, a package of non-identical items, or multiple homogeneous items. Value information broadly defines who knows what. There are two commonly assumed models, the Independent Private Value model (IPV) and the Common Value model. If bidders know with certainty the value they individually place on an item the auction uses the Independent Private Values model. Individual valuations have a common distribution but are statistically independent of the other customers' valuations (Beam, Segev & Shanthikumar, 1996). A Common Value object, on the other hand, is assumed to have a single value but information regarding this value is varied among bidders. The bidders' valuation is dependent on at least one common objective variable, possibly resale value or future royalties (Kagel, 1995; Das & Sundram, 1997; Milgrom, 1989). Due to the statistical dependence inherent in the Common Value model, bidders tend to infer information from others' bids (Beam, et al., 1996). Milgrom and Weber (1982) refer to the positive correlation between bidder valuations in the Common Value model as affiliation. The payoff function involves decisions surrounding the financial transfer of a product such as the award mechanism or the rule used to determine the winning bid, final price and recipient, the presence or absence of a reservation price, and other participation costs (Engelbrecht-Wiggins, 1980). Occasionally included in the calculation of the 12 payoff function are charges for preparing and submitting bids and participation fees. The price paid by the winner for the object can depend solely on the final bids or on something correlated with the item's values such as royalties (McAfee & McMillan, 1987). In single object auctions, the payoff function routinely awards the object to the highest bidder if that bid exceeds the seller's reservation price. The seller has the right to retain the item should bidding fall below a predetermined minimum amount, referred to as his reservation price (Milgrom, 1989). Finally, strategies refer to how a bidder executes her bid. Milgrom (1989) defines a "pure" bidding strategy as one that is based on a function of the information the bidder knows. If all bidders accurately predict the other participants' bidding strategies and then use that information to select their own strategy, Nash Equilibrium is achieved (Nash, 1950). Nash Equilibrium (or rational-expectations) strategies maximize the expected utility of the outcome and is used routinely as the strategy of choice in classical auction theory (Engelbrecht- Wiggins, 1980). 2.3 Auction Types 2.3. 1 Single Item Auctions There are four basic types of auctions used when a unique item is bought and sold. They can be classified by the rules that govern the exchange of goods. The rules affect bidding strategies and incentives and thus transaction efficiency. English Auction: By far the most common type of auction, the English auction is an oral, outcry, ascending auction where progressively higher bids are solicited until only one bidder remains. The object is awarded to the remaining bidder at the price equal to 13 her highest bid. At equilibrium the bidder who values the item the most will retain the object at a price equal to their second highest valuation, therefore the English auction is efficient (Milgrom, 1989). Due to the open nature of the auction, bidders can observe the behavior of other bidders, process this information and dynamically modify their reservation prices (under the Common Value model) (Beam, Segev and Shanthikumar, 1996). The dominant bidding strategy used is to bid until the price exceeds the buyer's willingness to pay, normally a small increment below the bidder's true valuation (Beam, et al, 1996). Examples include art, antique and livestock auctions. Dutch Auction: Similar to the English auction, the Dutch auction is an open outcry, oral auction. It differs only in the direction of the bid progression. In a Dutch auction the auctioneer calls out an initial high price and then successively lowers the price until a bidder claims the object, normally by shouting "mine!"(Choi & Whinston, 1998). Unlike the English auction, since the auction concludes with the first bid, bidders cannot gain signal information from the behavior of other bidders (Beam et al., 1996). The dominant bidding strategy used is to claim the object when the bid equals a small increment below the bidder's true valuation (Beam et al., 1996). The increment between the bidder's true valuation and the actual bid is the buyer's surplus. The cut flower market is an example of this type of auction. First Price Auction: This mechanism is also known as the First Price Sealed Bid Auction. Potential buyers submit a single sealed written bid. Bids are opened simultaneously and the item is awarded to the buyer who submitted the highest bid at a price equal to her bid (Milgrom, 1989). As in Dutch auctions, information cannot be gleaned from observing other bidders' behavior, therefore bidding strategies are based on 14 the participant's individual value of the object and the expected behavior of the other customers (Beam, et al., 1996). This auction may be inefficient since the bidding strategy employed is affected by information asymmetries and thus may result in not awarding the item to the highest value bidder (Milgrom, 1989). Government procurement contracts commonly use this auction type. Second Price Auction: This is also known as the Vickrey or sealed-bid second price auction. As with the first price sealed bid auction, buyers submit sealed bids with the highest bidder claiming the object. However, as the name implies, the price paid for the item is equal to the second highest bid rather than the winning bid (Vickrey, 1961). Bidding one's true valuation is the dominant strategy for this auction since the object will be awarded at some increment below the winning bid, ensuring consumer surplus (Engelbrecht-Wiggans, 1980). The Vickrey auction duplicates the principle characteristics of the English auction and, due to the similar theoretical properties discussed in depth in section 2.4, as well as notational efficiency, English auctions are customarily modeled as Second Price auctions (Milgrom, 1989). Variations of the four general categories have spawned a multitude of auctions. For example, fees can be charged for participation or the seller may impose a reservation price below which he will not sell (McAfee & McMillan, 1987). 2.3.2 Multiple Item Auctions Vickrey (1961) first proposed the "multiple auction" where several identical units are sold to bidders who desire but one item. Two variations of the progressive auction, simultaneous and sequential, are most commonly used to facilitate multi-unit sales. How 15 the auction(s) are conducted within the multi-unit environment (i.e., sequentially or simultaneously) propagate a variety of alternative designs. Additionally, recent progress has been made in facilitating package bidding within a multi-object variation of the traditional English auction. Sequential auctions utilize one of the standard or modified auction forms but execute them serially until all goods have been exhausted (Vickery, 1961). Problems exist with sequential auctions making them less attractive than simultaneous auctions. First, they reduce the bidder's ability to efficiently aggregate. Once an auction is complete the items are allocated, if in subsequent auctions the bidder is unable to obtain a complementary product, the value of the previously acquired object diminishes. With the sequential auction you can not modify earlier bids. McAfee and McMillan, (1996) and Ashennfelter (1989) also discovered that sequential auctions produce various prices for identical items depending on their position in the sales sequence (later sales tend to fetch greater prices). Finally, bidders that are budget-constrained can be eliminated by one or a group of bidders driving up the price in the early rounds, thus effectively exhausting the constrained budget (Benoit & Krishna, 1998). Revenue comparisons conducted by Benoit and Krishna (1998) show that sequential auctions have appropriate applications. Sequential auctions were discovered to outperform simultaneous if objects are substantially different or if the complementarities are significant (Benoit & Krishna, 1998; Krishna & Rosenthal, 1995). Alternatively, a collection of auctions equal to the number of objects could be held simultaneously. Simultaneous ascending auctions are covered in detail by McMillan (1994), Krishna and Rosenthal (1995), Crampton (1995), McAfee and MccMillan (1996), 16 and Milgrom (1997). With simultaneous ascending auctions bidding is open for multiple items at the same time and remains open as long as there is active bidding on some unit. Bidding occurs in rounds with the results posted at the end of each (Milgrom, 1997). Information access allows participants to analyze their position with respect to the bundle of items they hope to acquire. Keeping all auctions open gives a bidder the flexibility to aggregate products in the manner she chooses and reconfigure those choices should the combination become too expensive (McAfee and McMillan, 1996). Arguably the most widely known form of multi-object simultaneous auction are the FCC Spectrum auctions. The government allocated PCS narrowband licenses using a simultaneous ascending auction, dubbed "the greatest auction in history" by the New York Times which was designed specifically to facilitate the aggregation of multiple licenses by a single buyer (Benoit & Krishna, 1998). The positive synergy between licenses in adjoining areas was acknowledged by the architects, but combination or package bidding was not allowed due to its perceived complexities (Cramton, 1995). Simultaneous auctions are subject to an exposure problem, a phenomenon causing bidder losses (DeMartini, et al. 1999). Losses result from "mutually destructive bidding" where bidders unable to obtain a complete set of goods due to competition are left holding goods priced at more than their value (Bykowsky, Cull & Ledyard, 1995). To protect themselves, bidders may bid less aggressively precipitating reductions in efficiency. To overcome this problem investigators have suggested allowing package bids (Ausubel, Cramton, McAfee & McMillan, 1997). Very little work had been done involving bundling of auction goods until the FCC auction design debate highlighted an assignment void involving auctions for multiple 17 heterogeneous goods with synergies. Palfrey (1983) had analyzed bundling decisions for multiple heterogeneous objects where demand was uncertain and found that seller surplus diminishes as the number of bidders increase. Information asymmetries led the seller to bundle items for which higher individual prices could have been obtained. Kim (1996) later derived an equilibrium model in which bidders incorporate their individual and complementary valuations so as to ensure that the auction is efficient with respect to the bundled value while not actually auctioning the bundle as a whole. Enlisting the help of electronic agents, Fan, Stallaert and Whinston (1998) introduced "bundle trading" to effectively construct investment portfolios. If complementarities exist among the items being sold, evidence suggests that it may be more appropriate to permit bidders to bid for packages, rather than simply bidding item by item such as in the FCC auction (Banks, Ledyard & Porter, 1989; Bykowsky, Cull & Ledyard, 1995; McMillan, Rothschild & Wilson, 1997; Ledyard, Porter & Rangel, 1997; DeMartini, Kwasnica, Ledyard & Porter; 1999). Unlike the work of Palfrey (1983) where the seller creates the bundle of goods, bidders form the bundles by submitting package bids in what is termed a "combinatorial auction." One of the first investigations into this auction format was conducted by Rassenti, Smith and Bulfin (1982) and allowed package bidding to allocate airport time slots to competing airlines. They employed a "set-packing" algorithm to determine resource shadow prices later used to ensure package prices fell at or below bid amounts. Empirical tests showed the mechanism to be efficient and demand revealing. Rothkopf, Pekec and Harstad (1998) describe this type of auction as one that facilitates a bidder's desire to submit bids for combinations of assets. 18 Three newly designed implementations of the combinatorial auction, the Adaptive User Selection Mechanism (AUSM), the Resource Allocation Design (RAD) auction and a Web-base implementation are being investigated to meet multiple item allocation needs when synergies between or among objects exist. The Adaptive User Selection Mechanism is a modification of the English ascending-bid auction that allows both package bids and individual item bids. Described by Banks et al. (1989) as a decentralized mechanism, with continuous bidding communicated via an electronic bulletin board. Initial implementations suffered from a new phenomenon, the threshold problem. It was discovered that when package bids are allowed, small bidders may not be able to dislodge a large but inefficient package bidder (see DeMartini et al.(1999) for an excellent description). A "standby" queue was added to facilitate coordination among bidders to form a large enough collection of small bids to displace the current winner(s) (Banks et al., 1989). Although the queue solved the threshold problem, it added complexity to the mechanism. The Resource Allocation Design (RAD) Auction simplifies the AUSM by introducing a new pricing rule eliminating the need for the standby queue and thereby overcoming the AUSM's complexity issue. A vector of single item prices is internally computed from bids and used to check minimum bid increment requirements and convey information to bidders. Bid opportunities are presented to bidders combating the formation of thresholds (DeMartini et al., 1999). Finally, Teich Wallenius, Wallenius, & Zaitsev (1999) offer an electronic auction for multiple homogeneous units that allows the bidders to specify if they will accept partial fulfillment of their package bid. Additionally, due to its semi-closed nature, sellers can establish various reservation prices for different quantity levels thus facilitating price ~ 19 discrimination. The auction is sealed in that bidders do not have access to the bids of others but the mechanism recommends entering bids to inactive bidders, or bids that based on current conditions would be a potentially winning bid. This design has been shown to overcome the "winners' curse" prevalent in common value auctions. Other problems faced in this arena stem from the sheer number of possible bundle combinations. In light of the complexity, Rothkopf et al. (1998) investigate how to determine a revenue maximizing set of non-conflicting bids and identify structures that are computationally manageable. Placing certain restrictions on the family of permitted bids formed the basis of their analysis. Nested combinatorial bids that form a single tree structure provide, through "rolling back" the tree, a straightforward way to determine the revenue maximizing outcome (Rothkopf et al., 1998). Additionally, if bid combinations are composed of either at most doubletons or at least a large proportion of the number of available assets, maximizing algorithms could be found that are mathematically tractable. Bids with the intervening cardinalities are considered NP-complete (Rothkopf et al., 1998). Some geographic structures such as an interval of consecutive assets or items that could be organized into a k-dimensional matrix, thereby permitting row or column-wise bids, were proven by Rothkopf et al. (1998) to be computationally manageable. 2.4 Framework: The Benchmark Model The next logical question to be answered is which of the auction forms is optimal? Bulow and Roberts (1989, pp. 1060) define an optimal auction as a "bidding mechanism designed to maximize a seller's expected profit." This complex topic has received a great deal of scholarly attention including work by Vickrey (1961), Myerson (1981), Bulow & 20 Roberts (1989), Riley and Samuelson (1981), Milgrom and Weber (1982). We will begin our analysis by presenting a simple framework. The following standard assumptions, gathered by McAfee and McMillan (1987) from early game theory models such as those defined in Vickrey's 1961 seminal paper, define the "Benchmark Model." The assumptions are common knowledge among the participants. 1 . All participants are risk neutral (bidders and sellers). 2. Bidder valuations are independent and private (Independent Private Value Model). The value (v/ ) that bidder i places on an object is independently drawn from a distribution F/. Note: although the individual values are private, all players know the distribution governing their valuation. 3. Bidders are symmetric, every buyer has the same cumulative distribution denoted by F. 4. There are no fees associated with the auction. The price paid by the winning bidder is dependent entirely on the bids themselves. Based on these fairly restrictive assumptions, each of the four basic auction types results in the same expected revenue. This notion is the basis of the Revenue Equivalence Theorem which states that for the benchmark model, the four standard auction forms yield the same price on average (Das & Sundram,1997; Milgrom, 1989; Vickrey, 1961; Ortega-Reichert, 1968; Myerson, 1981; McAfee & McMillan, 1987). Fueling the field of optimality study are modifications to the basic or benchmark assumptions. 21 2.5 Modifying The Benchmark Model Assumptions There are several modeling issues that warrant consideration when choosing particular auction rules. Most, but not all, correspond to the benchmark model assumptions of risk aversion, value formulation, bidder asymmetry, fees and the number of items to be sold. Strength of bidding competition and the potential for collusion also must be addressed. Uncertainty is central to choosing to utilize an auction as the sales mechanism. Should the seller possess perfect information, the need for price discovery would be moot and posted prices would optimize the seller's surplus (McAfee & McMillan, 1987). How the participants deal with this uncertainty determines their degree of risk aversion. Studies by Hanson and Menezes (1968), Baron (1972) and McAfee and McMillan (1987) confirm that varying the degree of risk aversion affects bidders' behavior. The buyer's surplus received by a bidder i with valuation v ; bidding b i is v ( . -b i if she is awarded the item and zero otherwise. To enhance the probability of winning, the risk-averse bidder increases the size of her bid, reducing her surplus and increasing the seller's surplus (Das & Sundaram, 1997). If either the seller or buyer is risk-averse, the seller prefers the Dutch or first-price auction (Harris & Raviv, 1981 ; Holt, 1979; Milgrom & Weber, 1982). When bidders are asymmetric (valuations are no longer based on a common distribution F), the Revenue Equivalence Theory does not hold (Das & Sundaram, 1997; McAfee & McMillan, 1987). Competition from the now disparate bidders has an effect on the determination of bids for the first price sealed bid auction since its bidding strategy 22 considers both the individual's value and that of the second highest competitor. Within this environment two bidders valuing the item equally may evaluate their nearest rival's value for an item differently, thereby leading to incongruous bids. The inconsistent bidding may award the item to a bidder without the highest value making this auction form inefficient (Das & Sundaram, 1997; McAfee & McMillan, 1987). Auction mechanisms with bidding strategies dependent on the participant's individual valuation (i.e., English, Dutch and Vickrey) remain efficient. The benchmark model assumes independent private values. Relaxing this assumption gives rise to another extreme, the common value model. Here bidders guess an item's unique true value (McAfee & McMillan, 1987). A phenomenon inherent with the common value assumption is the "winner's curse;" defined by Engelbrecht-Wiggans (1980 pp. 133) as "when the individual to whom the object is awarded tends to be the one who most overestimated the true value of the object." Information asymmetries account for the variation in bids. Here, Milgrom and Weber (1982) show that the English auction performs best in generating the greatest revenue followed by the second-price auction. Dutch and first-price auctions are equivalent as least effective under the common value assumption. Value uncertain bidders can acquire additional information by observing the behavior of other bidders in the English auction. Additionally, Milgrom and Weber (1982) propose that the seller can increase his expected revenue by providing the bidders with information correlated to the item's true value. This phenomon is refered to as the linkage principle is based on the fact that with additional information initially low-value bidders will raise their estimates, thereby promoting more aggressive bidding (Milgrom 23 & Weber, 1982). More recent literature has found that this principle does not hold beyond single item auctions (Perry & Reny, 1 999) So far we have based bidder payments entirely on the bids. Relaxing this assumption the seller can obtain additional information about valuations (McAfee & McMillan, 1987). There are many auctions, such as for book publishing and mineral rights, where payment depends on both the bid and information revealed ex post (via royalty rate or sharing parameter) (Das & Sundaram, 1997). The price paidp is a combination of the bid price, a royalty rate r, and the value v of the object unknown at the time of the auction p = b + rv . Introducing a royalty rate reduces the impact of the inherent variances in bidder valuations, thus inducing bidders to act more aggressively. Seller revenue rises with aggressive bidding (McAfee and McMillian, 1987). Most auction theory literature assumes that bidders act non-cooperatively, that is they do not agree to modify their competitive bidding behavior to manipulate equilibrium pricing (Kagel, 1995). In reality, collusion exists in the form of cartels or rings; agreements between bidders regarding bidding aggressiveness and/or predetermination of winners (McAfee & McMillian, 1987). Mead (1967) hypothesized that ascending-bid auctions were more susceptible to collusion than were sealed-bid auctions. Milgrom (1987) confirmed these results using the case of two bidders agreeing to alternate wins. The intuition for this result rests with being able to hide secret price concessions using a sealed bid mechanism, which is impossible in an open ascending auction. Bidding rings or cartels operate on the premise that without competition from the other ring members a designated member can obtain the item at a reduced price. The item is then re-auctioned 24 among the cartel members, with members sharing in the proceeds resulting from the difference in original auction price and the cartel auction price (McAfee and McMillan, 1987). To combat these activities, Cassady (1967) recommends establishing a reservation price that increases with the number of potential cartel members. Another consideration for auction models is the potential strength of bidding competition. Holt (1979) and Harris and Raviv (1981) have shown that increasing the number of bidders increases seller revenue on average. They propose that the greater the number of bidders, the smaller the gap, on average, between the value of the highest and second highest bidder (the winning price). In independent private valuation first price auctions the uncertainty of the number of participants can be exploited. McAfee and McMillan (1987) show that if the number of bidders is unknown and they have constant or decreasing absolute risk aversion, then concealing the number of bidders enhances revenue. The results so far have applied to auctions for a single item. The impact of varying the number of items for auction is gaining a great deal of attention. Both Vickery (1961) and Weber (1983) look at how the "benchmark model" holds in this setting. They discovered that using the Independent Private Values model (IPV) and Nash equilibrium bidding strategies, sustains the Revenue Equivalence when bidders take only one item. Kim (1996) and Lengwiler (1999) look at the issues raised when auctioning more than one item. When the bidder can purchase more than one unit, Engelbrecht and Kahn (1998) claim striking differences emerge. Namely, although a weak form of revenue equivalence holds, the various auction formats (i.e., uniform price, discriminatory or pay- your-bid, and Vickrey) allocate units differently. Attempts have been made to establish 25 which auction performs better for the seller (Back and Zender, 1993; Noussair, 1995; Katzman, 1995; Engelbrecht-Wiggans & Kahn, 1998). Engelbrecht-Wiggans and Kahn (1998) discovered that with uniform price auctions (a common form of simultaneous multi-unit auction in which high bids win the units, but all units are sold for the same price) tend to encourage zero bids. Pay-your-bid auctions, requiring the winners to pay the individual winning bid, outperform uniform price auctions according to Katzman (1995) while the Vickrey auction provides the seller with the most revenue. The complexity of multi-unit auctions has also affected the study of mechanism optimality. Armstrong (1999) considers the optimality of heterogeneous multiple unit auctions with package bids. Although his analysis was limited to two objects, he found that bundled auctions are efficient but generate different revenue which are strictly optimal in some circumstances. Revenue equivalence does not generally hold within this environment if values are discretely distributed (Armstrong, 1999). The presence of financial constraints introduces important differences into traditional auction theory. Most notably the revenue equivalence theorem fails (Pitchik & Shotter, 1988; Che & Gale, 1996, 1998). In the case of private information and absolute spending limits, Che and Gale (1996, 1998) found that first-price auctions yield higher expected revenue and social surplus than the other standard auction forms. Also a subsequent bidder's payoff is influenced by the price paid by rival bidders (Benoit & Krishna, 1998; Pitchik & Shotter, 1988). When faced with budget-constrained bidders, the order that items are presented for sale in a sequential auction is important. Benoit and Krishna (1998) demonstrated that it is not always optimal to sell the more valuable object first. Budget constraints likewise impact the strategic bidding behavior of auction 26 participants. Pitchik and Schotter's 1988 experiments using sequential auction with complete information discovered that the trembling hand perfect equilibrium is more representative than Nash equilibrium in predicting prices. Trembling hand perfection allows for bidders to "tremble" or make mistakes but eventually equilibrium will be achieved by taking their rival's mistakes into consideration in the limit or in this case at the completion of a sequence of auctions (Fudenberg & Tirole, 1991). This equilibrium is robust enough to compensate for the possibility that some players may not play their dominant strategies (Rasmussen, 1989). Financial constraints may be absolute with a preset upper bound, be limited to a certain amount on average, or may be determined endogenously as part of the strategic auction decisions (Engelbrecht-Wiggans, 1987; Benoit & Krishna, 1998). To combat the negative effects of budget constraints Che and Gale (1996) propose a policy that alleviates indivisibility of the good, allows joint bidding, and offers seller provided financing. Most of what we know about combinatorial auctions has been discovered through empirical studies. Recent experimental work by DeMartini et al. (1999, pp. 22) comparing multi-object auctions reveals "the option to bid for packages clearly improves performance in difficult environments, and does not degrade performance in simple environments." They also presented evidence that the RAD combinatorial auction outperforms both non-combinatorial models and earlier combinatorial (i.e., AUSM) models. Performance was judged on efficiency, auction length, and bidder losses. From the seller's perspective, package bidding was shown to reduce revenues as a percent of the maximum possible (but not average seller revenue). An interesting caveat of their investigation looked at the tradeoff between bidder profits and seller revenue and 27 suggested that high seller revenue is driven by high bidder losses (DeMartini et al., 1999). This posses two concerns, that of possible bidder default when faced with copious expenses as well as potentially decreasing consumer goodwill. The RAD design was able to achieve revenue gains while at the same time yielding high seller revenue, implying the mechanism is effective in minimizing the tradeoff between the opposing objectives (DeMartini et al., 1999). Solving a large problem with this mechanism could prove computationally intractable requiring some sort of heuristic to reach an acceptable conclusion (Rothkopf et al., 1998). Recently two-sided versions of these combinatorial auctions have been deployed, one for trading environmental emissions permits and another to support bond trading. The bond trading mechanism was built to handle 2,000 bonds (commodities) and 50,000 bids. Given the complex bids allowed, a lot of non- convexities, this means about 200,000 variables and 300,000 constraints. A fully relaxed linear program solution takes about 20 minutes to solve. The heuristic algorithm produces a solution which exceeds 85% of the best known bound, 90% of the time (Personal correspondence Ledyard, 1999). This is the first large-scale introduction and will prove an interesting test of the tractability of the auction form. 2.6 Electronic Auctions The introduction of auctions on the Internet has heralded a resurgence in their popularity as a selling mechanism and as an area of academic research. Much of the classic auction theory is being reevaluated in light of the new medium and plentiful data. An empirical investigation by Bapna, Goes and Gupta (1998) revealed that classical assumptions might not hold with electronic auctions. Namely, they found heterogeneity 28 among bidders, characterized by different bidding motivations such as the entertainment value of participation and other rational and irrational bidding strategies. Introduction of software agents, or automated bidding mechanisms, described as "hyper-rational" by Varian (1995), may account for some of this heterogeneity. Yet another study suggests the revenue equivalence theorem is not supported for on-line auctions (Lucking-Reiley, 1999). A field study of 100 on-line auctions by Beam and Segev (1998) recommends a set of criteria for "good" auctions and provides an overview of current practices. Traditional auctions differ from electronic auctions in several ways that may account for the departure from classical theory. For example, a traditional auction is held at a physical location, is conducted by an auctioneer and lasts a few minutes. In the classical setting this leads to a great deal of expense to establish a site, employ an auctioneer and gather the potential customers. Goods must be transported to a central location and may not be easily examined due to time or physical limitations (Turban, 1997). Conversely, electronic auctions close on average once per week, with many closing daily or hourly, they can be conducted anywhere, use an electronic agent as the auctioneer, and multimedia and database facilities allow for extended complexity of the trade object description (Beam and Segev, 1998; Klein and O'Keefe, 1998). Additionally, the Internet provides a global pool of potential bidders suggesting more aggressive bidding resulting from increased participation. Electronic auctions have lowered entry barriers for all auction participants including auctioneers, suppliers or sellers and consumers (Klein & O'Keefe, 1998). For example, E-Bay is an on-line auction that provides a forum where any seller can submit items for sale and reap the benefits of worldwide exposure. An opportunity associated with electronic auctions is the 29 potential to establish more complex trading rules through utilization of the environment's computing power (Klein & O'Keefe, 1998). One of the most noteworthy departures from the classical auction format is the emergence of various multiple object auctions. The strategy of distributing the multiple objects amongst winning bidders and preferences given to those who bid in bulk have formed different on-line auction mechanisms. For example, one of the most popular on- line auction forms is the multi-unit English auction. A common version of this auction type is the "Yankee Auction" in which a specified number of identical items are offered for sale simultaneously. At the close of the auction, the highest bidders win and pay their bid price (Vakrat & Seidmann, 1998). Bids are ranked in order of price, then quantity, then time of initial bid. Specifically, if two or more bids are for the same price, the larger quantity bids take precedence over smaller quantity bids, while if bids and quantity are the same, then the earlier bid takes precedence over later bids (Beam & Segev, 1998). Bapna, Goes and Gupta (1998) describe a modification of the Vickery Auction used on- line which adopts a uniform pricing scheme over the collection of items where each winner pays a price equal to the highest rejected bid. Modeling the emerging on-line auction forms has proven a formidable task. Vakrat and Seidmann (1998) establish a model that incorporates the "time dimension" of online auctions or the impact of extending bidding over extended periods of time and space. Beam et al. (1999), using a Markov Chain, were able to model a typical online single item auction and extend their model to allow for the sale of multiple identical items where each bidder wants at most one item. The lack of adherence to classical auction theory assumptions and the variety of online mechanisms have hampered the quest for a 30 single concise model. The most recent advances, combinatorial auctions, have only been investigated experimentally and due to the heuristic nature of their solutions have yet to be modeled definitively. 2.7 Summary In this chapter we presented a synopsis of classical and emerging auction theory. A great deal of scholarly research exists in the field providing well established guidelines on everything from bidding strategies to optimality of various auction forms. New discoveries are emerging due to the changing environment heralded by auctions migrating to the Internet and the evolution propagated by harnessing computing power. Unique, previously unworkable, auction forms have been introduced that do not readily conform to classical theory therefore revitalizing this exciting area of study. CHAPTER 3 APPLICATION ENVIRONMENT AND MODEL 3.1 Network Television Practices Television advertising sales provides an interesting arena in which to investigate the use of the Incompletely Specified Combinatorial Auction (ISCA). Sissors and Bumba (1989) describe network television as a negotiated medium; similar to commodities bought and sold on the commodities exchange. There are three markets for television, "up-front "or long-term, "scatter" or short term and "opportunistic" or last minute buys (Katz, 1995). The majority of sales are conducted during "up-front" where contracts usually involve campaigns spanning an entire broadcast year. Scatter buys are generally for an upcoming quarter while the sale of excess last minute inventory is referred to as opportunistic buys (Sissors & Bumba, 1989). Advertisers seek to maximize the number of exposures to their desired demographic group per dollar or to minimize the cost per thousand viewers (CPM) while networks attempt to maximize the dollars received per show. Currently all sales are negotiated with no fixed price for placement in individual shows and evaluated on the CPM for a single designated demographic category. Media buyers must meet a predetermined amount of exposures to satisfy campaign goals. Supply and demand plays a significant role in negotiations for what can be considered a perishable good, since any 31 32 commercial time that is unsold at airtime can never be recovered. Advertiser demand for show placement, viewer demand indicated by audience delivery estimates, network overhead and expenses, and the proximity to airdate combine to form the basis for network reservation prices (Sissors & Bumba, 1989). Heterogeneity in campaign length and size, the advertised brand's buying power and estimated show ratings determine an advertiser's valuation for individual units and collectively entire campaigns. These valuations can vary greatly, as do their budgets. Auctions, due to their ability to facilitate price discovery and maximize seller surplus for items with widely dispersed values, are logical sales mechanisms for this environment. The combinatorial auction with its ability to accept package bids is best suited, among the current auction designs, to accommodate the synergies between products as well as the need to aggregate or bundle goods to meet buyer's campaign exposure requirements. In this environment there are also ample substitutes so buyers are not restricted to obtaining a specific item but may be satisfied with any number of substitutes available. The current versions of combinatorial auctions do not allow for substitutes or bids that do not precisely specify the desired objects. Our auction will be employed to accommodate the following "up-front" sales practices. Commercial sales are negotiated by daypart, i.e., specific time slots within the day such as primetime, daytime, kids and sports. We will concentrate on primetime where approximately 250 to 300 buyers compete for a finite amount commercial airtime in the upcoming season. Primetime extends from 8 p.m. to 1 1 p.m. with shows varying 33 Figure 3 . 1 Example of Pod Placement in an Hour Show in length from 30 minutes to 2 hours. An hour show generally contains 5 to 7 commercial pods and roughly 4 to 8 15-second slots per pod. See Figure 3.1. A pod is a collection of commercials normally lasting one to two minutes and includes a number of commercials of various lengths. The base unit in our auction will be the 1 5-second spot. All national television time is priced based on a 30-second spot. Advertisers wishing to utilize longer or shorter duration commercials (i.e., 15 second or 60 second) can expect the amount charged to be adjusted according to the length (Katz, 1995). Rarely, networks will charge a premium for handling of non-standard commercial lengths to discourage a large number of 1 5-second commercials that contribute to clutter. Clutter, generated by an overwhelming number of ads appearing in a show or pod, dilutes the strength of the advertiser's message (Sissors & Bumba, 1989). Our model assumes the price for a 15-second (60-second) commercial is one-half (twice) that of a 30. Campaigns can consist of either a single length commercial or a mix of lengths. For example, an advertiser may run strictly 15, 30, 45 or 60-second commercials, or any combination of these lengths in a single campaign. 34 Although it would appear most cost effective to purchase all 15-second commercials, since reach, or the number of viewers exposed to a commercial, is relatively the same regardless of commercial length, the 30-second commercial is most prevalent. It has been suggested that 30-second commercials better satisfy the creative needs of advertisers who are seeking to gain both consumer attention and convey the product message. To allow comparison between packages of various length commercials, advertisers use 30-second equivalents, where a 15-second commercial represents a half a unit, with 30-seconds being the base unit and a 60-second commercial is comparable to 2 units. We simplify our calculations by redefining the base unit as a 15-second commercial representing 1/2 the reported demographics and the longer commercials a multiple of this new base unit. This corresponds with our treatment of unit pricing. Although, as noted earlier, the amount of exposure is not effected by the length of commercial, in this scenario the demographics are scaled by the length of the commercial. The show's list price is then divided by the total number of exposures to determine the Cost Per Million (CPM). This equivalized CPM allows the buyer to analyze the best mixture of commercial lengths. 3.1.1 Environmental Constraints There are constraints imposed on the placement of ads. It is common practice to guarantee that competing products do not appear in the same pod, referred to as "pod protection." Two similar products can advertise in the same show but every effort is 35 made to ensure that they do not appear in the same commercial break. However, 15- second commercials are excluded from this protection. Media buyers often express preferences for placement in particular shows and occasionally sales are conditional on acquiring those specified shows. In addition, buyers may require that their advertisements not appear in selected shows due to what may be deemed inappropriate content. 15-second commercials require special handling. To avoid clutter, industry practice allows at most two 15's in the same pod. Duplicate ads, or more than one advertisement of any length from any one buyer, are not allowed to appear in the same pod. However, this restriction is relaxed for 15-second commercials. If, for example, an additional 15-second spot is required to complete a pod then a single advertiser's 15's may be "book-ended" or placed at the beginning and end of the same pod. Airdates are also a critical consideration. Although, advertisers may not have specific tastes for individual programs, they may require that an ad appear on certain dates to coincide with other media campaigns (i.e., radio, billboard, cable television, etc). Campaigns are scheduled as continuity (continuous over a length of time), bursts (ads placed at a specific frequency over an extended period such as twice a month all year), or flights where ads aired for specific periods are followed by periods of inactivity (Katz, 1995). 3.1.2 Negotiation Strategies Individual show pricing and commercial availability statistics are considered proprietary and jealously protected by both the network and advertisers. Although 36 television stations may publish "rate cards," the rates shown are viewed as the starting point for negotiations and do not reflect the ultimate prices (Merskin, 1999). Both parties exploit these information asymmetries during mediation. There is considerable negotiation back and forth in terms of what the media buyer is willing to pay for a particular offering or collection of show placements and what the network representatives feel is a fair and acceptable price. In this industry there is no after market where buyers can sell directly to other advertisers. Network representatives calculate their package prices based on a discount rate to the list price. This rate varies with supply and demand but has an explicit upper limit established by the daypart manager. A variety of facts are exchanged between parties in the negotiation. They usually include the buyer's stated budget (not necessarily his true budget), a minimum reach requirement for designated demographic, the length(s) of commercials for the campaign. Flighting information is also provided which often, but not always includes, a set of desired and/or forbidden shows or air-dates, the length of commercials allowed in each show and a maximum number of commercials per show. The seller also knows the type or brand of service/product advertised. Collectively, the information provided allows the network to generate a package that is presented to the media buyer for approval. The deal is evaluated based on a 30-second equivalized cost per million (CPM) for the demographic. Proposals are iteratively modified until the parties reach an agreement. Our auction model accepts multi-dimensional bids from all buyers and allows market forces to determine the allocation and prices that generate equilibrium. 37 3,2 Auction Description We propose a progressive semi-closed auction format that allows the media buyer to dynamically create individual bundles from a selection of commercial slots upon which they then bid. Our research will provide a new and innovative way of using an auction mechanism by allowing inexact bidding with multiple evaluative criteria as well as providing for constraints unique to the television sales environment. Bidders are given the flexibility to change and or modify their bids and bundles until a stopping criterion has been reached. Suggestions are provided to the buyers to help them formulate successive bids, but active pricing will not be disclosed. This semi-closed format, proposed by Tiech (1999), will satisfy the need for non-disclosure of market prices that is required by both buyer and seller. Additional constraints that will be modeled include separation of competing ads, meeting bidder's demographic group exposure requirements while ensuring the seller receives his reservation prices, accommodating specific show placement (non-placement) requests with commercial length specification while not exceeding an upper bound on the number of ads allowed per show. Our model assumes that campaigns are continuous throughout the season thus does not provide for flighting nor does it contain provisions for special programming that may displace regularly scheduled shows during the course of the year. We model our auction as an integer program. A summary of the notation is presented in Table 3.1. Our main decision variable is x u p s b , a binary variable set to 1 if a particular buyer b is allotted a unit u in podp for show s. 38 3.2.1 Notation Table 3.1 Summary of Notation General u,p,s,b,i DV Shows S Subscripts s=show, 6=buyer, /;=pods, w=pod part , /= allowable ad campaign length (using this order). Signifies a decision variable. Number of shows. P s Number of pods in show s. L s List price for each 1 5-second unit in show *. D s Vector of 1 5-second demographic values for show s. u P , Number of 1 5-second portions in pod p for show s. c, Maximum number of total units in show s available to sell. Buyers: B Number of buyers. T b Target Vector of desired demographic impressions for buyer b. K Vector of desired shows for buyer b (h sb = 1 if show s is desired by buyer b, otherwise) Note that h b can be a zero vector. *r+ Set of specified commercial length(s) in show s for buyer b. K, b Set of allowable commercial length(s) in show s for buyer b. H b ,H b Min/max number of desired shows that buyer b must have ( H_ b < h b < H b). z» Number of correct length commercials allowed in show s by buyer b. M b Type of merchandise advertised by buyer b. <*b>KILb , H b , I s b , N s b , M b , K s b bid from buyer b. a b is the amount bid. v b (d) value of buyer b's advertising given a cumulative demographic vector d. Seller: J p,s,b DV: 1 if bidder b has more than 15-seconds in pod/? in show s. y b DV: 0,1 variable. If 0, buyer b can't buy any pods p. X u,p.s, b DV: 0,1 variable. If 1, buyer b, has spot u in podp in show 5. p,s,b,i DV: 0,1 variable. If 1 pod p of show s for buyer b uses an allowable number of advertising slots. Z p.s.b DV: 0,1 variable. 1 if /V ajAi =1 otherwise 0. (notational simplicity) Js.b DV: 0,1 variable. If 1, buyer b has any unit in show s. r budget discount rate applied to the list price. 39 3.2.2 Objective Function This problem focuses on a fixed time horizon of some specified number of weeks, each week of which is a repeat of the pattern sold in the auction. The seller solves B PI: max £«„>>„ 4=1 The objective function maximizes the total revenue from accepted bids, a b . The variable y b is an indicator variable that is set to 1 if the bid is accepted subject to the following constraints. The objective in this case is to maximize revenue. This approach is selected, over maximizing profit because it achieves a stated goal of satisfying a predefined budget. Additionally, the product involved is considered perishable and therefore the seller is more concerned with depleting inventory than selling at the greatest profit. Should profit be the motivating factor our objective function can be restated as follows: (API) max ^a b y b - (1-r) £ £ £2X*. 6=1 6=1 ( fi u „.s \ I. \ V I=I \ p=l " =1 / J J With this formulation the seller reservation price is incorporated into the objective and therefore can be dropped from the constraints, i.e. Equation (1.1). 3.2.3 Constraints Rarely are sales predicated solely on price and availability. Incorporating the constraints of the environment may be more challenging than determining the highest 40 bids in the television industry. The following constraints are required to adequately represent the restrictions inherent in commercial airtime sales. 3.2.3.1 Reservation requirement The reservation requirement in the television industry is based on a discount rate, r that is applied to the list price for each show, L s . Daypart managers must meet an annual budget that is a proportion of the total possible revenue available based on the list price. The discount to list reflects this proportion, however, discount rates for individual sales may be above or below the discount as long as ultimately the aggregate meets or exceeds the budget. Therefore the sum of the accepted bids must be greater than the discounted commercials purchased where x s6 = 1 indicates that a commercial has been placed in podp of show s by buyer b. The following formula first determines the non- discounted revenue per show over all the shows and buyers and then applies the discount rate. The resulting discounted revenue requirement is compared with the total amount bid by all buyers to insure that the minimum reservation price is received. (i-D I^^mI if Ilk,,,, A=l s=l reservation requirement /; \p~\ u=\ J 3.2.3.2 Maximum seller coverage Although there is a finite amount of commercial airtime available, not all is targeted for sale during "up-front" sales. The maximum coverage constraint insures that at most a specific number of commercials are sold per show as noted by C s . ( 1 -2) L^ZjV*-^ s = l,...,S maximum coverage i=l p=l u =l 41 3.2.3.3 Maximum spot availability Each show is broken into pods, usually one- to two-minute blocks of airtime reserved for commercial placement. The number of pods per show and their length vary from show to show. The following guarantees that the number of commercial placements per pod does not exceed the number of spots available to accommodate them. The number of individual units in each pod summed over all buyers must be less than or equal to the total number available in that pod. (1.3) XZVi-^ p = l,...P s s = \,...,S max availability per pod 6=1 n=l 3.2.3.4 Buyer selection indicator If a particular bidder b does not obtain any airtime the following constraint forces all his x values to zero and thus drops her bid from consideration. s « Urn* ( s p, 5=1 p = \ U = \ PS V S = 1 P = l J y b b = l,...,B can't buy if not selected Equation (1 .4) can also be written as (Al-4) x upsb <y b u = l,...,U p , s P = \,..,P 5 s = \,...,S b = \,...,B This alternative formulation is an example of constraint disaggregation for binary variables and has been shown to provide for a stronger LP relaxation (Johnson, Nemhauser & Savelsbergh, 2000). The original formulation will cause B constraints to be included in the formulation, one for each bidder in the problem. The alternative expression enumerates each combination of bidder, show, pod and unit. Adding more constraints and thus growing the size of the problem seems counterintuitive to the goal of improving the LP relaxation. However, Johnson, et al. (2000, pg. 5) suggest that "to 42 obtain strong bounds, it may be necessary to have a formulation in which either the number of constraints or the number of variables (or possibly both) is exponential in the size of the natural description of the problem." 3.2.3.5 Campaign commercial length constraint Advertising campaigns may consist of commercials of varying lengths. A campaign composed of only 15, 30, 45 or 60-second spots must eliminate any collection of 15-second units in an individual pod that will not form the desired commercial length. Buyers may also have mixed campaigns, or campaigns that consist of a combination of lengths. N sb is a set of permissible commercial lengths for each show s supplied by buyer b. Note that the permissible collection of lengths can vary by show facilitating a buyer's need to change the length(s) of the campaign over time. Industry practice dictates that no more than one commercial per buyer appears in the same pod. An exception to this rule allows that at most two 15-second units from the same advertiser may be placed in the same pod to fill an empty 15-second slot and complete the pod. To account for this exception we define _ f^u{2}ifle^aiid2«5^ *«*- N $b otherwise Together Equations (1.5 a) and (1.5b) require the selected units in each pod to correspond to one of the allowable lengths listed in N sb . The unit slots are numbered for convenience but the number does not correspond to a specific location in a pod, therefore there is no need to insure that the units are consecutive when forming a 30, 45 or 60- second commercial. 43 (1.5a) 2X#**"X&*w P = U^ = U^ = U5 campaign length U=l I€/V, ft Equation (1.5b) prevents more than one correct length commercial for buyer b from appearing in pod/? of show s. Note, two 15-second commercials are allowed in one pod if le N sb . Note that z psb is equivalent to /./, jAJ indicating if set to 1 that buyer b ieN, has a correct length commercial in pod/? of show s. z psb is used within our formulation to simplify the notation but will not appear as a variable in the implementation of our problem. (1.5b)z pji <l p-\,...,P s s -\,...,S b = l,...,B commercials per pod 3.2.3.6 Anti-Clutter Control Placing a large number of different commercials in the same pod weakens the impact of all commercial messages within that pod. This phenomenon results from the "clutter" exacerbated by the use of 15-second commercials. To reduce clutter, Equation (1.6) allows at most two 15-second ads to appear in each pod. B 0-6) £/,,oj ^2 p = \,...,P s s = l,...,S anti-clutter b=\ 3.2.3.7 Frequency: Max commercials per show Controlling the number of commercials appearing in each show will provide the buyer with the ability to spread or aggregate commercials over the length of a campaign week. K sb indicates the number of correct length commercials that are allowed in show s by buyer b. Should a buyer want to place all of her inventory early in the week she would set K sb high for shows during the desired days and other days to zero. A buyer can 44 identify a forbidden show, say show s' , by setting K s , b - . Should a buyer forbid a show, during implementation of the model, the corresponding variables will not be generated. Normally, buyers want their ads to appear only once per show to enhance the number of different viewers that are exposed to their spot, in this case all K s b 's would be set to 1 . Equation (1.7) provides for this constraint. S (1.7) ^ z P ,s,b-^s,b s = l,...,S b = \,...,B maximum spots per show P =\ 3.2.3.8 Demographic gross impression guarantee Media buyers desire a specific amount of demographic reach, or number of people exposed to their commercial during their campaign. There are a variety of demographic categories upon which a show is rated. Each show's gross impressions per category forms the demographic vector D s and indicates the seller's estimated reach for that particular show in the upcoming season. D s is ordered by the categories: Women 18 to 49, Women 25-54, Men 18-49, Men 25-54, Adults 18-49 and Adults 25-54. T b represents the vector of demographic reach or gross impressions that the buyer needs to meet the product's campaign goals and is ordered with the same categories in D s . Note that although total number of gross impressions per show, D s , in reality does not change with the length of the commercial our model uses equivalized 30-second calculations that differentiate based on the length of commercial. For example, the number of gross impressions for a 15-second spot is 1 unit of demographics while the unit gross impressions for a 30, 45 or 60-second commercial is 2, 3 and 4 respectively. Bidders normally evaluate their package on a single demographic category. The sum of the total 45 number of 15 second units, times the specified demographic gross impressions over all selected shows must meet or exceed the required reach for the specified demographic group(s). Equation (1.8) assures that the minimum demographic requirement is achieved. f p. u„. \ J=l \p=l u=\ ) D s > T b y b b = \,...,B demographic reach required 3.2.3.9 Show placement requirement In addition to the actual dollar amount bid and demographic requirements, a buyer may specify desired shows within which they would like their commercials placed. Setting h sb to 1 indicates that buyer b wants placement in show s. She can further indicate her willingness to deviate from her program choice by setting the upper H b and lower H_ b bounds to the number of shows required. j s b identifies which shows a buyer has been allocated and is determined with the following formulas. j sb 's is set equal to 1 if buyer b has any slot in show s and otherwise. 0- 9a ) £**.>* A* s = \,...,S b = l,...,B Show allocation 0- 9b ) L 2 „** P ,U s = l-,S b = l,...,B p=\ Equation (1.10) ensures that a buyer is allotted at least H_ b shows and no more than//,, of the shows requested. To satisfy this constraint at least H_ b j sb 's will have to be set to 1 and no more than H b . s (1.10) //* > JX^ > // 6 >•„ b = \,...,B desiredshows 46 3.2.3.10 Pod protection constraints Networks routinely guarantee that competing advertisements do not appear in the same pod. The group of equations (1.11 a-d) implements this notion of "pod protection." Pod protection is normally not given to 15 -second commercials, therefore we need only investigate anti-competition when a buyer has two or more units in a particular pod. The decision variable f psb is set to 1 if a bidder b has two or more 15-second units in a particular pod/? of show s. When the number of units a bidder has per show is there is no competition and Equation (1.11a) forces both / , b and z p s b to zero. (Mltf2**«*««#+/*M J»-W>. s = \,...,S b = \,...,B, u = l In the case where one unit is assigned in a particular show to buyer b, pod protection is not enforced and the requirement that z psJ> equal or exceed f psb in Equation (1.11b) sets f b to zero, and z psb to at most one. This corresponds with the fact that buyer b has a single unit in any pod of show s. (l.Ub)f psb <z psl , p = \,...,P s s = \,...,S b = l,...,B, Equation (1.11c) will force z b to one in this case. Pod protection only becomes an issue when two or more units are assigned within the same pod of a show to a single bidder thereby generating a potential 30-second or longer commercial. Equations (1.1 la-c) will force z psb to one and f psb to one when two or more spots are bought by buyer b in show s, pod p. (t.iic)^ iW ;iz^+ £t/,.,-i u=\ \p=\ f pjtjk p = l,...,P s s = \,...,S b = l,...,B, 47 Finally, Equation (1.1 Id) will keep competitors away from a protected pod in show s for buyer b. (\.\\d)f psi +z psj <\ i<j,j = 2,...,B VM t =Mj, p = l,...,P 5 s = \,...,S . An example will help clarify this fairly complicated methodology. Suppose we have two buyers i andj who are being considered for placement in podp of show 5. Further suppose that buyer i wants a 30-second spot in the pod and buyer j wants a 1 5 -second commercial in the same pod. Therefore the > jc, ... =2 and Yjc .=1. Table 3.2 «=1 u=\ lists the possible values of the z and/variables in equations 1.11a through 1.11c. If buyer Table 3.2 Variable Value Allocations for Pod Protection ^Variable Equations 30-second or > Commercial 15-Second Commercial No Commercial f . p,s,i f . J p.s.j p.s.j f . p,sj 1.11a Oorl Oorl Oorl Oorl 1.11b 1 Oorl 1 1 1.11c 1 1 1 i has a 30-second or greater commercial in a pod both f psj and z p s ( are set to 1 through the series of equations. Buyery, with a 15-second commercial in the same pod, has only his z psJ set to 1 . Equation 1 . 1 Id uses the fact that only 30-second or greater commercials have both f psb = 1 and z psb - 1 , while 15-second commercials have only z P .s.b = 1 t0 prevent both from being placed in the same pod. If a buyer does not have a commercial in a pod both variables are set to zero. In our example 48 \fpsi = v + \ z p,sj ■ J/> 1 is a contradiction to what is allowed by Equation 1 . 1 Id. Therefore, since Equation 1.1 Id is only applicable when the products advertised are the same between two buyers, buyers i andy could not appear in the same pod if they were selling like products. 3.2.3.11 Bid specification and ordering The action starts with buyers placing bids [a b ,h b ,H_ b ,Hb, I psb ,N sb ,M b , K sb ). If a buyer submits more than one bid, the most recent one is used. If more than one bid is for the same amount, priority is given to the earlier bid through a lexicographic ordering imposed by altering bids with a timestamp, t b , as M where t is the current time and M is sufficiently large. 3.2.3.12 Bidder reservation price The auctioneer solves PI and presents the solution to the buyers. An infeasible solution may also be announced in which case, nothing is accepted by the seller. A rational buyer will only accept a feasible solution if v /> y P =\ K-i J J *a b , where a b < Bidder's Budget. If everyone accepts the solution, the auction is over. Otherwise, new bids can be submitted. When there is only one show and one pod with only one pod part, this reduces to a normal first price English auction. 49 3.3 Summary This chapter defines the network television advertising sales environment. The description includes the product characteristics, environmental constraints imposed on the allocation of goods and current negotiation strategies. A detailed integer program was developed to incorporate industry practices into a semi-sealed progressive combinatorial auction designed to replace the current negotiated environment. The problem objective is to maximize seller revenue while satisfying all constraints imposed by both the buyers and the seller. Buyer constraints and requirements are conveyed via a multi-criteria incompletely specified package bid. To accommodate industry practices the auction problem becomes quite complex. A few of the many constraints incorporated in the model include those designed to separate competing commercials, retain a portion of inventory for later markets and achieve specified demographic exposures in a particular demographic category while satisfying individual show placement requests. The complexity and combinatorial nature of the auction suggests the need for a heuristic solution method, which is explored is subsequent chapters. CHAPTER 4 CONSTRAINT PROGRAMMING 4. 1 Introduction Constraint Satisfaction Problems (CSP) involve finding values for all problem variables that simultaneously satisfy all problem specific constraints. Constraints can be viewed as a relationship between variables that restrict their possible instantiations. The paradigm has been studied since the 1960's and 1970's when the artificial intelligence community applied it to picture processing (Montanari 1970; Waltz 1975). The ability to achieve solutions to these complex problems rests on the notion of eliminating impossible alternatives from consideration as early in the allocation as possible. Early elimination reduces domains from which values are chosen and thus facilitates expeditious results. Recently a great deal of attention has focused on Constraint Programming (CP) due to its ability to solve combinatorial problems such as the one described in this research. Constraint Programming takes the solutions to a standard CSP and applies them to an objective function which is successfully tightened to find an optimal solution (Bartak, 1999). Constraint Programming has various advantages over other methodologies. Of major importance is the time it takes to achieve a solution. CP algorithms can often achieve solutions more quickly than can integer programming methods. Additionally, CP representation corresponds more closely with the entities of 50 51 the original problem. Thus making formulations simpler to compose, heuristics more readily developed and the solutions less difficult to interpret (Bartak, 1999). By using constraint programming as a basis for our heuristic we hope to capitalize on these advantages. This chapter begins with a brief introduction to constraint satisfaction problems. Section 4.2 defines the constraint satisfaction problem and methodology. Various CSP solution techniques are described in sections 4.3 through 4.6. Section 4.7 introduces Constraint Programming. The remaining section explores how these methodologies apply to the auction problem presented in this research. 4.2 Constraint Satisfaction Problems The auction problem developed in Section 3.2 is a combinatorial auction and thus achieving an optimal solution has been shown to be an NP-Complete problem (Rothkopf et al., 1998). As such, a heuristic is required to allow a satisficing solution to be reached in real time. Combinatorial problems are found in areas such as planning, scheduling, generalized assignment and resource allocation and have been effectively formulated as constraint satisfaction problems (CSP) (Nonobe & Ibaraki, 1997). Constraint Satisfaction is a general term describing a class of problems involving a set of variables that are to be instantiated from an associated domain while satisfying a set of constraints that limit the assignment (Mackworth, 1992). CSPs use a variety of search methodologies to find a feasible solution. The goal of a constraint satisfaction problem (CSP) is the assignment of values to its variables that will satisfy all constraints. More formally, the finite CSP is defined by 52 its three components. V: a finite set of variables {X x , X 2 ,..., X n } , D: the set of corresponding domains JD, ,D 2 ,...,D n } where D\ is the finite domain of Xj, and C is a finite set of constraints or relations {C,,C 2 ,...,C r } restricting the assignment of values to variables. A constraint C ijk between the variables X i ,X j ,X k ... is any subset of the possible combinations of values ofXj,Xj,X k .... For example the cross product C Ljk C A x Dj xD k x... indicates the possible combinations of values that the constraint allows (Brailsford, Potts, & Smith, 1998). If there exists an assignment of a value from a variable's domain for all variables that satisfy every constraint then there is a feasible solution to the problem, otherwise it is said to be unsatisfiable. Solving the CSP can be accomplished by either constructing a solution by iterative variable assignments leading to a feasible solution or by starting with an initial solution (but not necessarily feasible) and subsequently modifying or repairing the solution until it becomes feasible. Known as the systematic search or "constructive" approach, the former methodology applies backtracking techniques and is usually designed to solve a given problem instance exactly. While the stochastic search or "repair" approach gradually repairs an initial solution in order to reduce the infeasibility until all constraints are satisfied. Several greedy algorithms, such as tabu, genetic algorithms or neural networks have been shown to be effective in generating initial solutions. The repair approach has been found to be particularly effective for large-scale problems (Nonobe & Ibaraki, 1 997). 53 4.3 Arc Consistency In a binary CSP, constraints involve only two variables and are visually depicted by a constraint graph (Figure 4.1). The nodes of the graph represent the variables and the XxXj-2 Constraint D,={1 5} D : ={1 5} (a) Original Domains X,<X r 2 Dj={1 5} (b) Domains with (X f X} arc-consistent X,<X f 2 Dr{4.5} (c) Domains with QCpXi and (X f X) arc-consistent Figure 4.1 Constraint Graph (Brailsford et al., 1999) lines or arcs connecting the nodes represent the constraints between them. Arc- consistency is achieved by reducing the domains of the problem variables until the remaining values are all supported; a value is supported if every constraint on the variable includes a tuple in which the variable takes this value and all other variables take supported values. For example if a constraint C,, exists between variables X i and X the arc (x^Xj) is arc consistent if for every value a in the domain D i of variable X t there is a value b in the domain D f of variable X . that satisfies the constraint C, ■ (see Figure 4.1b & c). In Figure lb, (X,,Xj) is arc-consistent but (Xj.Xj ) is not, while in 54 Figure 4.1c the variables are fully arc-consistent, b e D } is called a supporting value for ae D t . Any values of a that do not satisfy the constraint, i.e. have no supporting value, are removed from the domain D, and in so doing makes the arc (Xj , X ; ) arc-consistent (Brailsford et al., 1999). However, the simple fact that none of the arc-consistent domains are empty does not imply that the CSP has a solution. A solution is achieved only if all variables can be assigned a specific value such that they all support each other. There are several arc-consistency algorithms employed to establish consistent domains. The importance of the algorithms rests in their ability to reduce the size of the problem and save computational processing time. Arc-consistency has been widely used as a preprocessing step to eliminate local inconsistencies before any attempt is made to construct a solution. Several algorithms have been developed that capitalize on the knowledge about constraint properties to reduce the cost of consistency checking, see Chen (1999) for an overview. CSPs are frequently a subpart of a larger application. In these cases it is often important to compute all possible solutions which can be systematically explored to find the best configuration for a given situation. Optimization problems can assume this approach, thus delaying optimization criterion development until a set of solutions has been discovered. This technique is tractable when the possible value assignments are discrete but faces challenges with continuous values since continuous domains admit an infinite set of values. To overcome the complexity of continuous value representation in a binary constraint environment Sam-Haroud & Faltings (1996) suggest descretizing variable ranges into one or a small collection of intervals that roughly approximate a 55 constraint by an enclosing box whose borders represent the unary outer projections of the variables involved. In this case values falling within the confines of this box are considered arc-consistent. 4.4 Systematic Search Algorithms Systematic search algorithms involve attempting to achieve a consistent solution by repeatedly extending partial solutions. The most basic algorithm called Generate and Test (GT) randomly selects a variable to instantiate and then checks that the labeling is consistent. It is inefficient in that the random selection of variables does not capitalize on problem specific information and thus must perform an exhaustive search. Backtracking improves on this technique and is best described as a depth-first instantiation technique. Another alternative involves enforcing arc-consistency, an elimination approach ruling out all solutions containing local inconsistencies (Mackworth, 1992). A branch and bound type search tree is typically used to graphically represent the current state of the search. A node represents a partial solution and the branches different values that could be assigned to some variable. Past variables are those that have already been assigned a value, while a. future variable has not yet been assigned a value. Choosing a branch of the tree to explore instantiates the variable with the value associated with the chosen branch. Should the domain of a future variable become empty the problem has reached a dead-end or has become annihilated. Note that mathematical programmers would use different terminology to describe the elements of the problem. For example, they would say, "fathomed" instead of "dead-end." 56 4.4. 1 Look Back Algorithms The most common algorithm for performing systematic search is backtracking; an approach that after variable instantiation "looks back" to ensure the assignment is consistent with previously instantiated variables. Backtracking incrementally attempts to reach a complete solution from an intermediate partial solution by repeatedly assigning values consistent with the partial solution. If a consistent value cannot be found the algorithm backs up to a point where successful choices can be made. The method that is used to choose which previous variable to return to in the event of inconsistencies defines the various backtracking algorithms. 4.4.1.1 Chronological Backtracking (BT) Chronological Backtracking (Bitner & Reingold, 1975) is the generic backtracking algorithm. At every stage of backtracking search, there is some current partial solution that the algorithm attempts to extent to a full solution. The process begins with the current variable being assigned a value from its domain. Then consistency is checked between this instantiation and the instantiations of the current partial solution. If any constraint between this variable and the past variables is violated the assignment is abandoned and the next domain value of the current variable is tried. If there are no more domain values left, BT backtracks to the most recently instantiated past variable, assigns it a new value and the process repeats. If all checks succeed, the branch is extended by instantiating the next variable to each of the values in its domain. If a value has been assigned to every variable a complete solution has been found otherwise the problem is infeasible (Mackworth, 1992). 57 4.4.1.2 Backjumping (BJ) Backjumping (Gaschnig, 1977) is similar to, but more intelligent than, Chronological Backtracking. BJ identifies the latest instantiated variable causing a constraint failure and proceeds directly to that variable when it reaches a dead-end. Instead of chronologically backtracking to the preceding variable, B J jumps back to the X< 2 - 5 > Chronological Backtrack {2,5,3,1} {2,5,3} {2,5,3,1,4}, {2,5,3,6} s 1 1 3 2 2 Q 1 1 1 1 1 3 1 Q 2 3 3 4 1 3 5 Q 2 1 2 2 6 2 1 3 2 3 4 5 6 n Backjump: \ Skips *^ circled / nodes / / / Figure 4.2 Partial Backtrack Tree (Kondrack & van Beek, 1997) deepest past variable that was checked against the current variable. For example, Figure 4.2 represents a partial backtracking tree from an n-queens problem described by Kondrak and van Beek (1997) that shows how the backjump technique skips the circled nodes. (N-queens is a classic problem used in artificial intelligence to demonstrate difficult problems. The goal is to assign chess queens positions the on an n by n game board such that no queen can capture another.) BJ reduces the number of consistency 58 checks by skipping search tree nodes thus it behaves more efficiently when all instantiations are inconsistent for the current variable. Changing the value assignment of the failure causing past variable may allow a consistent instantiation to be found for the current variable. Backtracking to any of the intervening variables will have not effect since they have not impact on the reason for the failure. 4.4.1.3 Conflict-Directed Backjumping (CBJ) By tracking previous failures, Conflict-Directed Backjumping (Prosser, 1993) demonstrates more sophisticated backjumping behavior than BJ. Every variable has its own conflict set that lists the past variables that have failed consistency checks with this current instantiation. Every time a consistency check between the instantiation of the current variable and an instantiation of some past variable fails, the past variable is added to the conflict set of current variable. When all possible values for the current variable have been exhausted, CBJ backjumps to the deepest past variable in its conflict set, this variable becomes the current variable and a new value assignment is attempted. Note that the variables in the conflict set of the variable that could not be instantiated are propagated up the tree and added the conflict set of the past variable so that no conflict information is lost. Figure 4.3 depicts a conflict set that would be formed for this example. 4.4.2 Look Ahead Algorithms A disadvantage of "Look Back" algorithms is late discovery of conflicts. The "Look Ahead" approach attempts to overcome this problem by looking at future variable assignments and eliminating impossible values from consideration earlier in the process. 59 Figure 4.3 Partial Backtrack Tree with CBJ Conflict Set 4.4.2.1 Forward Checking (FC) Forward Checking (Haralick & Elliot, 1980; McGregor, 1979) performs consistency checks from the current instantiation to future variables. The algorithm assigns a value to current variable from its domain then propagates the effect of that assignment to future variables by removing inconsistent values from their domains. Only when the future domain is annihilated (becomes empty), indicating that the current assignment has lead to a dead-end, are backtracking techniques employed. If a dead-end is reached the domains of the future variables are returned to their original state, and the next value is tried. If all values have been exhausted for the current variable domain, FC backtracks chronologically to the most recent successfully instantiated variable. This process continues until a complete solution is found or until all possible assignments have lead to a dead-end, in which case the problem has no solution. Forward Checking, in 60 contrast with backward checking algorithms, visits only consistent nodes, although not necessarily all of them. 4.4.2.2 Maintaining Arc-Consistency (MAC) Similar to Forward Checking, Maintaining Arc-Consistency (Sabin & Freuder, 1994) focuses on checking future variables for arc-consistency. However, MAC not only checks the consistency of all potential future variables and deletes any values that are not supported by the current variable, it also checks for consistency between the newly identified future variables and their values. This type of incremental arc-consistency algorithm for re-establishing arc-consistency after each assignment reduces the size of the overall problem and thus has been shown to be efficient (Van Hentenryck, Deville and Teng, 1992). 4.4.3 Hybrid Backtracking/Forward Checking Algorithms Various combinations of the previously described basic algorithms have been proposed to combine their advantages. For example Forward Checking and Conflict Directed Backjumping (FC-CBJ) tracks information about inconsistent variables and subsequently uses this information to determine the backtracking point. This algorithm has the advantage of establishing a conflict set to more efficiently direct the backward movement of the Forward Checking algorithm when it encounters a dead-end. Another extension, Backmarking (BM) improves the efficiency of the backtracking algorithms by adding a marking scheme (Gaschnig, 1977). Without the marking scheme consistency checks are performed to determine if the current instantiation of variables satisfies the constraint between the variables without regard to any historical checks that may have 61 already determined the consistency between these same two variables. The BM marking scheme reduces the number of consistency checks by employing the notion that if at the most recent node where a given instantiation was checked, the instantiation failed against some past instantiation that has not yet changed, then it will fail again. Therefore, all consistency checks involving it need not be investigated. It can also be assumed that a successful instantiation of some past instantiation that has not yet changed will succeed again. By marking the instantiations that have already been tested we avoid redundant consistency checks. The implication is that we need only check past instantiations that have changed or are "unmarked." Imposing a marking scheme on an algorithm does not change the nodes visited and therefore can extend any of the basic algorithms. Kondrak and van Beek (1997) evaluated the efficiency of several backtracking algorithms with respect to the number of nodes visited and the number of consistency checks performed. They found that the hybrid backtracking algorithms such as Forward Checking and Conflict-Directed Backjumping, Backmarking with Backjumping and Backmarking with Conflict-Directed Backjumping tend to outperform the original algorithms. In fact, FC-CBJ has been shown to be among the best for solving hard problems (Kondrak & van Beek, 1997; Smith & Grant, 1995). 4.4.4 Improving Performance The order in which variables are chosen for instantiation can play a significant roll in the performance of the algorithm. Variable ordering can be either static or dynamic. With a static variable ordering the order of the variables must be established prior to the constraint network being passed to the backtracking algorithm. A static order is in 62 contrast to a dynamic order of instantiation in which the decision of which variable to instantiate next is based on the current state of the search. Large portions of the search space can be pruned by employing the "fail-first principle" which chooses the most constrained variable first thereby forcing failures higher in the backtrack search tree (Van Hentenryck & Saraswat, 1996). A dynamic ordering algorithm that chooses the variable with the minimum remaining values (MRV) in its domain has been developed for use with both backtracking (Sabin & Frueder, 1994) and forward checking (Bacchua & van Ran, 1995) algorithms and has been shown to perform well on specific problems. The order in which the values are chosen will likewise determine how quickly the algorithm achieves a solution by allowing the most promising value to be assigned first. What constitutes "promising" is problem specific, for example if you are attempting to maximize profits, ordering the values for largest to smallest may achieve the best results. 4.5 Arc-Consistency Algorithms Arc-Consistency algorithms complement, rather than substitute for, backtracking algorithms. Arc-consistency algorithms remove inconsistencies from the network generated by an instantiation that can never be part of a global solution. Removal of inconsistencies reduces thrashing (Mackworth, 1977). Mackworth (1992, p287) describes thrashing "as the repeated exploration of subtrees of the backtrack search tree that differ only in inessential features such as the assignment of variables irrelevant to the future of the subtree." By analyzing the various basis of thrashing behavior in backtracking, arc-consistency algorithms can eliminate the source. 63 Instantiating a variable impacts the domains of all prior variables and consistency algorithms must determine if the instantiation has violated any constraints or caused prior instantiations to be in violation. The most widely used consistency algorithms are AC-3 and AC-4. Unlike the previous algorithms that evaluated every arc, AC-3 rechecks consistency of only those arcs that could have been affected by current instantiation. AC- 4 uses the same approach but maintains a special data structure that prevents repeated reexamination of pairs of values (Mackworth 1977). Other algorithms exploit problem specific knowledge. For example AC-7 (Bessiere, Frueder & Regin, 1999) takes advantage of the bi-directional property of binary constraints to remove redundant checks. This algorithm works on the simple notion that a value a at node I (I,a) supports a value b at node J (J,b) if and only if (J,b) supports (I,a). Constraint bi-directionality properties allow the algorithm to perform fewer consistency checks and thus improve computational efficiency. Specifically, AC-7 can avoid checking if (J,b) supports (I,a) since it knows that the inverse, (I,a) supports (J,b), is true. Another arc-consistency algorithm, AC-8 (Chen, 1999) breaks the problem into smaller sub-problems then solves them sequentially. 4.6 Stochastic Search Algorithms Stochastic search algorithms begin with a solution that may or may not be feasible and repairs it using a variety of techniques to achieve feasibility. This class of algorithms will normally achieve a feasible solution more rapidly than their systematic counterpart. The quality of the solution is predicated on the initial solution and the technique used for repairs. Stochastic algorithms have been proposed that use hill-climbing (Minton, 64 Johnston, Phillips & Laird, 1992), neural networks (Popescu, 1997; Kurgollus & Sankur, 1999), and genetic algorithms. Kanoh, Matsumote, Hasegawa, Kato & Nishihara (1997) suggest that genetic algorithms (GAs), due to their global search characteristics, provide effective solutions to CSPs that have many local optima. In fact, GAs have been used to effectively seed CSPs designed to solve ship maintenance scheduling (Deris, Omatu, Ohta, Kutar & Samat, 1 997) and timetable planning problems (Deris, Omatu, Ohta, & Saad, 1999). Combining the two methods takes advantage of the strength of both constraint satisfaction methodologies and GA techniques. The genetic algorithm plays its role as a tool to generate promising solutions while constraint-based reasoning processes the constraints to ensure that the solutions are legal and valid. Kanoh et al. (1997) further modify the mutation process of the standard GA by substituting "viral infection" for standard mutation. A virus is defined as a partial solution to the CSP and is generated by the GA along with other candidate solutions. Crossover and infection then generate new candidate solutions. Infection gives direction to the evolution by substituting the genes of the virus for those of the individual generating a new candidate solution based on partial solutions proven to be consistent. 4.7 Constraint Programming Constraint Programming finds variable instantiations that simultaneously satisfy all specified constraints while optimizing a stated objective. One strategy used for Constraint Programming is to model the problem as a CSP. After a feasible solution to the CSP has been found an additional constraint is added to represent the objective function. The new constraint requires that the objective strictly improve over the 65 objective value of the current CSP solution. This process is repeated until no feasible solution can be found. The last solution obtained prior to the problem becoming unsatisfiable is an optimal solution (Nonobe & Ibaraki, 1998; Potts & Smith, 1999). 4.8 Advertising Sales Application Defining the television commercial time allocation problem as a constraint programming problem involves specifying the variables, domains and constraints as well as the ordering of variable instantiations and value assignments. Variables in the problem represent the airtime assignment to each bidder and the values assigned form a tuple indicating the shows that have been allocated. The allocation is subject to the following constraints: • Maximize Seller Revenue: The overall objective function that must increase at each iteration. • Reservation requirement: The aggregate sum of the all accepted bids must be greater than the sum of the discounted list prices for the commercials purchased. • Maximum seller coverage: A seller specified maximum number of commercial slots must be sold in each show. • Maximum spot availability: The number of commercial placements per pod cannot exceed the number of spots available to accommodate them. Assignments must be within the range of the domain. • Buyer selection indicator: A buyer cannot be assigned units if his bid has been rejected. • Campaign commercial length: The number of units assigned to a buyer in each show must be a multiple of 15 that corresponds with the campaign length. For example a buyer with a 30-second campaign must has either zero units in a show or a multiple of two. • Anti-Clutter Restraints: No more than two 15-second commercials can appear in the same pod. • Maximum Commercials per Show: The number of correct length commercials in each show must not exceed the bidder specified maximum. This could be as small as zero which effectively eliminates that show from consideration. 66 • Demographic gross impression guarantee: The demographic gross impressions summed over all selected shows and equivalized by commercial length must meet or exceed the required reach for the specified demographic group for each bidder. • Show placement minimum: Winning bidders should be placed in the shows they requested. The minimum number of requested show assignments should correspond with the lower bound specified by the bidder. • Show placement maximum: Winning bidders should not be placed in an identified show more than the maximum number of times indicated by the upper bound specified by the bidder • Pod protection: No two buyers advertising the same category product can be placed in the same pod if at least one has a 30-second commercial. • Bid amount not exceeded: The sum of the discounted list prices for the allocation of units to each bidder must be less than or equal to their amount bid. The constraint programming methodologies will be employed to determine variable instantiation and manage the large domains of the problem. Variable instantiation ordering involves sorting the bidders by some criteria of interest. Both variable instantiation and value ordering will be discussed in detail in subsequent chapters. 4.9 Summary This chapter presented an overview of constraint satisfaction problems and constraint programming. The former involves finding a set of values that simultaneously satisfies all constraints while the later extends the feasible solution to the CSP by including an objective function that is iteratively tightened to find an optimal solution. We looked a various algorithms designed to discover satisfying allocations. Arc consistency techniques, algorithms employed to control the consistency of domains were reviewed. They are important to our research as they provide an efficient means of managing the large domains of our problem. Finally, we introduced our auction mechanism in constraint programming language. CHAPTER 5 HUERISTIC DEVELOPMENT 5.1 Introduction A direct attack on solving problem PI is probably doomed. For example, in a representative problem with 325 bidders competing for 587 units in 109 pods across 24 shows PI generates approximately 278,000 binary variables and 587,000 constraints. A heuristic is clearly needed. The heuristic used to solve our combinatorial auction in real time is developed in this chapter. The overall approach is outlined in Section 5.1 . It incorporates a mixture of problem aggregation with linear, constraint and dynamic programming methods. Once we give the overall approach, we focus on the particulars. Many of the decisions necessary to discover an optimal allocation of goods can be determined at an aggregate, or show level rather than at the unit or pod level. Working with the aggregate problem dramatically reduces the size of the problem. Descriptions of the aggregate sub-problems are presented in section 5.2. The results of these sub- problems are incorporated into the master problem in section 5.4. The aggregate problems use constraint programming methods as an efficient way to collapse the size of the original search space. Section 5.3 defines the constraint programming aspect of the heuristic that will manage the domains from which the allocations are chosen. Constraint programming employs simple computer programming logic to replace complicated 67 68 equations thus provides a more efficient method of ensuring that constraints are enforced. Finally, branch and bound methodology is used to search for an optimal allocation, search guiding heuristics and fathoming criteria are presented in section 5.5. 5.2 Overview The solution methodology employed to allocate units in our Incompletely Specified Combinatorial Auction is fairly complicated incorporating several techniques. Figure 5.1 presents an overview of the procedures. The auction begins with the collection of bids. Each bid is subjected to an initial feasibility check to ensure that it meets minimum requirements for entry. This is accomplished by solving an aggregate problem defined below. Once all bids have been tendered, an initial feasible solution is generated with the use of heuristics that will be defined in detail in section 5.4. An upper-bound is established using a linear relaxation of a second type of aggregate integer program. This bound is used to judge the quality of our solutions. The best solution to date is then used to start a branch and bound search. At the end of each auction round, the selected stopping criterion is checked. If stopping conditions are not met, bidders are informed of the results. Loosing bidders will have the opportunity to change their bids commensurate with their behavior profile. When all stopping conditions have been met, the current bid amounts are replaced with bidder reservation prices (but otherwise unaltered) and are used to compute a solution to be used for the efficiency calculation. 69 C Start ") ■* For All Agents < No Suggest Bid Modification Adjust Bids Get Bid Check feasibility by solving Sub-Problems All Bids Processed? ± Generate Initial Feasible Solutions Heuristics A and B Solve LP-Upperbound T BFS Scan 30% of Remaining Time DFS Scan 70% of Remaining Time No Get Next Bid Figure 5. 1 Auction Overview Auction Flowchart 70 5.3 Aggregate Sub-Problems The majority of constraints involved in the auction problem can be determined by examining the allocations of each show rather than a pod or unit level allocation. The overall driving heuristic is a greedy allocation of show slots to bidders. Each bid is considered sequentially, conditional on the tentative allocations made to other bidders. By aggregating to the show level we reduce the size of the problem and thus enhance our ability to achieve a solution. Let 8(x) be the normal Kronecker delta, i.e., Also, let x sb be the number of allowable units that bidder b may purchase in show s and X s b be the current domain of x s b . The domain of x s b will change as other variables associated with earlier accepted bids are instantiated either because units become unavailable or some constraint such as pod protection or maximum spots per show would be violated. As we show in Section 5.4, X s b incorporates all the constraints given in Equations (1.2)-(1.1 Id) except for demographic reach and the desired shows constraints. These latter two are handled directly in the following aggregate problem. We define the aggregated problem, (AP b ) for each bidder as (AP b ) ° b s = (i- r) min s Y. L * x s.b 5=1 DAi ^T b K b s *2 *A*.j> )*H> 71 When there are no current other assignments, the objective value is labeled a b which gives the minimum discounted show costs needed to satisfy all problem constraints (1.2) - (1.1 Id). When there are current assignments meeting (1.2) - (1.1 Id), then (AP b ) provides an assignment for this bid (if it has a feasible solution) that, together with the current assignments, meet all constraints (1.2) - (1.1 Id). By minimizing the discounted costs, we hope to also, in total, satisfy the one remaining constraint, constraint (1.1), the seller reservation price constraint. If there is no feasible solution, then set the x u psb variables to zero. Otherwise, a solution to (AP b ) can be expanded to yield x upsb values by recovering a combination yielding the correct entry in X sb . There may be many such combinations. No currently protected pod will be violated by these x u psJ) . If (AP b ) has a feasible solution, then we set y b = 1 . If not, we set y b = . The resulting y vector indicates the eligible participants for this round. The remaining decision variables in the original problem (PI) can be recovered by analysis of the expanded solution x u s b 's. A simple count of the ultimate allocation of x's for each bidder b in each show s and pod/? will determine the value to assign f psb . If the sum of the x's is greater than 1 in a pod then that bidder has more than a 15-second commercial in that pod and / , b is set to 1. This same number when compared to the set of allowable commercial lengths, N s b , yields the values to assign the I psbi variable. If a commercial of length i appears in the final allocation in a particular pod/? of show 5 for this buyer I psbi is assigned a value of 1 otherwise it is set 72 to 0. This same counting technique aggregated to the show level will identify the appropriate j s b 's to set tol indicating that buyer b has a presence in show s. The aggregate problem (AP b ) is solved using dynamic programming. Notice that, with the exception of the last constraint, this is a straightforward Knapsack program. The final constraint can make this a non-linear problem (because of the Kronecker operation) if either or both H_ b and Hb are greater than zero and the h's have values necessitating the consideration of these constraints. We utilize one of several dynamic programming routines designed to solve the sub-problem, the choice of which depends on the values of H_ b and Hb and the nature of the h 's that have been selected. The dynamic programs provide exact optimal solutions to (AP b ). However, these can take some time to solve since the Tfr values may be large. At various points, to be discussed, we use a heuristic based on linear programming ideas to give good (often optimal) solutions to the aggregate problem (AP b ). We call these methods, FastAP. Just as we utilize one of several dynamic programming routines designed to solve the sub-problem, the choice of which depends on the values of H_ b and Hb and the nature of the h's that have been selected, we also have different FastAP approaches. Overall, however, they are based on linear programming relaxations. When the show selection constraints aren't needed, a straightforward LP Knapsack problem is solved. Otherwise, a slightly more complicated version is employed to satisfy the show selection constraints. Each solution is refined using problem reduction methods which shrink the domains based on simple dominance tests. 73 A problem similar to (AP b ) is given below and proves useful in several situations. When no assignments have been made, let s b (MN„) t?„ = min £*,, JlD s x 5b >T b s=\ Using the same techniques deployed to solve (AP b ) we are able to determine the minimum number of units, r] b , needed to satisfy all of the constraints (1.2) - (1.1 Id) for bidb. 5.4 Domain Management - Constraint Programming Effectively managing the x sb domains is extremely important to the heuristics ability to reach a timely solution to this problem. Due to its combinatorial nature and the large number of available units, the problem size can quickly become insurmountable. We employ constraint programming concepts as a means of coping with these sizes. Simple programming logic can replace complicated logic equations providing a more efficient method of ensuring that constraints are enforced. By dynamically reducing the size of the domain as units become unavailable and only generating the combinations that satisfy an individual buyer's constraints we avoid total enumeration. We utilize a "greedy" assignment methodology were we assign one bidder at a time and then adjust the remaining domain to reflect the resulting slot assignments. 74 In the previous section we developed an aggregate problem used as a basic component for solving PI . This formulation relies heavily on the domains X s b . The following procedure is used to determine the domain for each bidder given the current available slots and previous allocation of bid. lfStf. ' s,b tf«i * 2 * N ,* Step LL e tX sb =<?> and y(N sb )=l , y\N sb ) is set to if there are no 15-second commercials in buyer 6's campaign indicating that the anti-clutter constraint is not applicable to this campaign. If the buyer is running 15-second commercials and not 30-second spots, this parameter will be set to 1 . When y\N s b ) = \ special consideration must be given to ensure that no more than 2 15-second commercials for this bidder appear in the same pod. Since the buyer is not running 30's two units in a pod must be individual 15- second commercials. Step 2. Let g p s be the remaining number of open slots in pod p of show s. Open slots are defined as those that are not yet owned. Additionally, if a competitor owns 2 or more slots in a podp of show s then no units in that pod are deemed available. If a competitor owns a 1 5-second slot in that pod then the pod is "weekly owned" and only 1 unit is considered open. This methodology ensures pod-protection and gives priority to current owners of weakly owned pods. Step 3. For each pod define X psb ={ne N sb : g sb > n). These are the campaign lengths feasible for each pod. The lengths allowed in each pod are entirely dependent on the number of units available and the allowed campaign lengths. For example if 75 there are 3 units available in a pod and a bidder is running 30- and 60-second commercials they could only have a 30-second (2 unit) spot in that pod. Step 4. Let 0, be the set of all combinations of size i = \,...,K sb of the sets X psb (used no more than once in a combination when y\N s b ) = or no more than once with the exception that two 15-second units are allowed in the same pod if y\N s b )= 1 . The aggregate over each show is X s b = [J®, • This enforces the anti-clutter constraint. Step 5. Remove each x sb e X sb from X sb where the number of currently committed slots plus x s b exceeds C s , thus limiting the number of assignments in each show to no more than the maximum allowable. An example will help clarify how the domains are computed. Assume for some show s and buyer b we have the following: • C s = 24 , and the current number of committed slots for that show is 17, leaving seven open units. • N s b = {l,4} or the campaign consisting of only 15- and 60-second commercials. • K sb = 4 (any combination of the allowable 15- or 60 second spots totaling at most 4 correct length commercials are allowed in show s). • P = 4. There are 4 pods in show s The number of open slots in each of the four pods are as indicated. g is =5, g 2 ,s = ' #3,, =7 > #4,* = 3 • The above states that this bidder is running campaigns of length 1 and 4 ( N s b = {l,4}), can have at most 4 commercials in this show ( K sb = 4 ), that there are 4 pods in the show (P = 4) having 5, 0, 7 and 3 remaining slots available to this bidder. The zero availability in pod two may have resulted from pod protection given to another bidder in a prior step 76 of the solution methodology or it may simply have been completely used by prior assignments. Step 1 gives X sb =<|> and YV N s,b) =1 - Step 2 is specified above by the g values. Step 3 gives X^ - {l,4}, X UJ > - <j> , X UJb = {1,4} , X, sM ^ {l}. Step 4 gives the following. The examples illustrate possible assignments. 0, = {l,4} (different combinations consisting of 1 correct length spot) 2 = {2,5,8} (e.g., 5 = a length 1 in pod 1 and length 4 in pod 3) 3 = {3,6,9} (e.g., 6 = a length 1 in pods 1 and 4 and length 4 in pod 3) 4 = {4,7,10} (e.g., 7 = two length 1 's in pod 1, a 4 in pod 3, and a 1 in pod 4) Then X sb ={1,2,3,4,5,6,7,8,9,10}. Step 5 requires us to remove 8, 9 and 10 since we have at most 7 units available to assign. Thus the final X sb - {1,2,3,4,5,6,7} is the domain for show s from which we select allocations to satisfy buyer b's requirements. Although this example might suggest the contrary, a domain need not have all the integers between the upper and lower element. 5.5 Master Problem An overview of the master problem is presented in Section 5.2, Figure 5.1. The goal is to find a solution that maximizes seller profits as specified in problem PI of Chapter 3 while satisfying constraints (1.1) to (1.1 Id). The approach employed utilizes the heuristics described in previous sections and methods defined here to determine an allocation that approaches optimality. 77 To establish a good initial solution to the allocation problem, consider the following two greedy algorithms. Assume we are given B bids. The two algorithms differ only by the sort criteria used in step 1. Step 1 : Repeat the following until all bids have been processed Sort the remaining bids by some criterion of interest with the most desirable bid designated as the top-most bid. See sorting criteria 1 and 2 below. Solve the aggregate sub-problem for the top-most remaining bid and make the appropriate assignments to the variables of PI. Step 2: While the amount bid by the selected bidders is less that the seller's reservation price for the collection of allocated units, i.e. B 5>bVb <(!-!•) £ J] EZ X ".P.s,b b=l b=l ^s=l \p=\ u=l J J Sort the remaining feasible bids by some criterion of interest with the least desirable bid designated as the top-most bid. See sorting criteria 3 below. Set the top-most active bid's aggregate sub-problem solution to infeasible and remove any current allocations to this bidder. Furthermore, the above procedure yields a feasible solution to the auction problem as is now shown. First, Step 2 guarantees the feasibility of the reservation requirement (1.1). The construction of the domains for each aggregate sub-problem plus the constraints of (AP b ) assures the feasibility of all the remaining constraints. See Figure 5.2 for an overview of this heuristic. 78 Start While Bids Still Unselected T Compute TotT d and TotD d Select Remaining Bid having max{(a b *TotT d )/ (T b *TotD d )} Solve AP for this bidder using current assignments Bid Selection Complete Yes / Record Initial I Feasible Solution A Repair Solution Sort Bids Max(Sum((L 5 *X sb ) /a b )) Delete Top-most remaining active bid from solution Figure 5.2 Heuristic Flowchart 5.5.1 Sorting Criteria 1 The first sorting criteria is designed to order the bidders in such a manner that those that contribute the most to maximizing seller revenue are assigned first. To accomplish this we find the bidder that solves the following 79 TotZ max fal TotD t d J where TotT = V remaining demographics * L s and TotD = v remaining required demographics * a b , and J is the demographic required by bidder b. We assume, as is industry practice, that each bidder's demographic requirement T^ is in only one demographic category. Simply stated, the bidder with the highest bid per thousand demographic requirements normalized by the cost of the specific demographic category and demand within that category is selected. 5.5.2 Sorting Criteria 2 The ratio of the actual bid amount, af, i and a b , the minimum possible cost allocation for that bid b, defines sorting criteria 2. The sorting equation is as follows ( „ \ max \ G bj 5.5.3 Sorting Criteria 3 The following sorting criteria will force those bidders with the largest actual cost to bid ratio to be removed first, enhancing the auction's ability to achieve a feasible solution. f s max 80 5.6 Branch and Bound Branch and bound techniques are employed to investigate the various combinations of bids that will maximize seller revenue. Total enumeration of the various combinations is impossible in any reasonable amount of time, thus we utilize heuristics to guide our branching behavior. At each branch, we take the partial solution from predecessor branches and solve (AP b ) (or FastAP). The amount of time allotted to computation in each round is pre-defined. Therefore we use time remaining as a guide to the search process. After preprocessing is complete, an initial solution determined and an upper bound on PI computed, the remaining time is used as follows. Thirty percent is spent in a Breadth First Search (BFS), the rest is dedicated to a Depth First Search (DFS). 5.6. 1 Breadth First Search (BFS) The Breadth First Search extends to three levels. This means that it looks at all orderings of all combinations of 3 bidders - time permitting. Below level three, depth first search is used but is limited to a relatively small number of branchings (we use five times the number of bidders). Bids are initially ordered by the heuristics previously described so as to rank them such that the top-most bids contribute the most to maximizing revenue. However, conflicts between these bids may prevent all of these most desirable bids from achieving an allocation. The order in which the bids are processed affects the allocation so all permutations of the three bids are explored. During the Breadth First phase, the FastAP heuristic is used. 81 For example, the BFS systematically explores all permutations of ordered bids {1,2,3} then bids {1,2,4}, {1,3,4}, {2,3,4}, etc, expanding each of the permutations with a DFS. This process continues until 30% of the remaining computational time has been exhausted at which point, the final 70% of computing time is dedicated to a strictly Depth First Search. 5.6.2 Depth First Search (DFS) A Depth First Search is employed during the final 70% of computational time to seek out the best combination of bids. This search is conducted in two stages, the first solves (AP b ) exactly using dynamic programming and lasts for 60% if the time allotted. Stage 2 utilizes FastAp and runs until the conclusion of the computational time. 5.6.3 Fathoming Criteria Some fathoming criteria that are used to limit the branch and bound search follow. 1 . Based on reservation price. Recall that a b is the objective value of a solution to the aggregate problem (AP b ) where no prior assignments have been made. Then any branching exploration should be restricted to cases where the amount bid by the feasible bidders meet the minimum cost allocation that satisfies all constraints. In other words, don't consider any selection of bids where 4=1 b=\ 2. Based on best feasible solution value to date. 82 Don't explore any assignment ofy's giving an objective value to PI that is less than the current best feasible solution subject to the amount of inventory available. That is, don't explore any y's satisfying: ^a b y b <Best Feasible Solution Value, 6=1 with B S f j r Jb y b <f j C s 6=1 s=\ 5.7 Determining an Upper Bound to PI : The overall problem (PI) is upper-bounded by: B U = maxY i a b y b B 6=1 a e 6=1 j=l 0<^<1 This formulation incorporates the results of the aggregate problem (AP b ) and the minimum number of units problem (MN b ) defined earlier together with constraint (1.1). The bound provides a way to judge the current best solution to all constraints (1.1) - (1 .1 Id). This problem is simple to solve since a bounded-variable Simplex method with only two constraints is trivial. 5.8 Summary To cope with the size and complexity of the problem and facilitate reaching a solution in real time a heuristic was developed and described in this chapter. The 83 heuristic solution to the combinatorial optimization problem (PI) is by no means trivial. Various techniques were employed to guide our quest for an optimal allocation, including a mixture of problem aggregation with linear, constraint and dynamic programming methods as well as branch and bound search. Subsequent chapters will test the efficacy of the methods engaged. CHAPTER 6 SIMULATED BIDDING AGENT DEVELOPMENT 6.1 Introduction Our experiment consists of simulating the execution of our auction under various conditions to analyze the mechanism's performance. To facilitate this we generate players that reflect the characteristics of the real world environment. An analysis of data received from a representative of a major television network provides a statistical basis for player typing. Each player or agent represents an individual bidder with defined parameters that reflect media buying practices within the industry. The parameters include bidder product requirements. To establish product requirements necessitates defining the desired demographic category and gross rating points (GRP) required as well as bidder reservation prices. Show selection for each agent includes a list of desired shows and an upper and lower bound to the number required. The number of commercials allowed in each show and the type of product being sold will also be specified. Finally, a bidding strategy is defined for each agent type that governs the agent's behavior during the auction's execution. A visual summary of the entire process of generating a bid agent is presented in Figure 6.1. We describe each process in detail in the remaining sections of this chapter. Every attempt was made to depict as many types of bidders as necessary to accurately represent the behavior of the market participants. 84 85 Establish Commercial Lengths for Campaign* (Single Frequency) -Yes Set Maximun Allowable Commercials Per Show = 1 Determine # of bidders Randomly assign a Demographic Category Determine Total Demographic GRP Required (Gamma dist. for each Demo) Calculate Bid Amount (Regression equation for each Demo Category based on GRP) Choose Product Type Establish Number of Commercials in Campaign Establish Exceptions to Max Allowable Commercials Per Show Establish Commercial Lengths for Campaign* (Multiple Frequency) Set Maximun Allowable Commercials Per Show* (70% ■ 1 , 28% = 2, 2% = 3) Select Number of Desired Shows Select Desired Shows Set Lower Bound on Desired Show Define Bidding Strategy Establish Entry Round Figure 6.1 Flowchart of Initial Agent Generation 86 Classical auction theory assumes homogeneity among auction participants, however new evidence suggests that in electronic auction several types exist. Bapna, Goes and Gupta (1998) describe three distinct bidder categories, Evaluators, Participators and Opportunists, these will be used as a basis for our bidder definitions. 6.2 Data Analysis The data analyzed for this research was provided by one of the major television networks. The source prefers to remain anonymous. Within this industry information, especially pricing and inventory availability, is extremely proprietary and jealously protected, therefore we have attempted to disguise the results of our analysis while at the same time benefit from the discovery of patterns. Our analysis consisted of reviewing two representative weeks of actual airtime allocations. The data consists of 150 unique bidders representing 209 purchases to acquire 1290 units of airtime across 48 shows. Not all information needed to formulate our buyer typing was known either because of our inability to access the appropriate data or the lack of representative data. We were required in some instances to make assumptions. Some of our assumptions stem from anecdotal evidence provided by our information source while others are based on expectations of a rational buyer in a competitive market. During the following discussion of buyer typing we will identify and justify the assumptions. The patterns and frequencies identified will be used as a basis from which we randomly generate characteristics of each agent and thus may not be exactly duplicated in our experiments. 87 6.3 Number of Buyers The number of bidding agents to generate was our first consideration. The two weeks of data consisted of roughly 90 to 120 buyers who were awarded "upfront" allocations in each week. Our industry source indicated that 300 to 350 buyers participate in "upfront" with their allocations distributed across the weeks of the year. As a conservative estimate we generate 325 bidding agents. 6.4 Demographic Category and Total Gross Rating Points Media buyers must achieve a certain amount of demographic exposure or gross rating points within a specific demographic group to satisfy their campaign needs. The A. C. Neilson Ratings for network television is the measure used to determine the number of people exposed to a particular program and hence to the commercials appearing in that show. The ratings are broken down in various categories representing the gender and age of the viewing audience. Six of these categories are typically associated with primetime advertising sales; Women, Men and Adults within age groups 18-49 and 25-54. Category assignments for each agent were randomly chosen from a uniform distribution over the values 1 to 6. An analysis of the data revealed that the amount of demographic gross rating points required by each buyer followed a gamma distribution. Figure 6.2 shows the distribution of the buyer frequencies over the total Gross Rating Points (GRP) averaged across all categories. The individual category distributions appear in Appendix A. Appropriate MLE estimates of Gamma distribution parameters a and (5 's were generated for each category. Simultaneously satisfying the following two equations by 88 25 in C I 3 m h V 20 15 10 r Z 5 o I Hi II HTTTTm HI n limn n n n 10000 20000 30000 40000 50000 Average Demographic GRP Figure 6.2 Average Gross Rating Points varying a gives us the estimated parameters. rn/? + ^(a) = ^ , « and d0 = *(»), where ^(a) = r'(a)/r(a) is the digamma function with P denoting the derivative of T(Law & Kelton, 1991). The /? values were then varied to maximize the goodness of fit measure. The Kolmogorov-Smirnov one-sample test was used to determine the goodness of fit between the estimated Gamma distribution and the sample values. The cumulative distribution for the theoretical Gamma distribution is compared to the cumulative distribution of the actual data. The maximum deviation from the theoretical distribution must be less than or equal to a critical value defined for the test. Results of the test are presented in Table 6.1 and validate at a 0.05 significance level that the sample came from a population having a Gamma distribution (Siegel, 1956). Using Phillips 89 (1971) gamma variate generator and the estimated a and j3 for the appropriate category we are able to generate a representative random demographic value to assign an agent. Table 6.1 Goodness of Fit Test Kolmogorov-Smirnov One-Sample Test Significance Level = .05 (2-tailed) Critical Value = .09407 Max Difference <= Critical Value? Demo 1 0.0675 Yes Demo 2 0.0657 Yes Demo 3 0.0777 Yes Demo 4 0.0721 Yes Demo 5 0.0696 Yes Demo 6 0.0751 Yes 6.5 Bidder Reservation Price The data analyzed for our study includes the amount that each successful buyer paid for each of their allocated commercials with the associated placement information. We can safely assume that the buyer's reservation price over all their units is at least the sum of the individual unit values. We also know the network's estimated gross rating points for the shows within the sampled weeks. The seller's rating estimates are not common knowledge among the buyers, instead buyers base their demographic requirement calculations from approximations discovered from historical ratings of prior seasons and market research on new programming. These approximations are fairly accurate in reflecting the seller's figures, therefore we apply the known seller rating estimates to determine roughly how many demographic gross rating points the buyers in the data desired by summing the demographics over the shows they were allocated. We 90 then equivilize the demographics to reflect the length of commercials. For example, a 30- second commercial would receive twice the demographic exposure of a 15-second spot. A strong linear relationship was found to exist between the price paid for the units and the equivilized demographic GRP for the associated shows but showed signs of heteroscedasticity. A natural logarithm transformation of both variables remedied the increasing variance. See Table 6.2 for a summary of the fit. Table 6.2 Regression Fitness Statistics LNPrice = Constant + (Coeficient * LNDemo) Demo R Square F t Sig. 1 .836 1056.437 32.503 .000 2 .837 1065.432 32.641 .000 3 .835 1047.752 32.369 .000 4 .834 1038.267 32.222 .000 5 .844 1118.842 33.449 .000 6 .846 1135.407 33.696 .000 By regressing logarithmic price against the logarithmic equivilized total demographic GRP within each demographic category we were able to establish equations for determining a representative reservation price, see Appendix B for the detailed results. Each category's regression equation was determined from 209 observations. Based on the demographic category and the total demographic GRP's formulated in the previous steps we can calculate, from the appropriate regression equation, individual reservation prices to assign the agents that reflect the amount and type of product desired. For the purposes of this study we assume buyers' valuations can be represented by a step function [ if constraints are not met, Reservation Price if constraints are met 91 An allocation has no value to the buyer unless all constraints have been met, while any allocation that satisfies the constraints is valued at his reservation price. Buyers are trying to satisfy explicit campaign goals at a minimal cost thus adding additional units to the minimal constraint satisfying allocation does not add value. The regression gives us the reservation prices representing those buyers who were successful in achieving an allocation. We recognize that there may have been participating buyers that were not successful in securing an allocation and others that were not forced to pay their true valuations, therefore we increase the variance of the actual reservation price assigned by a random amount uniformly distributed between 20% above or below the calculated figure. 6.6 Commercial Lengths and Frequency An analysis of the historical data provided indicates that approximately 76% of bidders aired multiple commercials within the campaign week, while 24% placed only one spot. Our agent demands reflect these statistics. Within the two groups, multiple or single placement, we were also able to determine a frequency of the lengths of commercials aired. Table 6.3 details the breakdown upon which we programmed our agents. Within the multiple commercial campaigns there were instances of mixed commercial lengths where a single buyer uses a variety of commercial lengths within the same campaign that we reflect in defining our agents. 92 Table 6.3 Number of Commercials in Campaign Length ~~~~~~\_^ Single Unit Multiple Units 15's 16% 21% 30's 76% 48% 60's 8% 2% 15's&30's 24% 30's&60's 2% Other mixed 3% 6.7 Limits on Number of Commercials Dispersing commercials across various shows ensures that as many different viewers as possible are exposed to an advertiser's message. Generally, advertisers limit to one the number of commercials in each show. The data confirmed that 70% of advertisers with multiple commercials in the campaign week allowed only one spot per show, while 28% accepted up to 2 and 2% permitted as many as 3. We capture these same frequencies within our agents. Exceptions to the norm involved either forbidding placement entirely or increasing the number of spots allowed in a particular show by one or more units. We pattern the exceptions in our agents as described in Figure 6.3. We have allowed 30% of all agents to have no modification to the number of commercials per show. Another 62% will forbid placement in some portion of the shows that they have not specifically requested, while 8% permit more than the normal maximum number of spots per show. 93 Maximun Commercials Per Show (K) No Modifications Increase 10% ofK'sby2 Change 5% of K's to Change 10% of K's to range (0-2) Change 20% of K's to Figure 6.3 Maximum commercials per show modification 6.8 Selection of Product Type The type of product advertised by our participants impacts on the allowable placement of the commercials. The industry practice of not allowing two commercials promoting the same type of product to appear in the same commercial break if one is at least 30-seconds long, referred to as "pod protection," makes distribution of product types across buyers an important consideration in our agent development. We were able to ascertain from the data provided the frequency of the various product types and use those frequencies to establish a representative mixture in our agents. We discovered a concentration in only a few product types such as retail, automobile sales, and restaurants. 6.9 Selection of Desired Shows The number and identification of desired shows assigned to each agent were determined randomly. The number of shows was based on the arbitrary distribution listed in Table 6.4. Once we had assigned the number desired, the selection of specific 94 shows was determined from one of three show orderings, minimum cost per thousand (CPM), maximum demographics in that agent's demographic category and minimum anticipated cost. Our assumption is that a rational buyer would want a selection of shows Table 6.4 Number of Shows Desired Percent of Bidders Range 30% No Preference 30% 1-3 Shows 30% 4-10 Shows 10% 11-15 Shows that will best satisfy their demographic needs within a particular category. Choosing from shows with the minimum CPM in that demographic category ensures that the buyer is getting the most cost efficient placements. Although the buyer does not know with certainty the CPM for each show we assume she has value and demographic estimates that are representative of those held by the seller. Therefore we sort the shows using the data on list prices and demographic GRP's provided by our industry expert. We further assume that selecting desired shows based on the minimum CPM to be the overwhelming choice among the buyers and assign shows to 60% of our agents using this ordering. Another approach is to choose from the shows with the highest demographic gross rating points regardless of the price. 30% of our agents employ this strategy that places the buyer in shows promising the most exposure to the viewers in her desired demographic category. To achieve the greatest frequency of placement buyers may want only the least expensive shows, 10% of our agents are assigned minimum cost shows. Table 6.5 indicates the allotment across the agents for each ordering. 95 Table 6.5 Show Selection Criteria Percent of Bidders Order 60% Min CPM 30% Max Demo 10% Min Cost Establishing the lower bound of the number of selected shows required by each bidders is determined as follows: 40% of agents place no bounds on the number of shows required, another 40 % set their lower bound at 2-3% of the selected shows. The remaining modifications are more restrictive with 10% requiring 4-6% of the selected shows, 6% require 6-8% and 4% having tight bounds, see Table 6.6. Table 6.6 Desired Show Bounds Bounds % of Bidders No Bounds 40% 2-3% of # Selected 40% 4-6% of # Selected 10% 6-8% of # Selected 6% Tight 4% Upper bounds were set at the number of shows selected. The frequencies were chosen at random but reflect anecdotal evidence. Buyers are described as routinely indicating that they would prefer as many of a particular type of programming as possible, but generally don't specify the exact the number required. Examples could be a desire by the buyer to appear mostly in situation comedy shows, or possibly only in news programming. Rarely, an advertiser may demand to appear in a specific show or group of 96 shows and if the network is unable to grant their request will not accept alternative placement. This last example represents a bidder with tight bounds. 6.10 Bidding Strategy A buyer's bidding strategy dictates their behavior during the execution of the auction. We model this behavior by how bid modifications are made throughout the course of the auction and the decision on when the bidder places her entering bid. Recent research on electronic auctions, such as the Multiple Vickery Auction and the English Auction for multiple items, has identified three specific types of bidders; Participants, Evaluators and Opportunists (Bapna et al., 1998). We use these types as a foundation on which to model our agents' bidding strategies. Evaluators have a clear idea of their valuation and place one bid early in the auction that reflects that value. If outbid they do not reenter the auction. Participators take a dynamic role by bidding early and actively modifying their bids as necessary to remain active during the course of the auction. Opportunists, or those bidders who place a minimum bid just before the auction closes, are not explicitly modeled as agents in our experiments because the end of the auction in not generally known. The Incompletely Specified Combinatorial Auction does allow bidders to enter in late rounds but since our auction is semi-sealed with soft closing rules the required signal information to assist the Opportunist in determining the minimum bid and or closing round is not available. Thus there is little incentive to delay bidding and we assume that the majority of bidders will enter in the early rounds. See Table 6.7 for a breakdown of the initial entering round parameters applied to the bidding agents. 97 Table 6.7 Initial Entry Round EntryRound Percent 1 80% 2 10% 3 2% 4 2% 5 1% 7 1% 10 1% 12 1% 15 2% The two major approaches to bid modification involve changing the bid amount or loosening constraints imposed on the choice of shows to fulfill the demographic GRP requirements. Bid modification tactics are broken into six styles, 5 represent the Participator type and the other takes on the characteristics of an Evaluator. We further divide Participators into five subcategories depending on how they make their bid modifications. The multidimensional nature of the ISC A bid allows for a variety of modifications. Of the Participators, two modify their bid amount only, two modify both their bid amount and the constraints imposed on commercial placement and one modifies only the constraints. We define BidAdjustors as those bidders who modify the price they are willing to pay for an allocation. Constraint Adjusters modify only the demand for, or restriction to, the shows included in the allocation, while AllAdjustors combine the techniques of bid and constraint modification. Participators that modify their bid amounts, those classified as BidAdjustors and AllAdjustors, do so by one of two increments. They may reenter the auction with an 98 offer incremented by a percentage of their rejected bid, the rules of the auction establish this minimum increase, see Figure 6.4. Alternatively, our ISCA provides the bidder AdjustBid AmountMax Yes- No Z" - Return ~"\ \ RecommendedBid / Return ReservationPrice. /"" Return ^ ReservationPric e^ AdjustBid AmountMin Yesn Return ReservationPrice Figure 6.4 Bid Adjustment Flowcharts with a recommended bid increment to assist in the formation of subsequent bids, agents may increase their prior bid by this recommended amount. The recommended increment is calculated as the difference between the amount the individual bid previously and the seller's discounted list price for what was determined to be the best allocation for that 99 bidder's demographic requirement in that round. Following the rules imposed by our auction, any recommended bid is at least the minimum percentage increase above the previous bid but may be greater. The option to choose between these two increments dictates the bid adjustment strategies, either Max or Min, depicted in Figure 6.4. In either case, prior to posting, a check is made to see if the interval between the prospective bid and the reservation price is less than the minimum bid amount required in the next round. If the gap is smaller than an allowable bid, the bidder will submit a bid equal to her reservation price to avoid a situation where her current bid is less than her reservation price but she can not reenter the bid because her next bid will not meet the minimum increment requirement. BidAdjustors and AllAdjustors choosing the maximum of the percentage or recommended increase are acting on the assumption that they will have a greater chance of achieving an allocation if they choose the largest increment. This approach could be viewed as representative of risk averse bidders with the difference between the minimum percentage and the recommended increase being the risk premium (Varian, 1992). If the buyer believes that there is a chance that a lower bid will be successful in the subsequent round the minimum increment strategy would be a better choice. Regardless of the strategy chosen, the buyer cannot bid an amount greater than her reservation price. Constraint adjustments involve relaxing the restrictions imposed on the shows required or allowed to be allocated to the bidder. These restrictions include the bounds on the number of desired shows, the number of shows included in the desired show list and the number of forbidden shows. Figure 6.5 depicts the various modifications that may be made to provide the seller greater freedom in his allocation. As a minimum the 100 bidder must loosen a restriction by one unit. Bidders are advised of the constraint(s) that cannot be met. For example the shows available to allocate a bidder may not satisfy the minimum number of shows desired by the bidder, in this case the bidder is notified that her lower bound of desired shows is too high. Agents use this information to direct the choice of constraint modification strategy. Figure 6.5 Constraint Adjustment Flowchart One or a combination of the modification strategies is assigned the agent at inception. The percent of agents assigned to each strategy will be varied during experimentation to determine if a particular strategy is dominant. When designated as inactive all bidder types, except the Evaluator, will attempt to reenter the auction following their adjustment strategy until they can no longer meet the minimum increment guidelines. 101 Figure 6.6 depicts the bidding strategies after the initial bids are placed. Notice that AllAdjustors first attempt to modify the amount they bid and when they have reached a point where they can no longer increase the dollars bid by the minimum increment they resort to modifying their constraints. Exit Auction Evaluate* Figure 6.6 Bid Strategy for Rounds > (for inactive bidders only) 6.11 Summary We created agents to act as bidders in our simulations. The information gathered from the data provided guidelines for establishing the parameters for the total number of bidders, demographic gross rating points, reservation price, number and length of commercials, type product and the number of commercials allowed in each show. The agent's demographic category, number of desired shows, the associated bounds to desired shows, and entry round were randomly assigned from frequencies based on anecdotal evidence about industry practices and justifiable assumptions. Bidding strategies were 102 founded on the characteristics of bidder types in electronic auctions proposed by Bapna et al. (1998) and the assumption of rational behavior of participants in a competitive environment with information asymmetries. We assume that bidders will accept an allocation as long as it meets the criteria and restrictions specified by the agent in the associated bid. Therefore, we do not include logic permitting bidder rejection of an allocation or early withdrawal from the game. CHAPTER 7 EXPERIMENTAL DESIGN 7.1 Introduction The goal of our experiments is to test the auction mechanism's performance under various conditions. The measures used to evaluate the Incompletely Specified Combinatorial Auction's performance are allocative efficiency, the optimality of unit assignment and the length of the auction. The test scenarios include varying the number of each type of bidders, changing the minimum bid increment requirement, applying various stopping rules and modifying the amount of calculation time the heuristic is given in each round. Section 7.2 defines the performance measures used in our analysis, while the subsections of 7.3 set up the parameters for each of the experiments. 7.2 Performance Measures Historically the performance of auctions has been judged on how well they allocate the product(s) in terms of efficiently and optimality. Additionally, consideration is given to the amount of time it takes to reach a stopping point or equilibrium. We will validate our mechanism using these same measures. We will also study our solution methodology by comparing its results with the solutions obtained by a commercial integer programming package on representative problems that are sufficiently small for it to reach a solution to the combinatorial optimization. 103 104 7.2.1 Efficiency When the seller always sells an object to the bidder with the highest realized valuation for that object, as long as that value is greater than the seller's reservation price, the auction is said to be efficient (Armstrong, 1999). While this measure is fairly straightforward in a single unit environment, complications arise when trying to evaluate efficiency for multi-item auctions, especially those involving package bids. In a combinatorial auction one must consider the impact of overlapping demand for the various items that may limit the feasible allocation of units when determining a mechanism's efficiency. Achieving efficiency has been the goal of many of the recently developed auction mechanisms including the famous Federal Communications Commission (FCC) spectrum license auctions (McMillan, 1994; McAfee & McMillan, 1996; Cramton, 1995). Another reason for the active interest in efficiency is that evidence suggests that efficiency and optimality are complementary in that an inefficient assignment of goods leads to less than optimal seller revenue (Ausubel & Cramtom, 1999). Establishing an exact measure for efficiency in the multi-unit environment has proven difficult. Krishna and Perry (1998) view efficiency from a social welfare prospective by defining an ex post efficient auction as one were the chosen allocation maximizes social welfare over all types of bidders. Simply stated this means that there is no other allocation that maximizes the sum of the agents' payoffs. Ausubel (1996) provides a procedure for extracting an efficient allocation in a sequential manner. By determining the allocation of goods associated with the highest total bids if Bidder i were 105 absent from the bidding we can determine the marginal surplus that bidder i brings to the auction. This process must be repeated for every possible permutation of the number of possible allocations to bidders and thus would become intractable for large problems. Experimental economics provides an alternative approach that has been effective for research into combinatorial auctions (Plott, 1997). In a laboratory setting information not readily discernable in a true environment can be controlled and manipulated for analysis. For example, in a combinatorial auction in order to determine efficiency the experimenter needs to extract each bidder's value for every possible subset of objects being sold. This information is normally privately held by each bidder. Recent laboratory experiments involving combinatorial auctions used this notion to establish valuations for the possible bundles created by the bidders. Assigning a redemption value V b (y) to be paid to bidder b for holding a combination of objects indicated by v, reservation values for the various combinations were established and known to the experimenter. The subjects involved in the study were paid an amount representing the redemption value of the combinations of goods they were ultimately allocated by the auction mechanism. Use of this type of financial incentive is a well documented methodology in experimental economics (Plott, 1997). With the value information experimenters were able to define efficiency as: I> b y b (A) E = ^ , V* where V* = max^\ b y b=l 106 subject to the feasibility of the y b 's. The y b (A)s are the final allocation chosen by the auction (Bykowsky, Cull & Ledyard, 1995; Ledyard, Porter & Rangel, 1997; DeMartini, Kwasnica, Ledyard & Porter, 1999). Notice that efficiency is defined on the set of feasible solutions, rather than over all possible combinations. In the simulation of our auction we also establish a reservation price for each bidder or agent. The valuations are a step function, where an allocation not meeting the constraints has no value to the bidder and a value equal to a defined reservation price for all allocations satisfying constraints. The items or shows in each bundle are not explicitly valued, but are represented in the valuation by constraints requiring placement in specific shows. To determine the efficiency of our auction we define the final allocation of the auction mechanism as: p y b (A)=argmax£a b y b=l s.t. Constraints (l.l)-(l.lld) Further we determine the maximum value attainable in the auction as: B I b=l P V* = max£v b y b s.t. Constraints (l.l)-(l.lld) From these two equations we can formulate an efficiency measure similar to those used in the prior combinatorial auctions studies as: Zv b y b (A) E = ^ , V* 107 Note that this is an estimation of the efficiency as it relies on the outcome of our heuristic that may not achieve an optimal solution to either problem. However, when solving each problem, we end with a range from our final feasible solution to a theoretical upper bound. This gap is often small and is reported in our experiments. 7.2.2 Optimality A major difficulty with allowing combinatorial bids is the computational difficulty of determining the revenue maximizing set of winning bids. A seller of n items could conceivably receive 2" -1 possible bid combinations. The selection of the best combination from among the potentially overlapping bids is a combinatorial optimization problem that is known to be NP-complete (Rothkopf, Pekec & Harstad, 1 998). Thus the investigation of optimality for combinatorial auctions has been relegated to investigating small problems and or problem structures that permit tractability (Armstrong, 1999; Rothkopf, etal., 1998). Optimal auctions, from the seller's perspective are those that maximize seller revenue. Maximum revenue, in a single item auction, results from allocating efficiently then extracting as much buyer surplus as possible (Myerson, 1981). Ausubel and Cramton (1996) contend that the seller maximizes revenue in a multi-unit auction by allocating objects efficiently subject to exceeding the seller's reservation price. Unfortunately, this notion has yet to be proven for combinatorial auctions. However, the measure of how much buyer surplus the auction is able to extract from the winning bidders is an important consideration in the design of the mechanism. We will report the 108 percentage of the maximum possible revenue from the final allocation actually captured by the seller as our measure of optimality. £(v b -a b )y b (A) Optimality = 1 - ^—g , Zv b y b (A) where y b (A) represents the final allocation of the auction mechanism. 7.2.3 Auction Length The time it takes for our iterative auction to reach a defined stopping point is an important design consideration. The number of rounds and the time between them will determine the length of the auction. The termination of our auction is based on soft stopping rules, the exact nature of those rules will be varied in the experiments to determine the most effective. There are tradeoffs between auction length and efficiency with an iterative auction format. Increasing the number of rounds provides an opportunity for bid modifications the may enhance the chances of creating packages with better fit and thus boosting efficiency. Lengthy auctions, however, could lead to reduced seller profitability from administrative costs associated with each round or opportunity costs associated with forgone rental revenue of the goods (DeMartini, et al., 1999). In our environment there is a generally agreed upon period over which upfront sales are conducted which suggests the maximum overall length of the auction. There is no required completion time that would dictate that the auction finish by an exact date and time. "Upfront" sales generally last three to four weeks, therefore an auction that doesn't 109 reach its goal for months would not be satisfactory. The minimum time between rounds, is influenced by the amount of time required by the heuristic to determine an allocation. 7.2.4 Solution Methodology Performance Ideally our auction will result in the optimal allocation of goods. Due to the complexity of the problem we have developed a heuristic that achieves a satisficing solution we trust is reflective of the optimal solution. To determine how well our heuristic performs we will compare its results with those obtained by a commercial integer programming package, CPLEX 6.5, on representative problems that are sufficiently small for it to reach a solution to the combinatorial optimization. We will also analyze the amount of time each mechanism takes to compute the solutions as time to completion is important to the performance of our auction. 7.3 The Experiments Using automated agents to simulate bidders we test the Incompletely Specified Combinatorial Auction (ISCA) on a variety of conditions. To determine the impact of the different bidder types on the efficiency, optimality, and length of the auction the percentages of each type are modified and the results analyzed. We also investigate the influence of altering the minimum bid increment. The effect of the various round lengths is analyzed by adjusting the amount of time given to the heuristic to determine the allocations. Experiments are also conducted to determine the impact of closing rules using four different conventions. Three of the rules are "soft" in that they depend on some activity inherent in the rounds of the auction and can not be determined in advance, while one is determined a priori. Finally, we conduct a comparative analysis of the 110 heuristic results and the solution to the integer programming problem on a small but representative problem. 7.3.1 Modification of Bidder Types To analyze the impact of the various bidder types we modify the percentage of bidders in the different types and compare on the performance and results of the Incompletely Specified Combinatorial Auction. Table 7.1 summarizes the experimental parameters for the modification of the participation of the various bidders categories. Table 7.1 Bidder Strategy Experiment Parameters Eval BidAdjustor AHAjustor Constr. Bid Increm Stopping Rule Round Time Min Max Min Max 100% N/A Activity 15 min 100% 5% Activity 15 min 100% 5% Activity 15 min 100% 5% Activity 15 min 100% 5% Activity 15 min 100% 5% Activity 15 min 50% 50% 5% Activity 15 min 50% 50% 5% Activity 15 min 1/6 1/6 1/6 1/6 1/6 1/6 5% Activity 15 min 5% 20% 20% 20% 30% 5% 5% Activity 15 min The first six trials test each bid strategy in isolation while the remainder look at the interaction of the bidding types. In our first experiment we simulate a first price sealed bid auction since an Evaluator bids her reservation price and if rejected does not modify her bid or reenter the auction. The remainder of the experiments involve some form of iteration, similar to a progressive auction. The second and third experiments restrict bid modifications to incrementing the amount bid. The remaining experiments exercise an Ill option that is fairly unique to the multi-criteria bid, that is the ability to modify the constraints imposed on the allocation by the buyer. Experiment four resembles an iterative first price auction where at each round the requested package is modified but not the amount bid. The fifth and sixth trials incorporate all bid modification strategies, with the sixth experiment representing what we feel is a plausible distribution of bidder types. We use this generic distribution in the remainder of the experiments. 7.3.2 Modification of Bid Increment Changing the minimum bid increment should impact the amount of time or number of rounds the auction takes to reach its stopping point. The greater the increment the more rapidly bidders will reach their reservation price. The bidder type for all experiments remains constant and reflects the plausible generic distribution across all types. A list of the bid increments tested is provided in Table 7.2. Note that this is a full factorial experiment with all dependent variables modified. Bidder types are consistent with previous experiments. Each minimum increment is tested against each stopping rule. For each activity based stopping rule we also investigate longer calculation times of 30 and 60-minutes to determine if the longer times have any impact. With the other stopping rules will investigate 5 and 15 -minute rounds only. 7.3.3 Modification of Stopping Rule Manipulating the stopping criteria of the auction can have a significant influence on the mechanisms performance. We analyze the effect of four stopping rules. The "activity" stopping rule allows the auction to continue until there are no new bids placed. This is the least restrictive of the rules. The "minimum revenue" rule continues the 112 Table 7.2 Full Factorial Experimental Design Eval BidAdjustor AHAdjustor Constr. Bid Increm Stopping Rule Round Time Min Max Min Max 5% 20% 20% 20% 30% 5% 5% 10% 15% Activity 5 min 15 min 30 min 60 min 5% 20% 20% 20% 30% 5% 5% 10% 15% Min Revenue 5 min 15 min 5% 20% 20% 20% 30% 5% 5% 10% 15% Min Revenue & Activity 5 min 15 min 30 min 60 min 5% 20% 20% 20% 30% 5% 5% 10% 15% # Rounds 5 min 15 min auction until a pre-specified revenue goal has been achieved. A combination of the two previous rules extends the auction until the allocation attains a revenue goal and there are no new bids. These rules are considered soft stopping rules that promote bidder activity. We also test a hard stopping rule where we designate, in advance, the round in which we will end the auction. We do not reveal the stopping round and the semi-seal format of our auction does not provide signal information from early rounds. Therefore, we assume bidders have no incentive to delay entry into the auction. The full factorial experiment presented in Table 7.2 indicates the parameters upon which the stopping criteria are tested 7.3.4 Modification of Maximum Round Time The amount of time that the heuristic is allowed to operate in each round will influence the mechanism's performance. The longer the amount of time allotted to the 113 mechanism to process the bid information the greater the opportunity for the heuristic to find the most efficient fit. Round lengths are specified in Table 7.2, notice that tests look at different combinations of round lengths dependent on the stopping rule. Since the activity based rules continue until no new bids are received their results should provide insight into the results of the other two rules. The decision not to conduct the longer 30 and 60 minute experiments for the Minimum Revenue and Maximum Round stopping rule was made in the interest of conserving experimental time. 7.3.5 Heuristic Methods versus Integer Programming The solution to the integer program presented in Chapter 3 provides a benchmark against which we compare the heuristic performance. Obviously, since this is a combinatorial optimization the problem must be scaled down to allow the auction to be solved to optimality on a commercial software package. CPLEX 6.5 is the integer program solver used for our study. The base problem solved by both mechanisms consists of 30 bidders competing for placement in 3 shows. The tests are conducted on the same computer to rule out any variability that could result from differing configurations. The test parameters reflect what was determined in the previous tests of the heuristic to achieve the greatest seller revenue. We will analyze the comparative running times of both mechanisms and ultimate solution values. Additionally, we will seed CPLEX with the heuristic 's final solution and see if CPLEX can find a better outcome. 114 7.4 Summary This chapter defines the performance measures with which we test our Incompletely Specified Combinatorial Auction. The measures are adapted from procedures commonly used in the auction literature. Our experiments have been defined not to test every possible combination of parameters, but rather to provide for a large and fairly representative number of the probable scenarios. We have established comparative tests that will pit our mechanism's performance against that of commercially available integer programming software. CHAPTER 8 EXPERIMENTAL RESULTS 8.1 Introduction This chapter presents the results of experiments conducted to determine the behavior and performance of the Incompletely Specified Combinatorial Auction. The experiments consisted of simulating bidding activity under a variety of conditions using artificial agents. Characteristics of the simulated agents are reported in Section 8.2. Section 8.3 analyses the characteristics of the various bidder categories and their impact on auction performance. As discussed in Chapter 7, we define performance using three measures, efficiency, optimality and revenue. The auction's stopping rule, the minimum increment required for subsequent bids, and the time our heuristic is given to determine an allocation in each round are the factors manipulated in our experiments. Sections 8.4, 8.5 and 8.7 provide details of the impact of varying these parameters. We also discuss in Section 8.6 how the seller's choice of discount rate, which establishes his reservation price, affects the auction outcome. Finally, we present a comparative analysis of our heuristic's performance and that of a commercial integer programming package. 8.2 Agent Summary Statistics By using artificial agents we were able to represent bidder behavior in a hyper rational manner and manipulate various aspect of that behavior to test how the 115 116 mechanism reacts to different parameters. Each experiment consisted of 325 randomly generated bidders vying for a limited amount of inventory. As discussed in detail in Chapter 7, the valuations held by the agents were determined from regression equations that were garnered from analyzing real data. We conducted several tests using what we will refer to as the "generic" bidder mix. The generic bidder mix consists of a plausibly representative percentage of bidders in each bidding strategy category. Table 8.1 gives a breakdown of the characteristics of this generic set of bidders. The table presents a summary of two different sets of bidders (i.e., two different sets of agents were generated) Table 8.1 Generic Bidder Summary Statistics Generic Bidder Summary Statistics Type Bidder Bidder Demo 1 Demo 2 Demo 3 Demo 4 Demo 5 Demo 6 Bounded # % # % # % # % # % # % # % # % Set1 E valuator 15 5% 5 33% 3 20% 1 7% 3 20% 1 7% 2 13% 7 47% ConstraintAdjustor 16 5% 3 19% 6 38% 1 6% 1 6% 4 25% 1 6% 8 50% AIIAdjustorMax 105 32% 16 15% 18 17% 19 18% 20 19% 21 20% 11 10% 45 43% AIIAdjustorMin 59 18% 14 24% 7 12% 11 19% 7 12% 11 19% 9 15% 24 41% BidAdjustorMax 59 18% 14 24% 6 10% 8 14% 11 19% 7 12% 13 22% 26 44% BidAdjustorMin 71 22% 13 18% 10 14% 17 24% 9 13% 9 13% 13 18% 31 44% Set 2 Evaluator 16 5% 5 31% 3 19% 1 6% 3 19% 1 6% 3 19% 7 44% BidAdjustorMin 68 21% 12 18% 11 16% 17 25% 11 16% 6 9% 11 16% 32 47% BidAdjustorMax 60 18% 15 25% 4 7% 7 12% 12 20% 10 17% 12 20% 30 50% AIIAdjustorMin 64 20% 13 20% 9 14% 13 20% 7 11% 12 19% 10 16% 25 39% AIIAdjustorMax 103 32% 17 17% 14 14% 19 18% 21 20% 20 19% 12 12% 43 42% ConstraintAdjustor 14 4% 1 7% 7 50% 1 7% 1 7% 3 21% 1 7% 7 50% with which we tested our auction mechanism. The rows indicate the different bidder types defined in Chapter 6 while the columns provide the distribution over these types. The first two columns are summary statistics that give the total number and percentage of 117 the indicated bidder type. The following columns indicate the number and percentage of the bidder type evaluating their placement in each demographic category. Finally, the last two columns indicate how many of the bidders in that category have indicated that they must have commercials placed in at least one of their requested shows. We define these type bidders as "bounded" bidders because they have specified a positive lower bound on the number of desired shows. Evaluators and ConstraintAdjustors represent five percent each of the total number of bidders, while AllAdjustorMin, BidAdjustorMax and BidAdjustorMin hold 18%, 18% and 22% respectively of the total bidder population. The largest category of bidders is the AllAdjustorMax type representing 32% of total bidders. Within each category there are an approximately equivalent number of bidders requiring placement in at lease one of their desired shows. Each bidder type is fairly evenly distributed across the various demographic categories, with any variability attributable to random generation of the agents. We also let bidders enter the auction in any round with the actual distribution of initial bid rounds for the participating bidders listed in Table 8.2. Each column in the table represents a round of the auction, while the rows give the actual number and percentage of bidders that enter in each round for the 2 sets of agents. Notice that the majority of bidders, 83 and 77%, for each agent set respectively, participate in the auction from the start, while some bidders wait until as late as round 15 to place their initial bid. 118 Table 8.2 Bidders' Entering Round Distribution Entry Round Distribution Rnd 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Agent Set 1 # 255 34 9 6 5 5 3 8 % 83% 11% 3% 2% 2% 0% 2% 0% 0% 1% 0% 0% 0% 0% 3% Agent Set 2 # 249 36 9 8 4 5 4 1 9 % 77% 11% 3% 2% 1% 0% 2% 0% 0% 1% 0% 0% 0% 0% 3% 8.3 Bidder Type Impact In Section 6.10 of Chapter 6 we defined six bidder categories based on the bidding strategy employed by the agent to modify a rejected bid. Although we use the generic distribution of bidder types in most of the experiments, it is of interest to analyze the impact that each type and various combinations of types have on revenue, efficiency, optimality, auction length, the amount of unsold inventory and number of winning bidders. A summary of the results is shown in Table 8.3. The top section of the table describes the different distributions tested for the two series of agents. We list several interesting characteristics of the auctions including the maximum revenue and the associated round in which it was achieved, efficiency, optimality and units of unsold inventory at the close of the auction. The table also includes information on the number of winning bidders and the percent of winners that are bounded or have a positive number of required shows. 8.3.1 Summary of Impact of Various Bidder Types The auction consisting of all ConstraintAdjustors posted the best results. This bidder category was not only able to achieve the highest revenue by also had the highest 119 Table 8.3 Impact of Differing Bidder Type Distribution Bidder Type Analysis Minutes per Round = 15 Stopping Rule = Activity Min. Bid Increment = 5% Bidder Distribution Evaluators 100% 1/6 5% BidAdjustors Min 100% 50% 1/6 20% Max 100% 50% 1/6 20% AIIAdjustors Min 100% 50% 1/6 20% Max 100% 50% 1/6 30% Constraint 100% 1/6 5% Results Set 1 Revenue 25472 23451 20031 26042 24414 27393 22496 25337 24866 24579 Round Achieved 3 22 11 20 16 18 16 22 12 15 Efficiency 100 94.39 86.67 96.04 93.48 100 90.47 95.30 95.62 96.07 Optimality 100 91.83 86.67 98.95 91.83 100 89.84 94.88 94.95 93.62 Unsold Inventory 4 4 49 1 1 1 13 3 3 # Winners 119 121 113 134 141 139 120 138 121 128 % Bounded 11% 13% 10% 1% 5% 1% 11% 4% 7% 5% Results Set 2 Revenue 25345 23552 20566 26263 24164 27405 22752 25554 25056 24451 Round Achieved 5 11 12 14 14 14 19 14 20 16 Efficiency 100 97.71 93.07 98.54 92.76 100 93.04 97.84 96.27 95.76 Optimality 100 91.89 88.72 96.95 91.58 100 91.21 94.87 96.43 93.20 Unsold Inventory 3 2 40 2 9 1 6 # Winners 118 110 116 133 139 141 112 132 127 126 % Bounded 9% 15% 18% 2% 4% 1% 13% 3% 9% 5% number of winning bidders, had minimal or no unsold inventory and 100% optimality and efficiency. These results were achieved in as little as 14 rounds, a little later than some of the other experiments. The data show that auctions consisting of only AIIAdjustors also performed well with regard to revenue, allocations to a consistently high number of bidders while leaving very little inventory unsold. Evaluators also faired well posting the second highest achieved revenue, 100% efficiency and optimality, with only one or two units of unsold inventory. BidAdjustors under-perform in as much as 120 they leave significant amounts of inventory unsold, achieve the least amount of revenue, select the fewest winners and function worst in terms of efficiency and optimality. Combining the various bidder types produces results that reflect both extremes. We analyze a uniform distribution across the different types as well as the "generic" distribution that is used for the majority of the experimentation in this study. The outcome for the combination of bidder types is weaker in all aspects than of the set of bidders willing to modify their constraints such as when the auction consists of only Constraint Adjustors or AllAdjustors. However, in comparison to the results obtained from the bidder sets consisting on only BidAdjustors, or the inflexible types, the combination of bidder categories obtained better performance measures. 8.3.2 Analysis of Bidder Type Results The characteristics of Constraint Adjustors, namely that their initial bid represents their reservation price and their willingness to modify their constraints to achieve an allocation, highlight the fact that flexible bids are more likely to be successful. This notion is further supported by the data from the experiments consisting of AllAdjustors (M in and Max) either individually or in combination. In contrast, as might be expected, the more inflexible bidders or those bidders who will only modify their bid amount and refuse to compromise their show selections, such as BidAdjustors, are not as effective. Based on the above discussion it would seem that an auction consisting of only Evaluators should have poor performance characteristics because this bidder type is completely inflexible, allowing for no modifications. However, when all 325 bidders are of this type there are enough unbounded Evaluators, those not requiring specific show 121 placements, to consume the available inventory. Since, Evaluators bid their true valuations, unconstrained Evaluators mimic the characteristics of Constraint Adjustors that have eliminated all their demands and therefore display the favorable characteristics indicated in Table 8.3. The true mix of bidder types in the actual environment in which the auction is deployed will influence the performance of the auction. The above results suggest that a higher the percentage of flexible auction participants will promote greater efficiency and optimality as well as increased revenue. 8.4 Bid Increment Impact To determine the impact of various minimum bid increases on the Incompletely Specified Combinatorial Auction's performance and establish a rule to apply to our mechanism we conducted experiments using three distinct increments, 5%, 10% and 15%. Appendix C Tables CI -CI 8 give detailed round by round descriptions of the performance measures for each combination of minimum bid increment, stopping rule and computing time. A summary of those results is included in Tables 8.4-8.6 presented below. The individual cells in each of the three tables, one table for each performance measure, represent the outcome for the combination of dependent variables. For example, the first cell of Table 8.4 indicates the revenue for an auction using the activity stopping rule with a 5% minimum bid increment that is allowed to calculate for 5 minutes is 24391.70. 122 8.4. 1 Analysis of Bid Increment Results Our analysis shows that varying the minimum required percentage increase for subsequent bids does have an impact on the performance of the auction. Because a larger increment requires the bids to escalate more quickly, the minimum revenue goal is achieved faster. In fact in our experiments the minimum revenue was achieved in round 5 or 6 with a 5% minimum, round 4 when a minimum 10% increase was required and as early as round 3 with a 15% increment. However, the data in Table 8.4 also shows that when the increment was highest, for example when the minimum increase required was 15%, the maximum overall revenue, in most cases, actually decreased from that achieved with a 10% increment when the auction was allowed to achieve equilibrium Table 8.4 Maximum Revenue Summary Revenue (000) Set1 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 24391.70 24578.50 25264.10 25052.10 24979.40 24818.50 MinRev 23146.70 23487.20 23538.10 23617.70 23377.90 23284.90 Max Round 24387.60 24522.30 24919.10 25143.20 24869.20 25069.40 Set 2 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 24409.40 24334.10 24641.60 24588.60 23593.50 24849.00 MinRev 23498.80 23203.60 23586.20 23498.30 23298.00 23395.00 MaxRound 24287.20 24138.00 24467.90 24370.70 24923.30 24646.20 using the activity stopping rule. We attribute this to the fact that the agents in our study are budget constrained and a high minimum increment forces more bidders out of the auction early because they have reached they reservation price, thus decreasing 123 competition by reducing the bidder pool. The highest overall revenue was obtained for an auction that required a 10% minimum increase and used the activity stopping rule. The greatest optimality was achieved using the highest bid increment. Generally, the auction is able to extract the most surplus from the winning bidders where those that required a 15% bid increment, see Table 8.5 for the details. The conditions generating the highest optimality were the Activity stopping rule with a 15% minimum bid increment that is allowed to calculate for 5 minutes. Table 8.5 Summary of Optimality Results Optimality Set1 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 93.4445 93.6227 95.5487 95.2880 96.2838 95.4169 MinRev 91.0156 92.4770 93.9426 94.0618 93.3870 93.7843 MaxRound 93.4635 93.8447 95.3553 95.4414 95.7468 95.7616 Set 2 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 93.2974 93.3839 94.0773 94.3596 94.7172 94.6865 MinRev 92.3043 91.9155 93.4855 93.3097 92.9948 93.2119 MaxRound 93.9622 92.6800 94.3917 93.9918 94.9689 94.3543 The most efficient auction, or the auction that most effectively assigned units to the bidders that value them the most, was not as consistent in terms of the impact of the minimum bid increment. Table 8.6 indicates that when the auction was allowed to continue for several rounds, as in the case of those using the activity and maximum round (10) stopping rules, the higher percentage increases forced higher efficiency. This could be because by requiring a higher subsequent bid the bidders' true valuations surfaced earlier, thus giving the mechanism the opportunity to assign units to those with the 124 Table 8.6 Summary of Efficiency Results Efficiency Set1 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 94.7058 96.0650 97.4008 96.5083 96.9639 96.7413 MinRev 89.4526 90.8648 91.5521 91.8615 98.0020 91.2745 MaxRound 93.9347 94.8273 95.0520 95.7361 95.7839 97.3613 Set 2 Stopping Rule Percent = 5% Percent = 10% Percent = 15% 5 Min 15 Min 5 Min 15 Min 5 Min 15 Min Activity 96.4054 95.5788 95.2012 95.9128 97.3315 94.9535 MinRev 91 .6006 90.6344 91.5030 91.3863 97.4600 91.8082 MaxRound 93.1122 92.5738 94.0633 94.1339 95.6039 94.3855 highest revealed valuations. However, in the case of the minimum revenue stopping rule the 15% the results were inconsistent between the 10% and 15% increments. Minimum revenue was achieved in round 3 under these parameters and one could speculate that the small number of rounds did not give an opportunity for those bidders with the highest true valuations to become the dominant bidders. Due to the shortness of the auction equilibrium was not achieved. Still another aspect of the auction that is influenced by the minimum increment percentage is the number of rounds needed to achieve equilibrium. Tests showed that on average when the activity stopping rule was employed auctions requiring only 5% increments needed an average of approximately 22 rounds to achieve equilibrium, 10% minimum increase auctions also finished in around 20 rounds while those requiring at least 15% added to previous unsuccessful bids concluded in 19 rounds. Figure 8.1 shows the revenue progression for 15-minute calculation times. Also notice that the higher the 125 required increment the faster the initial revenue gain, however the 10% increment eventually achieves the highest revenue. Revenue Per Round 26000 24000 18000 -iiJJ I i*-f-frj-I-MJJ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Round 5% 10% 15% Figure 8.1 Revenue Attained and Stopping Round For Each Percentage Increment We tested the significance of the impact of the percentage increase on the independent variables, efficiency, optimality and revenue to confirm the conjecture presented above. The results support our claims that the minimum increment required does effect the performance of the auction. The results of the Multivariate Analysis of Variance are presented in Figure 8.2 below. The P-value of .0001 for all tests indicates that the test is significant and we can therefore reject the hypothesis that there is no overall percentage increase effect and conclude that the various levels of minimum bid 126 increments do impact the performance measures of the Incompletely Specified Combinatorial Auction. Manova Test Criteria and F Approximations for the Hypothesis of no Overall PCT Effect H = Type I SS&CP Matrix for PCT E = Error SS&CP Matrix S=2 M=0 N=7 Num Den Statistic Value F DF DF Pr>F Wilks' Lambda 0.08968056 12.4761 6 32 0.0001 Pillai's Trace 1.34202819 1 1 .5580 6 34 0.0001 Hotelling-Lawley Trace 5.33683854 13.3421 6 30 0.0001 Roy's Greatest Root 4.18717260 23.7273 3 17 0.0001 Note: F Statistic for Roy's Greatest Root is an upper bound. Note: F Statistic for Wilk's Lambda is exact. Fig 8.2 Manova: Percentage Effect on Auction Performance Although, evidence suggests that increments of 10% or 15% achieve the best results for our mechanism it is important to acknowledge the psychological impact of the larger bid increases. Within the environment represented in this study the bid amounts correspond to hundreds of thousands, even millions of dollars. The difference between a 5% and 10% minimum increment could be significant. The decision on minimum bid increment should be tempered by a consideration of the scale of the amounts to be tendered. 8.4.2 Summary of Bid Increment Findings The results of our experiments show that modifying the minimum bid increment does impact the efficiency, optimality, realized revenue and length of the auction. A 10% minimum increment coupled with either the activity or maximum round stopping rule 127 yields the best results in terms of revenue and efficiency, while optimality is maximized when using the largest increment. If brevity of the auction is important a larger required increase facilitates early attainment of a predefined revenue goal. 8.5 Analysis of Stopping Rule Effect Four stopping rules were employed in the experiments to determine the performance characteristics of the Incompletely Specified Combinatorial Auction. They are the Activity Rule that resembles the progress of a classic English auction allowing the auction to continue until no further bids are submitted. To imitate an English auction where the seller has a reservation price we designed a stopping rule that combined the Activity rule with a requirement to acquire a predetermined minimum amount of revenue. As it turns out in our setting the minimum revenue was obtained in each of the auctions using the activity rule. Thus the outcome is the same for both categories and we do not duplicate the results. The two other stopping rules terminate the auction when a predetermined revenue goal has been reached or a designated round completed. Evidence from the experiments conducted in this study indicates that the choice of stopping rule does indeed influence the mechanism's performance characteristics. Tables 8.4-8.6, presented in the previous section provide details on the variability of the performance measures between rules. As one might expect, the activity rule realizes the best over all performance measures as it allows the auction to achieve a natural equilibrium. While the minimum revenue rule stops accepting bids even though there may be bidders willing to participate, thus extracting the least surplus and possibly inefficiently allocating units. The Manova results confirm the significance of the effect 128 of the stopping rule. P-values in Figure 8.3 equaling 0.0001 for all tests indicate that we can reject the hypothesis of no overall stopping rule effect and conclude that differing the stopping rule for the auction impacts its performance characteristics. Manova Test Criteria and F Approximations for the Hypothesis of no Overall RULE Effect H = Type I SS&CP Matrix for RULE E = Error SS&CP Matrix S=2 M=0 N=7 Statistic Value F Wilks' Lambda 0.040998950 21 .0065 Pillai's Trace 1.40614602 13.4177 Hotelling-Lawley Trace 12.4846154 31.2115 Roy's Greatest Root 1 1 .53949096 65.3904 Note: F Statistic for Roy's Greatest Root is an upper bound Note: F Statistic for Wilk's Lambda is exact Num Den DF DF Pr>F 6 32 0.0001 6 34 0.0001 6 30 0.0001 3 17 0.0001 Fig 8.3 Manova: Rule Effect on Auction Performance 8.5.1 Trickle Effect While analyzing the data on auctions using the activity rule we noted a phenomenon that we refer to as the Trickle Effect. In a number of the experiments the bidding continued for several rounds yet there was no improvement in revenue (specifics are provided in Appendix C, Tables CI -CI 2). The auction did not terminate since, during each round, there was at least one revised bid submitted. A more detailed look at the data indicated that the majority of revisions were being made to constraints, for example decreasing the number of shows required. Due to the nature of the multi-criteria bid, a bidder could conceivably enter a highly restrictive low bid in the initial rounds and continue making modifications to constraints and or her bid amount for an extended 129 number of rounds. There may be some merit to this approach; the bidder could be attempting to obtain signal information from the recommended bids provided by the mechanism. Further study is warranted into this particular bidding strategy. This type of bidding could prolong the auction beyond a natural stopping point. We did not limit how the constraints were modified by our agents, allowing any agent to modify their constraints to completely eliminate all restrictions given enough rounds. The percentage of winning bidders that ended the auction with a positive lower bound on the number of required shows decreased with the length of the auction. The maximum percentage of constrained bidders in any auction was 24%, with most auctions ending with only 2% to 7% of bidders constrained. This is much less than the 44% of original bidders requiring placement in at least one show. 8.5.2 Summary of Stopping Rule Influence The choice of stopping rule has been shown to impact the performance of the auction mechanism. The activity stopping rule was the overall best choice to achieve the highest revenue, optimality and efficiency. However, this rule may potentially prolong the auction beyond a reasonable number of rounds due to the Trickle Effect, the ability of bidders to make minor modifications to their bid by modifying the different restrictions conveyed by the multi-criteria combinatorial bid. 8.6 Influence of Seller Reservation Price The minimum revenue goal established for our experiments was calculated by summing the discounted list prices for the units available for sale. These discounted list prices are used throughout our solution method in various functions necessary to 130 determine allocations to bidders. Television Network management establish this discount based on anticipated market demand thus it may vary from the 55% employed in our experiments. To determine if varying the rate had a significant impact on our auction performance we tested discount rates of 45, 50, 55, 60 and 65 percent. The experimental parameters consisted of the activity stopping rule, a 10% minimum bid increment and 15 minute calculation time. Table 8.7 presents the results of the experiments. Each column Table 8.7 Analysis of Discount Rate Impact Discount Rate Analysis Stopping Rule = Activity Minutes per Round = 15 Min. Bid Increment = 10% Discount Rate 45% 50% 55% 60% 65% Revenue Goal 28260 25691 23122 20552 17983 Revenue 21308 24848 25052 24933 24890 Round Achieved 16 12 7 7 16 Efficiency 93.51 99.23 96.51 100.00 96.95 Optimality 95.85 96.93 95.29 95.13 95.01 Unsold Inventory 100 13 5 2 2 # Winners 110 121 124 131 121 % Bounded 4% 9% 7% 9% 4% Set 2 Revenue Goal 28260 25691 23122 20552 17983 Revenue 20998 24662 24589 24344 24502 Round Achieved 13 16 12 11 11 Efficiency 96.05 94.95 95.91 95.94 96.13 Optimality 96.45 95.78 94.36 94.15 93.37 Unsold Inventory 107 16 3 2 # Winners 111 124 124 121 127 % Bounded 3% 2% 3% 6% 7% presents data on each of the different discount rates. We have included statistics on the performance measures, revenue, efficiency and optimality as well as other parameters of interest. The data reveals that at the extremes, such as with a discount rate of 45 or 65 percent the realized revenue is less than for the more moderate discount rates. The most 131 efficient allocations are achieved when the discount rate is either 50 or 60%, while optimality steadily decreases as the discount rate increases. Using an Anova we tested the significance of the impact of varying the discount rate on the performance measures. The results presented in Table 8.8 indicate that the Table 8.8 Analysis of Variance for Various Discount Rates Analysis of Variance Procedure Dependent Variable: EFF Source DF Sum of Squares Mean Square F Value Pr>F Model 4 11.10296 2.77574 0.66 0.6478 Error 5 21.143 4.2286 Corrected Total 9 32.24596 R-Square C.V. Root MSE EFF Mean 0.344321 2.130541 2.056356 96.518 Source DF Anova SS Mean Square F Value Pr>F DISCOUNT 4 11.10296 2.77574 0.66 0.6478 Dependent Variable: OPT Source DF Sum of Squares Mean Square F Value Pr>F Model 4 7.41146 1 .852865 2.99 0.1304 Error 5 3.0987 0.61974 Corrected Total 9 10.51016 R-Square C.V. Root MSE OPT Mean 0.70571 0.82665 0.78723567 95.232 Source DF Anova SS Mean Square F Value Pr>F DISCOUNT 4 7.41146 1 .852865 2.99 0.1304 Dependent Variable: REV Source DF Sum of Squares Mean Square F Value Pr>F Model 4 20479917.4 5119979.35 60.77 .0002 Error 5 421265.00 84253.00 Corrected Total 9 20901182.40 R-Square C.V. Root MSE REV Mean .979845 1.208797 290.2636732 24012.60 Source DF Anova SS Mean Square F Value Pr>F DISCOUNT 4 20479917.4 5119979.35 60.77 .0002 discount rate does make a significant impact on revenue and to a lesser degree optimality, but we could not conclude that there is a difference in efficiency. The tests indicate that the choice of discount rate is important and should be based on the ultimate goal of the 132 seller. If the seller's goal is to have the most optimal allocation the evidence suggests that lower discount rate should be applied. However, to obtain the greatest revenue a moderate discount is the obvious choice. Special consideration should be given if the closing rule of choice is the attainment of a minimum revenue goal. In our experiments, the minimum revenue goal was determined as a sum of the discounted list for the units available, a larger discount rate will promote the auction reaching the stated goal. If the discount rate is too low an auction using the Minimum Revenue stopping rule may never terminate. Notice in Table 8.7 only those auctions with at discount rate of 55% or greater were able to achieve their revenue goal. 8.7 Heuristic Performance: Changing Computing Time 8.7.1 Standard Heuristic Performance The final controlled variable in our experiments is the calculation time given our heuristic to determine an allocation. We experimented with four periods, 5, 15, 30 and 60 minutes. The preliminary results from tests using the activity stopping rule indicated that there was no significant improvement from the longer, 30 and 60 minute, runs. Therefore, in the interest of time we tested the remaining closing rules using only 5 and 15 minute calculation times. Refer back to Tables 8.4-8.6 for a summary of the impact on the performance measures from altering the calculation time. We report the results of the 30 and 60 minute calculation times in Appendix C, Tables C3, C4, C7, C8, CI 1 and C12. 133 It was anticipated that the longer the mechanism was given to determine an allocation the better that allocation. However, at first glance it would appear that on occasion the additional calculation time had a negative effect on the performance parameters. This result seemed counterintuitive and after further investigation we were able to attribute the occasional reduced performance to a phenomenon commonly found in nature and used in simulated annealing search methods. Annealing is a process in which physical substances are melted and then gradually cooled until some solid state is reached. The process is very sensitive to the rate at which it is cooled, a rate that is too rapid or slow will negatively affect the quality of the final product. Giving our mechanism a longer calculation time allows it to possibly find allocations for more bidders thus they become winners in that round and are not required to modify their bids to be considered in the next round. Although, the auction performs better in initial rounds, improvement in later rounds is reduced because the broader early allocations reduce the ability of the mechanism to extract buyer surplus. The Manova results presented in Figure 8.4 indicate that the time given to the mechanism to determine an allocation is not a significant factor influencing performance characteristics. All four significance tests give an F value of .2503 and a P-value of 0.0963 which are not significant therefore we can not reject the null hypothesis that calculation time has no overall effect on the independent variables efficiency, optimality and revenue. When time is coupled with percentage we see that there is a significant impact on the auction's performance. Table 8.5 shows that all tests are significant at the 95% level 134 Manova Test Criteria and F Approximations for the Hypothesis of no Overall TIME Effect H = Type I SS&CP Matrix for TIME E = Error SS&CP Matrix S=1 M=0.5 N=7 Statistic Value F Wilks' Lambda 0.68065413 2.5023 Pillai's Trace 0.31934587 2.5023 Hotelling-Lawley Trace 0.46917495 2.5023 Roy's Greatest Root 0.46917495 2.5023 Num Den DF DF Pr>F 3 16 0.0963 3 16 0.0963 3 16 0.0963 3 16 0.0963 Figure 8.4 Manova Time Effect on Auction Performance and we can reject the hypotheses that there is no overall effect of the combination of percentage and time on the performance of our auction. Similar results are obtainedfrom the interaction of time with the other independent variables indicating a need to consider the amount of time given the mechanism to determine an allocation. Manova Test Criteria and F Approximations for the Hypothesis of no Overall PCTTIME Effec H = Type I SS&CP Matrix for PCT*TIME E = Error SS&CP Matrix S=2 M=0 N=7 Num Den Statistic Value F DF DF Pr>F Wilks' Lambda 0.40757782 3.0206 6 32 0.0187 Pillai's Trace 0.59442881 2.3965 6 34 0.0487 Hotelling-Lawley Trace 1 .44859584 3.6215 6 30 0.0080 Roy's Greatest Root 1 .4451 891 5 8.1894 3 17 0.0014 Note: F Statistic for Roy's Greatest Root s an upper bound Note: F Statistic for Wilk's Lambda is exact Figure 8.5 Manova Percent*Time Effect on Auction Performance 135 8.7.2 FastMode Heuristic Performance The solution heuristic engaged by the auction to determine allocations to bidders incorporates a variety of techniques that are described in detail in Chapter 5. Two of the approaches taken are to solve an aggregate subproblem exactly using dynamic programming or employ a heuristic based on linear programming relaxations referred to as FastAP. FastAP is used during the breadth first search phase of our branch and bound procedure and for 40% of the time spent in the depth first search, the remaining solutions at each branch are determined using dynamic programming. To gain a better understanding of the contribution of FastAP on the heuristic's performance we modified the solution methodology to utilize only FastAP. That is, no exact dynamic programming methods were employed. An Anova analysis comparing the results of the modified heuristic with those obtained from the original formulation indicates that there is no significant difference between the two methodologies. The low F- Values and high probabilities shown in Table 8.9 for each of the independent variables support the conclusion that there are no differences between the performance measures for the two heuristics. 8.8 Heuristic Performance Versus Integer Program The solution to the integer problem presented in Chapter 3 acts as a benchmark against which we compare our heuristic's performance. To facilitate achieving a solution using a commercial integer programming solver, CPLEX 6.5, the problem had to be 136 Table 8.9 ANOVA Comparing FastAP to Original Heuristic Analysis of Variance Procedure Dependent Variable: EFF Source DF Sum of Squares Mean Square F Value Pr>F Model 2 4.70523180 2.35261590 0.40 0.6706 Error 51 297.87654976 5.84071666 Corrected Total 53 302.58178156 R-Square C.V. Root MSE EFF Mean .015550 2.564011 241675747 94.25691852 Source DF Anova SS Mean Square F Value Pr>F GROUP 2 4.70523180 2.35261590 0.40 0.6706 Dependent Variable: OPT Source DF Sum of Squares Mean Square F Value Pr>F Model 2 6.35720916 3.17860458 2.03 0.1416 Error 51 79.80139247 1.56473319 Corrected Total 53 86.15860163 R-Square C.V. Root MSE OPT Mean 0.073785 1 .328598 1 .25089296 94.15135741 Source DF Anova SS Mean Square F Value Pr>F GROUP 2 6.35720916 3.17860458 2.03 0.1416 Dependent Variable: REV Source DF Sum of Squares Mean Square F Value Pr>F Model 2 1366473.73778 683236.86889 1.46 0.2420 Error 51 23879297.42221 468221.51808 Corrected Total 53 25245771.15999 R-Square C.V. Root MSE REV Mean 0.054127 2.814713 684.26713941 24310.36667 Source DF Anova SS Mean Square F Value Pr>F GROUP 2 1366473.73778 683236.86889 1.46 0.2420 scaled down considerably from the size represented in the previous experiments. The reduced problem consists of 30 bidders vying for 104 units distributed across 3 shows. We chose to compare the results from one round of activity. The integer problem was generated using the parameters of the third round of bidding from an auction using 5 minutes of calculation time, 10% minimum bid increments and the activity stopping rule. The number of active bidders in round 3 had been reduced to 12 from the original 30. With the above parameters the Incompletely Specified Combinatorial Auction was able to 137 complete the entire auction consisting of 5 rounds in a total of 15 minutes. The duration of the auction includes time used to generate agents, calculate upper bounds, output MPS formatted version of the problem for CPLEX at each auction round, output all solution files for possible CPLEX usage as well as determine the appropriate allocation of units in each of the 5 rounds. The ISCA found a solution that produced revenue of $1728.31 for the seller with a gap of 0.038198%. An integer problem representing a single round, round 3, of the auction was entered into CPLEX. After over 43 hours the program was unable obtain a single feasible integer solution. We then seeded CPLEX with the solution obtained by our mechanism for round three. CPLEX confirmed that the solution was indeed feasible and after 24 hours was unable to improve on the solution. The initial gap reported by CPLEX for this solution was 43.74%. 8.9 Summary This chapter presented the results of experiments testing the performance of the Incompletely Specified Combinatorial Auction. We have shown that the mechanism is efficient, the efficiency range for all experiments was 86.67 to 100%. The mechanism also scored well with respect to optimality with a minimum optimality of 86.67%, recorded for an auction consisting entirely of inflexible bidders or those not willing to adjust their constraints, and a maximum of 100% optimality. The experiments proved that utilizing the Incompletely Specified Combinatorial Auction a seller can not only achieve a desired revenue but could conceivably exceed the desired goal when the activity or maximum round stopping rules are employed. Our analysis also provided 138 evidence that the choice of minimum bid increment and stopping rule affect the performance of the mechanism measured in terms of efficiency, optimality, realized revenue and auction length in terms of the number of rounds required to achieve an equilibrium stopping point. A combination of the activity stopping rule and a 10% minimum bid increment posted the best results. Varying the amount of time, between 5 and 60 minutes, that the heuristic is given to determine an allocation impacted the performance of the mechanism when couples with the other independent variables. Use of the heuristic solution methodology allows us to find a solution to a complex combinatorial optimization problem that is too large to be accommodated by the current state of the art integer program solver, CPLEX 6.5. CHAPTER 9 CONCLUSION 9.1 Introduction This chapter contains a discussion of the conclusions garnered from this study as well as proposed directions for future research. We originally posed the question of whether or not an auction mechanism could be designed to accommodate the complexities of a negotiated environment, namely the need for non-specific multi- dimensional bids to guide rather than dictate allocations. In previous chapters we have explored the design issues and reported the results of simulated testing of the prototype mechanism in Chapter 8. In Section 9.2 we discuss these results and draw conclusions about the efficacy of the mechanism. Additionally, limitations of the study are presented to qualify the outcomes in Section 9.3. We conclude the chapter by offering directions for future research into this type of mechanism, including model revisions and experimentation using human subjects. 9.2 Project Overview This research was motivated by the need for a new auction mechanism that can accommodate buying needs not being fulfilled by current designs. We identified the characteristics missing from current auctions mechanisms that were necessary for an auction to replace or enhance a negotiated environment and made provisions to 139 140 incorporate them into our mechanism. A representative negotiated environment was identified, that of television network sales, and described. We described a simple bid structure and modeled an allocation procedure by an integer program. Our auction mechanism, dubbed the Incompletely Specified Combinatorial Auction, consists of multiple rounds of bidding and allocation. Bid modification rules, stopping rules and other features of our auction were also developed. A heuristic was designed to facilitate attaining a satisficing solution to the complex combinatorial optimization problem that is needed to determine product allocations and winner selection. A simulated auction environment was chosen to test the performance characteristics of our auction mechanism. From data supplied by a representative television network we were able to extract patterns that were used to determine product characteristics such as inventory levels and list prices. We were also able to model buying patterns, including the number of units desired, demographic requirements and associated reservation prices. Using this information we generated artificial agents to act as participants in our simulated auction. Experiments were conducted to discover how well the mechanism performed in terms of efficiency, optimality and realized revenue. 9.3 Conclusions This research has presented evidence that an auction mechanism can indeed be developed to accommodate the special needs of a negotiated environment. The mechanism modifies a combinatorial auction to accept bids that are incompletely specified in that they provide guidelines to direct rather than dictate the allocation of goods. The mechanism also gives the bidders the ability to impose restrictions on the 141 allocation through specifications of the multi-criteria package bid. Experiments establish the mechanism as efficient, optimal and revenue maximizing. Analysis of the heuristic developed to accommodate the large problem dimensions indicates that the solutions are optimal or near optimal. As important, the time it takes the heuristic to reach a satisficing solution is minimal and well within the limits imposed by the real-world environment. 9.4 Limitations This research presents a preliminary investigation into a new auction mechanism. The nature of the investigation has important limitations. First, in order to gain insight into the efficacy of the mechanism we have limited our experiments to simulation with artificial agents. We acknowledge the fact that all nuances inherent to human behavior cannot be adequately programmed into agents. However, it should be noted that artificial agents are being used extensively to assist bidders with various online auctions and their hyper-rational behavior has been favorably compared to Economist's game theoretic model of participant interaction (Varian, 1995). In this study we do not address various aspects of auction theory that should be reviewed before this mechanism is deployed. These issues include buyer trust of the mechanism, potential for bidder collaboration, and other game theoretic characteristics such as more sophisticated bidding strategies. Our model accommodates the sale of a week of airtime and we make the simplifying assumption that buyers' campaigns are continuous and thus the purchase pattern will repeat from week to week throughout the year. In reality, buyers will want to "flight their campaigns," or place advertising only during specific weeks or days of the year. In order to accommodate flighting our mechanism will need to be expanded to 52 142 weeks and accept buyer specified airdates. Extending our simple bid structure to 52 weeks will be challenging. Finally, our mechanism is designed to assist or replace a negotiated environment, yet we have not attempted in this study to analyze the business process changes that would be necessary to facilitate the transition. We anticipate, especially in the television industry, that conversion from negotiation to a business-to-business electronic auction may be met with a great deal of resistance. 9.5 Direction for Future Research As indicated earlier, this is a preliminary study of our mechanism and as such there is a great deal yet to discover about the mechanism's use as well as new design issues to explore. This section will propose a variety of related subjects that have yet to be considered regarding the mechanism presented in this study. 9.5.1 Expansion of the Mechanism The mechanism was designed to allocate a week's worth of airtime with the assumption the buyers campaigns are continuous throughout the year and the allocation would be consistent across all 52 weeks. This simplifying assumption fails on two accounts. First, continuous campaigns that last an entire year are rare. Buyers are more likely to want their advertising placed in specific weeks that correspond to dates of other media purchases such as radio and magazine. These active weeks are routinely followed by periods of inactivity or a reduction in their exposure requirements. Additionally, by assuming that each week is a duplicate of the generic week that is auctioned we do not allow for variations in shows throughout the year. Networks routinely schedule special 143 programming such as sporting events or mini-series whose demographic exposures and costs are not necessarily equivalent to the shows they replace. A classic example would be the Superbowl which commands premium prices. Accommodating these nuances further supports the need to investigate how to expand the auction to encompass 52 weeks of inventory. The current design does not allow the bidder to reject an allocation. It can be argued that since the units assigned are not necessarily completely specified by the buyer, due to the inexact nature of the bid, that the buyer should have the option to reject an individual allocation. Currently, the only recourse the bidder has is to submit a bid with a higher bid amount or reduced restrictions and hope for a better allocation in subsequent rounds. Expanding the design to a double-sided auction would provide the necessary bid- offer format to facilitate the bidder's rejection of an unacceptable allocation. Although the mechanism was designed to meet the needs of a particular industry, namely the television industry, it can be generalized to other areas. Not all industries are as protective of their pricing and inventory information, therefore an obvious model modification would be to design an open format that provides signal information to buyers. Generalizing the ISCA concepts to other environments would require identifying the decision variables associated with the purchase of products. An example could be the purchase of component parts for a manufacturing process. These type purchase decisions are often dependent on delivery options, financial terms and conditions as well as product characteristics and mixes. The bidder would need to specify the various parts, the number desired in total, a specific delivery date and financial considerations such as 144 interest rate. Flexibility could be incorporated into the bid by establishing bounds on delivery date and or product requirements. These constraints would then be modeled in the allocation engine of the auction mechanism. Identifying problem domains where ISCA might be applicable is an area for future research. 9.5.2 Empirical Investigations One of the limitations of this research is the use of simulation as the sole means of testing the mechanism's performance. An empirical study using human subjects would supplement our understanding of the effectiveness of the auction mechanism. Several issues, such as human computer interaction, trust, bidding strategies and collusion, can be explored empirically. Establishing bidder trust in a semi-sealed auction has, to our knowledge, not been investigated yet could be a defining issue on the mechanism's acceptance. The fact that the mechanism suggests bids to inactive buyers implies that the mechanism must be considered trustworthy if bidders are to act on the information provided. Another question about the semi-sealed format is its impact on collusion. Sealed-bid auctions are less susceptible to collusion than are open auctions because actual bids are not displayed allowing bidders to deviate from collusive pricing agreements without fear of detection (Mead, 1967; Milgrom, 1987b). It would appear that the same results would hold for the semi-sealed format, human studies could be designed to investigate this phenomenon. Expanding the bid criteria exacerbates the complexity associated with combinatorial auctions. Investigating the interface design and display information is 145 another important aspect of the mechanism design that would also benefit from human subject studies. 9.5.3 Game Theory Studies Another extension of this research would be to explore the impact of various bidding strategies. Questions such as the most advantageous time for a bidder to enter the auction and whether or not to bid one's true valuation upon entry have yet to be answered. This study briefly looked at various bidder types and attempted to model their expected behavior, however further analysis into the distribution of these types is warranted. 9.6 Summary We have shown that there is indeed an auction mechanism that can be designed to adapt to the needs inherent to the complex environment of negotiations. We have summarized our conclusions concerning the performance characteristic of such a mechanism. This chapter presented various limitations to the research that suggest avenues for further research. The Incompletely Specified Combinatorial Auction is an auction model in its infancy, thus the mechanism poses great opportunities for further development and refinement. APPENDIX A DISTRIBUTION OF DEMOGRAPHIC REQUIRMENTS BY CATEGORY Std. Dev = 9067.70 Mean = 9607 N = 209.00 % %, % % % % \ \ % v % °% % °% °% % °o °o °o °o °o °o °o °o "o "o ^i> ^o u o Women 18-49 Wififfi iiiTi i Tiiiiiiiiiiii im iiiiiii i iiiiiiii i iii" Std. Dev= 10684.18 Mean= 11286 N = 209.00 % % <?* '<?? % % % % % % \ \ % % % o °0 % % % % % % % % % % % % \ Women 25-54 146 147 Men 18-49 Std. Dev = 5789.46 Mean = 6173 N = 209.00 Std. Dev = 671 1.52 Mean = 7218 N = 209.00 % \ \ % \ % \ % % \ \ \ % % ° ° °o °o °o °o °o °o °o u o a o u o u o Men 25-54 148 20- 10- MPH \) fc|jLM-"r Std. Dev= 14823.72 Mean= 15779 N ■ 209.00 ?n * 'y -?, <?7 *> $r 9, >, Q? 3 7 7 7 7 7 ^ % °o °o °o °o °o °o °o <h* °o~ r o~ 7 o„ fa ° °o °o °o °o u o u o °o u o u o u o Q u o u O Q Adults 18-49 Std. Dev= 17353.35 Mean = 18503 N = 209.00 7 n 7 7 A, vj> r, & 7 e, >, <9 7 9, ? r, £> a, / v °o n 7 o n 7 o n 7 o n 'o n 7 o n 7 o n 7 o n 7 o n 7 o n % %^ D % % o o o o o o o o o o o o o o o 'O u O w O w O V Adults 25-54 APPENDIX B REGRESSION OF PRICE AND DEMOGRAPHICS Demographic 1 Women 18-49 12- te. a. z ■:■& . .ft.-' - . ■ ■ -. ■ LNDEM01 Regression Women 1 8-49 and Price Model Summary Model R R Square Adjusted R Square Std. Error of the Estimate 1 .914 .836 .835 .3204 a Predictors: (Constant), LNDEM01 AN OVA Model Sum of Squares df Mean Square F Sig. 1 Regression 108.425 1 108.425 1056.437 .000 Residual 21.245 207 .103 Total 129.670 208 a Predictors: (Constant), LNDEM01 b Dependent Variable: LNPRICE Coefficients Model Unstandardized Coefficients Standardized Coefficients t Sig. B Std. Error Beta 1 (Constant) 4.258 .243 17.505 .000 LNDEM01 .891 .027 .914 32.503 .000 a Dependent Variable: LNPRICE 149 150 Demographic 2 Women 25-54 15 LU O or 0_ 7 8 9 LNDEM02 Regression Women 25-54 and Price Model Summary 10 Model R .915 R Square .837 Adjusted R Square .837 Std. Error of the Estimate .3192 a Predictors: (Constant), LNDEM02 AN OVA Model Sum of Squares df Mean Square F Sig. 1 Regression 108.575 1 108.575 1065.432 .000 Residual 21.095 207 .102 Total 129.670 208 a Predi ;tors: (Constant ), LNDEMO 2 b Dependent Variable: LNPRICE Coefficients Model Unstandardized Coefficients Standardized Coefficients t Sig. B Std. Error Beta 1 (Constant) 4.049 .249 16.285 .000 LNDEM02 .898 .028 .915 32.641 .000 a Dependent Variable: LNPRICE Demographic 3 Men 18-49 151 Demographic 3 Men 1 8-49 15 LU O a: Q- LNDEM03 Regression Men 1 8-49 and Price Model Summary Model R .914 R Square .835 Adjusted R Square .834 Std. Error of the Estimate .3215 a Predictors: (Constant), LNDEM03 AN OVA Model Sum of Squares df Mean Square F Sig. 1 Regression| 108.278 1 108.278 1047.752 .000 Residual 21.392 207 .103 Total] 129.670 208 a Predictors: (Constant), LNDEM03 b Dependent Variable: LNPRICE Coefficients Model Unstandardized Coefficients Standardized Coefficients t Sig. B Std. Error Beta 1 (Constant) 4.629 .233 19.883 .000 LNDEM03 .894 .028 .914 32.369 .000 a Dependent Variable: LNPRICE 152 Demographic 4 Men 25-54 15 LU O or o. 14- 13 12 11. 10 o # B *S n „ n -si □ B 10 LNDEM04 Regression Men 25-54 and Price Model Summary Model R R Square Adjusted R Square Std. Error of the Estimate 1 .913 .834 .833 .3227 a Predictors: (Constant), LNDEM04 ANOVA a Predictors: (Constant), LNDEM04 b Dependent Variable: LNPRICE 11 | Sum of Model | Squares df Mean Square F Sig. 1 Regressionl 108.115 1 108.115 1038.267 .000 Residual 21.555 207 .104 Total) 129.670 208 Coefficients Model Unstandardized Coefficients Standardized Coefficients t Sig. B Std. Error Beta 1 (Constant) 4.414 .241 18.353 .000 LNDEM04 .902 .028 .913 32.222 .000 a Dependent Variable: LNPRICE 153 Demographic 5 Adults 1 8-49 15- LU O en 0_ 14 13 12- 11 10 10 11 12 LNDEM05 Regression Adults 18-49 Model Summary Model R R Square Adjusted R Square Std. Error of the Estimate 1 .919 .844 .843 .3127 a Predictors: (Constant), LNDEM05 AN OVA Model Regression Residual Total Sum of Squares 109.425 20.245 129.670 df 207 208 Mean Square 109.425 1118.842 9.780E-02 Sig. .000 a Predictors: (Constant), LNDEM05 b Dependent Variable: LNPRICE Coefficients Unstandardized Coefficients Standardized Coefficients t Sig. Model B Std. Error Beta 1 (Constant) 3.709 .253 14.674 .000 LNDEM05 .902 .027 .919 33.449 .000 a Dependent Variable: LNPRICE 154 Demographic 6 Adults 25-54 15- LU O or 14- 13 12 11 - 10 a a a d D a % □ "p fa ^^fl Eb_jfi a o D B B D 10 11 12 LNDEM06 Regression Adults 25-54 Model Summary Model R .920 R Square .846 Adjusted R Square .845 Std. Error of the Estimate .3108 a Predictors: (Constant), LNDEM06 ANOVA Model Sum of Squares df Mean Square F Sig. 1 Regression 109.675 1 109.675 1135.407 .000 Residual 19.995 207 9.660E-02 Total 129.670 208 a Predictors: (Constant), LNDEM06 b Dependent Variable: LNPRICE Coefficients Model Unstandardized Coefficients Standardized Coefficients t Sig. B Std. Error Beta 1 (Constant) 3.468 .258 13.444 .000 LNDEM06 .912 .027 .920 33.696 .000 a Dependent Variable: LNPRICE APPENDIX C EXPERIMENTAL RESULTS Table CI Activity Rule - 5% Increment - 5 & 15 Minute - Set 1 Experiment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 5% Activity 15 Generic 5% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 278 19558.90 88.1961 2 278 20479.10 88.8792 3 254 20474.80 89.1492 3 253 21575.60 89.3750 4 240 21527.20 90.1414 4 237 22217.10 90.1766 ***C*"** 224 23146.70 91.0156 5 220 22881.80 90.6210 6 203 23506.00 91.5384 ***£*** 196 23487.20 92.4770 7 195 23841 .30 93.1144 7 186 23815.00 92.9266 8 168 23890.60 93.6205 8 169 24023.90 93.6125 9 160 24387.60 93.4635 9 148 24154.20 94.4255 10 152 24387.60 93.4635 10 145 24522.30 93.8447 11 146 24387.60 93.4635 11 142 24522.30 93.8447 12 141 24387.60 93.4635 12 137 24522.30 93.8447 13 138 24391 .70 93.4445 13 135 24522.30 93.8447 14 136 24391.70 93.4445 14 134 24522.30 93.8447 15 143 24391.70 93.4445 15 143 24578.50 93.6227 16 140 24391.70 93.4445 16 141 24578.50 93.6227 17 139 24391.70 93.4445 17 141 24578.50 93.6227 18 134 24391.70 93.4445 18 137 24578.50 93.6227 19 133 24391.70 93.4445 19 135 24578.50 93.6227 20 132 24391 .70 93.4445 20 134 24578.50 93.6227 21 133 24578.50 93.6227 Efficiency: 94.7058 Gap:| 11.7144 Efficiency: 96.065 Gap 4.8607 155 156 Table C2 Activity Rule - 5% Increment - 5 & 1 5 Minute - Set 2 Experiment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 5% Activity 15 Generic 5% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 269 20857.30 89.7142 2 269 20937.30 89.7495 3 247 22077.60 90.9819 3 249 22837.90 90.9757 4 235 22835.10 91.2939 4 232 22837.90 90.9757 ***c*** 217 23222.40 92.1958 5 206 22930.70 91 .0544 6 190 23457.80 92.1380 ***C*** 186 23203.60 91.9155 7 176 23938.30 92.8715 7 176 23535.60 92.3030 8 159 23938.30 92.8715 8 153 23659.60 93.5633 9 144 23973.00 93.0584 9 144 23979.70 92.9056 10 145 24153.10 93.1164 10 144 24138.00 92.6800 11 138 24153.10 93.1164 11 141 24138.00 92.6800 12 136 24155.70 93.1354 12 137 24138.00 92.6800 13 134 24155.70 93.1354 13 135 24138.00 92.6800 14 134 24155.70 93.1354 14 135 24138.00 92.6800 15 141 24155.70 93.1354 15 142 24138.00 92.6800 16 140 24155.70 93.1354 16 139 24194.80 92.9077 17 136 24409.40 93.2974 17 136 24320.80 93.0409 18 134 24409.40 93.2974 18 135 24320.80 93.0409 19 133 24409.40 93.2974 19 133 24320.80 93.0409 20 132 24409.40 93.2974 20 129 24320.80 93.0409 21 131 24409.40 93.2974 21 129 24334.10 93.3839 22 131 24409.40 93.2974 22 129 24334.10 93.3839 23 130 2440940 93.2974 23 129 24334.1 C 93.3839 24 128 24334.1 C 93.3839 25 128 24334. 1C 93.3839 26 127 24334.1 C 93.3839 Efficiency: 96.4054 Gap 5.4141 Efficiency: 95.5788 Gap 5.2129 157 Table C3 Activity Rule - 5% Increment - 30 & 60 Minute - Set 1 ExDeriment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 5% Activity 60 Generic 5% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18921.50 86.7711 1 255 18921.50 86.7711 2 278 20450.30 88.7718 2 278 20450.30 88.7718 3 256 20944.60 89.9528 3 256 20944.60 89.9528 4 234 22720.60 90.5945 4 234 22816.30 90.8370 5 217 23041.10 91.5958 5 216 23112.00 91.6281 ***£>*** 187 23361.50 92.3777 ***6*" 187 23315.90 92.2291 7 183 23816.30 93.5409 7 183 23759.80 93.8397 8 169 23816.30 93.5409 8 166 23961.10 93.4099 9 154 24175.20 93.7210 9 154 23972.40 93.4551 10 145 24279.50 93.7379 10 147 24165.60 93.4205 11 141 24279.50 93.7379 11 141 24184.10 93.6485 12 137 24279.50 93.7379 12 137 24184.10 93.6485 13 134 24279.50 93.7379 13 135 24184.10 93.6485 14 133 24279.50 93.7379 14 135 24283.00 94.0178 15 142 24279.50 93.7379 15 144 24283.00 94.0178 16 138 24279.50 93.7379 16 141 24341 .90 94.1552 17 136 24279.50 93.7379 17 138 24341.90 94.1552 18 134 24279.50 93.7379 18 136 24341.90 94.1552 19 132 24279.50 93.7379 19 134 24392.30 94.8055 20 131 24279.50 93.7379 20 130 24473.50 94.6952 21 130 24473.50 94.6952 22 126 24473.50 94.6952 23 125 24473.50 94.6952 Efficiency: 94.879 Gap: 7.5142 Efficiency: 98.6405 Gap: 1.8511 158 Table C4 Activity Rule - 5% Increment - 30 & 60 Minute - Set 2 Experiment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 5% Activity 60 Generic 5% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19204.50 88.1924 1 248 19204.50 88.1924 2 269 20937.30 89.7495 2 269 20937.30 89.7495 3 249 22837.90 90.9757 3 249 22837.90 90.9757 4 232 23106.70 90.8965 4 232 23106.70 90.8965 ***c*** 217 23384.20 92.5969 ***c*** 217 23386.40 92.5065 6 197 23640.50 92.5408 6 196 23540.10 92.8275 7 175 23853.80 93.0955 7 176 23918.50 92.4601 8 162 24117.60 92.8127 8 155 24145.60 92.7926 9 148 24118.50 93.4416 9 147 24145.60 92.7926 10 147 24192.50 93.2168 10 143 24356.90 92.5507 11 144 24214.90 93.3793 11 138 24356.90 92.5507 12 142 24306.60 93.5021 12 134 24356.90 92.5507 13 142 24486.60 93.9484 13 134 24356.90 92.5507 14 141 24621.10 93.8396 14 134 24356.90 92.5507 15 146 24633.8C 93.7369 15 143 24356.90 92.5507 16 143 24656.8C 93.6082 16 139 24356.90 92.5507 17 138 24565.8C 93.6082 17 135 24356.90 92.5507 18 136 24565.8C 93.6082 18 133 24356.90 92.5507 19 134 24565.8C I 93.6082 19 132 24381.70 92.9378 20 133 24565.8C I 93.6082 20 129 24381 .70 92.9378 Efficiency: 95.2037 Gap 7.1454 Efficiency: 94.0463 Gap 7.7778 159 Table C5 Activity Rule - 10% Increment - 5 & 15 Minute - Set 1 Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 10% Activity 15 Generic 10% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 272 20931 .20 89.4097 2 272 20931.20 89.4097 3 246 23097.20 92.5025 3 246 23097.20 92.5025 ■k**A*** 212 23539.20 94.2181 ***A**ir 212 23636.30 93.7651 5 185 23781.80 94.0913 5 184 24207.30 94.5288 6 162 24802.40 95.7664 6 156 24705.70 95.2158 7 156 24914.30 95.1333 7 150 25052.10 95.2880 8 149 24962.90 95.4638 8 145 25052.10 95.2880 9 141 24962.90 95.4638 9 138 25052.10 95.2880 10 143 25004.70 95.2536 10 137 25052.10 95.2880 11 139 25004.70 95.2536 11 136 25052.10 95.2880 12 137 25090.90 95.4766 12 133 25052.10 95.2880 13 136 25170.40 95.5566 13 133 25052.10 95.2880 14 136 25170.40 95.5566 14 132 25052.10 95.2880 15 145 25170.40 95.5566 15 140 25052.10 95.2880 16 139 25170.40 95.5566 16 136 25052.10 95.2880 17 138 25196.70 95.5597 17 135 25052.10 95.2880 18 136 25264.10 95.5487 18 133 25052.10 95.2880 19 135 25264.10 95.5487 19 131 25052.10 95.2880 20 135 25264.10 95.5487 20 131 25052.10 95.2880 21 134 25264.10 95.5487 21 130 25052.10 95.2880 22 134 25264.10 95.5487 23 134 25264.10 95.5487 24 133 25264.10 95.5487 Efficiency: 97.4008 Gap 5.8607 Efficiency: 96.5083 Gap 7.2824J 160 Table C6 Activity Rule - 10% Increment - 5 & 15 Minute - Set 2 Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 10% Activity 15 Generic 10% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 260 21074.80 90.4370 2 261 21891.30 90.8288 3 234 22886.20 92.4315 3 231 22686.70 91.5543 ***/*** 203 23532.20 93.2763 ***A*** 202 23498.30 93.3097 5 176 23855.70 93.7636 5 183 23986.90 93.4585 6 155 24152.30 93.9759 6 153 24027.10 93.8715 7 152 24372.00 93.7524 7 150 24324.80 93.9720 8 142 24372.00 93.7524 8 141 24324.80 93.9720 9 140 24372.00 93.7524 9 136 24324.80 93.9720 10 141 24372.00 93.7524 10 140 24370.70 93.9918 11 137 24461.60 94.0362 11 138 24421.20 94.3690 12 135 24461.60 94.0362 12 136 24588.60 94.3596 13 135 24641 .60 94.0773 13 133 24588.60 94.3596 14 135 24641.60 94.0773 14 131 24588.60 94.3596 15 141 24641.60 94.0773 15 139 24588.60 94.3596 16 139 24641.60 94.0773 16 138 24588.60 94.3596 17 135 24641.60 94.0773 17 136 24588.60 94.3596 18 133 24641 .60 94.0773 18 132 24588.60 94.3596 19 133 24641.60 94.0773 19 131 24588.60 94.3596 20 132 24641.60 94.0773 20 131 24588.60 94.3596 21 130 24588.60 94.3596 Efficiency: 95.2012 Gap 8.8182 Efficiency: 95.9128 Gap 11.1256 161 Table C7 Activity Rule - 1 0% Increment - 30 & 60 Minute - Set 1 Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 10% Activity 60 Generic 10% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18921.50 86.7711 1 255 18921.50 86.7711 2 273 20866.00 89.8837 2 273 20866.00 89.8837 3 251 22671.10 91.4325 3 251 23013.40 92.2690 ***A*** 227 23693.90 93.7658 ***A*** 218 23776.50 94.2215 5 195 24300.50 94.4896 5 182 24244.90 94.6758 6 157 24479.90 95.3027 6 155 24616.90 95.3836 7 154 24982.90 95.2842 7 150 24922.70 95.4581 8 142 24982.90 95.2842 8 141 25057.20 95.5444 9 135 24982.90 95.2842 9 133 25057.20 95.5444 10 135 24982.90 95.2842 10 134 25057.20 95.5444 11 135 24982.90 95.2842 11 133 25057.20 95.5444 12 131 24982.90 95.2842 12 130 25057.20 95.5444 13 130 25047.50 95.5340 13 129 25057.20 95.5444 14 129 25047.50 95.5340 14 128 25069.00 95.6060 15 138 25047.50 95.5340 15 137 25069.00 95.6060 16 134 25047.50 95.5340 16 134 25069.00 95.6060 17 132 25047.50 95.5340 17 131 25069.00 95.6060 18 128 25047.5C 95.5340 18 127 25069.00 95.6060 19 127 25047.50 95.5340 19 126 25069.00 95.6060 Efficiency: 96.0483 Gap 5.6402 Efficiency: 96.7611 Gap 9.6151 162 Table C8 Activity Rule - 1 0% Increment - 30 & 60 Minute - Set 2 Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 10% Activity 60 Generic 10% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19204.50 88.1924 1 248 19204.50 88.1924 2 261 21891.30 90.8288 2 261 21891.30 90.8288 3 231 22686.70 91.5543 3 231 22686.70 91.5543 ■k**A*** 202 23498.30 93.3097 ***A*** 202 23432.90 92.8737 5 183 23836.10 93.2136 5 182 23833.20 93.1977 6 154 24124.30 94.1025 6 159 24205.40 94.0264 7 149 24282.50 93.9223 7 150 24315.10 93.7581 8 142 24342.90 93.6358 8 143 24321.50 94.2648 9 139 24354.20 94.1615 9 138 24451 .00 94.1833 10 141 24465.70 94.1486 10 140 24451 .00 94.1833 11 139 24623.70 94.2581 11 138 24451 .00 94.1833 12 139 24623.70 94.2581 12 135 24473.90 94.4432 13 135 24623.70 94.2581 13 135 24473.90 94.4432 14 134 24650.80 94.3572 14 135 24495.60 94.9036 15 143 24650.80 94.3572 15 142 24742.50 94.6947 16 141 24650.80 94.3572 16 140 24742.50 94.6947 17 136 24650.80 94.3572 17 139 24742.50 94.6947 18 134 24650.80 94.3572 18 136 24742.50 94.6947 19 132 24650.80 94.3572 19 133 24742.5C 94.6947 20 132 24650.80 94.3572 20 133 24742.50 94.6947 21 131 24650.80 94.3572 21 132 24742.5C 94.6947 Efficiency: 94.7756 Gap 8.3092 Efficiency: 96.1138 Gap 12.4754 163 Table C9 Activity Rule - 15% Increment - 5 & 15 Minute - Set 1 Experiment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 15% Activity 15 Generic 15% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 258 21922.70 91.1307 2 258 22079.90 91.1946 ***o*** 229 23377.90 93.3870 ***q*** 224 23284.90 93.7843 4 197 24256.40 95.4258 4 191 24209.30 94.9298 5 173 24652.60 95.4636 5 168 24731.50 95.2879 6 152 24790.20 95.8046 6 154 24731.50 95.2879 7 146 24828.60 95.6090 7 142 24731.50 95.2879 8 136 24869.20 95.7468 8 135 24731.50 95.2879 9 134 24869.20 95.7468 9 132 24731.50 95.2879 10 136 24869.20 95.7468 10 132 24731.50 95.2879 11 134 24869.20 95.7468 11 131 24736.50 95.2888 12 131 24877.50 95.9355 12 128 24742.00 95.3353 13 130 24921.50 96.0266 13 127 24818.50 95.4169 14 127 24979.40 96.2838 14 125 24818.50 95.4169 15 133 24979.40 96.2838 15 132 24818.50 95.4169 16 129 24979.40 96.2838 16 129 24818.50 95.4169 17 126 24979.40 96.2838 17 124 24818.50 95.4169 18 124 24979.40 96.2838 18 123 24818.50 95.4169 19 123 24979.40 96.2838 19 122 24818.50 95.4169 Efficiency: 96.9639 Gap: 4.57951 Efficiency: 96.7413 Gap: 13.4971 164 Table C 1 Activity Rule - 1 5% Increment - 5 & 1 5 Minute - Set 2 ExDeriment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 15% Activity 15 Generic 15% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 249 20734.40 91.0614 2 249 21724.70 90.6287 ***o*** 216 23298.00 92.9948 ***o*** 217 23395.00 93.2119 4 196 23432.40 93.9796 4 198 24145.60 94.3555 5 175 23432.40 93.9796 5 170 24322.50 94.2412 6 159 23593.50 94.7172 6 149 24449.30 94.4447 7 155 23593.50 94.7172 7 146 24481.90 94.5034 8 149 23593.50 94.7172 8 138 24575.10 94.3865 9 148 23593.50 94.7172 9 136 24575.10 94.3865 10 151 23593.50 94.7172 10 140 24575.10 94.3865 11 147 23593.50 94.7172 11 137 24695.10 94.6493 12 147 23593.50 94.7172 12 135 24760.40 95.0584 13 146 23593.50 94.7172 13 130 24817.50 94.9181 14 144 23593.50 94.7172 14 129 24817.50 94.9181 15 153 23593.50 94.7172 15 138 24849.00 94.6865 16 149 23593.50 94.7172 16 133 24849.00 94.6865 17 146 23593.50 94.7172 17 133 24849.00 94.6865 18 144 23593.5C 94.7172 18 130 24849.00 94.6865 19 144 23593. 50 94.7172 19 129 24849.0C 94.6865 20 144 23593.5C 94.7172 21 143 23593.5C 94.7172 Efficiency- 97.3315 Gap 3.2963 Efficiency: 94.9535 Gap 5.8667 165 Table C 1 1 Activity Rule - 1 5% Increment - 30 & 60 Minute - Set 1 * * Experiment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 15% Activity 60 Generic 15% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 248 19142.10 88.2187 1 255 18921.50 86.7711 2 258 22354.80 90.6081 2 258 22354.80 90.6081 ***0*** 223 23395.10 93.6812 ***o*** 223 23395.10 93.6812 4 197 24256.10 95.2656 4 197 24319.30 95.3356 5 167 24738.30 95.7055 5 165 24775.80 95.3783 6 149 24859.70 95.7925 6 148 24901.60 95.3821 7 146 24873.10 95.6688 7 145 24901 .60 95.3821 8 140 25025.50 95.4377 8 138 24940.70 95.3822 9 137 25025.50 95.4377 9 136 24940.70 95.3822 10 140 25025.50 95.4377 10 139 24940.70 95.3822 11 139 25025.50 95.4377 11 137 24985.10 95.7504 12 136 25056.90 95.4432 12 136 25010.20 95.6194 13 135 25056.90 95.4432 13 133 25010.20 95.6194 14 134 25056.90 95.4432 14 133 25010.20 95.6194 15 142 25056.90 95.4432 15 139 25010.20 95.6194 16 138 25056.90 95.4432 16 136 25010.20 95.6194 17 136 25056.90 95.4432 17 131 25010.20 95.6194 18 134 25056.90 95.4432 18 131 25010.20 95.6194 19 133 25056.9C 95.4432 19 131 2501 0.2C 95.6194 20 130 2501 0.2C 95.6194 Efficiency: 95.757 Gap 8.2197 Efficiency: 96.4832 Gap 12.4506 166 Table C U Activity Rule - 1 5% Increment - 30 & 60 Minute - Set 2 Experiment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 30 Generic 15% Activity 60 Generic 15% Activity Round #Bids Revenue Optimality Round #Bids Revenue Optimality Set 2 1 248 19204.50 88.1924 1 248 19204.50 88.1924 2 249 21724.70 90.6287 2 249 21724.70 90.6287 ***o*** 217 23237.90 93.2119 ***0*** 217 23395.00 93.2119 4 197 24122.40 94.5231 4 198 24145.60 94.3555 5 176 24503.50 94.0921 5 170 24322.50 94.2412 6 147 24517.90 94.1268 6 149 24449.30 94.4447 7 147 24540.20 94.1814 7 146 24481 .90 94.5034 8 140 24604.50 94.0115 8 138 24575.10 94.3865 9 138 24825.30 94.0886 9 136 24575.10 94.3865 10 140 24831.00 94.1542 10 140 24575.10 94.3865 11 139 24919.30 94.1737 11 137 24695.10 94.6493 12 138 24954.00 94.1574 12 135 24760.40 95.0584 13 138 25001.70 94.1918 13 130 24817.50 94.9181 14 138 25001.70 94.1918 14 129 24817.50 94.9181 15 146 25001.70 94.1918 15 138 24849.00 94.6865 16 144 25001.70 94.1918 16 133 24849.0C 94.6865 17 141 25001.70 94.1918 17 133 24849.0C 94.6865 18 137 25001.70 94.1918 18 130 24849.0C 94.6865 19 137 25001.70 94.1918 19 129 24849.0C 94.6865 20 136 25001.70 94.1918 Efficiency: 94.7003 Gap 7.9444 Efficiency: 94.9535 Gap 5.8667 167 Table C 1 3 Minimum Revenue Rule - 5% Increment - 5 & 1 5 Minute Experiment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 5% MinRev 15 Generic 5% MinRev Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 278 19558.90 88.1961 2 278 20479.10 88.8792 3 254 20474.80 89.1492 3 253 21575.60 89.3750 4 240 21527.20 90.1414 4 237 22217.10 90.1766 ***c*** 224 23146.70 91.0156 5 220 22881.80 90.6210 ***£>*** 196 23487.20 92.4770 Efficiency: 89.4526 Gap: 21.2059 Efficiency: 90.8648 20.3426 20.8953 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 269 20857.30 89.7142 2 269 20937.30 89.7495 3 247 22084.50 90.9464 3 249 22837.90 90.9757 4 235 23035.30 91.4878 4 232 22837.90 90.9757 5 217 23035.30 91.4878 5 206 22930.70 91 .0544 *** 6 *** 185 23498.80 92.3043 ***6*" 186 23203.60 91.9155 Efficiency: 91.6006 Gap 20.1352 Efficiency: 90.6344 Gap: 21.2625 Table C 1 4 Minimum Revenue Rule - 1 0% Increment - 5 & 1 5 Minute Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 10% MinRev 15 Generic 10% MinRev Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 272 20931.20 89.4097 2 272 20931.20 89.4097 3 246 23097.20 92.5025 3 246 23097.20 92.5025 *** A-k-k-k 212 23538.10 93.9426 ******* 212 23617.70 94.0618 Efficiency: 91.5521 Gap: 22.1833 Efficiency: 91.8615 Gap: 21.8349 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 260 21074.80 90.4370 2 261 21891.30 90.8288 3 234 22890.80 92.4501 3 231 22686.70 91.5543 ***A*** 204 23586.20 93.4855 ■k-k-kA*** 202 23498.30 93.3097 Efficiency: 91.503 Gap: 21.5993 Efficiency: 91.3863 Gap: 20.8866 168 Table C 1 5 Minimum Revenue Rule - 1 5% Increment - 5 & 1 5 Minute Experiment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 15% MinRev 15 Generic 15% MinRev Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 258 21922.70 91.1307 2 258 22079.90 91.1946 ***o*** 229 23377.90 93.3870 ***o*** 224 23284.90 93.7843 Efficiency: 98.002 Gap: 21.6325 Efficiency: 91.2745 Gap: 21.8929 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 249 20734.40 91.0614 2 249 21724.70 90.6287 ***o*** 216 23298.00 92.9948 ***o*** 217 23395.00 93.2119 Efficiency: 97.46 Gap: 22.1324 Efficiency: 91.8082 Gap: 20.7417 169 Table C 1 6 Maximum Round=l Rule - 5% Increment - 5 & 1 5 Minute Experiment - 5% Increments - Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 5% Round=10 15 Generic 5% Round=10 Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 278 19558.90 88.1961 2 278 20479.10 88.8792 3 254 20474.80 89.1492 3 253 21575.60 89.3750 4 240 21527.20 90.1414 4 237 22217.10 90.1766 ***c*** 224 23146.70 91.0156 5 220 22881.80 90.6210 6 203 23506.00 91.5384 ***£*** 196 23487.20 92.4770 7 195 23841.30 93.1144 7 186 23815.00 92.9266 8 168 23890.60 93.6205 8 169 24023.90 93.6125 9 160 24387.60 93.4635 9 148 24154.20 94.4255 10 152 24387.60 93.4635 10 145 24522.30 93.8447 Efficiency: 93.9347 Gap: 16.3186 Efficiency: 94.8273 Gap: 15.5720 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 269 20857.30 89.7142 2 269 20937.30 89.7495 3 247 22084.50 90.9464 3 249 22837.90 90.9757 4 235 23035.30 91.4878 4 232 22837.90 90.9757 5 235 23035.30 91.4878 5 206 22930.70 91.0544 ***£*** 194 23851.30 92.1951 ***•>*** 186 23203.60 91.9155 7 184 23998.40 93.2668 7 176 23535.60 92.3030 8 168 24287.20 93.9622 8 153 23659.60 93.5633 9 162 24287.20 93.9622 9 144 23979.70 92.9056 10 159 24287.20 93.9622 10 144 24138.00 92.6800 Efficiency: 93.1122 Gap 16.4597 Efficiency: 92.5738 Gap 17.2806 170 Table C 1 7 Maximum Round=l Rule - 1 0% Increment - 5 & 1 5 Minute Experiment -10% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 10% Round=10 15 Generic 10% Round=10 Round #Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 272 20931.20 89.4097 2 272 20931.20 89.4097 3 246 23097.20 92.5025 3 246 23097.20 92.5025 ***A*** 212 23641.70 94.3282 •k** Alt-kit 212 23543.50 93.6646 5 187 23767.80 94.0879 5 183 24250.90 94.7524 6 162 24594.70 95.7148 6 154 24590.10 95.2736 7 156 24919.10 95.3553 7 147 24907.30 94.9794 8 147 24919.10 95.3553 8 143 25015.60 95.4790 9 139 24919.10 95.3553 9 137 25015.60 95.4790 10 139 24919.10 95.3553 10 138 25143.20 95.4414 Efficiency: 95.052 Gap: 10.9086 Efficiency: 95.7361 Gap: 11.9127 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 260 21074.80 90.4370 2 261 21891.30 90.8288 3 234 22886.20 92.4315 3 231 22686.70 91.5543 ***j\*** 203 23508.40 93.2528 ■kit* Ait-kit 202 23498.30 93.3097 5 179 23897.80 93.9488 5 183 23986.90 93.4585 6 158 24308.50 94.1326 6 153 24027.10 93.8715 7 148 24392.30 94.2361 7 150 24324.80 93.9720 8 146 24392.30 94.2361 8 141 24324.80 93.9720 9 141 24467.90 94.3917 9 136 24324.80 93.9720 10 143 24467.90 94.3917 10 140 24370.70 93.9918 Efficiency: 94.0633 Gap: 16.7943 Efficiency: 94.1339 Gap: 14.2980 171 Table C 1 8 Maximum Round=l Rule - 1 5% Increment - 5 & 1 5 Minute Experiment -15% Increments-Various Round Lengths Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule Minutes Per Round Bidder Set Minimum Bid Increment Closing Rule 5 Generic 15% Round=10 15 Generic 15% Round=10 Round # Bids Revenue Optimality Round #Bids Revenue Optimality 1 255 18546.60 87.9986 1 255 18546.60 87.9986 2 258 21922.70 91.1307 2 258 22079.90 91.1946 ***o*** 229 23377.90 93.3870 ***o*** 224 23284.90 93.7843 4 197 24256.40 95.4258 4 191 24193.80 95.3229 5 173 24652.60 95.4636 5 170 24562.30 95.3437 6 152 24790.20 95.8046 6 149 24667.70 96.2084 7 146 24828.60 95.6090 7 140 25026.20 95.8695 8 136 24869.20 95.7468 8 137 25026.20 95.8695 9 134 24869.20 95.7468 9 136 25038.20 95.9120 10 136 24869.20 95.7468 10 136 25069.40 95.7616 Efficiency: 95.7839 Gap: 12.3736 Efficiency: 97.3613 Gap: 9.7123 Set 2 1 248 19142.10 88.2187 1 248 19204.50 88.1924 2 249 20734.40 91.0614 2 249 21724.70 90.6287 ***o*** 216 23298.00 92.9948 ***o*** 217 23395.00 93.2119 4 196 23502.40 93.9535 4 198 24030.20 94.0111 5 176 23507.50 94.8602 5 173 24362.90 94.2297 6 161 23957.60 94.8943 6 154 24637.20 94.4737 7 162 24591.30 94.5547 7 149 24637.20 94.4737 8 156 24721.20 94.6581 8 144 24637.20 94.4737 9 150 24812.60 94.6767 9 140 24637.20 94.4737 10 153 24923.30 94.9689 10 143 24646.20 94.3543 Efficiency: 95.6039 Gap 12.3772 Efficiency: 94.3855 Gap: 9.4156 172 Table CI 9 Unsold Inventory Activity Stoppi ngl Rule Unsold Inventory \Show Experiment^ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Total Activity/MinRev 5Min5% 1 1 1 1 4 5Min10% 1 1 1 1 4 5Min15% 1 1 15Min5% 1 1 1 3 15Min10% 1 1 1 1 5 15Min15% 1 2 30Min5% 1 1 1 1 5 30Min10% 1 1 1 1 5 30Min15% 1 1 1 4 60Min5% 1 1 1 3 60Min10% 1 1 1 1 1 6 60Min15% 1 1 3 Set 2 5Min5% 1 1 2 5Min10% 1 1 1 4 5Min15% 2 1 1 5 15Min5% 1 1 1 1 4 15Min10% 1 1 1 3 15Min15% 1 1 1 4 30Min5% 1 2 30Min10% 1 1 30Min15% 1 1 3 60Min5% 1 1 1 1 4 60Min10% 1 1 60Min15% 1 1 1 4 173 Table C20 I Unsold Inventory Minimum Revenue Stopping Rule Unsold nventory ^\ Show Experiment^ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Total MinRevenue 5Min5% 1 1 2 5Min10% 1 1 1 1 1 5 5Min15% 1 1 2 15Min5% 1 1 15Min10% 1 1 1 3 15Min15% 1 1 1 1 1 5 Set 2 5Min5% 1 1 1 1 4 5Min10% 1 1 1 1 4 5Min15% 1 1 2 15Min5% 1 1 2 15Min10% 1 1 1 1 4 15Min15% 1 1 Table C21 1 Unsold Inventory Maximum Round= =10 Stopping Rule Unsold Inventory ^\Show Experiments 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Total MaxRound=10 5Min5% 1 1 1 1 4 5Min10% 1 1 1 1 5 5Min15% 1 2 15Min5% 1 1 1 1 5 15Min10% 1 1 1 4 15Min15% 1 1 3 Set 2 5Min5% 1 1 1 1 4 5Min10% 1 1 1 3 5Min15% 1 1 1 3 15Min5% 1 1 1 1 1 1 6 15Min10% 1 1 2 15Min15% 1 1 1 1 4 174 Table C22 Winning Bidder Type Distribution - Activity Stopping Rule -Setl Winning Bidder Type Analysis Activity Stopping Rule Set1) Experiment 5Min5%C 15Min5%C 30Min5%C 60Min5%C 5Min10%C 15Min10%C Evaluators 4 5 4 8 4 4 3% 4% 3% 7% 3% 3% Bid Adjustors Min 28 26 29 29 27 29 22% 20% 23% 24% 21% 23% Max 11 15 9 7 9 10 9% 12% 7% 6% 7% 8% All Adjustors Min 33 34 34 32 31 29 26% 27% 27% 26% 24% 23% Max 39 38 39 36 48 42 31% 30% 31% 29% 38% 34% Constraint Adjustors 11 10 10 11 8 10 9% 8% 8% 9% 6% 8% Total Bidders 126 128 125 123 127 124 Lower Bounded 5 7 7 8 6 8 4% 5% 6% 7% 5% 6% Experiment 30Min10%C 60Min10%C 5Min15%C 15Min15%C 30Min15%C 60Min15%C Evaluators 5 5 9 5 4 4 4% 4% 7% 4% 3% 3% Bid Adjustors Min 26 26 24 24 26 25 21% 21% 20% 21% 20% 20% Max 8 9 10 12 11 12 7% 7% 8% 10% 9% 10% All Adjustors Min 29 28 28 26 29 30 24% 23% 23% 22% 23% 24% Max 43 42 41 39 46 43 35% 35% 34% 33% 36% 35% Constraint Adjustors 11 11 10 11 11 10 9% 9% 8% 9% 9% 8% Total Bidders 122 121 122 117 127 124 Lower 5 4 8 6 6 7 Bound* ;d 4% 3% 7% 5% 5% 6% 175 Table C23 Winning Bidder Type Distribution - Activity Stopping Rule - Set 2 Wi nning Bidder Type Analysis Activity Stopping Rule (Set 2) Experiment 5Min5% 15Min5% 30Min5% 60Min5% 5Min10% 15Min10% Evaluators 6 6 5 5 5 5 5% 5% 4% 4% 4% 4% Bid Adjustors Min 24 22 25 22 21 22 19% 18% 20% 18% 17% 18% Max 9 11 10 9 8 9 7% 9% 8% 7% 6% 7% All Adjustors Min 32 38 35 35 31 30 26% 31% 28% 28% 25% 24% Max 46 38 44 43 52 49 37% 31% 35% 35% 41% 40% Constraint Adjustors 8 7 8 9 9 9 6% 6% 6% 7% 7% 7% Total Bidders 125 122 127 123 126 124 Lower Bounded 5 6 7 4 3 4 4% 5% 6% 3% 2% 3% Experiment 30Min10% 60Min10% 5Min15% 15Min15% 30Min15% 60Min15% Evaluators 5 6 10 6 5 6 4% 5% 7% 5% 4% 5% Bid Adjustors Min 21 20 24 21 21 21 17% 16% 17% 17% 16% 17% Max 9 11 13 12 11 12 7% 9% 9% 10% 8% 10% All Adjustors Min 33 33 34 34 35 34 26% 26% 24% 27% 27% 27% Max 48 48 54 43 49 43 38% 38% 38% 35% 38% 35% Constraint Adjustors 9 9 7 8 9 8 7% 7% 5% 6% 7% 6% Total Bidders 125 127 142 124 130 124 Lower 3 4 24 3 5 2 Bound 3d 2% 3% 17% 2% 4% 2% 176 Table C24 Winning Bidder Type Distribution - Minimum Revenue Stopping Rule Winning Bidder Type Analysis Minimum Revenue Stopping Rule (Set 1) Experiment 5Min5%A 15Min5%A 5Min10%A 15Min10%A 5Min15%A 15Min15%A Evaluators 5 5 5 5 4 5 4% 4% 4% 4% 3% 4% Bid Adjustors Min 23 20 24 22 23 24 18% 17% 20% 19% 19% 21% Max 14 13 12 13 15 13 11% 11% 10% 11% 12% 11% All Adjustors Min 25 27 29 28 32 29 20% 23% 25% 24% 26% 25% Max 47 43 38 39 41 38 38% 36% 32% 33% 33% 32% Constraint Adjustors 11 11 10 10 9 8 9% 9% 8% 9% 7% 7% Total Bidders 125 119 118 117 124 117 Lower Bounded 11 12 8 8 9 9 9% 10% 7% 7% 7% 8% Minimum Revenue Stopping Rule (Set 2) Experiment 5Min5%A 15Min5%A 5Min10%A 15Min10%A 5Min15%A 15Min15%A Evaluators 5 6 7 7 5 6 4% 5% 6% 6% 4% 5% Bid Adjustors Min 20 24 16 15 20 20 17% 20% 15% 14% 16% 16% Max 8 10 13 13 15 15 7% 8% 12% 12% 12% 12% All Adjustors Min 33 30 28 26 34 33 27% 25% 26% 24% 27% 27% Max 46 44 35 39 44 42 38% 36% 32% 36% 35% 34% Constraint Adjustors 9 8 9 9 8 7 7% 7% 8% 8% 6% 6% Total Bidders 121 122 108 109 126 123 Lower 7 8 12 12 10 13 Boundi ?d 6% 7% 11% 11% 8% 11% 177 Table C24 Winning Bidder Type Distributioi i - Maximun iRound=10 Stopping Rul Winning Bidder Type Analysis Maximum Round = 10 Stopping Rule (Set 1) Experiment 5M5%D10 15M5%D10 5M10%D10 15M10%D10 5M15%D10 15M15%D10 Evaluators 5 5 5 4 4 5 4% 4% 4% 3% 3% 4% Bid Adjustors Min 27 26 28 25 25 24 22% 20% 22% 20% 20% 19% Max 11 13 10 9 11 11 9% 10% 8% 7% 9% 9% All Adjustors Min 33 34 27 29 29 27 26% 27% 21% 24% 24% 22% Max 38 39 46 45 42 47 30% 30% 37% 37% 34% 38% Constraint Adjustors 11 11 10 11 11 11 9% 9% 8% 9% 9% 9% Total Bidders 125 128 126 123 122 125 Lower Bounded 7 8 4 4 6 10 6% 6% 3% 3% 5% 8% Maximum Round = 10 Stopping Rule (Set 2) Experiment 5M5%D10 15M5%D10 5M10%D10 15M10%D10 5M15%D10 15M15%D10 Evaluators 7 5 5 5 6 6 5% 4% 4% 4% 4% 5% Bid Adjustors Min 24 24 21 22 22 21 18% 20% 17% 18% 16% 16% Max 13 10 8 9 14 12 10% 8% 6% 7% 10% 9% All Adjustors Min 35 36 31 29 39 32 27% 30% 25% 24% 28% 25% Max 44 40 52 49 51 49 33% 33% 41% 40% 36% 38% Constraint Adjustors 9 7 9 9 8 9 7% 6% 7% 7% 6% 7% Total Bidders 132 122 126 123 140 129 Lower 14 9 3 5 6 7 Boundi sd 11% 7% 2% 4% 4% 5% LIST OF REFERENCES Armstrong, M. (1999)."Optimal Multi-Object Auctions." Unpublished working paper Nuffield College, Oxford, UK. Ashenfelter, O. (1989). How Auctions Work for Wine and Art. Journal of Economic Perspectives 3:23-36 Ausubel, L. M. (1996). "An Efficient Ascending-Bid Auction for Dissimilar Objects." Unpublished working paper University of Maryland, College Park. 4 January 1996. Ausubel, L. M., P. Cramton. R. P. McAfee, & J. McMillan (1997). Synergies in Wireless Telephony: Evidence from the Broadband PCS Auctions. Journal of Economics & Management Strategy 6(3):497-527. Ausubel, L. M., & P. Cramtom (1999). "The Optimality of Being Efficient." Unpublished working paper University of Maryland, College Park. 18 June 1999. Bacchus, F., & P. van Run (1995). Dynamic Variable Ordering in CSPs. Proceedings of the First International Conference on Principles and practices of Constraint Programming. Cassis. Lecture Notes in Computer Science 976:258-275. Bakos, Y. (1997). Reducing Buyer Search Costs: Implications for Electronic Marketplaces. Management Science 43(12):1676-1692. (1998). The Emerging Role of Electronic Marketplaces on the Internet. Communications of the /lCM41(8):35-42. Bakos, Y., & E. Brynjolfsson (1998). "Bundling Information Goods: Pricing, Profits and Efficiency." Work in Review for Management Science Banks, J. S., J. O. Ledyard, & D. P. Porter (1989). Allocating Uncertain and Unresponsive Resources: An Experimental Approach. RAND Journal of Economics 20( 1 ): 1 -21 . Bapna, R., P. Goes, & A. Gupta (1998). "A Theoretical and Empirical Investigation of Multi-item On-line Auctions." Forthcoming in Information Technology and Management, 1999. 178 179 (1998). "Designing and Managing On-line Service Quality and Product Mix Under Uncertain Demand and Fixed Short-term Capacity." Submitted to Management Science. Baron, D. P. (1972). Incentive Contracts and Competitive Bidding. American Economic Review, 62(6):384-394. Bartak, R. (1999). Constraint Programming: In pursuit of the Holy Grail. Proceedings of WDS99 (Invited lecture), Prague, pp. 1-10. Beam, C, & A. Segev (1998). "Auctions on the Internet: A Field Study." Unpublished working paper 98-WP-1032 University of California, Berkeley. Beam, C, A. Segev, & J. G. Shanthikumar (1996). "Electronic Negotiation through Internet-based Auctions." Unpublished working paper 96-WP-1019 University of California, Berkeley (1999). "Optimal Design of Internet-based Auctions." Unpublished working paper 98-WP-1034 University of California, Berkeley. Benoit, J-P. and V. Krishna (1998) "Multi-Object Auctions with Budget Constrained Bidders." Working Paper, New York University and Pennsylvania State University. Bessiere, C, E. Freuder, & J. Regin. (1999). Using Constraint Metaknowledge to Reduce Arc Consistency Computation. Artificial Intelligence 107:125-148. Bitner, J. R., & E. M. Reingold. (1975). Backtrack Programming Techniques. Communications of the ACM 18:651-656. Black, K. & J. Zender (1993). Auctions of Divisible Goods: On the Rationale for the Treasury Experiment. Review of Financial Studies 6(4):733-764. Brailsford, S. C, C. N. Potts, & B. M. Smith. (1999). Constraint Satisfaction Problems: Algorithms and Applications. European Journal of Operational Research 1 19:557- 581. Bulow, J., & J. Roberts (1989). The Simple Economics of Optimal Auctions. Journal of Political Economy 97(5): 1 060- 1 090. Bykowsky, M. M., R. J. Cull, & J. O. Ledyard (1995). "Mutually Destructive Bidding: The FCC Auction Design Problem." Caltech Social Science Working Paper 916. January. 180 Cassady, R. Jr. (1967). Auctions and Auctioneering . University of California Press Berkeley & Los Angeles, CA. Che, Y. K., & I. Gale (1996). Financial Constraints in Auctions: Effects and Antidotes. Applied Microeconomics 6:97- 1 20. Che, Y. K., & I. Gale (1998). Standard Auctions with Financially Constrained Bidders. Review of Economic Studies 65:1-21. Chen, Yangjun (1999). Arc Consistency Revisited. Information Processing Letters 70:175-184. Choi, S. Y., D. O. Stahl, & A. B. Whinston (1997). The Economics of Electronic Commerce . Macmillan Technical Publishing, Indianapolis, IN. pp. 380-381. Choi, S. Y., & A. B. Whinston (1998). The Smart Economy: Technologies and Applications . To be published by Addison- Wesley Longman 1999. Coleman, C. Y. (1999). Two Start-Ups Plan to Market Unsold Radio Time on the Web. Wall Street Journal Friday, November 12 Cramton, P. C. (1995). The PCS Spectrum Auctions: An Early Assessment. Journal of Economics and Management Strategy 6(3):431-495. Das, S. R., & R. K. Sundaram (1997). "Auction Theory: A Summary with Applications to Treasury Markets." NBER Working Paper Series, National Bureau of Economic Research. Forthcoming in Financial Markets, Institutions and Instruments. DeMartini, C, A. M. Kwasnica. J. O. Ledyard, & D. Porter (1999). "A New and Improved Design for Multi-Object Iterative Auctions." Caltech Social Science Working Paper No. 1054 November 1998, revised March 1999. Deris, S., S. Omatu. H. Ohta, & P. Saad (1997). Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning. Engineering Applications of Artificial Intelligence 12:241-253. Deris, S., S. Omatu. H. Ohta. S. Kutar, & P. A. Samat (1997). Ship Maintenance Scheduling by Genetic Algorithm and Constraint-based Reasoning. European Journal of Operational Research 1 12:489-502. Deris, S., S. Omatu, H. Ohta, & P. Saad (1999). Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning. Engineering Applications of Artificial Intelligence, 1 2 : 24 1 -25 3 . 181 Domowitz, I., & J. Wang (1992). Auctions as Algorithms. Journal of Economic Dynamics and Control 18(l):29-60. Engelbrecht-Wiggans, R. (1980). Auctions and Bidding Models: A Survey. Management ' Science 26(2): 119-142. (1987). Optimal Constrained Bidding. InternationalJournal of Game Theory 16(2):115-121. Engelbrecht-Wiggans, R. and C. M. Kahn (1998) Multi-unit Auctions with Uniform Prices. Economic Theory, 12:227-258. Fan, M., Stallaert. J., & A. B. Whinston (1998). Creating Electronic Markets. Dr. Dobb 's Journal: Software Tools for the Professional Programmer 23(1 1):52-56. Freidman, D. (1991). The Double Auction Market Institution: A Survey. In: The Double Auction Market, Institutions, Theories, and Evidence . 1993 Addison- Wesley Publishing Co., Reading, MA. Fudenberg, D., J. Tirole (1991). Game Theory . MIT Press. Cambridge, MA. Gaschnig, J. (1977). A General Backtracking Algorithm that Eliminates Most Redundant Tests. Proceedings IJCAI-7 Cambridge, MA. pp.457. (1978). Experimental Case Studies of Backtrack vs. Waltz-type vs. New Algorithms for Satisficing Assignment Problems. Proceedings of the 2nd Biennial Conference of the Canadian Society for Computational Studies of Intelligence Toronto, Ont. pp. 268-277. Gu, J. (1993). Local Search for Satisfiability (SAT) Problem. IEEE Transactions on Systems, Man, and Cybernetics 23:1 108-1 129. Guttman, R. H., A. G. Moukas, & P. Maes (2000). Agent-mediated Electronic Commerce: An MIT Media Laboratory Perspective." Forthcoming in: International Journal of Electronic Commerce, 2000 Issue. Hanson, D. L. & C. F. Menezes (1968). Risk Aversion and Bidding Theory. In J.P. Quirk and A.M. Zarley (eds.), Papers in Quantitative Eeconomics , Lawrence, pp. 521-542. Haralick, R. M., & G. L. Elliott (1980). "Increasing Tree Search Efficiency for Constraint Satisfaction Problems." Tech. Rept. TR94-10. University of Alberta, Edmonton. Alta. Harris, M. & A. Raviv (1981). Allocation Mechanisms and the Design of Auctions. Econometrica, 49:1477-1499. 182 Hazlett, T. W. (1996). "Assigning Property Rights to Radio Spectrum Users: Why Did FCC License Auctions Take 67 Years?" Paper presented at the Conference Law and Economics of Property Rights to Radio Spectrum, Tomales Bay, Cal., July 1996) Holt, C. A. Jr. (1979). Competitive Bidding for Contracts Under Alternative Auction Procedures. Journal of Political Economy, 88:433-445. Johnson, E. L., G. L. Nemhauser, & M. W. P. Savelsbergh (2000). Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition. INFORMS Journal on Computing 12(1) Winter Kagel, J. H. (1995). Auctions: A Survey of Experimental Research. In John H. Kagel and Alvin E. Roth (eds.), The Handbook of Experimental Economics (pp. 501-586). New Jersey: Princeton University Press. Kanoh, H., M. Matsumoto. K. Hasegawa. N. Kato, & S. Nishihara (1997). Solving Constraint-Satisfaction Problems by a Genetic Algorithm Adopting Viral Infection. Engineering Application of Artificial Intelligence 10(6):53 1-537. Katz, H. (1995). The Media Handbook . NTC Business Books, Lincolnwood, IL Katzman, B (1995). "Multi-Unit Auctions with Incomplete Information" working paper University of Miami Klein, S. (1997). Introduction to Electronic Auctions. International Journal of Electronic Markets 7(4):3-6. Klein, S., & R.M. O'Keefe (1998). The Impact of the Web on Auctions: Some Empirical Evidence and Theoretical Considerations. Submitted to International Journal of Electronic Commerce. Kim, H-S. (1996). Equilibrium and Efficiency in Auctions of Complementary Goods Without Bundling. Economic Letters 52:49-54. Kondrak, G., & P. van Beek (1997). A Theoretical Evaluation of Selected Backtracking Algorithms. Artificial Intelligence 89:365-387. Krishna, V., & R.W. Rosenthal (1995). "Simultaneous Auctions with Synergies." Unpublished working paper RePEc:wpa:wuwpga:9503004 by Economics Working Paper Archive at WUSTL . Kuchinskas, S. (1999). AdAuction Sell an Alternative. Adweek 40(\2):36. 183 Kurgollus, F., & B. Sankur (1999). Image Segmentation Based on Multi-scan Constraint Satisfaction Neural Network. Pattern Recognition Letters 20:1553-1563. Ledyard, J. O., D. Porter, & A. Rangel (1997). Experiments Testing Multiobject Allocation Mechanisms. Journal of Economics & Management Strategy 6(3):639- 675. Lee, H. G. (1997). AUCNET: Electronic Intermediary for Used-Car Transactions. International Journal of Electronic Markets 7(4):24-27. Lengwiler, Y. (1999). The Multiple Unit Auction with Variable Supply. Economic Theory, 14(2): 373-392 Lewis, T. R., & D. E. M. Sappington (1994). Supplying Information to Facilitate Price Discrimination. International Economic Review 35(2):309-327. Lu, X., & R. P. McAfee (1995). The Evolutionary Stability of Auctions Over Bargaining. Games and Economic Behavior 15:228-254. Lucking-Reiley, D. (1999) Using Field Experiments to Test Equivalence Between Auction Formats: Magic on the Internet. American Economic Review, 89(5): 1063- 1095 Mackworth, A. K. (1977). Consistency in Networks of Relations. Artificial Intelligence, 8:99-118. (1992). Constraint Satisfaction. In: Encyclopedia of Artificial Intelligence 2nd ed . Wiley, New York pp. 285-293. Mand, A. (1998). Adauction.com Adds Execs. Money. In: Race to Top. Mediaweek 8(22):26. McAfee, R. P., & J. McMillan (1987). Auctions and Bidding. Journal of Economic Literature, 25:699-738. (1996). Analyzing the Airwaves Auction. Journal of Economic Perspectives 10(1):159-175. McGregor, J. J. (1979). Relational Consistency Algorithms and Their Application in Finding Subgraph and Graph Isomorphisms. Information Sciences 19:229-250. McMillan, J. (1994). Selling Spectrum Rights. Journal of Economic Perspectives 8(3):145-162. 184 McMillan, J., M. Rothschild, & R. Wilson (1997). Introduction. Journal of Economics & Management Strategy, 6(3):425-430. Mead, W. J. (1967) Natural Resource Disposal Policy - Oral Auction Versus Sealed Bid. Natural Resources Planning Journal M: 194-224. Merskin, D. L. (1999). The Media Buyer in the Advertising Agency in The Advertising Business: Operations, Creativity, Media Planning, Integrated Communications edited by J. P Jones. Sage Publications. Thousand Oaks, CA. Milgrom, P. (1987) Auction Theory. In Truman F. Bewley (ed.) Advances I Economic Theory: Fifth World Congress . Cambridge: Cambridge University Press. (1989). Auctions and Bidding: A Primer. Journal of Economic Perspectives 3(3. pp. 3-22. (1997). "Putting Auction Theory to Work: The Simultaneous Ascending Auction." Unpublished working paper Stanford University. Milgrom, P., & R. J. Weber (1982). A Theory of Auctions and Competitive Bidding. Econometrica 50(5):1089-1 122. Miller, R. M. (1990). The Design of Decentralized Auction Mechanisms That Coordinate Continuous Trade in Synthetic Securities. Journal of Economic Dynamics & Control 14(2):237-253. Minton, S., M. D. Johnston. A. B. Phillips, & P. Laird (1992). Minimizing Conflicts: A Heuristic Repair method for Constraint Satisfaction and Scheduling Problems. Artificial Intelligence 58: 166-205. Montanari, U. (1974). Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science, 21:95-132. Myerson, R. B. (1981). Optimal Auction Design. Mathematics of Operations Research 6(l):58-73. Nash, J. F. Jr. (1950). The Bargaining Problem. Econometrica, 18:155-162. Nonobe, K., & T. Ibaraki (1998). A Tabu Search Approach to the Constraint Satisfaction Problem as a General Problem Solver. European Journal of Operational Research 106:599-623. Noussair, C. (1995). Equilibrium in a Multi-Object Uniform Price Sealed Bid Auction with Multi-unit Demands. Economic Theory, 5:337-351. 185 Ortega-Reichert, A. (1968). Models for Competitive Bidding Under Uncertainty. Stanford University Ph.D. Thesis (and Technical Report No. 8, Department of Operations Research, Stanford University). Palfrey, T. R. (1983). Bundling Decisions by a Multiproduct Monopolist with Incomplete Information. Econometrica, 51:463-484. Perry, M., & P. J. Reny (1999). On the Failure of the Linkage Principle in Multi-Unit Auctions. Econometrica 67(4):895-900. Pitchik, C, & A Schotter (1988). Perfect Equilibria in Budget-constrained Auctions: An Experimental Study. RAND Journal of Economics 19(3):363-388. Plott, C. R., (1997). Laboratory Experimental Testbeds: Application to the PCS Auction. Journal of Economics & Management Strategy 6 (3):605-638. Popescu, I. (1997). Using Artificial Neural Networks for Constraint Satisfaction Problem. Nonlinear Analysis. Theory Methods & Applications 30(5):2937-2944. Prosser, P., (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computer Intelligence 5:269-299. Rasmusen, E. (1989). , Games and Information: An Introduction to Game Theory, First Edition . Blackwell Publishers, Cambridge University Press, Oxford, U.K. Rassenti, S. J., V. L. Smith, & R. L. Bulfin (1982). A Combinatorial Auction Mechanism for Airport Time Slot Allocation. Bell Journal of Economics 13:402-417 Reck, M. (1997). Trading-Process Characteristics of Electronic Auctions. International Journal of Electronic Markets 7(4): 17-23. Rigoli, J. (1998). Web-auction Stocks on Rise. Computerworld 32(30):92. Riley, J. G. & W. F. Samuelson (1981). Optimal Auctions. American Economic Review, 71:375-387 Ross, C. (1998). Optimizers & TV Upfront: How They Affect Ad Buying. Advertising Age 69(26):3,16. Rothkopf, M. H. (1977). Bidding in Simultaneous Auctions with a Constraint on Exposure. Operations Research 25(4):620-629. Rothkopf, M. H., & R. M. Harstad (1994). Modelling Competitive Bidding: A Critical Essay. Management Science 40(3):364-384. 186 Rothkopf, M. H., A. Pekec, & R. M. Harstad (1998). Computationally Manageable Combinational Auctions. Management Science 44(8):1 131-1 147. Sabin, D., & E. C. Freuder (1994). Contradiction Conventional Wisdom in Constraint Satisfaction. Proceedings of the 11th European Conference of Artificial Intelligence, Amsterdam pp. 125-129. Sam-Haroud, D., & B. V. Faltings (1996). Consistency Techniques for Continuous Constraints. Constraints Journal 1. 1996. Selman, B., H. Levesque, & D. Mitchell (1992). A New Method for Solving Hard Satisfiability Problems. Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI) pp. 440-446. Siegel, S. (1956). Nonparametric Statistics for the Behavioral Sciences . 1956 McGraw- Hill Book Company. Inc., New York, NY. Sissors, J. Z., & L. Bumba (1989). Advertising Media Planning 3rd Edition 1989 NTC Business Books, Lincolnwood, IL. Smith, B. M., & S. A. Grant (1995). Sparse Constraint Graphs and Exceptionally Hard Problems. Proceedings IJCAI-95 Montreal, Que. pp. 646-651. Stewart, J. (2000). Dot.coms on NAPTE Floor. Spots-n-dots: The Daily News of TV Sales Friday, January 28, 2000. Stone, M. (1998). Classifieds on Steroids: Auction Ads. Editor & Publisher 131(36):26.30. Teich, J., H. Wallenius, J. Wallenius, & A. Zaitsev. (1999). A Multiple Unit Auction Algorithm: Some Theory and a Web Implementation. Electronic Markets 9(3): 1-7. Tsang, E. (1993). Foundations for Constraint Satisfaction . Academic Press. London, UK. 1993. Turban, R. (1997). Auctions and Bidding on the Internet: An Assessment. International Journal of Electronic Markets 7(4):7-l 1. Vakrat, Y., & A. Seidmann (1998). "Analysis and Design Models for Online Auctions." Presented at INFORMS 4th Conference on Information Systems and Technology May 26. 1998. van Heck, E., & P. M. Ribbers (1997). Experiences with Electronic Auctions in the Dutch Flower Industry. International Journal of Electronic Markets 7(4):29-34. 187 van Heck, E., & P. Vervest (1998). How Should CIOs Deal with Web-Based Auctions? Communications of the ACM 41(7):99-100. Van Hentenryck, P., Y. Deville, C. M. Teng (1992) A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence, 57(2/3):291-321. Van Hentenryck, P., & V. Saraswat (1996). Strategic Direction in Constraint Programming. ACM Computing Surveys 28(4):701-726. Varian, H. R. (1992). Microeconomic Analysis 3rd Edition . W. W. Norton & Company. Inc., New York, NY. (1995). "Economic Mechanism Design for Computerized Agents." Presented at the USENIX Workshop on Electronic Commerce, July, 1995, New York, NY. Vickery, W. (1961). Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance 16:8-37. Wallace, M., (1995). "Constraint Programming." Working Paper William Penney Laboratory, Imperial College, London Sept. 1995. Waltz, D. L. (1975). Understanding Line Drawings of Scenes with Shadows, in: Psychology of Computer Vision , McGraw-Hill, New York Wang, R. (1993). Auctions Versus Posted-Price Selling. The American Economic Review 83(4):838-851. Weaver, J. (1999). How Much Do I Hear for that Ad?. MSNBC News Article. http://www.msnbc.com/news.325684.asp . Oct. 25, 1999 Weber, R. J. (1983). Multi-Object Auctions. In Reichar Engelbrecht-Wiggans, Martin Shubik, and Robert M. Stark (eds), Auctions, Bidding, and Contracting (pp. 165- 191). New York: New York University Press. Wrigley, C. D. (1997). Design Criteria for Electronic Market Servers. International Journal of Electronic Markets 7(4):12-16. BIOGRAPHICAL SKETCH Joni L. Jones was born in Sandpoint, Idaho in October 1958. She received her Bachelor of Science in Business Administration from the University of Illinois at Chicago in 1992. Joni spent several years in the Unites States Navy where she worked as an Air Traffic Controller. After completing her undergraduate studies she worked for a major television network as an assistant sales representative. She has also worked as a computer software instructor before returning to pursue her PhD in Decision and Information Sciences in 1996. She intends to pursue an academic research and teaching career following the completion of her doctoral degree. 188 I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy Gary J. l46ehler, Chairman John B. Higdon Eminent Scholar of Decision and Information Sciences I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Steven M. Shugan v /<- Steven Russell Berrie Eminent Scholar of Marketing I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Sanin ireicuk Eren^tc /Professor of Decision and Information Sciences I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. ^f^f-^ fsihg Keryieth Cheng Associate Professor of Decision and Information Sciences I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Daniel G. Conway / Assistant Professor of Decision and Information Sciences I certify that I have read this study and that in my opinion it conforms to acceptable standards of scholarly presentation and is fully adequate, in scope and quality, as a dissertation for the degree of Doctor of Philosophy. Indranil Bose Assistant Professor of Decision and Information Sciences This dissertation was submitted to the Graduate Faculty of the Department of Decision and Information Sciences in the Warrington College of Business Administration and to the Graduate School and was accepted as partial fulfillment of the requirements for the degree of Doctor of Philosophy. August 2000 Dean, Graduate School ,;m UNIVERSITY OF FLORIDA 3 1262 08555 0274