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