Optimal design of the online auction channel: Analytical, empirical, and computational insights

INTRODUCTION

Online auctions, in the absence of spatial, temporal, and geographic constraints, provide an alternative supply chain channel for the distribution of goods and services. This channel differs from the common posted-price mechanism that is typically used in the retail sector. In consumer-oriented markets, buyers can now experience the thrill of winning a product, potentially at a bargain, as opposed to the typically more tedious notion of buying it. Sellers, on the other hand, have an additional channel to distribute their goods, and the opportunity to liquidate rapidly aging goods at greater than salvage values. The primary facilitator of this phenomenon is the widespread adoption of electronic commerce over an open-source, ubiquitous Internet Protocol (IP) based network.

In this paper, we concentrate on optimizing the design of an emerging business-to-consumer (B2C) distribution channel known as Yankee auctions. Such auctions sell multiple identical units of a good to multiple buyers using an ascending and open auction mechanism, which has its roots in the English auction, yet are significantly different.

This work presents an analytical model that characterizes the revenue generation process of Yankee auctions. To validate the analytical model and to gain a better understanding of the revenue generation process of such auctions, we analyze real-world empirical data collected by a software agent that tracked these auctions round the clock. An interesting by-product of the auction data collection process is our ability to construct empirical demand curves for the auctioned goods. Consumer demand information is an important input in supply chain management. It provides the feedback necessary for making key decisions downstream in the supply chain. We demonstrate, using the capabilities of the Internet, how dynamic pricing mechanisms such as online auctions can provide opportunities for integration of demand information into the mechanism design process. This enhances the mechanisms in two ways. First, by appropriately setting the online auction parameters, auctioneers can maximize their returns. Secondly, by recognizing the demand implication and visualizing the trading process a priori, the eventual allocation can be more equitable, thus resulting in higher welfare for both consumers and the auctioneer.

To validate and complement the analytical model, we also introduce a flexible simulation model, offering auctioneers a portfolio of tools, varying in their level of abstraction and information intensity requirements, to help auctioneers maximize their revenues. In summary, this portfolio of decision-making tools provides a relatively risk-free and cost-effective approach to managing this new, webbased dynamic pricing distribution channel prevalent in the online setting, namely, the Yankee auction.

The rest of this paper is organized as follows. In the next section we describe the revenue generation process of the Yankee auction mechanism. Our understanding of the revenue generation process of Yankee auctions directs us to focus our attention to the combinatorial dynamics of the penultimate rounds of the auction, which forms the basis of our theoretical model in this paper. Later we show how the theoretical results can be applied to actual Yankee auctions by using consumer demand estimates derived from real collected data. That follows with a validation approach to the theoretical analysis using a simulation tool under varying degree of information abstraction. We conclude with an overview of our approach and a summary of the findings of the paper.

THE YANKEE AUCTION MECHANISM

The Yankee auction is a special case of multi-unit English auction. Here, multiple units of the same product are sold to multiple bidders. It is well known (Rothkopf & Harstad, 1994a) that single-item results (a vast majority of auction theory studies fall under this category) do not carry over in multiple-unit settings. The multiunit and discrete nature of these mechanisms renders the traditional analytic framework of game theory intractable (Nautz & Wolfstetter, 1997).

The auction is progressive in nature; however, each new bid does not have to be strictly greater than the previous bid since there are multiple units available. The set of winning bids consists of the top N bids, where N is the number of units up for auction. A new bid either has to be equal to the minimum bid that is among the winning bids (if the set of winning bids has a cardinality of less than N), or it has to be at least equal to the minimum winning bid plus a pre-specified minimum bid increment. With multiple identical items on offer, it is possible to observe several winning bids that are equal. Once the consumers have bid for the entire lot size, a new bid will have to be greater than the smallest winning bid. When such a bid is submitted, the winner with the smallest winning bid is replaced by the new bid. If several offers are equal and at the minimum winning bid level, a time priority is applied to determine the bid to be displaced when a new and higher offer is received. The last bid at the minimum winning bid level becomes the first to leave the auction winners' list. This process continues until the auction closes. At this point the auction winners are determined. The auction terminates on or after a pre-announced closing time, and the winning bidders pay the amount they last bid to win the auction. Most auctions have a going, going, gone period such that the auction terminates after the closing time has passed and no further bids are received in the last five minutes. Note that in multiunit settings this often leads to discriminatory pricing with consumers paying different amounts for the same item. Such auctions are used on a variety of auction sites on the Internet, pioneered by Egghead.com's Surplus Auctions (now defunct) and now popularized by Ubid.com.

The key factors that auctioneers can control in Yankee auctions are: (1) the lot size; (2) the bid increment; (3) the auction duration; and (4) the opening bid.

Ignoring monitoring costs for the present, we assume that customers maximize their net value and hence always bid at the current ask price, provided that the current ask price does not exceed their valuation of the item. Rothkopf and Harstad (1994b), in their single item analysis, characterize this as the pedestrian approach to bidding. Such a strategy is consistent with the rational, net worth maximizing assumption for consumers. Easley and Tenorio (1999) extend this result to Yankee auctions, conditioning it on the absence of any cost of preparing and submitting a bid. Notably, such a strategy could involve active manual participation or could be undertaken using a programmed software agent that bids the minimum required bid at any stage during the auction. Both have been observed in practice. In adopting this strategy, bidders choose to be no more aggressive than necessary to continue competing.

Bid Increment and Auction Revenue

Bapna (1999) uses a regression model to show that amongst all the control factors mentioned in the previous section, the bid increment is the only factor significant in explaining variations of auction revenues. Additionally, anecdotal evidence suggests that auctioneers realize the importance of bid increments. We routinely observed that similar items are auctioned, at different times, using different bid increments.

While most of existing theory (for a detailed overview, see McAfee and McMillan, 1987; Milgrom, 1989; and Milgrom and Weber, 1982) analyzes auctions under either the private or the common value setting, the online context in which these B2C auctions occur makes such a strict classification inaccurate. A close observation of the types of goods sold in these liquidation kinds of auctions indicates that most of the items (such as computer hardware and consumer electronics) have both idiosyncratic (private) and common value elements. This is more so given the presence of imperfect substitutes and price-comparison agents that provide information regarding the alternative comparable products and their posted prices. Thus, based on the general model of Milgrom and Weber (1982), the multiunit B2C auctions lie in the continuum between the private and common value models. See Paarsch (1992) on how to decide between the common values and private value paradigms in auctions. The presence of price-comparison agents creates a mass of consumer valuation at or around the prevailing market price. Consequently, we would expect that in progressive online auctions, such as the Yankee auction, such bid levels would be realized towards the end of the auctions, rather than in the beginning or intermediate stages. This forms the motivation behind our attention to the combinatorial dynamics of the penultimate auction rounds.

Assuming that bidders are rational and follow a pedestrian bidding strategy, Bapna, Goes, and Gupta (2000) have shown that at the final stage of the auction, at most two bidding levels are observed. At a minimum, all bids would be at the lower level, while the other extreme would be to have all bidders at the higher level. The difference between the two bidding levels is equal to the bid increment. From an auctioneer's perspective the larger the number of bidders at the higher bid level, the greater the revenue. Intuitively, the process of determining the optimal bid increment is to create a partition in the discrete valuation space of the bidders such that the higher bid level becomes feasible to the maximum possible number of bidders. It follows that such a partitioning policy would optimize the expected revenue.

In the next section we present our analytical model that characterizes the expected revenue for Yankee auctions.

THE THEORETICAL MODEL

Based on a multivariate regression analysis of multi-unit Yankee auctions, Bapna, Goes, and Gupta (2000, 2001 a) revealed that, to a large extent, the valuation of the marginal consumer and the bid increment set by the auctioneer, determine the range of the auction revenues. The standard practice in the auction literature is to define the marginal consumer as either the highest unsuccessful bidder or the lowest successful bidder (Bulow & Roberts, 1989). Both definitions characterize the price-setting consumer and are equally useful in examining the structural characteristics of these auctions. We consider in this paper the marginal bidder as the highest unsuccessful bidder.

In the derivation of a theoretical model for the auctioneer's expected revenue, we assume that all bidders employ a pedestrian strategy, that is, at any point in time during the course of the auction, they will not bid higher than the required minimum to make it to the winner's list. The implication of this assumption is that the winning bids display at most two values, say, B and B + k, where k is the bid increment. IMAGE FORMULA 28IMAGE FORMULA 33IMAGE FORMULA 34IMAGE FORMULA 35

From the expected revenue expression in equations 1-3, it is clear that the bid increment k = a key determinant of the auction revenue. In this paper we seek to establish calibration mechanisms for the bid increment that optimize the expected auction revenue. A critical parameter necessary to optimize the bid increment is the value of the probability p that a bidder will be able to bid at the next higher bid level above B^sub 0^. To estimate p the auctioneer needs some information on the bidders valuation, a non-trivial task. Using such information, for any given bidding level, the auctioneers can infer the number of bidders who may have valuations for the product that are equal to or higher than the next feasible bid level.

Before we describe the empirical estimation tools, we would like to provide further intuition into the optimization of the expected revenue by setting the optimal bid increment using a numerical example:

Numerical Example 2. Suppose an auction has five items on sale, and the valuations for the highest six bidders are as follows:

Let B^sub 0^ = $110. Without knowing the actual valuation of each bidder, it would be sufficient if the auctioneer knew the number of bidders with a valuation above a certain bidding level. With the set of bidders above, the following table summarizes the relevant information for the auctioneer.

Therefore, if the marginal bid is 110, a bid increment can be determined that gives the optimum revenue. IMAGE FORMULA 47

From the table above, it is clear that setting the bid increment at $11 would yield the optimal expected revenue.

The above example assumes that the auctioneer knows the distribution of bidders' valuations a priori. It is common in auction theory to assume some known continuous distribution to which consumer valuations are said to belong. In this study we make use of automated software data collecting agents to track real online auctions, and in doing so build historical repositories of bid patterns that permit the empirical estimation of p values, as well as for making informed distributional assumptions regarding the bidders' valuations. In the next section we explain how we collect data from real online auctions and use it for deriving empirical distributions of the p values. We are also able to fit uniform distributions to the critical fractile of bidders' valuations obtained from the empirical observations. This, in turn, allows us to analytically obtain the optimal bid increment and revenue.

APPLYING ANALYTICAL RESULTS TO REAL AUCTIONS

Data Collection

An automatic agent was programmed to capture, directly from the website, the html document containing a particular auction's product description, minimum required bid, lot size and current high bidders at frequent intervals of 5-15 minutes. A parsing module developed in Visual Basic was utilized to condense all the information pertinent to a single auction, including all the submitted bids, into a single spreadsheet. We tracked over 150 auctions; however, complete bidding data was available for 65 auctions. The screening process was designed to ensure: (1) that there was no sampling loss (due to occasional server breakdowns), and (2) that there was sufficient interest in the auction itself, given that some auctions did not attract any bidders. Data collection lasted over a period of 6 months so as to guarantee a large enough sample-size (> 20) for each of the levels of bid increment chosen ($10 and $20). From the data collected we can construct the bidding history of each bidder who participated in each of the 65 auctions.

Obtaining Empirical Valuation Data

Based on the final bid of each bidder, a valuation is generated for that bidder by adding a random number drawn from U(O, k). For the losing bidders using a pedestrian bidding strategy, this is a rational estimate because the final bid offer can be considered a tight lower bound on the consumer's valuation. If the consumer's real valuation is greater than one bid increment above the final bid, then the bidder should have been able to constitute a new bid and either be in the winners' list or propel the auction to a higher bidding level. For the winners of the auction, these estimates are conservative, because as we saw in section 3, that auction can stop with the N winners not necessarily bidding all the way to close to their real valuation: However, for the purpose of estimating the effect on auctioneers' revenue they may be adequate. Table 2 gives a list of bids on one of the auctions that we observed and the consumer valuations inferred from these bids.

Optimizing Auction Revenues Using Empirical Distributions IMAGE FORMULA 55IMAGE FORMULA 65

Optimizing Auction Revenues Using Inferred Uniform Distribution

Our optimization approach is based on the knowledge of the critical fractile of the N + 1 highest valuations, which is contained in the upper-tail of the overall consumer value distribution. Since most of the theoretical distributions are relatively flat in the tail, we conjecture that it may be possible to approximate the critical fractile distribution with a uniform distribution.

From the data we collected, we can compute the number of distinct bidders that placed a bid at or above a given bid level, and thus can construct an implicit demand curve of the auction participants by calculating the number of people that will be willing to purchase a product at any given price.

Since a uniformly distributed value distribution produces a demand curve that is a linearly descending straight line, we can test our hypothesis that the distribution in the critical fractile is uniformly distributed by testing whether the demand curve is indeed a linearly descending straight line. We performed this test by taking the tail data of bids (data for last few bidding cycles) for each tracked auction. We then constructed the demand curves by computing the number of distinct individuals that placed a bid at a given bid level or higher. Figure 2 shows a representative demand curve based on the data for auction represented in Table 2 earlier. As the figure indicates, we get a fairly straight-line representation with acceptable distortions in real data. IMAGE FORMULA 68IMAGE FORMULA 72

Therefore, by estimating the critical fractile using an uniform distribution, we are able to use equation (7) and interactively determine the optimal value of the bid increment and the associated maximized revenue.

Equation (7) also provides insights into the structure of optimal bid increment with respect to the number of items on sale. This result is formalized in the following proposition: IMAGE FORMULA 77

RESULTS AND VALIDATION

Validation via Simulation

Bapna et al. (2001b) developed a robust simulation tool for replicating Yankee auction runs. The input to the simulation is the list of all final bids placed by all bidders in a real auction. A valuation is generated for each bidder by using a process similar to what is described earlier in this paper. The simulation program reads these valuations from a file, and for any given bid increment it can generate a specified number of runs representing different possibilities of bidding outcome as represented by the combinatorial possibilities illustrated in the theoretical model selection.

This simulation tool has proven to be very robust; comprehensive tests showed that the bidding streams, generated by the simulation, are samples of the same distribution as the real auction occurrence. It provides a very effective means to assess the impact of the choice of auction parameters. For example, Bapna et al. (2001b) discovered that, with respect to the bid increment, the revenue function is multi-modal; that is, one can often obtain optimal values for the revenue at multiple choices of the bid increment. It was also observed that in most cases the auctioneers chose bid increments that were far from the optimal choices. Due to its flexibility and robustness, this simulation tool was chosen to validate the theoretical results of this paper. In particular, we wish to compare two theoretically estimated measures of optimal revenues with two simulated scenarios.

The two theoretically estimated quantities are:

* The optimal revenue R(k^sub TO^) obtained from expression (3), when the bid increment k^sub TO^ is determined based on the estimated p represented in equation (4) using the empirical data directly. This is done by numerically evaluating equation (3) for all feasible choices of bid increments.

* The optimal revenue R(k^sub TU^) obtained from expression (3), when the bid increment k^sub TU^ is chosen by using equation (7); that is, the underlying assumption is that the critical fractile comes from a uniform distribution.

Each one of these are compared to the following two scenarios obtained from using the simulation tool:

* The maximum revenue R^sub S^(k^sub SO^) obtained by using the simulation tool to computationally evaluate each feasible bid increment and identify the optimal one (k^sub SO^). This comparison is intended to measure the accuracy of our analytical approach in deriving the optimal revenue.

* The optimal revenue generated by the simulation tool using the corresponding optimal bid increment, RS(k^sub TO^) or RS(k^sub TU^). This comparison test is intended to measure the impact of using the optimal bid increment derived by each theoretical model.

Recalling that the auctioneers' primary interest is in maximizing revenue, we wish to test the accuracy of the analytical model using our simulation tool under two different levels of information intensity (empirical and uniform). Our focus is on the examination of the equivalence of the revenue structures. We do this in a two-stage process beginning first by exploring simple percentage deviations between the theoretical and simulated revenues, followed by a rigorous trace drive simulation validation procedure suggested by Kleijnen et al. (1996, 1998).

Exploratory Data Analysis

Based on the data acquired from real-world auctions as discussed in the previous section, we ran 31 replications for each auction at each of the three revenue cases: Rs(k^sub SO^), RS(k^sub TO^), and RS(k^sub TU^). We used the average of the 31 runs for each of the 65 auctions under each revenue case to compare to the theoretical cases R(k^sub TO^) and R(k^sub TU^). The results for the 65 auctions are presented in Table 5 in terms of the mean percentage deviation from the corresponding simulated case.

The first row indicates that when using real valuations in the theoretical model, we achieve an average deviation of 0.48%lo from the simulation results using the best possible bid increment. This leads us to form an initial belief that given the empirically derived probability p, the theoretically optimal revenue is structurally similar to the simulated maximum revenue.

The theoretically determined optimal bid increment is often different from the bid increment at which the simulated revenue is maximized. Therefore, another issue worth exploring is whether the simulated revenue at the theoretically optimal bid increment is significantly lower than the estimated theoretical revenue. In row two of Table 5 we observe that while applying the theoretically derived bid increment in the simulation, the deviation is 0.47%. This result further adds a measure of robustness to our initial belief that the analytically determined bid increment is the one that maximizes the auctioneers' revenue. Both rows 1 and 2 of Table 5 were examined under the high information intensity case when the auctioneer had empirical distributions of consumer's valuations.

However, in many instances an auctioneer may have a more limited set ot information regarding the consumer valuations. For example, an auctioneer may only have estimates of lower and upper bounds on expected prices that consumers might be willing to pay. Based on our findings of the previous section, the revenue comparisons in rows 3 and 4 of Table 5 are conducted using a uniform distribution for the consumer valuations. It is clear that with lower information intensity, as compared to the empirical knowledge case, the accuracy of the theoretical model is not as high as the mean percentage deviation increases to 5.85%, but is still within a very reasonable range.

Trace Driven Validation

To validate more rigorously our analytical results against our simulation model, we adopted a trace-driven validation technique, as proposed by Kleijnen et al. (1996, 1998). The idea is to compare results of two temporal streams, in our case a theoretical stream of auction revenue values and a simulated stream. We are able to do this because our analysis captures the temporal dimensions of the auctions we tracked. They varied for each auction along the dimensions of lot size, price magnitude, and number of participating bidders. The trace driven validation approach tests if the two streams have identical means and variances. While details of the approach are beyond the scope of this paper, we present the main methodology below.

The validation procedure for comparing the revenues using the 65 auctions involves using the following 2 regression models. IMAGE FORMULA 92IMAGE FORMULA 96

There is overwhelming support for the equivalence of means for all revenue comparisons. There is also overwhelming support for the equivalence of variances for the comparisons involving theoretical model with empirical observed valuations. The support goes down (R2 goes up in the fourth column of Table 6) for the comparisons of the theoretical model with assumed uniform valuations. This is not surprising because under the uniform assumption we have more loss of information since individual valuations are not used and therefore more variability. As Kleijnen et al. (1996, 1998) point out, this is the case when the two distributions do not have equivalent variances. In other words, though the central tendencies are equivalent, the distributions themselves are not. Kleijnen et al. (1998) suggest that when the results of second regression are nonconforming to the hypothesis of equal variance, individual tests or pairwise t-test should be used to further investigate the properties.

Therefore, at the individual auction level, we test whether the theoretical revenue was equivalent to the mean of the 31 simulation runs for that auction. We used a standard t-test of difference of means. Table 7 shows the number of individual auctions in which we failed to reject revenue equivalence (theoretical vs. simulated) at the 10% significance level, for the same comparisons above.

Table 7 indicates that in a large number of cases even with limited information (assuming uniform critical fractile valuations) we can at least predict the expected revenue. Overall, the results indicate that if the auctioneer has access to empirical consumer valuations, the theoretical model can be used with a high degree of accuracy to determine the optimal bid increment for the auction. If these valuations are not available, but the customer demand of the critical fractile can still be inferred through a uniform distribution, the bid increment determined by the theoretical model can still yield very good results. From Table 7, revenues generated by using such bid increments can be very accurate two-thirds of the time. From the results in Table 5, on the average, the revenues obtained by using these bid increments are off by less than 4%.

The overall significance of our findings from the exploratory data analysis and the trace driven validation is that there appears to be strong support for the use of the theoretically computed bid increment in the design of multi unit online auction. By choosing the analytically determined bid increment, auctioneers can expect to maximize their revenues. There is also an interesting cost-benefit tradeoff between the cost of acquiring the information necessary to plug into the model (the p estimate) and the corresponding revenue benefit.

CONCLUDING REMARKS

In this paper we provide approaches at various levels of modeling and data abstractions to address the problem of optimal auction design. The actual applicability of each approach might depend upon the specific product and/or market information availability. Figure 3 provides a conceptual framework for integrating the insights provided in this paper into the design of online Yankee auctions. Beginning with tracking real online auctions to obtain estimates of consumer valuations and the demand curve, we develop a theoretical model of the revenue generation process. The optimization of this model requires estimates of the probabilities that bidders will bid at the next higher bid level, above the marginal bid.

To summarize, we developed a theoretical basis for determining the optimal bid increment setting for online Yankee auctions, an important emerging channel in the supply chain. The theory relies on the information that the auctioneer has regarding the bidder valuations. On the one extreme, relying on the empirical distribution of bidder valuations, our theoretical model can be used to determine optimal bid increment setting. The results of the theoretical model were tested using a simulation tool and we observed that the theoretically optimal bid increment yields maximal revenues. Similar, but not as strong, results are obtained if we rely on a uniform distributional characterization of the bidder valuation in the critical fractile, as opposed to an empirical one. It should be noted from an information cost perspective, the latter is far easier to ascertain than the former, hence the corresponding slight weakness in the result. In other words, depending on the amount of information available to the auctioneers, a low or high information intensity track could be pursued and optimal bid increments can be derived. The simulation tool can be used to explore a variety of scenarios and policies, and can be used as a test bed to improve the design and/or parameterization of a given auction.

From a practical perspective we expect auctioneers to have some prior estimates of the marginal (Bo) and the maximum valuations that consumers could be expected to have for a product being auctioned. These could be obtained from historical distributional data, price comparison agents, and other third party sources. They could use these initial estimates to compute the optimal bid increment and initiate the auction. As the auction progresses, it may be necessary that the original estimates may need to be revised, or quite simply a more accurate estimation of Bo may become available to the auctioneers. The revised estimate would capture the dynamics of that particular auction and the bidding strategies being employed in it. It would then behold the auctioneer to reapply our computationally efficient optimization procedure with the revised parameter estimates and dynamically adjust the auction parameters as the auction progresses. For instance, an auction could start with a bid increment of $20 and switch to a lower bid increment of, say, $10 as it appears to be closing.

In future work we will focus our attentions to other auction parameters in the design of online auctions that require optimization. These include, but are no limited to, the auction duration and the lot size among others. [Received: October 6, 2001. Accepted: July 3, 2002.]