(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Incompletely specified combinatorial auction : an alternative allocation mechanism for business-to-business negotiations"

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