0 0 14 views

**Unformatted text preview:**

Zero Intelligence Plus and Gjerstad Dickhaut Agents for Sealed Bid Auctions A J Bagnall and I E Toft School of Computing Sciences University of East Anglia Norwich England NR4 7TJ ajb it cmp uea ac uk Abstract The increasing prevalence of auctions as a method of conducting a variety of transactions has promoted interest in modelling bidding behaviours with simulated agent models The majority of popular research has focused on double auctions i e auctions with multiple buyers and sellers In this paper we investigate agent models of sealed bid auctions i e single seller auctions where each buyer submits a single bid We propose an adaptation of two learning mechanisms used in double auctions Zero Intelligence Plus ZIP and Gjerstad Dickhaut GD for sealed bid auctions The experimental results determine if a single agent adopting ZIP GD bidding mechanisms is able to learn the known optimal strategy through experience We experiment with two types of sealed bid auctions first price sealed bid and second price sealed bid Quantitive analysis shows that whilst ZIP agents learn a good strategy they do not learn the optimal strategy whereas GD agents learn an optimal strategy in first price auctions 1 Introduction The increase in the level of Internet connectivity has allowed the WWW to become a hub for electronic trading places Buyers and sellers are now able to trade in previously inaccessible markets Some of the important questions facing market overseers and traders are what are the optimal strategies for a given auction structure how do agents learn the optimal strategy and how does restriction of information prevent agents from learning a strategy These questions have been addressed through auction theory 7 12 field studies 8 experimental lab studies 9 and agent simulations 2 4 Recently there has been particular interest in the study of agents for continuous double auctions CDA 2 3 5 6 10 We adapt learning mechanisms developed for CDA to investigate agent architectures for sealed bid auctions We broadly classify agent architectures in the following way memory free agents memory based agents and modelling agents The simplest type of agent stores no explicit information about past auctions and simply reacts to the previous auction outcomes These so called memory free reactive agents have been examined extensively in 1 2 The second type of agent we call memory based agents These agents store some historical information about auctions and adjust their strategy based on some estimate of a global picture of auction outcomes They are considered to be more sophisticated than memory free agents and have been used in 5 10 The third type of agent we consider to be a modelling agent these agents also store information about past auctions Rather than using the market information directly these agents form models of competitors behaviour to estimate the correct action or strategy for example see 6 It is our belief that prior to examining agent behaviour in complex dynamic multi agent systems any agent architectures should be tested in learning environments where a known optimal strategy exists In this paper we examine the success of a single adaptive agent in learning the optimal strategy when competing against a population of nonadaptive agents We use the Private Values Model PVM for auctions because under some constraints there are provably optimal strategies These strategies provide a metric with which we may assess the ability of an adaptive agent in learning a strategy They also are an obvious choice of strategy for the non adaptive agents The rest of this paper is structured as follows Section 2 describes the auction model and the simulation structure Section 3 details how the memory free ZIP 2 algorithm has been adjusted for sealed bid auctions and assesses how well it performs in simulations Our experiments demonstrate that the complexity of the problem is such that memory free agents learn a good but suboptimal strategy Section 4 de scribes the memory based Gjerstad Dickhaut GD 3 algorithm for sealed bid auctions The GD agents perform better than ZIP agents and on one class of sealed bid auctions learn an optimal strategy In Section 5 we present our conclusions 2 Simulated Auction Model The PVM 12 is commonly assumed in auction research For a PVM auction of N interested bidders each bidder or agent i has a valuation xi of the single object Each xi is an observation of an i i d random variable Xi with range 0 is the universal maximum value and distribution function F assumed to be identical for all bidders Open auctions auctions that allow bidders to observe other agents bids such as English auctions ascending price and Dutch auctions descending price allow for multiple bids by each bidder Under the PVM open auctions have strategically equivalent sealed bid auctions auctions where each bidder can submit at most one hidden bid Hence we restrict our attention to sealed bid auctions An agent i forms a bid bi with a bid function i 0 i xi bi The set of all bids for a particular auction is denoted B b1 b2 bN The winning agent w is the highest bidder w arg max bi B i N We consider two auction formats which differ in their method of price determination In First Price Sealed Bid FPSB auctions the winner pays the price they bid i e p max bi B bw i N Under the PVM FPSB auctions are strategically equivalent to open Dutch auctions In Second Price Sealed Bid SPSB auctions the winner pays the amount bid by the second highest bidder p max bi B i N i6 w Under the PVM SPSB auctions are strategically equivalent to open English auctions The benefits of the PVM are that for certain auction mechanisms and assumptions there is provably optimal behaviour Hence we can measure the performance of intelligent adaptive agents and assess under what conditions learning is most effective This is a necessary condition to studying more interesting and realistic scenarios where the assumptions under the PVM concerning the competitors behaviour do not necessarily hold true In any auction an agent s profit or reward is xi p if i w ri xi 0 otherwise 1 The problem facing an agent is to find the bid function that will maximize profit If we assume that all the agents are using the same bid function a symmetric equilibrium is a strategy where no single bidder can do better by using any other function A symmetric equilibria represents an optimal bidding strategy for any agent competing against other agents following the optimal