Zero Intelligence Plus and Gjerstad-Dickhaut Agents for Sealed Bid AuctionsA. J. Bagnall and I. E. ToftSchool of Computing SciencesUniversity of East AngliaNorwichEngland NR4 7TJ{ajb,it}@cmp.uea.ac.ukAbstractThe increasing prevalence of auctions as a method ofconducting a variety of transactions has promoted inter-est in modelling bidding behaviours with simulated agentmodels. The majority of popular research has focused ondouble auctions, i.e. auctions with multiple buyers and sell-ers. In this paper we investigate agent models of sealed bidauctions, i.e. single seller auctions where each buyer sub-mits a single bid. We propose an adaptation of two learn-ing mechanisms used in double auctions, Zero IntelligencePlus (ZIP) and Gjerstad-Dickhaut (GD), for sealed bid auc-tions. The experimental results determine if a single agentadopting ZIP & GD bidding mechanisms is able to learnthe known optimal strategy through experience. We experi-ment with two types of sealed bid auctions, first price sealedbid and second price sealed bid. Quantitive analysis showsthat whilst ZIP agents learn a good strategy they do notlearn the optimal strategy, whereas GD agents learn an op-timal strategy in first price auctions.1. IntroductionThe increase in the level of Internet connectivity has al-lowed the WWW to become a hub for electronic tradingplaces. Buyers and sellers are now able to trade in previ-ously inaccessible markets. Some of the important ques-tions facing market overseers and traders are: what are theoptimal strategies for a given auction structure; how doagents learn the optimal strategy; and how does restric-tion of information prevent agents from learning a strategy?These questions have been addressed through auction the-ory [7, 12], field studies [8], experimental lab studies [9],and agent simulations [2, 4]. Recently there has been par-ticular interest in the study of agents for continuous doubleauctions (CDA) [2,3,5,6,10].We adapt learning mechanisms developed for CDA toinvestigate agent architectures for sealed bid auctions. Webroadly classify agent architectures in the following way:memory free agents, memory based agents and modellingagents.The simplest type of agent stores no explicit informa-tion about past auctions and simply reacts to the previ-ous auction outcomes. These so called memory free reac-tive agents have been examined extensively in [1, 2]. Thesecond type of agent we call memory based agents. Theseagents store some historical information about auctions andadjust their strategy based on some estimate of a global pic-ture of auction outcomes. They are considered to be moresophisticated than memory free agents and have been usedin [5,10]. The third type of agent we consider to be a mod-elling agent, these agents also store information about pastauctions. Rather than using the market information directlythese agents form models of competitors behaviour to esti-mate the correct action or strategy (for example, see [6]).It is our belief that prior to examining agent behaviourin complex, dynamic multi-agent systems, any agent archi-tectures should be tested in learning environments wherea known optimal strategy exists. In this paper we examinethe success of a single adaptive agent in learning the opti-mal strategy when competing against a population of non-adaptive agents. We use the Private Values Model (PVM)for auctions because, under some constraints, there areprovably optimal strategies. These strategies provide a met-ric with which we may assess the ability of an adaptiveagent in learning a strategy. They also are an obvious choiceof strategy for the non-adaptive agents.The rest of this paper is structured as follows: Section 2describes the auction model and the simulation structure.Section 3 details how the memory free ZIP [2] algorithm hasbeen adjusted for sealed bid auctions and assesses how wellit performs in simulations. Our experiments demonstratethat the complexity of the problem is such that memory freeagents learn a good, but suboptimal strategy. Section 4 de-scribes the memory based Gjerstad-Dickhaut (GD) [3] algo-rithm for sealed bid auctions. The GD agents perform bet-ter than ZIP agents, and on one class of sealed bid auctionslearn an optimal strategy. In Section 5 we present our con-clusions.2. Simulated Auction ModelThe PVM [12] is commonly assumed in auction re-search. For a PVM auction of N interested bidders, eachbidder (or agent) i has a valuation xiof the single object.Each xiis an observation of an i.i.d. random variable Xiwith range [0, φ] (φ is the universal maximum value) anddistribution function F , assumed to be identical for all bid-ders.Open auctions (auctions that allow bidders to observeother agents’ bids) such as English auctions (ascendingprice) and Dutch auctions (descending price) allow for mul-tiple bids by each bidder. Under the PVM, open auctionshave strategically equivalent sealed bid auctions (auctionswhere each bidder can submit at most one hidden bid).Hence we restrict our attention to sealed bid auctions. Anagent i forms a bid biwith 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 bid-der,w = arg maxi∈N(bi∈ B).We consider two auction formats which differ in theirmethod of price determination. In First Price Sealed Bid(FPSB) auctions, the winner pays the price they bid, i.e.p = maxi∈N(bi∈ B) = bw.Under the PVM, FPSB auctions are strategically equiva-lent to open Dutch auctions. In Second Price Sealed Bid(SPSB) auctions, the winner pays the amount bid by the sec-ond highest bidderp = maxi∈N,i6=w(bi∈ B).Under the PVM, SPSB auctions are strategically equivalentto open English auctions.The benefits of the PVM are that for certain auctionmechanisms and assumptions there is provably optimal be-haviour. Hence we can measure the performance of intel-ligent adaptive agents and assess under what conditionslearning is most effective. This is a necessary condition tostudying more interesting (and realistic) scenarios wherethe assumptions under the PVM concerning the competi-tors behaviour do not necessarily hold true.In any auction an agent’s profit (or reward) isri(xi) =(xi− p if i = w0 otherwise.(1)The problem facing an agent is to find the bid function thatwill maximize profit. If we assume that all the agents areusing the same bid function, a symmetric equilibrium is astrategy, β∗, where no