Generating Bayes-Nash Equilibria to Design Autonomous Trading Agents

1 Introduction

Auctions are becoming an increasingly popular method for transacting business, both between individuals over the Internet and between businesses and their suppliers. In this context, auction theory provides us with some simple equilibria, mostly for the case when a single item is being bought or sold. However, in practice, agents (or humans) are rarely interested in a single item. Rather, they often wish to bid in several auctions in parallel for multiple goods. Moreover, the fact that the value of each good to an agent often depends on other goods makes this problem particularly hard. Given this background, the International Trading Agent Competition (TAC) [Wellman et al., 2001] defined a benchmark game that incorporates several elements found in real marketplaces, and different researchers adopted a variety of approaches to tackle the problem (see e.g. [Stone et al., 2002] or [Greenwald and Boyan, 2001]). Now, most of these approaches operate based on some form of heuristics, because it is widely claimed that a principled theoretic approach is not practical. However, in [Vetsikas and Selman, 2003] we outline a general, principled methodology for systematically exploring the space of bidding strategies for complex games with multiple interdependent goods, which are traded in several different auctions, like TAC, where it is not possible to find an equilibrium solution. Specifically, to handle this complexity, we decompose the problem into sub-parts, which are then analyzed separately, before the various resulting strategies are recombined to generate the strategy the agent should use.

Against this background, in this paper we actually compute Bayes-Nash equilibria for some of these sub-problems and

Bart Selman

CS Dept., Cornell University, Ithaca, NY 14853, USA selman@cs.cornell.edu

then use them to generate new trading strategies. Even though our general methodology is motivated from the fact that complex games cannot be analyzed using the current game theoretic tools, by concentrating on one sub-problem, we can now analyze it. In particular, we examine auctions that have a set of possible closing times, one of which is chosen randomly for the auction to end at, and compute several novel equilibria. To evaluate our work we applied it to a sub-problem of TAC, the purchase of a hotel room of a particular type. In more detail, in TAC Classic, m = 16 rooms are available in each category (meaning hotel and day) and they are sold in separate, ascending, multi-unit, mth -price auctions (one per category). These auctions close at randomly determined times and, more specifically, a random auction will close every minute throughout the game. The agents want to buy up to 8 rooms, but for ease of analysis we assume that each such agent is represented by 8 sub-agents, each of which is interested in a single room. In this way, we have N = 8 × 8 = 64 agents each wishing to buy 1 unit (room) in the auction. Between closing times, the agents may place bids, but these are not opened until the next possible closing time; hence each round that takes place between consecutive closing times is effectively a sealed bid auction. The agents' bids are binding, as they cannot subsequently be retracted. 1

This paper makes a number of contributions to the state of the art. In section 2, we analyze the Bayes-Nash equilibria that exist in mth -price auctions with multiple possible closing times and compute several equilibria that have not been seen in the literature before. In particular, the equilibrium that we look for in each case is the unique symmetric equilibrium. Now, some of the initial stages of this work appeared in [Vetsikas and Selman, 2006] where we presented equilibria for the 2-round case, without any implementation details. The current paper extends this very preliminary work by presenting equilibria (with proofs in most cases) for the general multi-round case, as well as for the special case of a first price auction. In section 3, we describe the implementation of this work to various cases, including the TAC game. Finally, in section 4, we generate two new TAC strategies inspired by this analysis, and we determine, via experiments, that one of them is superior. We then used this strategy in the actual competition (where the corresponding agent was highly successful). We conclude this paper, in section 5, by detailing interesting directions for future extensions of this work.

1 As well as being a benchmark for the international competition, there are also a number of real world auction settings that exhibit these characteristics. The Yahoo! auctions have a "random" closing time, since they are extended every time a new bid is placed. In addition governments sometimes conduct rounds of binding and nonbinding bids when privatizing resources (normally the first rounds consist of non-binding bids, and the latter rounds of binding ones). As in TAC, after each round of binding bids, there is a chance that the government will decide, for political or economic reasons, to end the auction (well before the last possible closing time). Furthermore, in many countries, the spectrum auctions for third generation cellular phones involved multiple rounds of bidding.

2 Computing the Equilibria

We assume that N risk-neutral agents wish to buy 1 unit of a certain good each. An independent seller sells m units of the desired good in an mth price auction. The agents have valuations (utilities) uri at round r which are i.i.d. drawn from distribution Fr(u). Each agent knows accurately its own valuation uri at the current round and all the distributions Fr(u). The probability that round r is the last round is known to be pr. If more rounds exist, an agent can submit new bids as long as they are greater or equal to the bid price from the end of the previous round; this is the minimum bid allowed at round r which is denoted as Qr. We make two different assumptions about the information each agent i knows about its utility ur′ i (r′ ≥ r) at the start of the round r:

• ur′ i can be assumed to be relatively similar to the current utility uri , and thus ur′ i ≃ uri ; this is reasonable for TAC because usually there is a correlation between the valuation of the same room over the course of the game. This assumption is used in theorems 3 and 5.
• The more general case is when the agent only knows that ur′ i is drawn from some distribution Gr′(u). This distribution could even be Gr′(u) = Fr′(u), when no information whatsoever exists. We use this assumption in theorem 6.

In addition, agents may not subtract bids. In the TAC game, when the valuation of a room drops below the bid price Qr, it is an optimal behavior for the agent to place a bid equal to Qr as late as possible, since in this way it might be lucky enough to get rid of the room. If only k < m agents have utilities uri ≥ Qr, the rest of the rooms are sold to (m- k) winners of the round (r - 1), that no longer wish to buy; all their bids are equal to Qr and the TAC rules state that the (m- k) earliest placed such bids will get the rooms, therefore this means that a random selection of those winners will get the rooms, as the order of their bid placements is random.

It should be noted that all the equilibria when p1 ̸= 1 are the solutions of differential equations of the form described

by theorem 1, which is taken from [Atkinson and Han, 2004]. Theorem 1 Let f(x, z) and ∂f(x,z) ∂z be continuous functions of x and z at all points (x, z) in some neighborhood of the initial point (x0, Y0). Then there is a unique function Y (x) defined on some interval [x0 - α, x0 + β], satisfying:

This theorem guarantees the existence and uniqueness of the equilibria we compute in the next sections.

2.1 Equilibria For A Single Unit Auction

In this section, m = 1 and the single unit is sold to the agent which submitted the highest bid at a price equal to its bid. In theorem 3, we assume that in the second round the utilities are drawn from the same distribution as in the first round, and that u2i ≃ ui. Each agent i submits a bid vi in the first round. We compute a Bayes-Nash equilibrium g(u) that maps utilities ui to bids vi. In the case of p1 = 1 (only one round) and Q1 = 0, we know from standard auction theory that each risk-neutral agent i with valuation ui should bid:

Theorem 2 If the starting price is Q1 ≥ 0 and the bidding lasts for exactly 1 round (p1 = 1) the equilibrium strategy is

Proof. Since Q1 > 0, (i) some agents might have stopped participating in the auction, since the current price Q1 exceeds their private valuation ui, and (ii) the probability distribution of the valuations F1(u) has changed, since now we know that the valuation of agents that still participate is ui ≥ Q1. The new probability distribution is:

We also know the probability πk of the event that exactly k agents participate in the auction at price Q1; it is the probability that exactly (k - 1) of the other agents' valuations 2 ui are ui ≥ Q1, which is (see e.g. [Rice, 1995]):

Let us assume that it is a Bayes-Nash equilibrium for each agent i to bid vi = g(ui). If k agents participate then the utility of agent i is 0, if it does not have the highest bid, and (ui - vi), if it does. The expected utility of agent i when it places a bid of vi (in the case of k agents) is:

Since vj = g(uj), it is Prob[vi ≥ vj] = FQ(g-1 (vi)). Let Φ(x) = (F1(x))N-1 . The expected utility regardless of the number of agents participating is:

The bid vi that maximizes EUi(vi) can be found by setting dEUi(vi) = 0 ⇔ (ui - vi) · Φ′ (g-1 (vi ))

dvi g′ (g-1 (vi)) = Φ(g-1 (vi)). Since we assumed that the optimal solution is vi = g(ui), the previous equation becomes:

The solution of this equation, for boundary condition g(Q1) = Q1, is equation 1; this can be easily verified. ■

2 Because from the point of view of a participating agent it does not know whether the other (N - 1) agents participate.

It should be noted that this theorem is reminiscent of the work in [McAfee and McMillan, 1987] concerning the equilibrium solution in the case that the distribution F1(u) has a minimum value vl, presented by equation 5 in that paper. In fact the two equilibria are given by similar equations, where the minimum valuation vl is substituted by the minimum allowable bid Q1. However there are also some important differences between theorem 2 and that work. In particular, in the case examined by theorem 2, the number of agents participating is not known a priori, because some of them may have a private valuation ui which is smaller than the minimum allowable bid Q1; this creates a fundamental difference compared to the case examined by McAfee and McMillan where there is a minimum valuation vl. Indeed, dealing with this uncertainty concerning the number of bidders, which participate in the auction, constitutes the core of the proof of theorem 2.

Theorem 3 If the starting price is Q1 = 0, a second round of bidding exists with probability (1 - p1) (p1 ̸= 0, 1) and the utility of the agents in the second round is drawn from the same distribution F2(u) = F1(u) as in the first round (and each agent i in fact has utility of a similar value to the utility ui of the first round) then the equilibrium strategy is the solution of the differential equation:

where the boundary condition is g(0) = 0,

Φ(x) = (F1(x))N-1 and Ψ(x) = 1 + 1-p1 p1 · (F1(x))N-1 . Proof. Due to space considerations we omit this proof. However it has similarities with the proof of theorem 5. ■

As a special case, we can examine this equation when only N = 2 agents participate and their valuations ui ∼ U[0, 1], which means that F1(u) = u, ∀u ∈ [0, 1]. Equation 5 becomes:

In figure 1 (left), we graph the solution for various values of 1-p p . We provide this figure in order to contrast with the Bayes-Nash equilibrium for the case that p = 1, which is g1(ui) = ui 2 (see e.g. [Krishna, 2002]). One may notice that as the probability (1 - p) of a second round increases, the equilibrium strategy suggests that the agent should bid less. In section 3, we compare these results with those produced by our algorithm for solving the R-round case.

2.2 Equilibria For Multiple Round Auctions

In this section we present the system of equations for computing the equilibria for the R-round auction (R ≥ 2). Let us define Φr(x) and Yr(x) as follows:

In the short paper [Vetsikas and Selman, 2006], 3 we give the following theorem for the 1-round case:

Theorem 4 If the starting price is Q1 ≥ 0 and the bidding lasts for exactly 1 round (p1 = 1) the equilibrium strategy is

3 This proof and other details that have been omitted from this paper may also be found at Dr. Vetsikas' thesis.[Vetsikas, 2005]

In the next proofs, we will use the following derivation from the proof of theorem 4, without proving it here; that the expected utility, if the auction closes at this round r, is:

Theorem 5 If the starting price of the current round r is Qr ≥ 0, the next round of bidding (r + 1) exists with probability (1 - pr) (pr ̸= 0, 1) and the utility of the agents in round r is drawn from the distribution Fr(u) (and each agent i in fact has utility uri of a similar value to the utility ui of the first round) then the equilibrium strategy is the solution of the differential equation:

where Ψr(u, x) = 1 - 1-pr pr · ∂Ur+1(u,x) ∂x , and Ur+1(ui,Qr+1) is the expected utility at round (r + 1), when the agent's utility is ui and the starting price is Qr+1. The boundary condition is g(Qr) = Qr.

In addition, the expected utility at round r given this strategy gr(ui) is then:

Proof. If the auction closes at the first round, then the expected utility is given by equation 8. To compute the expected utility from the other rounds, we need to examine the value of Qr+1, which depends on the bids placed in the current round. The probability distribution of the (m-1)th and mth highest bids among all other agents at this round, named respectively B(m-1) and B(m) , are Prob[B(m-1) ⩽ v] = Yr(g-1 (v)) and Prob[B(m) ⩽ v] = Φr(g-1 (v)). If B(m) > vr i , then Qr+1 = B(m) . If B(m-1) > vr i ≥ B(m) , then the agent submitted the mth price, so Qr+1 = vr i . If vr i ≥ B(m-1) , then Qr+1 = B(m-1) . Note that Prob[Qr+1 = vr i ] =

As a result, we can now compute the expected utility from the rest of the rounds U ∗ i as follows:

utility: u

Figure 1: Equilibrium strategies for case N = 2, m = 1 and utility drawn from uniform distribution U[0, 1], (left) using equation 6 for the case when R = 2 rounds exist, and Q1 = 0, and (right) using the algorithm of figure 2 for the 1st round of 8 and probabilities pr equal to those of TAC.

The expected utility for both rounds is:

The bid vi that maximizes EU r i (vr i ) can be found by setting dEU r i (vr i ) dvr i = 0. Then we set vr i = gr(ui) and eventually we derive the differential equation 9.

If ui = Qr then the agent must bid vr i = Qr, hence the boundary condition.

From equations 11 and 12, by substituting vr i = gr(ui), we derive equation 10. ■

In the following theorem the utility in the later rounds is assumed not to be precisely known and to be drawn from distribution Gr (u).

Theorem 6 If the starting price of the current round r is Qr ≥ 0, the next round of bidding (r+1) exists with probability (1-pr) (pr ̸= 0, 1), and the utility of the agents in round r is drawn from the distribution Fr(u) (and each agent i knows more accurately that, in fact, its utility uri is drawn from distribution Gr(u)), then the equilibrium strategy gr(uri ,Qr) is the solution of the differential equation:

and the expected utility at round r when uri is drawn from Gr(u) is:

The boundary condition is g(uri , Qr) = Qr, when uri = Qr. Ur(uri , Qr) is the expected utility at round r, when the agent's utility is uri and the starting price is Qr and given that gr(uri ,Qr) has been computed it is:

Proof. Due to space limitations and because the proof of this theorem shares a number of common steps with the proof of theorem 5, we will give a sketch of the proof. One should notice that equation 15 is derived in almost the same way as equation 10. However since the utility uri in round r is not precisely known, and is drawn from distribution Gr(u), we must use equation 14 in order to compute the expected utility at a round r, based on all posible utility values. The other important difference between the two proofs, is that we must also compute the expected gain of utility (actually it's negative, so it's a loss) U r+1 L (Qr+1) if the agent is a winner in the round r and in the next round (r + 1) its utility is ur+1 i < Qr+1. Initially we compute the utility difference U r+1 L (ur+1 i ,Qr+1), and then it is

The final equation for U r+1 L (Qr+1) is:

The rest of the proof proceeds along the same lines as the proof of theorem 5. ■

Set UR+1(u, Q) = 0, ∀u, Q for r = R to 1 do ∀u, Q set Ψr(u, Q) = 1 - 1-pr pr · ∂ ∂Q Ur+1(u, Q) ∀Q compute gr(u, Q) by solving Differential Eq. 9 ∀u, Q compute Ur(u, Qr) using equation 10 end for

3 Implementation

Figure 2 provides the algorithm that we used in order to compute the equilibrium described by theorem 5 using Matlab. At each round r, starting from the last round (R), the equilibrium strategy and expected utility from round (r + 1) are used to compute the equilibrium strategy for round r, using the equations of theorem 5. To solve equation 9, we used the differential equation solver ode45. R is set to R = 8 rounds in all cases, since TAC hotel auctions can have up to 8 rounds.

Initially we computed the equilibria for a uniform distribution. The simplest case is when N = 2 agents are buying m = 1 items; this case was used in order to compare the results of the algorithm with the known solution as shown in figure 1. We only present the equilibrium strategy for the first round of 8 rounds here in figure 1 (right); the solutions of all the other rounds have similar graphs with different curvatures. One notices that in earlier rounds the agent bids less than in the later rounds as was expected. By comparing figure 1 (left) to the solution for the 7th round, we verify that they are identical for the case that the current price Q = 0. However we observed that the solution at each round is very similar to the solution that we would get if, instead of several later rounds (with probability (1 - p) that the auction will close later), we only have one possible later round (again with probability (1-p) that the auction does not close at this round, but at the next one). This indicates that, from the pointof view of the agent, the number of possible rounds does not matter, as long as the probability of having more rounds is the same. For example, the equilibrium strategies for all the rounds are almost identical to the one presented in figure 1 (left) when Q = 0. This would mean that we only need to solve one differential equation instead of a system when the utility distribution is the same in every round.

Still using a uniform distribution, we computed the equilibria when N = 64 agents are buying m = 16 items; this uses the correct number of agents and items for a real TAC scenario. In every round the equilibrium strategy is to bid closer to each agent's utility; that is 94% or more in round 1 and almost 100% in the last round. This happens because of the fact that many more agents participate, compared to the number of items offered. In this case, the agent makes a profit by the fact that its bid is likely not to be the mth price, and thus, usually pays less than its actual bid, if it wins.

Finally, we computed the equilibria using an experiment derived distribution. Since our stated goal was to apply these equilibria to a TAC agent in order to generate more candidate strategies, we collected the utilities of the hotel rooms from a large number of actual games and used these to create the distributions Fr(u) and Gr(u). The cdf of the distribution Fr(u) that we used is presented in figure 3. We make sure that these functions and their derivatives are continuous, so that we can apply ode45 and guarantee uniqueness. To do this, we group all the samples in buckets of size 2, and then to make it continuous, we expand each bucket to a normal distribution with σ = 2 and center μ equal to the center of the bucket; this is the most common way, which is used in statistics, for turning sampled discrete distributions into continuous ones. In figure 4, we present the equilibrium strategy for rounds 1, 5 and 8. The fact that the utility distribution Fr(u) is different in every round causes the bid function to vary significantly between different rounds. In the later rounds, it is advisable to bid close to the marginal utility ui that the agent gets if it buys a unit of the commodity sold in the auction, whereas in the early rounds, it is preferable to bid closer to the current price Q of the auction.

We also computed the equilibrium strategies described by theorem 6. We set the distribution of the later rounds Gr(u) to be equal to Gr(u) = Fr(u|u ≥ ur-1), which means that we disregard any value of u that is smaller than the utility ur-1 in the previous round; this is reasonable for TAC, since utilities rarely decrease between rounds. We only need to add one step to the algorithm of figure 2 in order to implement this: before finishing each iteration, we add a step (see equation 14) in order to compute the utility of this round when the utility uri is only known to be drawn fromdistributionGr(u). Even though, due to space limitations, we can't show any figures of the equilibrium strategies, they all have the same general form as the strategies generated by theorem 5. However, for any values of the valuation u and starting price Q and at every round r these strategies bid less than the corresponding strategies given by theorem 5; this is something that we expected, because of the form of distribution Gr(u), which only allows for higher than the current utility uri .

4 Strategy Generation and Experiments

Each candidate strategy for the hotel auctions determines the prices offered in each round; they are differentiated by how aggressively the agent bids. In [Vetsikas and Selman, 2003], we present three strategies. Two of them are the boundary strategies, that is the lowest and highest possible prices respectively, that a rational agent would ever consider bidding at:

(i) the L(owest aggressiveness) strategy is to bid reasonably close to the current bid price Q of the auction, which is the lowest price that one can offer for its bid to be valid, and (ii) the H(ighest aggressiveness) strategy is to bid progressively closer to the actual (marginal) utility it has for the item, which is the highest price that a rational agent should bid at if it doesn't wish to lose money.

Then we must generate a number of intermediate strategies, which would bid between the lowest and highest reasonable prices (these are the bids of the boundary strategies) at each instance. In [Vetsikas and Selman, 2003], we proposed one such strategy which worked very well in practice (iii) the M(oderate aggressiveness) strategy, which combines the behaviour of the boundary strategies (L and H) depending on the marginal utility of the desired good: if the marginal utility is low, then it bids similarly to the L strategy, whereas if it is high, it bids similarly to the H strategy.

In this paper we expand this methodology to use strategies based on the equilibria presented in section 2.2: (iv) the actual E(quilibrium) strategy gr(u,Q), which was computed in section 3 by applying the equations of theorem 5 for the TAC (experiment derived) distribution, is used.

However, the basic premise for generating this equilibrium was that each agent is interested in maximizing its own profit. In contrast, in a competition, like TAC, the actual goal of each agent is to beat the competition; that is, maximize the difference of its profit to that of the other agents, rather than to just maximize its profit. This change can have a significant impact on the equilibrium strategy. To explore this issue we looked at the single item (m = 1) first price auction with N = 2 agents and R = 2 rounds when the valuations are drawn from uniform distribution U [0, 1].

The equilibrium strategy for a (S)ingle round is g(ui) = ui 2 , and for (T)wo rounds is given by equation 6. Figure 5 presents the expected utilities in all possible combinations of the two agents for varying values of the probability p of the auction closing after the first round. We observe that, when only the S strategy is used, the scores are the lowest, whereas when only the T strategy is used, the scores are highest. However, when the two agents use different strategies, one uses S and the other T, the S strategy usually performs better than the T strategy. This verifies that in a competition the more aggressive S strategy, which bids higher than T, would win, whereas if we care only about maximizing profit, the S strategy is dominated by the T strategy; we expected this since T is an equilibrium strategy for the two-round auction.

We also computed the equilibrium strategy for the "competition objective function" (that is to maximize the difference of profit rather than the actual profit). This strategy would beat the g(ui) = ui 2 strategy in direct competition for a single-round auction: its expected utility is 0.136 vs 0.125. 4 Theorem 7 If we care about maximizing the difference in profit from the opponent, then the Bayes-Nash equilibrium strategy for the first-price, single-unit, single-round auction when two agents participate with i.i.d. utilities drawn from the uniform distribution U[0, 1] is g∗ (ui) = 2 3 · ui This demonstrates that the E strategy's bids are lower than they should be in order to beat the opponents. By looking at the form of gr(u,Q) in all rounds (see figure 4), we observe that, at round 1 the bids are a bit higher than the current price Q, at round 8 closer to the marginal utility, and in the intermediate rounds, the bids are approximately equal to a weighted sum of the values provided by these extreme strategies with the weight equal to the probability pr of the current round r being the one when the auction closes. Since the problem of the E strategy are these bid levels, we modify it:

4 In [Brandt et al., 2007] the authors present an analysis of the equilibria that exist in 1st and 2nd price sealed bid auctions, for a variety of objective functions (i.e. for varying significance of the effect that the opponents' gain has on the agent's utility). In [Vetsikas and Jennings, 2007], we extend these results and present the equilibria for multi-unit auctions, i.e. the mth and (m+ 1)th price sealed bid auctions. We prove that, in some cases, the agent should increase significantly its bid if it wishes to outperform its competition; this can lead to bidding more than its true valuation even in an mth price auction.

(v) the P strategy, which uses the boundary strategies L and H (rather than E) as the strategies that give the two extreme values (low and high), and mixes these values in the same way as E, namely by placing bids at a price equal to the weighted sum of those bids with weights pr and (1 - pr) respectively.

We would like to point out that bidding more aggressively, i.e. higher, than suggested by the strategies we present in this paper, is actually going to produce inferior results, even in the case that the agent is interested in outperforming the competition. The reason for this is that, if the agent bids higher than that point, it will end up paying too much for whatever it buys, and this amount will be higher than the benefit from the opportunities, which are stolen from its competitors.

We now have 3 intermediate strategies to test, in addition to the two boundary ones. According to our methodology, we must organize a tournament among the intermediate strategies in order to determine the best strategy, as we should not use more than two of the agents employing intermediate strategies. The rest of the agents use the boundary strategies and the number is varied, so that the whole spectrum of possible strategic combinations might be explored. To determine which is the best strategy we use paired t tests 5 on the scores of the agents; and, generally, we consider scores to be statistically significant if the test is below 5% (and definitely less than 10% in a small number of cases only). 6 In the first phase, we use intermediate strategies M and E. The results are presented in table 1. The M agents outperform the E agents by a small margin (about 2.5%). This is mainly due to the fact that in competition there is a different objective than simply maximizing one's profit, as we have demonstrated earlier in this section. Note that the difference between the M and H agents is not quite statistically significant, but, with more experiments, it probably would be and thus is denoted by ✓?. 7 This is not important, however, as we found out what we wanted from this phase, namely that we should promote the M agent to the next phase of the tournament. Thus, in the last phase, we use intermediate strategies M and P. The results are presented in table 2. Here the M and the P agents outperform the L agents. The other agents perform reasonably similarly between themselves, and, in fact, the performances were statistically similar for most cases (as denoted in the table). The only exceptions to this rule were the performance of the P agents (about +1%) as opposed to that of the M and H agents in the case that two agents of each type participated. Based on this, and empirical data from the early rounds of TAC 2005, we decided that the P agent is performing best, which is the reason it was chosen as the strategy we used in most of the seeding round and the finals of TAC 2005.

5 This test was used in similar work, e.g. [Stone et al., 2002], to evaluate performance differences between agents.

6 To make this more precise, let us consider the first experiment in table 1 where the average score difference between the L and M agents is 1%. There are two M and four L agents participating in that experiment, with average scores 3359 and 3364 for each of the individual M agents and 3326, 3327, 3322 and 3335 for each of the L agents. We calculate p-values for all eight possible pairings of M with L agents. Six of these p-values are between 2% and 5% (all of them except for the values of the L agent with average score 3335 to both the M agents). These last two p-values are 6% and 9%. Based on our criteria, we consider this to be an indication of statistically different scores.

7 The p-values, in this case, for all eight agent combinations that we examine, range from 3% to 16%, so it does not meet our stated criteria for statistical significance.

Strategy M was used as our TAC entry since the semi-finals of TAC 2002 thru the finals of TAC 2004. In 2005 we used the P strategy mainly. The performance in the seeding, semifinal and final rounds of TAC show this (in parenthesis we give the difference from the top competing agent):

2002: Semi-final 1st (+0.55%), Final 1st (+1.85%).

2003: Seeding 1st (+1.63%), Semi-final 1st (+5.37%), Final 3rd (-1.81%).

2004: Seeding 1st (+3.12%), Semi-final 1st (+6.57%), Final 1st (+7.10%).

2005: Seeding 1st (+2.63%), Semi-final 1st (+1.61%), Final 2nd (-0.50%).

Throughout this time, our agent has consistently achieved the highest scores in the competition. In 2004 our agent was first in all rounds with statistically significant differences in the scores, which has never happened before or since in TAC Classic. In 2005 the top three finalists Mertacor, WhiteBear05, and Walverine were very close to each other. The reason for this extremely competent performance by all agents seems to have been (at least partly) the fact that the other two top scoring agents adopted some of our techniques; in particular, the founding principle of our methodology that trading commodities should be based entirely on maximizing the agent's utility. Walverine used this especially in redesigning their procurement of entertainment tickets. Moreover, the Walverine team also used an experimental methodology [Reeves et al., 2005] which is probably the closest approach to the one we outlined in [Vetsikas and Selman, 2003]. However, no one else thought that it was feasible to look for an equilibrium strategy, even for a sub-problem of a large problem like TAC, and thus our approach as outlined in this paper is truly unique.

5 Conclusions and Future Work

This paper analyzed auctions that have a set of possible closing times, one of which is chosen randomly for the auction to end at. These auctions can be decomposed into one or more rounds, each of which is defined by the interval between possible closing times, and during which the auction is treated as sealed bid. Specifically, we analyzed the Bayes-Nash equilibria that exist in such cases and computed several novel solutions for these auctions. In so doing, we deal with the tradeoff that exists in this case, namely the price offered in the agent's bids. We also explained how to apply these results in the design of a TAC agent; we generated two new trading strategies (E and P) based on the form of the equilibria we computed, one of which (P) was successfully used in our top-scoring agent during the 2005 competition.

We are currently working towards generating equilibria for multi-demand auctions; this would allow us to remove the current restriction that each agent must bid for a single item. While this improvement is not expected to change the results of our analysis for the TAC game significantly, 8 success in this endeavor will lead to a more generally applicable result, which is important for a wide range of game theoretic situations.

We are also working on recomputing the equilibria for the "competition objective function", namely when the agent wishes both to maximize its own profit and minimize that of its opponents, which is more realistic for a competition setting. We have been able to generate equilibria for the mth and (m+1)th price auctions with one round of bidding for a range of objective functions. We plan to incorporate this work in the analysis presented in this paper in order to generate strategies that are more appropriate to a competition setting like TAC.

Acknowledgements

We would like to thank prof. Robin Mason at the University of Southampton, and prof. Steven H. Strogatz at Cornell University, as well as the reviewers of this paper, for comments on this work.

Most of this research was undertaken as part of the first author's thesis. The latter parts, as well as ongoing related work, is undertaken as part of the ALADDIN (Autonomous Learning Agents for Decentralised Data and Information Systems) project, which is jointly funded by a BAE Systems and EPSRC (Engineering and Physical Research Council) strategic partnership (EP/C548051/1).

8 The reason why this happens is as follows. Our analysis shows that the top bid of each agent is the same under both approaches and the other bids, from highest to lowest, are affected progressively more. This means that the bids for the top-valued three or four rooms are not affected (the top one) or are affected relatively little. As these are the highest bids placed by the agents, they are the ones likely to affect the closing price of the auction; the rest are for rooms with minimal marginal utilities, as observed in the simulations, and thus cannot in practice affect the final result.