CHAPTER 14

Automatic Search of Behavior Strategies in Auctions

D. QUINTANA

Universidad Carlos III de Madrid, Spain

A. MOCHÓN

Universidad Nacional de Educación a Distancia, Spain

14.1 INTRODUCTION

Auctions have become a key mechanism in allocating items at different prices in many markets. Due to their special features and different formats, they are a useful tool for getting supply and demand to equilibrium. Some relevant markets where auctions are currently used are sales of personal communication services (PCSs), licenses, emission permits, electricity, and transportation services. It is very difficult to list the numerous papers on auctions but some examples are: Ref. 1 collects together in two volumes most of the relevant papers in the economics literature of auctions up to the year 2000; ref. 2 gives an account of developments in the field in the 40 years since Vickrey's pioneering paper; ref. 3 surveys the basic theory of how auctions work and describes the world-record-setting 3G mobile-phone license auctions; and ref. 4 gives an up-to-date treatment of both traditional theories of optimal auctions and newer theories of multiunit auctions and package auctions.

The study of auctions has traditionally been carried out by analytical means. However, this approach usually requires simplifying assumptions to reduce the complexity involved. This limitation is being tackled with the introduction of agent-based computational economics. This approach is based on simulations of auctions by intelligent artificial agents. The behavior of these agents is often adaptive and relies on different decision algorithms derived from the field of artificial intelligence, such as genetic algorithms (GAs), artificial neural networks, or evolutionary strategies.

This chapter deals with the search for bidding strategies in a specific multiunit auction: the Ausubel auction. For this purpose, we develop a GA that tries to maximize the bidders' payoff. GAs are a robust method of adaptive searching, learning, and optimization in complex problem domains [5]. We start validating the model by testing it under circumstances for which there is an analytical solution, and then we focus our attention on the outcomes obtained when we face a new setting: the presence of synergies. The remainder of the chapter is structured as follows. A revision of previous work done in auctions with computational techniques is given in Section 14.2. In Section 14.3 we present the theoretical framework of the Ausubel auction. The description of the GA and the bidding functions tested are described in Section 14.4. In Section 14.5 we evaluate the experimental results. Finally, we summarize the main conclusions and outline potential futures work.

14.2 EVOLUTIONARY TECHNIQUES IN AUCTIONS

The use of computational simulation to analyze auctions is not new. There are several researchers who rely on computational experiments to study the complex and stochastic processes inherent in auction learning models [6]. The most popular approach examines the interaction of artificial adaptive agents (AAAs), developing their behavior with adaptive learning algorithms such as GAs, genetic programming (GP), or evolutionary strategies (ES).

A contentious issue in the design of the experimental framework concerns encoding the possible strategies that bidders can follow. Table 14.1 presents some of the most relevant pieces of work on the subject. Some authors use agents that are already implemented, such as agents with zero intelligent plus learning heuristics (ZIP). Cliff and Preist [7–9] tested this technique for the continuous double auction. Moreover, Cliff [10] proposed an automated online auction that allows a wide range of possible market mechanisms. Cliff models the market by means of a set of ZIP traders. These markets were allowed to evolve using a GA, in order to minimize the deviation of transaction prices from the theoretical equilibrium prices. Other authors prefer to develop agents with their own particular bidding protocol. Andreoni and Miller [6] developed a GA to capture the bidding patterns for first- and second-price auction formats with affiliated private values, independent private values, and common values. The algorithm searched over two-parameter linear functions in each auction. Dawid [11] modeled a two-population GA to study the learning behavior of buyers and sellers in a sealed-bid double auction with private information. Each individual in the population was encoded with a string, and a fitness value is calculated measuring the success of the individual by the average payoff earned in the last period (a group of m iterations).

Byde [12] also explored the possibility of using GAs in a sealed-bid auction where payments were determined by linear combinations of first- and second-price auctions. The strategy followed by an agent was defined by a piecewise linear function from input signal to bid. All agents followed optimal strategies that were determined by a GA. Anthony and Jennings [13,14] suggested an agent-based approach to bidding strategy evolution for specific environments using GAs. These authors tested the English, Dutch, and Vickrey auction. The behavior of the agents was subjected to a set of polynomial functions that represented bidding constraints. These functions were denoted as tactics and their combination was referred to as a strategy. The strategy requires the allocation by the agent of the appropriate weight to each tactic. These weights plus the set of parameters required to define the constraint functions mentioned conforms the array of floating-point values that define the individuals in the population to be evolved. Finally, Saez et al. [15] explored the bidding behavior and the effects on revenue and efficiency when one bidder evolves according to a GA. The auction format selected was the auction developed by Ausubel [16,17]. Saez et al. tested the algorithm for several rationing rules, and the results suggested that the selection of a rationing rule can be a key point in the final outcome of this auction mechanism.

TABLE 14.1 Summary of Work with Auctions and EC

14.3 THEORETICAL FRAMEWORK: THE AUSUBEL AUCTION

The research presented in this chapter is focused on the Ausubel auction (see [16,17]), which is defined as follows:

The analysis of auctions using adaptive agents can be performed using different approaches. The one that we are going to choose is focused on bidders and their behavior. We simulate Ausubel auctions where individual agents try to identify, in an autonomous way, strategies that result in higher profits for them. Therefore, we are facing an optimization problem. Given a set of agents (bidders) with specific personal values, each tries to find the bidding strategy that maximizes the payoff. The payoff is the difference between the value derived from the lots that they win and the price they paid for them.

Once we have set this starting point, we make a methodological proposal that will be built around the idea that agents, chasing individual targets, might obtain extraordinary profits in a dynamic environment with certain strategies. To understand the different strategies a bidder can have in an auction, it is useful to comprehend first the concept of personal value and marginal value. The personal value is the personal or estimated worth for a commodity that a person has. The marginal value is the increase in total personal value associated with an increment of a unit in consumption. Bidders can exhibit:

• Diminishing marginal values (substitutes in consumptions). This means that when a bidder increases his consumption by 1 unit, his total personal value increases but at a decreasing rate this is, he has diminishing marginal values. For example, consuming 1 unit can yield a personal value of 10 (v_{i, 1} = 10), and consuming 2 units can yield a total personal value of 15, so the second unit has a marginal value of 5 (v_{i, 2} = 5).
• Synergies (complementarities in consumptions). We are in the presence of synergies when the value of consuming multiple objects exceeds the sum of the objects' values separately. For example, consuming 1 unit can yield a personal value of 10, and consuming 2 units together can yield a total personal value of 25.

According to their values, bidders can follow three main strategies: underbid, overbid, and bid sincerely. Underbidding means to submit bids for lower prices than the personal values. Overbids are bids higher than the personal values. Finally, if bidders bid sincerely, they bid according to their true personal value.

To define the auction outcome, it is necessary first to make a basic specification of the model from the formulation in [16]. In each auction the seller offers M number of indivisible units of a homogeneous good to n number of bidders. Each bidder i obtains a marginal value of v_i,_k for the kth unit of the good, for k = 1, …, M. Thus, if bidder i gets units for a total payment of , he obtains a payoff of

For any round l, the aggregate demand by all bidders is . The cumulative vector of quantities clinched by bidder i at prices up to p^l is defined by

Given the individual quantities clinched at price p^l, set , defined as

The auction outcome associated with any final history l = L is defined by

In the same way, the seller's revenue per auction is defined as the total payments by all bidders:

Table 14.2 includes an example of the Ausubel auction where participants bid sincerely and exhibit diminishing marginal values. The outcome of this example is reported in Table 14.3.

Ausubel demonstrated that in this auction format, when bidders have weakly diminishing marginal values (substitutes in consumptions), sincere bidding (SB) by every bidder is an ex post perfect equilibrium yielding to an efficient outcome. Nevertheless, there are several markets where synergies or complementarities (when the value of multiple objects exceeds the sum of the objects' values separately) can be found. Probably, the best known are the personal communication services license sales, done in most countries (United States, UK, Germany, etc.). In this sector the agents might be interested in acquiring two or more geographically neighboring licenses (local synergies), or multiple licenses, in order to get economies of scale (global synergies) [18]. In this circumstance (i.e., in the presence of synergies), the theoretical equilibrium for the Ausubel auction is yet to be found.

TABLE 14.2 Auction Process in Which All Bidders Bid Sincerely and Exhibit Diminishing Marginal Values^a

TABLE 14.3 Auction Outcome When All Bidders Bid Sincerely

As we mentioned earlier, in the experiments done, we consider two possible scenarios: The first one is a basic framework with decreasing marginal value (substitutes in consumption). The second deals with the presence of synergies (complementarities in consumption). Both can be studied using the codification of strategies presented in the following section.

14.4 ALGORITHMIC PROPOSAL

We present an artificial market where agents operate following bidding strategies that evolve with time. The algorithm that drives this evolution is a GA. This algorithm assesses the fitness of each strategy through the profit that the bidder obtains in a simulated auction. In every case, strategies are fixed for each auction but vary within successive auctions.

The experimental setting consists of 15 lots and four bidders that are risk neutral and have no limits on the amount they can spend (all variables are considered discrete). All bidders have independent private values that are observed privately by the respective bidders, making this an incomplete information game. Bidders have no bid information regarding the development of the auction process, as they only know whether the auction is still open (there is no dropout information). At the heart of this approach lie bidding functions that are determined by two main elements: personal values and potential strategies. We begin with the former.

In the basic experimental setting, all bidders have decreasing marginal values. This means that every bidder has a set of values organized from higher to lower that specify the marginal value from the consumption of each additional unit. Since there is an analytical solution regarding the existence equilibrium, we tested this environment. To do so, we force each bidder to define his or her values for at least as many items as the total supply. Bidders' values are drawn independently and identically distributed from a uniform distribution with support [0, 200], with new random draws for each additional unit. For experiments that involve synergies, every bidder has a set of values organized from lower to higher that specify the marginal value for the consumption of each additional unit. Bidders' values are also drawn independently and are identically distributed from a uniform distribution with support [0, 10,000], with new random draws for each additional unit.

For both experimental settings, in each auction bidders use a strategy codified in the chromosome of the individual that represents that bidder. The definition of the GA strategy suggested requires the identification of actions. Each action is defined in terms of deviations (over- and underbidding) from the SB strategy. The quantity demanded according to the SB strategy of bidder i in round l is represented by , the units demanded if bidders bid according to their true values. The bidders have 13 possible actions to consider, which are represented in Table 14.4. All these strategies have an upper bound that is the lowest of either the number of units being auctioned or, alternatively, the units demanded in the previous round (as demand is required to be nonincreasing). The lower bound is the number of units that the participant has already clinched. It is possible that some strategies lead to noninteger numbers. In these circumstances the GA rounds up. The objective function that the GA tries to maximize is the payoff of each bidder. For this purpose, encoding the bidding strategies is a direct process. The 13 possible actions can be encoded with 4 bits (including the SB strategy, ).

TABLE 14.4 Each Bidder Considers 13 Possible Actions or Bidding Strategies

14.5 EXPERIMENTAL ANALYSIS

In this section we analyze the experimental results in the presence of decreasing marginal utilities and synergies, with 15 items to be auctioned and four bidders. We study revenues and efficiency as well as the bidders' behavior and payoff. As we already mentioned, revenues are measured as the monetary units that the seller gets after each auction (see Equation 14.6). Furthermore, an auction is considered to be efficient when it allocates the object to the bidder who values it the most ex post the auction. Therefore, for these experiments, efficiency is defined as the sum of the personal values of the 15 units sold in an auction as a percentage of the sum of the 15 highest personal values in that auction (full efficiency = 100%). Finally, the bidders' payoff (see Equation 14.1) and bidding strategy are analyzed in each environment.

The assessment of the GA is made by running 10,000 auctions per experiment. The marginal values are initialized randomly for each experiment, but they are constant for all the GA executions, this is, they have the same marginal values for the 10,000 auctions. For the GA we used the standard implementation of the SimpleGA developed by GALib. The parameters used for the experiments are reported in Table 14.5. We use a vector of 4 bits for encoding each bidder (13 strategies). As we are working with four bidders, our population size is 4.

The first step in analyzing the auction outcome with the GA and decreasing marginal values is to study the bidders' behavior. Bidders try all possible strategies, but finally, bidders tend to bid sincerely (76.07% bidders follow this strategy). In terms of revenues and efficiency, if we compare the results obtained by the GA and the results predicted (i.e., those yielding an outcome based on all bidders bidding sincerely), we observe that the actual average revenue with the GA is higher than that predicted. However, this difference represents only 12%. The GA aims to improve the bidders' payoff. Therefore, all bidding strategies are tested. 72.84% of the auctions yield to the same revenue that would be obtained if all bidders did SB. The average efficiency level (98.8%) is also very close to the one predicted (100%), and 76.13% of the auctions yield to full efficiency. This difference is because the GA tries all possible bidding strategies and because of the evolution and mutation effects. At the beginning, all the strategies are settled randomly, and most of them correspond to bad strategies. Moreover, new individuals are always created with the mutation operator. However, bidders finally tend to bid sincerely.

TABLE 14.5 Parameters Used for the Experiments

The bidders' payoff is another convenient way to study the participants' behavior. Table 14.6 includes the percentage of iterations that the bidders' strategy yield to the same payoff as bidding sincerely. The results reveal that most bidders using the GA strategies are getting the same payoff as those using the SB strategy. The GA has been tested in 50 experiments, and in all of them bidders tend to SB. This finding corroborates the theory established by Ausubel [17]: that SB is a weakly dominant strategy in this auction, with no bid information and weakly decreasing marginal values.

We repeat the same tests in an environment that involves synergies (when the value of multiple objects exceeds the sum of the objects' values separately). The effect over revenues and efficiency that the strategy proposed by the GA yields is summarized in Table 14.7. The average revenues obtained with the GA are very close to those that would be obtained if all bidders were to bid sincerely. The difference is only 2%. Of the 10,000 iterations, 75.12% yield to the same revenues as if all bidders do SB. As bidders are primarily bidding sincerely, the average efficiency level is also very close to full efficiency (92.9%). Furthermore, 86.19% of the iterations gave an efficiency level of 100%.

TABLE 14.6 Bidders' Payoff with Decreasing Marginal Values^a

Bidder	Times (%) Payoff GA = Payoff SB
1	73.69
2	73.60
3	72.88
4	74.00

^aNumber of iterations in which each bidder earns the same payoff as if all bidders do SB.

TABLE 14.7 Revenue and Efficiency Analysis in the Presence of Synergies^a

Figure 14.1 GA and SB revenue per iteration in the presence of synergies (last 1000 auctions).

Figure 14.2 Efficiency per auction in the presence of synergies for the last 1000 auctions.

Revenues per auction for the last 1000 iterations are represented in Figure 14.1. This figure just corroborates the intuition drawn from Table 14.7: SB is the most frequent strategy. The efficiency analysis for the last 1000 iterations is represented in Figure 14.2. Although the GA yields to some efficiency levels below 100%, those strategies are not stable. Nevertheless, the strategy that bidders tend to use yields full efficiency. When bidders bid sincerely, those participants with the highest valuations are awarded the items. However, it is also possible for this strategy to earn negative payoff in the presence of synergies. If one bidder does not clinch all the units demanded at the standing price, his or her valuation can be lower than the total payment. In this circumstance he or she will have a negative payoff (exposure problem). Even so, the GA best strategy without dropout information is to bid sincerely. Bidders have no information during the auction to respond to their rival's bids. As Table 14.8 shows, bidders usually earn the same payoff as if they all bid sincerely.

TABLE 14.8 Bidders' Payoff in the Presence of Synergies^a

Bidder	Times(%) Payoff GA = Payoff SB
1	94.91
2	84.18
3	95.41
4	75.07

^aNumber of iterations during which each bidder earns the same payoff as if all bidders do SB.

The GA has been tested in 50 experiments within this environment. In all experiments conducted, bidders finally tend to bid sincerely. As there is no theory model developed for this assumption, the results predicted were uncertain. Similarly, as bidders tend to bid sincerely, efficient allocation of the items remains.

14.6 CONCLUSIONS

In this chapter we have dealt with the subject of bidding strategy optimization by means of evolutionary computation. This work is focused on a specific dynamic ascending multiunit auction which is referred to as the Ausubel auction. Given the complexity of studying this framework using traditional tools, we present an approach based on agent-based economic modeling.

We have developed a GA that can be employed successfully to evolve bidding strategies for this auction format. The GA aims to maximize each bidder's fitness, measured in terms of the the actual payoff. For this purpose, the algorithm generates 13 different bidding strategies or actions defined in terms of deviations from the SB strategy: overbidding, underbidding, or bidding sincerely. The experiments simulates auctions of 15 lots among four bidders. Each experiment was run for 10,000 iterations.

The results that we have obtained using decreasing marginal utilities and no bid information are consistent with the conclusions drawn by Ausubel [16,17] that established that SB is a weakly dominant strategy and an ex post perfect equilibrium. In all 50 computational experiments performed in this study, bidders tended to bid sincerely. The main contribution of this work is a study of this auction in the presence of synergies, as no theoretical model has yet been developed with this assumption. In the 50 experiments conducted, the algorithm evolves SB as the most frequent strategy. There are several directions in which the work presented could be extended. First, the information rule established can have important implications. Therefore, it could be interesting to analyze the outcome of the auction assuming that there is dropout information during the auctions that is, bidders have full bid information. Another alternative could be to let bidders have memories of their past experiences. Another possibility lying ahead is study of the final lot allocation when the bidders' values are interdependent (i.e., assuming common values). Finally, assessment of the sensitivity of the results to a wider range of combinations of number of bidders and items to be auctioned would be very interesting.

Acknowledgments

The authors are partially supported by the Spanish MEC and FEDER under contract TIN2005-08818-C04-02 (the OPLINK project).

REFERENCES

1. P. Klemperer. The Economic Theory of Auctions, vols. I and II. Edward Elgar, Cheltenham, UK, 2000.

2. V. Krishna. Auction Theory. Academic Press, San Diego, CA, 2002.

3. P. Klemperer. Auctions: Theory and Practice. Princeton University Press, Princeton, NJ, 2003.

4. P. Milgrom. Putting Auction Theory to Work. Cambridge University Press, New York, 2004.

5. J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975.

6. J. Andreoni and J. H. Miller. Auctions with artificial adaptive agents. Games and Economic Behaviour, 10:39–64, 1995.

7. D. Cliff. Evolving parameter sets for adaptive trading agents in continuous double-auction markets. In Proceedings of the Agents'98 Workshop on Artificial Societies and Computational Markets, 1998, pp. 38–47.

8. C. Preist and M. Van Tol. Adaptive agents in a persistent shout double auction. In Proceedings of the 1st International Conference on the Internet, Computing and Economics. ACM Press, New York, 1998, pp. 11–18.

9. C. Preist. Commodity trading using an agent-based iterated double auction. In Proceedings of the 3rd Annual Conference on Autonomous Agents, 1999, pp. 131–138.

10. D. Cliff. Exploration in evolutionary design of online auction market mechanisms. Electronic Commerce Research and Applications, 2(2):162–175, 2003.

11. H. Dawid. On the convergence of genetic learning in a double auction market. Journal of Economic Dynamics and Control, 23:1545–1567, 1999.

12. A. Byde. Applying evolutionary game theory to auction mechanism design. In Proceedings of the ACM Conference on Electronic Commerce, 2003, pp. 192–193.

13. P. Anthony and N. R. Jennings. Evolving bidding strategies for multiple auctions. In Proceedings of the 15th European Conference on Artificial Intelligence, 2002, pp. 178–182.

14. P. Anthony and N. R. Jennings. Developing a bidding agent for multiple heterogeneous auctions. ACM Transactions on Internet Technology, 3(3):185–217, 2003.

15. Y. Saez, D. Quintana, P. Isasi, and A. Mochon. Effects of a rationing rule on the Ausubel auction: a genetic algorithm implementation. Computational Intelligence, 23(2):221–235, 2007.

16. L. M. Ausubel. An efficient ascending-bid auction for multiple objects. Working Paper 97-06. University of Maryland, College Park, MD, 1997.

17. L. M. Ausubel. An efficient ascending-bid auction for multiple objects. American Economic Review, 94:1452–1475, 2004.

18. L. M. Ausubel, P. Cramton, P. McAfee, and J. McMillan. Synergies in wireless telephony: evidence from the broadband PCS auctions. Journal of Economics and Management Strategy, 6(3):497–527, 1997.

19. S. Hon-Snir, D. Monderer, and A. Sera. A learning approach to auctions. Journal of Economic Theory, 82 (1): 65–88, 1998.

20. S. Park, E. H. Durfee, and W. P. Birmingham. An adaptive agent bidding strategy based on autonomous agents. In Proceedings of the 3rd Annual Conference on Autonomous Agents, ACM Press, New York, 1999, pp. 147–153.

21. C. Preist. Algorithm design for agents which participate in multiple simultaneous auctions. Hewlett Packard Laboratories Technical Report HPL-2000-88, 2000.

22. J. Bower and D. Bunn. Experimental analysis of the efficiency of uniform-price versus discriminatory auctions in the England and Wales electricity market. Journal of Economic Dynamics and Control, 25: 561–592, 2001.

23. A. Byde. An optimal dynamic programming model for algorithm design in simultaneous auctions. Hewlett Packard Laboratories Technical Report HPL-2001-67, 2001.

24. Z. Qin. Evolving marketplace designs by artificial agents. M.Sc. Thesis, Computer Science Department, Bristol University, 2002.

25. A. Byde, C. Preist, and N. R. Jenning. Decision procedures for multiple auctions. In Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems: Part 2, ACM Press, New York, 2002, pp. 613–620.

26. S. Phelps, S. Parsons, P. McBurney, and E. Sklar. Co-evolution of auction mechanisms and trading strategies: towards a novel approach to microeconomic design. In Proceedings of GECCO 2002, 2002, pp. 65–72.

27. E. Ogston and S. Vassiliadis. A peer-to-peer agent auction. In Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems: Part 1, ACM Press, New York, 2002, pp. 151–159.

28. M. P. Wellman, J. K. Mackie-Mason, D. M. Reeves, and S. Swaminathan. Exploring bidding strategies for market-based scheduling. In Proceedings of the 4th ACM Conference on Electronic Commerce, ACM Press, New York, 2003, pp. 115–124.

29. S. M. Bohte, E. H. Gerding, and J. A. La Poutre. Market-based recommendation: agents that compete for consumer attention. ACM Transactions on Internet Technologies, 4:420–448, 2004.

30. A. Mochon, D. Quintana, Y. Saez, and P. Isasi. Analysis of Ausubel auctions by means of evolutionary computation. In Proceedings of the IEEE Congress on Evolutionary Computation 2005: Vol 3, 2005, pp. 2645–2652.