Sellers Competing for Buyers in Online Markets: Reserve Prices, Shill Bids, and Auction Fees

1 Introduction

Online markets are becoming increasingly prevalent and extend to a wide variety of areas such as e-commerce, Grid computing, recommender systems, and sensor networks. To date, much of the existing research has focused on the design and operation of individual auctions or exchanges for allocating goods and services. In practice, however, similar items are typically offered by multiple independent sellers that compete for buyers and set their own terms and conditions (such as their reserve price and the type and duration of the auction) within an institution that mediates between buyers and sellers. Examples of such institutions include eBay, Amazon and Yahoo!, where at any point in time multiple concurrent auctions with different settings are selling similar objects, resulting in strong competition 1 .

∗This research was undertaken as part of the EPSRC funded project on Market-Based Control (GR/T10664/01).

1 To illustrate the scale of this competition, within eBay alone close to a thousand auctions for selling Apple's iPod nano were running worldwide at the time of writing.

Given this competition, a key research question is how a seller should select their auction settings in order to best attract buyers and so increase their expected profits. In this paper, we consider this issue in terms of setting the seller's reserve price (since the role of the reserve price has received attention in both single isolated auctions and also in cases where sellers compete). In particular, we extend the existing analysis by considering how sellers may improve their profit by shill bidding (i.e., bidding within their own auction as a means of setting an implicit reserve price). We do so analytically in the case of two sellers, and then develop an evolutionary simulation to enable us to solve the general case of multiple sellers. Moreover, since shill bidding is generally undesirable (it undermines trust in the institution and decreases overall market efficiency), we then extend our evolutionary simulation to investigate how the institution can deter shill bidding through the use of appropriate auction fees. More specifically, we make the following contributions:

• We analytically describe the seller's equilibrium strategies for setting reserve prices for the two-seller case, and we advance the current state-of-the-art by finding Nash equilibria by iteratively discretising the search space. We show that, although no pure strategies exist when the sellers are symmetric, these can be found if production costs differ sufficiently between the two sellers.
• For the first time, we investigate shill bidding within a setting of competing sellers. To this end, we derive analytical expressions for the seller's expected utility when sellers shill bid. Using these expressions, we show that, without auction fees, a seller can considerably benefit by shill bidding when faced with competition.
• We introduce an evolutionary simulation technique that allows us to extend the analytical approach described above to the general case where an arbitrary number of sellers compete, and we benchmark this approach against our analytical results.
• Finally, we extend our evolutionary simulation, and use it to compare various types of auction fees. We evaluate the ability of different fees to deter shill bidding and quantify their impact on market efficiency. We show the novel results that within a market with competing sellers, auction fees based on the difference between the payment and the reserve price are more effective than

the more commonly used auction fees with regards to deterring shill bidding and increasing market efficiency.

The remainder of the paper is organised as follows. Section 2 describes related work in this area and section 3 describes our model of competing sellers. Section 4 analyses the buyer and seller strategies, and identifies the cases for which a pure Nash equilibrium exists, in the case of two sellers. Section 5 introduces an evolutionary simulation that allows us to solve the general case of multiple sellers. In section 6 we compare auction fees, and finally, section 7 concludes.

2 RelatedWork

McAfee [1993] was the first to consider mechanism design and reserve prices in the context of competing sellers. In his paper, sellers can choose any direct mechanism and these mechanisms are conducted for multiple periods with discounted future payoffs. However, he assumed that (i) a seller ignores his influence on the profits offered to buyers by other sellers, and (ii) that expected profits in future periods are invariant to deviation of a seller in the current period. As McAfee notes, these assumptions are only reasonable in the case of infinitely many players. In contrast, we consider the more realistic finite case, with a small numbers of buyers and sellers, where strategic considerations become important.

Subsequent papers have relaxed some of McAfee's strong assumptions. In Burguet and S´akovics [1999], a unique equilibrium strategy for the buyers in the two-seller case is derived (see also section 4.1). In addition, they show that there always exists an equilibrium for the sellers, but this cannot be a symmetric one in pure strategies. They are unable to fully characterize the mixed equilibrium, but argue that sellers set a reserve price above their own valuation of the item. This analysis is generalised for a large number of sellers in HernandoVeciana [2005], where it is shown that reserve prices tend to production costs in the limit case for asymmetric sellers.

Our work extends these results in a number of ways. First, we are able to locate pure Nash equilibria for the asymmetric seller setting (analytically in the case of two sellers and through an evolutionary simulation in the general case). Second, we introduce a mediator that charges commission fees to the seller for running the auction, and we investigate the case that sellers submit shill bids. Such shill bidding has previously been researched within isolated auctions [Wang et al., 2004; Kauffman and Wood, 2005]. However, our work is the first that considers shill bidding as a result of sellers having to compete. Finally, we investigate how auction fees can best be used to reduce a seller's incentive to shill bid. This is important since in many auctions shill bidding is illegal, but since it is hard to detect, it is difficult to prevent in practice. Again, whilst using auction fees to deter shill bidding has been considered in isolated auctions [Wang et al., 2004], here we investigate this issue in the context of competing sellers, and also consider how the auction fees affect the overall efficiency of the market.

Finally, we note that our work is also closely related to recent research on simultaneous auctions [Anthony and Jennings, 2003; Byde et al., 2002]. However, unlike our case, this research does not explicitly consider that the sellers need to tune their auction parameters such as the reserve price in order to attract buyers.

3 Model of Competing Sellers

The model of competing sellers proceeds in four stages (see figure 1). First, the mediator (an institution such as eBay or Yahoo! that runs the auctions) announces the auction fees to the sellers. The sellers then simultaneously post their reserve prices in the second stage. In the third stage, the buyers simultaneously select an auction (or, equivalently, a seller) based on the observed reserve prices. In the final stage, the buyers (and possibly the sellers who are shill bidding) submit bids and the auctions are executed concurrently. We now detail the three main components of our model:

3.1 TheMediator

The mediator decides on the auction fees and determines the market rules or mechanism to be used in the auctions. In our current model, we use a second-price sealed bid (or Vickrey) auction, in which the highest bidder wins but pays the price of the second-highest bidder.

3.2 The Sellers

A seller has the option to openly declare a minimum or reserve price. In addition, the seller is able to shill bid. If the shill bid wins the auction, effectively no sale is made, but a seller is still required to pay the auction fees.

3.3 The Buyers

A buyer first selects a single auction based on the announced reserve price, and then bids in the selected auction. Note that buyers are unaware that sellers shill bid. The bidding strategy is not affected by the reserve price; it is a weakly dominant strategy to bid the true value [Krishna, 2002]. On the other hand, the reserve price is an important factor in determining which auction the buyer should choose. To this end, the buyer's equilibrium strategies for selecting an auction are detailed in the next section.

4 Theoretical Analysis: Two Sellers

A complete analysis of equilibrium behaviour and market efficiency for the complete model is intractable [McAfee, 1993]. Therefore, in this section, we analyse a simplified version with two sellers and no auction fees (in section 5 we consider the general case of more than two sellers and in section 6 we address the complete model). We assume that there are N risk neutral buyers, each of whom requires just one item. Each buyer has valuation v independently drawn from a commonly known cumulative distribution F with density f and support [0, 1]. Each risk neutral seller offers one item for sale, has production costs xi, and decides upon a reserve price ri and shill bid si. Production costs are only incurred in case the item is sold. The preferences of buyers and sellers are described by von Neumann and Morgenstern utility functions.

4.1 Buyer EquilibriumBehaviour

The buyers' behaviour for two sellers has been analysed in [Burguet and S´akovics, 1999]. A rational buyer with valuation v < r1 will not attend any auction. Furthermore, if r1 < v < r2, the buyer will always go to seller 1. The interesting case occurs when v > r2. In a symmetric Nash equilibrium, there is a unique cut-off point 1 ≥ w ≥ r2 where buyers with v < w will always go to seller 1, and buyers with v ≥ w will randomize equally between the two auctions 2 . The cut-off point w is exactly where a buyer's expected utility is equal for both auctions, and is thus found by solving:

where F(y, w) = F (y) + [1 - F (w)]/2. Given this cut-off point, we can now calculate the sellers' expected revenue.

4.2 Seller EquilibriumBehaviour

To calculate the equilibrium behaviour of the sellers, we derive a general expression for the sellers' expected utility. This is calculated by considering the probability of one of three events occurring: (i) no bidders having valuations above the reserve price and the item does not sell, (ii) only one bidder having a valuation above the reserve price and the item sells at the reserve price, or (iii) two or more bidders having valuations above the reserve price and the item sells at a price equal to the second highest valuation. Thus, the expected utility of seller i who has a production cost of xi and sets a reserve price of ri is:

2 In the case of multiple sellers, the buyers' equilibrium strategy yields a sequence of cut-off points [Hernando-Veciana, 2005]. However, in this case, the sellers' equilibrium strategy can not be solved analytically, thus in section 5.1 we present an evolutionary simulation approach to find this equilibrium.

where G(y) is the probability that a bidder is present in the auction and that this bidder has a valuation greater than y.

Now, in the auction with no competing sellers, we have the standard result that G(y) = 1 - F (y) and G′ (y) = -f (y). However, for two competing sellers, we must account for the fact that the number and valuation of the bidders in the auction is determined by the bidders' cut-off point w. Thus, for sellers (with the lower reserve price) this probablity is given by:

and for seller 2, by:

Thus, the sellers' expected utility depends on the reserve price of both sellers and the equilibrium behaviour is complex. We now apply this result to three different cases: (i) where both sellers declare public reserve prices, (ii) where one seller declares a public reserve price and the other submits a shill bid, and (iii) where both sellers shill bid 3 .

Both Sellers Announce Public Reserve Prices.

In this case, the equilibrium strategy of each seller is given by a Nash equilibrium at which each seller's reserve price is a utility maximising best response to the reserve price of the competing seller. When x1 = x2, no pure strategy Nash equilibrium exists [Burguet and S´akovics, 1999]. However, when the sellers have sufficiently different production costs, we find that a pure Nash equilibrium exists where the reserve price of both sellers is higher than their production costs. We find this equilibrium numerically by iteratively discretising the space of possible reserve prices. That is, for all possible values of r1 and r2 that satisfy the conditions x1 ≤ r1 ≤ 1 and r1 ≤ r2 ≤ 1, we calculate w and hence the expected utility of the two sellers. We then search these reserve price combinations to find the values of r∗ 1 and r∗ 2 that represent the utility maximising best responses to one another. By iterating the process and using a finer discretisation at each stage, we are able to calculate the Nash equilibrium to any degree of precision, and we can confirm that this is indeed the pure Nash equilibrium by checking that the utility of seller 2 cannot be further improved by undercutting seller 1 (i.e. U2(r2, x2) < U2(r∗ 2 , x2) ∀ r2 < r∗ 1 ). Figure 2 shows an example of the utilities of each seller at this equilibrium (in this case x1 = 0.25, x2 = 0.50 and N = 10). Note that in this case there is clearly no advantage for seller 2 to undercut seller 1, and the reserve prices of r1 = 0.49 and r2 = 0.63 represent a stable Nash equilibrium from which neither seller will unilaterally deviate. Figure 3 shows a plot indicating the range of asymmetric cases (i.e., cases where x1 ̸= x2) in which we find a pure strategy Nash equilibrium.

3 When a seller shill bids, the declared reserve price has no additional benefit. Thus we assume they declare no reserve price (or, equivalently, declare a zero reserve price). In the next section, however, we relax this assumption.

As can be seen, the symmetric case is very much a special case, and the majority of possible production cost combinations yield unique pure strategy Nash equilibria, at which we can calculate the seller's expected utility.

One Seller Shill Bids.

Rather than announce a public reserve price, either seller may choose to announce a reserve price of zero to attract bidders, and then submit a shill bid to prevent the item from selling at too low a price. Thus, the seller who does not shill bid (seller 2 since r2 will be greater than r1) should declare a reserve price that is a best response to the zero reserve price announced by the bidder who does shill bid. This reserve price is simply given by the value of r2 that maximises U2(r2, x2), given that we calculate G2(y) as in equation (3) and take r1 = 0 in order to calculate w. Given the best response reserve price of seller 2, and the resulting value of w, we can also calculate the shill bid that seller 1 should submit in order to maximise its own expected utility. By substituting s1 for r1 in equation 1, and using G1(y) as given in equation (2), we find the shill bid that maximises U1(s1, x1).

Both Sellers Shill Bid.

Finally, when both sellers declare a zero reserve price and shill bid, the bidders will randomise equally between either auction, since there is no reserve price information to guide their decision. Thus we find the equilibrium shill bids of both sellers by again substituting si for ri in equation 1 and hence finding the value of si that maximises Ui(si, xi) when w = 0.

Table 1 shows an example of the resulting four strategy com-

Seller 2

binations as a normal form game (in this case N = 10, x1 = 0.25, and x2 = 0.5). Note that both sellers have dominant strategies to submit shill bids (this result holds in general in the absence of auction fees). At this equilibrium, seller 2 achieves its maximum possible utility. However, seller 1 receives more when neither seller shill bids and would thus prefer a mechanism that deters shill bidding.

5 Empirical Analysis: Beyond Two Sellers

In this section, we describe and validate an evolutionary simulation that allows us to simultaneously solve both the buyers' and sellers' equilibrium strategies in the more general setting beyond the two-seller case. Since our goal is to use this evolutionary simulation to compare auction fees, we also relax the assumption that a seller places a zero reserve price when shill bidding. This assumption was reasonable in the previous section and allowed us to derive analytic results. However, in the presence of auction fees we require that sellers are able to trade-off between the reserve price that they set, and the value of the shill bid that they submit.

We chose an evolutionary simulation, or more precisely evolutionary algorithms, since they provide a powerful metaphor for learning in economics. In the past, they have been successfully applied to settings where, like the one we consider here, game-theoretic solutions are not available [Anthony and Jennings, 2003; Bohte et al., 2004].

In the following, M refers to the number of sellers in the game, and N to the number of buyers.

5.1 The Evolutionary Simulation

Our simulation works as follows. The evolutionary algorithm (EA) maintains two populations, one with seller and one with buyer strategies. A seller strategy determines both the shill bid and reserve price for each auction 4 . As each of the M

4 Note that, although a seller always places a shill bid, setting this value below or equal to the reserve price is equivalent to not shill bidding. Moreover, the simulation has the option to disable the shill bid or the reserve price, which is used in Section 5.2 to validate the simulation results against the analytical solutions.

sellers can have different production costs affecting the optimal values, a strategy contains separate reserve prices and shill bids for each seller in the game (thus the number of sellers M affects the size of the strategies, but not the size of the seller population, which is independent of M). A buyer strategy determines the cut-off points for selecting one of the sellers as described in section 4.1. The buyer and seller strategies are encoded using real values within the range [0, 1].

The strategies are evaluated as follows. At each generation, M seller and N buyer strategies are randomly selected from the populations and compete against one another in a number of games. Although each strategy in the seller population contains the reserve price and shill bid for all sellers in the game, it is important that they are evaluated by competing against different strategies. Otherwise, a strategy would maximise the payoff in self-play, and would not be encouraged to reach the Nash equilibrium solution. When a game is played, each of the M selected strategies takes on the role of one of the sellers in the game. In order to evaluate each strategy as a whole, the game is played several times with the same strategies but with different roles for the seller strategies. The average payoff in these games then determines the strategies' fitness. This process is repeated until all strategies are evaluated and the fittest strategies are then selected for the next generation. Furthermore, new strategies are explored by slightly modifying existing individuals using a mutation operator. The evolutionary process is repeated for a fixed number of generations.

It is important to note that, as explained earlier, we assume that buyers are unaware that sellers shill bid (i.e., the sellers in the game have private information). Thus, we are not simply finding the Nash equilibrium of one large game, but we are effectively finding equilibria in two interrelated games; a buyer game in which buyers select sellers based on the announced reserve prices of the sellers, and a seller game, where sellers seek to attract buyers by announcing attractive reserve prices whilst simultaneously using shill bids to increase their revenue. To achieve this within the evolutionary algorithm, we simultaneously co-evolve the populations of buyer and seller strategies, but determine the payoffs of the buyer and seller strategies separately (i.e., the buyer payoffs are determined as though sellers do not shill bid, whilst the seller payoffs are determined by the 'real' game).

The results in this paper are based on the following EA settings. Each population contains 30 strategies and the evolutionary results are obtained after 500 generations. Each strategy is evaluated by playing 1000 competing sellers games with randomly generated buyer valuations. These valuations are selected from a uniform distribution with support [0, 1].

5.2 Validation

In order to validate our evolutionary simulation we compare it to the analytical results for two sellers from section 4.2. Figure 4 shows a comparison for all four cases whereby the two bidders either announce a non-zero reserve price, or alternatively, announce a zero reserve price and then submit a shill bid. In these experiments, seller 1 and 2's production costs are set to 0.25 and 0.5 respectively. These settings were chosen to illustrate representative outcomes when both sellers have non-zero and asymmetric production costs. However, similar results are obtained for other combinations of production costs (such results are not shown due to space limitations). As can be seen, the results show an extremely good match. In addition, we find that, although analytical results are not available for more than two auctions, even with more sellers the simulation results converge and are consistent across runs with different initial random seeds.

6 Auction Fees andMarket Efficiency

In this section we consider how the mediating institution can deter shill bidding by applying appropriate auction fees. To this end, we apply the evolutionary simulation to compare two types of auction fees. In addition, we investigate to what extent the market is efficient and how auction fees and shill bidding affect this efficiency. Efficiency is a desirable property since an efficient market extracts the maximum surplus that is available, and thus, it is important to take efficiency into consideration when setting the auction fees.

6.1 Auction Fees

We consider two types of fees: (i) the closing-price (CP) fee that is a fraction, β, of the selling price (where β is the CP commission rate) and (ii) the reserve-difference (RD) fee that is calculated as a fraction, δ, of the difference between the selling price and the seller's declared reserve price (where δ is the RD commission rate). The first type of fee is the most common in online auctions such as eBay, Yahoo!, and Amazon, as well as in traditional auctions such as Sotheby's and Christie's. The second type of fee is less common and was first introduced by Wang et al. [2004] where it was shown to prevent shilling for particular bidder valuation distributions in an isolated auction 5 . Similarly, our aim is to apply auction fees in order to reduce the incentive of a seller to shill bid, but we are considering a setting with competing sellers, and, in addition, we are concerned with the efficiency of the market.

Another popular type of auction fee is the buyer's premium, which is paid by the winner of the auction and is a fraction of the closing price. Although this fee is typically not applied to online auctions, it is still very common in traditional auctions. Surprisingly, however, we find that this fee is equivalent to the closing-price fee, provided that bidders are rational (space limitations preclude a formal analysis here). To see this, note that a bidder with a given valuation will correct his/her bid in the second-price auction such that the bid plus the fee in case the bid is accepted is equal to the bidder's valuation. Interestingly, since all buyers thus lower their bids, the seller ends up paying for the fee even though the fee is originally charged to the buyers. The same holds in case of other auctions such as the first-price auction.

6.2 Market Efficiency

A market is efficient when the items are awarded to the buyers with the highest valuations. Here, we measure the relative efficiency η of an allocation K, where η is given by:

where K∗ = argmaxk∈K[∑Ni=1 vi(k) - ∑Mi=1 xi(k)] is an efficient allocation, K is the set of all possible allocations, N is the number of bidders, M is the number of sellers, vi(k) is bidder i's utility for an allocation k ∈ K, and xi(k) is seller i's production costs for a given allocation (in order to prevent a negative value we add production costs xi in both the denominator and the numerator).

5 Rather confusingly, they refer to this fee as the commission fee.

Now, a certain amount of inefficiency is inherent to the competing sellers game as a result of the buyers randomising over sellers. For example, if two buyers with the highest valuation both happen to choose seller 1, only one of them is allocated the item and efficiency is not reached. However, shill bidding further reduces this efficiency. Firstly, this occurs because shill bidding enables a seller to hide its production costs and therefore attract buyers that have no chance of winning. A second source of inefficiency arises because a declared reserve price is usually low due to competition. An optimal shill bid, on the other hand, is higher than a declared reserve price (and higher than production costs), resulting in less sales, and therefore a lower efficiency.

6.3 Results

We now compare auction fees by considering: (1) the shill effect, which is measured as the difference that a buyer pays on average with and without shill bids, (2) the relative efficiency η as described in section 6.2, and (3) the seller costs, which is the average that a seller pays to the mediator (i.e., the auctioneer). The experimental results are shown in figure 5 for different commission rates and number of sellers. In these experiments, each seller's production costs are randomly selected from a uniform distribution with support [0, 0.5] at the beginning of each run. In addition, the number of bidders is set to an average of 3 per auction 6 .

As shown in figure 5(a), the RD fee is consistently better at reducing the shill effect, irrespective of the number of sellers. This is because the fee provides an incentive for lowering the shill bid as well as increasing the reserve price (since this reduces the difference between the closing price and reserve price). The CP fee, on the other hand, is neutral with regards to the reserve price.

By increasing the reserve price buyers can make a more informed decision about which seller to choose. This is especially important if sellers have different production costs. On the other hand, a higher reserve price may cause inefficiencies if this results in less items being sold. Figure 5(b), however, shows that both fees increase the market efficiency because of the reduced shill bid, and that the RD fees are more effective (if the RD fees are increased even further, however, the market becomes less efficient due to the high reserve prices, and CP fees perform better). The latter occurs because, with RD fees, the sellers' reserve prices better reflect their production costs. This is also confirmed by other experiments showing that the efficiency increase is similar for both fees if sellers have no production costs (not shown due to space limitation).

6 We note, however, that similar results are obtained with other settings.

We also consider the amount that sellers pay to the auctioneer. These seller costs are important when mediators are competing for sellers, and sellers may thus choose a different mediator with lower fees. As shown in figure 5(c), the RD fee results in much lower costs on average. Therefore, the RD fees are much more effective given the same costs.

Finally, we consider whether buyers actually benefit from the reduced shill effect. The results, depicted in figure 6, show a steady increase in buyer utility on average as the commission rates increase (this increase is not significantly different for RD and CP fees, however). Interestingly, these results imply that buyer utility increases even in case of a buyer's premium, since this fee is essentially equivalent to the CP fee (see section 6.1).

To conclude, the experiments show that the RD fee is more effective in deterring shill bidding and increasing market efficiency. These results generalise beyond the two-seller case, where the increased competition among sellers lowers the reserve prices and provides additional incentive to shill bid. This is consistent with earlier results showing that RD auction fees can deter shill bidding for isolated auctions [Wang et al., 2004]. However, our results show, for the first time, that these fees are also effective for a setting where sellers compete. Moreover, we see that, when using the RD fee, sellers pay much less to the mediator overall compared to CP fees. The latter is especially important in a larger setting where multiple mediating institutions compete to attract sellers.

7 Conclusions

Traditionally, competition among sellers has been ignored when designing auctions and setting auction parameters.

However, in this paper, we have shown that auction parameters (such as a reserve price) play an important role in determining the number and type of buyers that are attracted to an auction when faced with competition. We have also shown that such competition provides an incentive for sellers to shill bid, but this can be avoided by a mediator that applies appropriate auction fees. These results become particularly relevant for online markets where competition is high due to the ease with which a buyer can search for particular goods. Thus, in these settings, our results can be used by sellers seeking to maximise their profit, or by the auction institution itself, seeking to use appropriate auction fees to deter shill bidding and thus increase the efficiency of the market.

Research on competing sellers is a relatively young field and there are still a large number of challenges remaining. In future work, we intend to investigate the case where buyers require multiple items and can participate in multiple concurrent auctions. Ultimately, we would like to extend the concept of competition to the institutions themselves, and consider a model in which the actual institutions attempt to attract both sellers and buyers, whilst seeking to maximise revenue through their auction fees.