AstonCAT-Plus: An Efficient Specialist for the TAC Market Design Tournament

1 Introduction

Double Auction (DA) market is a market in which multiple buyers compete to purchase many items that are simultaneously offered for sale by multiple sellers [He et al., 2003]. This mechanism has dominated today's financial instruments exchange for its high allocative efficiency and simplicity in implementation. As economy and technologies evolve, the burgeoning online trading system and electronic marketplaces have offered traders more freedom than ever to trade their securities across the world. Given this, one DA market has to face competitions from other similar markets running concurrently around the world.

In order to explore automated mechanism design, the International Trading Agent Competition (TAC) market design tournament (also called CAT) simulates the competitive environment of multiple double auction markets. Entrants of the competition called specialists need to design their own strategies for the following policies [Cai et al., 2009]: clearing policy deciding how to match traders' offers and when to execute transactions; pricing policy calculating transactional prices; accepting policy judging what offers can be placed in the market; and charging policy determining what are appropriate fees. Another principal entity in CAT is the trader who may be either a buyer or seller willing to exchange goods. Traders are provided by the organiser and equipped with a trading strategy selected from four most studied ones: ZI, ZIP, GD, RE [Gode and Sunder, 1993; Cliff and Bruten, 1997;

Gjerstad and Dickhaut, 1998; Nicolaisen et al., 2001] and a market selection strategy which is mainly based on the history of the trader's profit made with each specialist.

A CAT game lasts a number of days (500 days in CAT2010). Each day consists of a number of trading rounds, which each lasts for a known constant length of time. The daily evaluation of the specialists is based on three metrics: (1) market share, which is the percentage of the total traders' population registered in the market; (2) profit share, which is the ratio of the daily profit a specialist obtains to the profit of all specialists and (3) transaction success rate (TSR), which is the percentage of the shouts accepted that result in transactions. The daily score of each specialist is the mean value of the above three metrics [Cai et al., 2009].

AstonCAT is a specialist designed for the CAT tournament. Inspired by its soaring improvement in performance on Day 3 of the competition (ranked 5th), we developed post-tournament version called AstonCAT-Plus which significantly outperforms its predecessor and achieves the highest TSR, allocative efficiency and average trader profit among all the specialists in controlled experiments. Our main contributions are: (1) We develop a new and effective equilibrium estimation algorithm reflecting both long-term and short-term market conditions. (2) We introduce intra-day shifting threshold shout accepting strategy. (3) We propose for the first time a clearing strategy which clears market based on profit target. (4) Our hierarchical market-adaptive charging strategy successfully solves the trade-off between maintaining a reasonably high market share and generating profit.

The rest of this paper is organised as follows: Section 2 presents the details of AstonCAT-Plus. Section 3 evaluates it through controlled experiments. Section 4 concludes.

2 AstonCAT-Plus

Figure 1 shows the architecture of AstonCAT-Plus. The strategies corresponds to the four policies mentioned in Section 1. Shout engine registers, sorts and classifies accepted shouts. It couples tightly with clearing strategy to determine which bids match which asks. Auctioneer acts as a coordinator assembling and passing information requested by other components. Market client deals with communication issues with the CAT server. Finally, market equilibrium estimator generates estimated current equilibrium price ˆ p∗ which is referred to by clearing, accepting and pricing strategies.

2.1 AstonCAT-Plus EquilibriumEstimation

According to micro-economy theory [Perloff, 1998], in order to efficiently allocate goods and fairly price transactions in a market, it is indispensable to estimate equilibrium price p∗ of the market. We estimate p∗ through running sliding windows on two independent streams of market information. One is run over the history of transaction prices to find short-term equilibrium price ps and the other over the averages of daily maximum transacted asks and the minimum transacted bids to find long-term equilibrium price pl. ps uses a higher weight for more recent transactions over a short window (typically 5) since ps is supposed to be reactive to the instant changes of market conditions. Let the last executed transaction be the kth transaction of the game, ps is calculated as follows,

where

pjt denotes the price of jth transaction and Wshort is the size of the sliding window. To obtain pl, the history of the maximum transacted ask a and minimum transacted bid b is maintained and the method described in [Honari et al., 2009] is used. Moreover, pl uses equal weight on every element over a relatively long window (typically 20) such that it reflects a long-term shifting tendency of our equilibrium price. Assuming day z's "DAYCLOSED" event has just occurred, pl can be obtained by,

where Wlong denotes the sliding window size and when z < Wlong, z itself is used as window size. Once pl value is established, it will be used for the next trading day.

Hence, we can see that ps contains only a few transactions' information and gets updated dozens of times a day whereas pl reflects several days' information and gets updated only once a day. By combining ps and pl, we have

where ωs is the weight of ps and the weight of pl is (1-ωs). According to experiments, the best ωs is chosen to be 0.3.

As shown by Table 4 (see Section 3.4), our transaction prices, which are normally our estimated equilibrium prices according to our pricing strategy, deviate from the theoretical ones by a small margin of 6.205 (6.28% of p∗ ). Moreover, AstonCAT-Plus achieves the highest allocative efficiency meaning that our traders retain 95.76% of the maximum profit that they can possibly get. Therefore, Formular 4 is effective for estimating market equilibrium.

2.2 Pricing Strategy

Our pricing policy simply sets transaction prices to ˆ p∗ if ˆ p∗ lies inside the bid-ask spread because p∗ represents where demand trades off supply. In the case that ˆ p∗ lies outside the spread, transaction price is set to the bid or ask price whichever is closer to ˆ p∗ to prevent negative transactional profit 1 . Comparing with side-biased pricing policy [Vytelingum et al., 2008], ours effectively rewards the intramarginal side in a transaction rather than the side with less population because short in number does not change an extramarginal trader to an intra-marginal one in CAT environment.

2.3 Shout Accepting Strategy

Shout accepting strategy decides whether a shout can be placed in our market. Our accepting thresholds are set around ˆ p∗ (see Figure 2). Firstly, due to the fact that the estimated equilibrium cannot be 100% accurate such that some slack can avoid intra-marginal shouts being wrongly rejected. More importantly, even ˆ p∗ is accurate, tolerance is still necessary because intra-marginal traders tend to attempt extramarginal shouts in order to gain a higher profit.

To this end, we set ˆ p∗ (1 + α) and ˆ p∗ (1 - α) as ask and bid thresholds respectively, where α, named slack rate, determines the degree of openness of the accepting policy. A small α will result in fewer accepted shouts and consequently less transactions than it should be. On the other hand, a large α will result in excess extra-marginal shouts and unfair matching between extra-marginal shouts and intra-marginal ones. Moreover, a too-open policy would reduce TSR due to lots of unmatchable shouts [Vytelingum et al., 2008]. To solve this trade-off, we decrease α with transactions such that the more the transactions, the tighter the thresholds become. At the beginning of each day, a large α can encourage shout submissions, which is important for maintaining market share. As transactions are executed, intra-marginal shouts (goods) are consumed which reduces the probability of new shouts being submitted by intra-marginal traders and extra-marginal shouts being matched. Therefore, a decreasing α can effectively block unmatchable shouts from extra-marginal traders and improve TSR. As a result, AstonCAT-Plus is not only attractive to traders (2nd best in market share) but also achieves the highest TSR in heterogeneous games of the controlled experiments (see Section 3.2).

1 Transactional profit is defined as profit generated by the difference between bid and ask prices.

An appropriate initial α is found via experiments between 0.15 and 0.35. Because seller and buyer quantities are usually not exactly symmetric, a bias to the side that is inadequately represented would give the fewer side more freedom and result in more balanced ask and bid profile. Let α0,a denote initial slack rate for sellers and α0,b for buyers respectively. α0,a and α0,b are updated daily as follows:

Where (nb+ns) 2 +(β-1)ns βns and (nb+ns) 2 +(β-1)nb βnb are bias ratios. ns and nb are the average number of sellers and buyers over last 5 days respectively. β ∈ [2, 5] is used to flatten the result such that the output will not be absurdly far from 1 even if there is a large difference in quantity between buyer and seller. During a day, α0,a and α0,b are deducted by a small value ϵ on every transaction until ask ratio ra and bid ratio rb reach their pre-defined limit la = 1.05 and lb = 0.95. Finally the ask and bid accepting thresholds τa and τb are,

where nt is the number of transactions happened in a trading day by the time of the calculation.

2.4 Market Clearing Strategy

While shout accepting strategy decides which shouts to be accepted, market clearing strategy decides how to match the accepted shouts and when to convert matches into transactions. AstonCAT-Plus's clearing strategy is a combination of Continuous Double Auction 2 (CDA) and our innovative profit per transaction (PPT) based clearing mechanism. Our PPT-based clearing scheme is designed to promote traders' profit. The idea behind it is: under certain conditions, we postpone transactions such that matched pairs within the same set of shouts can be reselected to prevent low-profit or extra-marginal transactions. Statistically, more than 70% of new shouts are submitted during first 3 rounds. Therefore, we use PPT-based clearing mechanism during this period to offer intra-marginal traders sufficient oppotunities to make their deserved profit. Responding to the change of market

2 Trade takes place as soon as there is a matchable pair of bid and ask offers in the market.

1. IF "SHOUTPLACED" event occurs THEN 2. shout engine sorts matched bid-ask pairs 3. IF round < 3 THEN /* clear market using PPT-based clearing scheme */ 4. flag = true 5. calculate average PPT for matched bid-ask pairs 6. IF matched shouts contain extra-marginal ones THEN flag = false 7. IF flag = true AND average PPT > θs THEN trigger clearing 8. ELSE IF flag = false AND average PPT > θl THEN trigger clearing 9. ELSE IFmatching volume > ntrader 10nmarket THEN trigger clearing 10. ELSE trigger clearing /* clear market using CDA */

conditions after 3 rounds such as reduced trading oppotunities, our clearing mechanism switches to CDA in order to focus on boosting transaction quantity as CDA gives intramarginal traders the greatest chances to exchange their remaining goods within the time left.

Figure 3 illustrates our clearing mechanism. The shout engine implements four-heap algorithm [Wurman et al., 1998]. ntrader is the total number of traders and nmarket is the total number of specialists. Two different minimum PPT limits θl and θs are employed. Extra-marginal transactions 3 do not get executed unless their average transactional profit is larger than θl. θs is considerably smaller than θl such that intra-marginal transactions have the priority to be cleared unless their profit is too small. However, as matching volume increases, we should not hold matches for too long even either PPT target can be reached because quantity of transaction must also be considered in order to maximise traders's total profit in our market. Therefore, statement on line 9 in Figure 3 sets a point where matches are cleared regardless of PPT. As for the values of θs and θl, we made them adaptive to perceptible traders' private value distribution. Assume that seller (buyer) will not attempt an ask (bid) under (over) his private value, highest attempted bid (bt) and lowest attempted ask (at ) over a number of days give an indication of trader's private distribution which confine the maximum of transaction profit. Accordingly, θs and θl are set 2% and 16% of bt - at . In our evaluation, specialists' actual PPTs are compared to show the effects of our clearing strategy (see Section 3.3).

2.5 Charging Strategy

The charging policy selects the type and the amount of the fees that registered traders should pay to obtain market services. AstonCAT-Plus only charges profit fee so that our market entry is free.

Our charging policy adapts fees according to our market status evaluated from several dimensions. As Figure 4 shows, our charging strategy consists of three hierarchical levels of rules. Upper level rules dominate lower ones such that fee updates fired by lower level rules are constraint within a rational range and direction defined by upper levels. Level-1 rules are set based on our current market share target completion which is a ratio between AstonCAT-Plus's current trader ncur and trader target ntar = number of traders number of markets . Average trader quantity of last 15 days is used as ncur. Level-1 functions to confine fees to a rational range instead of updating fees directly. Level-2 rules determines the direction of fee modification based on market trend which is identified using market trend ratio rt = ncur overall mean of daily traders . If rt > 1.16, "up" market trend is identified. If rt < 0.92, "down" market trend is identified. In the case that market trend cannot be detected, decision will be made by Level-3 which also determines step size of fee updates. The benchmark for setting Level-3 rules is called moving trend identified by moving trend ratio rv which is weighted ncur with higher weight for more recent days over ncur. rv > 1.06 indicates "up" moving trend, rv < 0.97 indicates "down" moving trend, and 0.97 ≤ rv ≤ 1.006 indicates no moving trend. Combining with decisions made by Level-2 rules, appropriate updating step sizes are selected (see Figure 4). Based on this charging strategy, our fees are rationally-confined, marketadaptive but stabilised against high volatility of market activities. Thus maintaining high market share and making high profit are well balanced.

3 An ask (bid) over (under) estimated equilibrium is identified as extra-marginal shout and transactions involving extra-marginal shouts are extra-marginal transactions.

3 Evaluation

This section analyses the performance of AstonCAT-Plus through controlled experiments in a similar way to [Niu et al., 2010] by which we attempt to relate market dynamics to our adaptive auction rules. Seven specialist agents 4 (see Table 1) are included in our experiments. Two types of experiments are conducted: heterogeneous games (240 traders) and head-to-head games (120 traders). Traders are uniformly distributed on the four provided trading strategies (ZIP, RE, ZI-C and GD) for both games. In heterogeneous games, AstonCAT-Plus competes with five opponent specialists developed by other institutes. In head-to-head games, AstonCAT-Plus competes with only one specialist each time which includes download agents and AstonCAT.

Our experiment setting is similar to that of CAT-2010 tournament: 500 days and 10 rounds on each day. However, 10 iterations were run instead of 3 in order to obtain statistically significant results. For intra-game analysis, data of a randomly selected representative game iteration are used.

4 We mainly include CAT-2010 agents and the latest version of known successful agents. All agents including AstonCAT and AstonCAT-Plus are available for download at http://www.sics.se/tac/showagents.php

3.1 Overall Performance

In heterogeneous games, AstonCAT-Plus achieves high performance - ranked 2nd according to the overall scores (see Figure 5). AstonCAT-Plus's average overall score of 10 iterations is only 1.71% lower than Mertacor (winner of CAT2010) but 29.96% higher than the next best agent Jackaroo (runner-up of CAT-2010). Statistically, AstonCAT-Plus's lead over other entrants is significant due to a very small p value (p value << 0.0001) in one tail paired t-test against each of them. Specifically, from Figure 5 we can also see that market share is a vital factor for the overall performance as the rank of overall score is monotonically associated with market share. Hence, maximising market share should undoubtedly be the primary target for CAT specialist design. Mertacor and AstonCAT-Plus together dominate the global market as sum of their market share (56.63%) is considerably more than the total of the other four specialists. Large market share also helps AstonCAT-Plus and Mertacor make the most profit although their average profit fee rate is just 4.15%which is far lower than some other agents like PersianCAT (20%) which make much less profit. Apparently, a small amount of fee on a large number of possible transactions after adequate market is gained is the best way to maximise a specialist's profit.

3.2 Transaction Success Rate

AstonCAT-Plus achieves the highest TSR among all the specialists. As Table 2 shows, AstonCAT-Plus is the only specialist that gained a more than 90% average TSR throughout heterogeneous games. From Table 2, we can also see that AstonCAT-Plus and Jackaroo outperforms Mertacor by 4.1% and 6.2% respectively in terms of TSR. However, AstonCATPlus's TSR is far more stable than Jackaroo as its standard deviation (0.0108) is less than half of that of Jackaroo (0.028). We attribute the success to our shifting threshold accepting strategy which ensures that unmatchable extra-marginal shouts submitted by extra-marginal traders can be blocked outside our market effectively as trading progresses.

3.3 Average Trader Profit

This subsection analyses the effects of our clearing strategy by comparing average trader profit of each specialist. Since a trader's average profit is determined by the average profit per transaction (PPT) and the average number of transactions per trader (TPT), we will look into these two factors in turn.

Figure 6 shows AstonCAT-Plus maintains a prominent advantage in terms of PPT. Although AstonCAT-Plus's average market share falls behind Mertacor's from day 210, our full-game mean of PPT exceeds Mertacor by 9.94 (21.2% of its mean). According to daily PPTs without averaging, only Mertacor and AstonCAT-Plus's daily PPT are stable with low standard deviation (3.72 and 4.30 respectively). The others' swing violently by a least standard deviation of 9.50. According to relative standard deviation to PPT mean (AstonCAT: 7.6%, Mertacor: 7.9%), AstonCAT-Plus achieves the highest PPT with the lowest variance.

High PPT alone does not mean traders make good profit in a market if their average number of transactions per trader (TPT) is small. At the start, everyone's TPT is around 1.5. But within a very short time, Mertacor and AstonCAT-Plus establish their lead almost simultaneously. Figure 7 shows, at the end of the game, traders with AstonCAT-Plus has traded averagely 1.77 goods out of three total entitlements which is 33.5%, 187.2%, 172.3%, 78.4% more than IAMwildCAT, PersianCAT, TWBB, Jackaroo respectively, but only 1.6% less than Mertacor. Our 2nd best TPT is mainly due to the clearing strategy that encourages intra-marginal transactions using smaller PPT threshold and switches to CDA at the right time.

Ultimately, PPT×TPT 2 gives us average trader profit.

Figure 7: Average transaction (goods traded) per trader.

AstonCAT-Plus's average trader profit (50.38) in this representative game significantly exceeds that of Mertacor, IAMwildCAT, Jackaroo, PersianCAT and TWBB by 19%, 75%, 130%, 303% and 335%, respectively.

3.4 Efficiency and Convergence

Allocative efficiency and convergence coefficient are two essential metrics to identify whether a market is efficient and stable. According to [Cai et al., 2009], the allocative efficiency is defined as the ratio of the trades' actual profit to the theoretical maximum profit (obtained had all traders traded at the theoretical equilibrium according to microeconomic theory), and the convergence coefficient is defined as standard deviation of transaction prices around daily theoretical equilibrium. According to the heterogeneous game results shown in Table 4, Mertacor and AstonCAT-Plus's efficiencies are significantly higher with significantly smaller standard deviation than other specialists, which means they are much more efficient and stable markets. AstonCAT-Plus is arguably more efficient than Mertacor not only because both our efficiency mean and maximum are better than Mertacor, but also that we keep our market in high efficiency considerably longer than Mertacor. AstonCAT-Plus achieves "> 95%" allocative efficiency for 395 days (79% of the game length) versus 308 days (62% of the game length) by Mertacor. Mainly we attribute our high efficiency to our accepting and clearing strategies.

3.5 Head-to-Head Games

We have also run head-to-head games between AstonCATPlus and each specialist from Table 1 and the results are generally consistent with heterogeneous games (see Table 3). Mertacor is still the only specialist that scores better than AstonCAT-Plus. Rather surprisingly, AstonCAT-Plus's average overall score is a massive 240% of that of AstonCAT which indicates the newer version successfully overcomes certain vulnerable points of the original one.

In this situation, we are also interested in how traders migrate and finally converge to one of the two markets. Figure 8 shows that market quickly converges to AstonCAT-Plus in the games against PersianCAT, TWBB and IAMwildCAT, gradually converges toward AstonCAT-Plus in the games against AstonCAT and Jackaroo. In the game against Mertacor, AstonCAT-Plus managed to hold an equilibrium of market share where traders do not converge to either market.

4 Conclusion

This paper details the strategy used by market specialist AstonCAT-Plus (post-tournament version for the TAC CAT). Specifically, we provide the novel strategies for accepting shouts, pricing transactions, clearing market and setting fees. AstonCAT-Plus is evaluated empirically with AstonCAT (tournament version for CAT-2010) and other top entrants of the competition, in which it performs stably and highly efficiently. Moreover, our mechanism has shown many adaptive features. For example, our clearing threshold adapts to the number of transactions and PPT limits adapt to perceptible traders' private value distributions. We believe some of our original ideas described in the paper can be borrowed by real world DA market designers.

As for future work, we will further improve our shout engine algorithm to enable clearing decision to be made on each individual bid-ask pair rather than the matched shouts bunch. Furthermore, most of our parameters are determined through experiments at the moment. We are going to design an evolutionary approach to learn optimal values for selected parameters through repeated games. By doing so, we believe the reusability of our mechanism can be improved too.