How to Choose the Bidding Strategy in Continuous Double Auctions:

Imitation versus Take-the-best Heuristics                                                                           Last update:12/2007

 

By Marta Posada & Adolfo López-Paredes

 

 

This WEB outlines the usage of a computer program described in the paper: How to Choose the Bidding Strategy in Continuous Double Auctions: Imitation versus Take-the-best Heuristics, published in 2008 in Journal of Artificial Societies and Social Simulation. The code is written in SDML which is a strictly declarative model language freely available from the Centre for Policy Modelling.

 

 

 

 

 

THE MODEL                                                                                                     [download source code]

 

 

The Figure 1 summarises the model structure which follows the guidelines adopted from human-subject market experiments. There are three dimensions which are essential in the design of any market experiment (Smith 1989): the institution (it is both the exchange rules and the way the contracts are closed), the environment (it includes the agent's endowments and values (reserve prices and marginal cost), resources, and knowledge), and the agents’ behaviour (it is the decisions taken by the agents). Alternative ontologies could be used to define the artificial model. But there are many advantages from adopting this standard because it is common to all the market results from experimental economics.

Figure 1: Model structure

 

We have defined a module hierarchy which allows us to add easily new bidding strategies or to substitute the institution by other (see Figure 2).

 

Figure 2: Module hierarchy

 

We have defined four agent types in the Market Module (see Figure 3): EnvironmentAgent, InstitutionAgent, SellerAgent and BuyerAgent.

 

InstitutionAgent inherits from PersistentCDAAgent which is defined in PersistentCDA Module.

 

BuyerAgent inherits from three agent types (KBuyerAgent, ZIPBuyerAgent and GDBuyerAgent) which correspond with the three alternative bidding strategies we have considered. Each one has been defined in different modules: KBuyerAgent in Klapan module, ZIPBuyerAgent in Cliff&Bruten module and GDBuyerAgent in Gjerstad module. Similarly, SellerAgent inherits from three agent types (KSellerAgent, ZIPSellerAgent and GDSellerAgent).

 

EnvironmentAgent is where we introduce the input data to run a simulation and where we obtain the output data. The input data are: supply, demand and the initial agents’ behaviour. Their values are defined in Market Module/EnvironmentAgent/Rulebases/Inicial. In the following subsections we explain how to do it. The output data are the transaction prices, the individual surplus obtained in each transaction, and the allocative market efficiency of each period. They are reported in Market Module/EnvironmentAgent/Rulebases/Final.

 

Each run consists of a sequence of fifteen consecutive trading periods, each lasting 100 time steps or rounds. The number of periods (numPeriod) and the number of rounds (numRound) are defined in Market Module/EnvironmentAgent/Rulebases/Inicial/eternity/Categories of rules/time levels setup/time simulation.

 

Figure 3: Type hierarchy

 

 

 

THE INSTITUTION: Continuous Double Auction (CDA)

 

We consider a Persistent CDA with a bid-ask spread reduction. Although the CDA protocol is well known, it is following detailed.

 

A new bid/offer has to provide better terms than previous outstanding-bid/outstanding-ask. A trade takes place when a new offer made is less than a pre-existing bid (currentBid) or when a new bid made is greater than a pre-existing offer (currentOffer). The pre-existing order is used to set the trade price. Otherwise, the order is appended to a queue of current open orders (rankQueueBid and rankQueueOffer).

                           

In Persistent Module/PersistentCDAAgent/Categories of clause definitions/parameters institution we have defined the following variables: 

  • currentBid: it is the bid of buyer who wants to buy more expensive than the others. If there are some buyers, we choose one randomly. If any buyer bids in this round, the currentBid is equal to the currentBid of the previous round. 

  • currentOffer: it is the offer of seller who wants to sell cheaper than the others. If there are some sellers, we choose one randomly. If any seller offers in this round, the currentOffer is equal to the currentOffer of the previous round.

  • rankQueueBid: We put the bids, which have not been accepted, in ascending order and we remove the previous bids which have been accepted.

  • rankQueueOffer: We put the offers, which have not been accepted, in ascending order and we remove the previous offers which have been accepted.

These variables are updated in Persistent Module/PersistentCDAAgent/Rulebases/Content/Categories of rules/current.

 

The transaction price is calculated in Persistent Module/PersistentCDAAgent/Rulebases/Content/Categories of rules/transaction. It is equal to the currentBid or to the currentOffer depending on the agent who accept the order was a seller or a buyer.

 

 

 

THE ENVIRONMENT

 

In the beginning of a run each agent is endowed with a finite number of units to trade. Agent-i has ni units to trade and he has a vector of valuations [Vi1, Vi2,…, Vini] for the corresponding units. Here Vi1 is the valuation to agent-i of the first unit, MCi2 is the valuation of the second unit, and so on. The valuations are private, i.e., each trader only knows his own valuations. The supply is the aggregation of sellers' valuations and the demand is the aggregation of buyers' valuations. We define them in MarketModule/EnvironmentAgent/Rulebases/Inicial/eternity/Categories of rules/setup environment/supply and demand setup.

 

This conceptualization of the environment enables to simulate different scenarios of market supply and demand. We have simulated three environments: E1, E2, and E3 (see Table 1)

 

E1 symmetric environment

E2 asymmetric environment

(demand is perfectly elastic)

E3 asymmetric environment

(supply is perfectly elastic)

[Download E1 Data]

[Download E2 Data]

[Download E3 Data]

Table 1: Environment scenarios

 

Although the number of sellers and buyers, and the agents' units are implicitly defined in supply and demand, we introduce the restriction that each trader has the same number of trading units (10 units) to prevent the agents from having relative initial advantage (numUnit 10 10\). We also specify the range of the orders (range 0 420\). The minimum and maximum range values are the currentBid and currentAsk in the first round of each period and in the round after a transaction, respectively.

 

 

 

THE AGENTS' BEHAVIOUR

 

In the beginning of a run each agent is endowed with a specific bidding behaviour from a portfolio of three alternatives strategies: ZIP, GD, and K. A model with n agents, each one with 3 bidding strategies (ZIP, GD, and K), requires the computation of n2/2+3n/2+1 populations that it is the number of combinations with repetition calculated as (k+n-1)!/(n! (k-1)!) where k is the number of bidding strategies, and n is the number of agents.

 

For example, for the specific population show in the Figure 3 of the paper, where all buyers are K and all sellers are GD, we define the buyers’'bidding behaviour in MarketModule/EnvironmentAgent/Rulebases/Inicial/period/Categories of rules/behaviour setup/fixed buyer behaviour (see Figure 4) and we define the sellers’ bidding behaviour in MarketModule/EnvironmentAgent/Rulebases/Inicial/period/Categories of rules/behaviour setup/fixed seller behaviour (see Figure 5).

 

Figure 4: Initial buyers' bidding behaviour

 

Figure 5: Initial sellers' bidding behaviour

 

 

The BuyerAgent and SellerAgent play four decisions: (1) Which bidding strategy should he choose to obtain a higher profit? Once this decision has been taken, each agent deliberates the following questions: (2) How much should he bid or ask? (3) When should he place a bid or an ask? (4) When should he accept an outstanding order?

 

 

  WHICH BIDDING STRATEGY SHOULD AN AGENT CHOOSE TO OBTAIN A HIGHER PROFIT?

 

We explore two fast and frugal heuristics (imitation versus take-the-best) to choose the bidding strategy. Although we also consider when the agents can not update their bidding strategies. How does the modeller select one of these options?

  • Agents can not update their bidding strategies: the rule in MarketModule/BuyerAgent/Rulebases/Inicial/round/Categories of rules/No change behaviour must be true and the rules of the others categories of rules must be false. It is similar in SellerAgent.

  • Agents update their bidding strategies using the take-the-best heuristic: the rules in MarketModule/BuyerAgent/Rulebases/Inicial/round/Categories of rules/change behaviour and in MarketModule/BuyerAgent/Rulebases/Inicial/round/Categories of rules/change behaviour: take the best must be true and the rules of the others categories of rules must be false. It is similar in SellerAgent.

  • Agents update their bidding strategies using the imitation heuristic: the rules in MarketModule/BuyerAgent/Rulebases/Inicial/round/Categories of rules/change behaviour and in MarketModule/BuyerAgent/Rulebases/Inicial/round/Categories of rules/change behaviour: imitation must be true and the rules of the others categories of rules must be false. It is similar in SellerAgent.

Thus, in the beginning of each trading period, each agent chooses a bidding strategy from a portfolio of three alternatives (ZIP, GD, and K).

 

If the imitation heuristic has been selected by the modeler, each agent changes his bidding strategy imitating the best bidding strategy in the following way: IF my profit is lower than the market average profit in the previous period THEN I will change my bidding strategy with a probability e. In case that the agent decides to change the bidding strategy, he imitates the bidding strategy with the highest average profit from the previous period (read paper for pseudo-code). To take the decision each trader knows his own profit, the market average profit, and the average profit for each bidding strategy.

 

If the take-the-best heuristic has been selected by the modeler, each agent changes his bidding strategy looking for the best in the following way: IF my profit in this period is not lower than it was in the previous one or my profit is greater than the minimum profit I expected THEN I don´t change my bidding strategy. Alternatively, I choose the bidding strategy which returns the highest profits based on past experience (read the paper for pseudo-code). The information each trader knows is his reservation prices and his memory (the transaction prices he made in the past, and both the maximum and minimum transaction price in each period). The agent does not know others’ bidding strategies or the profit achieved by other agents. To form his beliefs, each agent compares if the orders from an alternative bidding strategy could have had lower or greater profits than the profits that have been obtained using the current bidding strategy (read paper for pseudo-code).

 

 

   HOW MUCH AN AGENT BID OR ASK?

 

The three bidding strategies we consider are:  GD (Gjerstad and Dickhaut 1998), K (Rust et al. 1993), and ZIP (Cliff and Burten 1997). They have been widely described in previous literature. We have used the same parameters which have been proposed in Tesauro and Das (2001).

 

Each GD agent has belief-learning skills. Each agent chooses the order that maximizes his expected surplus, defined as the product of the gain from trade and the probability for an order to be accepted. The GD agents use the history of the recent market activity to calculate a belief function estimating the probability for an order to be accepted.  The buyers' GD bidding strategy is defined in Gjerstad Module/GDBuyerAgent/Rulebases/content/Categories of rules/behaviour rule. The belief function must be defined in Gjerstad Module/GDBuyerAgent/Rulebases/content/Categories of rules/belief process but it is in PersitentCDA Module/PresistentCDAAgent/Rulebases/content/Categories of rules/belief process. The reason is memory economy because all agents calculate the same belief function. Accordingly, the parameter value (memory) is defined in CPersitentCDA Module/PresistentCDAAgent/Rulebases/Initial/eternity/Categories of rules/memories setup. It is similar in GDSellerAgent.

 

Each K agent exhibits a parasitic behaviour. The basic idea behind this bidding strategy is: “wait in the background and let others negotiate and accept an order when it is interesting”. The buyers' K bidding strategy is defined in Kaplan Module/KBuyerAgent/Rulebases/content/Categories of rules/behaviour rule, the parameters values (minimum profit expected, time out, and ratio of orders) are defined in Kaplan Module/KBuyerAgent/Rulebases/Initial/eternity/Categories of rules/setup parameters. It is similar in KSellerAgent.

 

Each ZIP agent has a mark-up μ that determines the price at which he is willing to buy or sell in an adaptative way. The agents learn to modify the profit margin using the information generated in the last trading period. The buyers' ZIP bidding strategy is defined in Cliff&Bruten Module/ZIPBuyerAgent/Rulebases/content/Categories of rules/behaviour rule and in .../Presit adaptation process, the initial parameters values (learning rate, momentum learning coefficient, and initial mark up) are defined in Cliff&Bruten Module/ZIPBuyerAgent/Rulebases/Initial/eternity/Categories of rules/setup adaptation parameters and the updated mark up is defined in Cliff&Bruten Module/ZIPBuyerAgent/Rulebases/Initial/round/Categories of rules/setup and update mark up. It is similar in ZIPSellerAgent.

 

If an agent does a transaction, he computes his profit in Market Module/BuyerAgent/Rulebases/content/Categories of rules/profits , and then he checks if he has already units to trade in Market Module/BuyerAgent/Rulebases/content/Categories of rules/available units. It is similar in SellerAgent.

 

 

   WHEN SHOULD AN AGENT BID OR ASK?

 

When an agent is active at a given time step, he may submit an order (a new one or the replacement of an open order).  Of course, the bid/ask must be also in agreement with spread reduction institution rule. The agents have a constant activation probability of 25 percent.  This decision is defined in Market Module/BuyerAgent/Rulebases/content/Categories of rules/behaviour rule/when bid . It is similar in SellerAgent.

 

 

   WHEN SHOULD AN AGENT ACCEPT AN OUTSTANDING ORDER?

 

A buyer accepts the current ask if his bid (submitted or not) is equal to or lower than the current ask. This decision is defined in Market Module/BuyerAgent/Rulebases/content/Categories of rules/behaviour rule/when accept .

 

Similarly, a seller accepts the current bid if his ask (submitted or not) is equal to or greater than the current bid. This decision is defined in Market Module/SellerAgent/Rulebases/content/ Categories of rules/behaviour rule/when accept .

 

 

 

MARKET RESULTS

 

 

The main issue of this paper is the analysis of the market performance, in terms of efficiency, price convergence, and individual surplus, when agent can choose endogenously the bidding strategy from a portfolio with the individual goal of getting higher profits. The results are reported in a file.num which structure is define in Market Module/EnvironmentAgent/Rulebases/Final.

 

We explore two fast and frugal heuristics (imitation versus take-the-best) to choose the bidding strategy. Previous to such analysis, we analyze the market performance when the agents can not update their bidding strategies. Although it is a simple setting, it is a convenient starting point to compare the market performance between the different scenarios. We have simulated the three alternatives to choose the bidding strategy (fixed, imitation, and take-the-best), each one in three environments (E1, E2, and E3).

 

PRICE CONVERGENCE: To measure the price convergence, we use the α convergence coefficient that was defined by Smith (1962) as the ratio of the standard deviation of exchange prices to the competitive equilibrium price. Hence it is a measure of the exchange price variation in relation to the competitive equilibrium price.

 

INDIVIDUAL SURPLUS: The individual surplus is measure in each transaction as the difference between the transaction price and the valuation of the unit traded. To have a graphical idea of the profit achieved by agents with the same bidding strategy, we represent the individual profit achieved by each agent in each exchange using a colour code (ZIP: red, GD: blue, K: yellow).

 

In Table 2 we attach the run data of a market populated by a heterogeneous population (10 GD sellers and 10 K buyers) in all scenarios simulated.

 

 

E1 symmetric environment

E2 asymmetric environment

(demand is perfectly elastic)

E3 asymmetric environment

(supply is perfectly elastic)

Fixed bidding strategy

[Data 1 simulation]

[Data 1 simulation]

[Data 1 simulation]

Change the bidding strategy Take-the-best heuristic

[Data 1 simulation]

[Data 1 simulation] [Data 1 simulation]
Imitation heuristic [Data 1 simulation] [Data 1 simulation] [Data 1 simulation]

Table 2: Price convergence results

 

ALLOCATIVE MARKET EFFICIENCY: We also follow Smith (1962) to measure the market efficiency who defined the allocative efficiency as the total profit actually earned by all the traders divided by the maximum total profit that could have been earned by all the traders (i.e., the sum of producer and consumer surplus).

 

In Table 3 we attach the run data of a video where we can compare the market efficiency of all populations of the bidding strategy space when the agents have fixed bidding strategies. We report these values using a 3D figure where the z-axis is the market efficiency and both x-axis and y-axis are the bidding strategy space. We represent the bidding strategy space by a two dimensional simplex grid with vertices corresponding to the pure bidding strategies (all ZIP, all GD, or all K), x is calculated as (2(nºGD/total agents)+(nºZIP/total agents)-1)/raiz(3) and y is calculated as nºZIP/total agents. We use a colour code to have a graphical idea of the regions where one bidding strategy is the most popular strategy: ZIP in the red region, GD in the blue one, and K in the yellow one.

 

 

E1 symmetric environment

E2 asymmetric environment

(demand is perfectly elastic)

E3 asymmetric environment

(supply is perfectly elastic)

Fixed bidding strategy

[See video]

[Download data video]

   
Change the bidding strategy Take-the-best heuristic      
Imitation heuristic      

Table 3: Price convergence results