Eitan Altman
email: eitan.altman@sophia.inria.fr

Hisao Kameda
email: kameda@cs.tsukuba.ac.jp

Yezekael Hayel
email: yezekael.hayel@univ-avignon.fr

Revisiting Collusion in Routing Games: a Load Balancing Problem

Keywords: Asymmetric game, Braess paradox, collusion measures, load balancing, Nash equilibrium

Is it profitable for players to unite and merge to a single player? Obviously, the sum of utilities at an equilibrium cannot exceed the sum obtained if all players join together. But what happens if only a subset of players join together? Previous work on collusion have already shown that the society may either gain or loose from collusion of a subset of players. In this paper we show for a simple load balancing example that not only the society may loose, but also the subset of players that collude may end up with a worse performance than without collusion. In doing so, we introduce new concepts that measure the price of collusion.

I. Introduction

To evaluate the efficiency of an equilibrium, simple measures such as the price of anarchy (or the price of stability) can summarize how bad does worst (respectively, the best) possible equilibrium perform with respect to the socially optimal solution. Although this indeed gives insight into the inefficiency of not joining together, these measures are far from being sufficient for evaluating possible benefits from aggregating several players into a single one.

First, one may question why we compare the sum of utilities. In fact, quite often one is interested in maximizing other function of the utilities rather than the sum. One may be interested in the impact of the merging on the performance of the player that has the worst performance. More generally, one may prefer a measure that indicates how well does an equilibrium perform in terms of Pareto efficiency. This direction has been carried by Kameda in [START_REF] Kameda | Coincident cost improvement vs. degradation by adding connections to noncooperative networks and distributed systems[END_REF] who provides a new definition of the efficiency of an equilibrium.

Next, one may wish to assess the effect of players merging together to one or more coalitions, on the equilibrium without requesting that all players merge to a single player (which is called then a grand coalition). One can then question how beneficial is it for the society to see the set of players replaced by coalitions of these players. In [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF], the authors define the price of collusion as the ratio between the social cost at equilibrium before and after the (worst possible) collusion scenario.

We argue that coalitions tend to form if there is an advantage to those involved in forming a coalition in merging together. Therefore, it seems to us fundamental to introduce a measures for price of collusion that would quantify the effect of collusion(s) on those involved in the collusion(s). We thus propose several other alternative definitions of price of collusion: one related to a single coalition, and another related to various coalitions that may occur coincidentally.

We investigate these concepts through a motivating example of a load balancing routing game. In particular we show that when a few players merge together, not only the society may loose but also the subgroup that colludes.

II. The load balancing problem

Model. Assume there is a set N 1 of n players such that player i among them has an amount of θ(i) to ship from node 1 to node 3. Each player among a set N 2 of m players with m ≥ n, has an amount of θ(i) to ship from node 2 to node 3. Node 3 has a link from both node 2 as well as from node 1, each with the same link cost of f . Let g denote the derivative of f . Links 1 and 2 are connected by a delay line with a fixed cost of d. The network is depicted in figure 1.

We denote for all user i, x i 1 (resp. x i 2 ) the amount of traffic that uses the link 1-3 (resp. the link 2-3). Note that for user i ∈ N 2 , x i 1 follows the two links 2-1 and 1-3. We set x 1 (resp x 2 ) the total amount of traffic on link 1-3 (resp. on link 2-3). We have:

x 1 = ∑ 2 j=1 ∑ i∈N j x i 1 , and x 2 = ∑ 2 j=1 ∑ i∈N j x i 2 .
For any player i, the cost of player i is given by

J i (x) =                x i 1 f (x 1 ) + (θ(i) -x i 1 ) f (x 2 ) + (θ(i) -x i 1 )d for i ∈ N 1 , x i 1 f (x 1 ) + (θ(i) -x i 1 ) f (x 2 ) + x i 1 d for i ∈ N 2 .
(1) Thus,

∂J i (x) ∂x i 1 = f (x 1 ) + x i 1 g(x 1 ) -f (x 2 ) -(θ(i) -x i 1 )g(x 2 ) + δ(i). (2)
where δ(i) = d for i ∈ N 2 and δ(i) = -d for i ∈ N 1 . Assume that at equilibrium, x i 1 and x i 2 are strictly positive for all i. Then the equilibrium flows are obtained by equating [START_REF] Kameda | Coincident cost improvement vs. degradation by adding connections to noncooperative networks and distributed systems[END_REF] to zero. This gives

x i 1 = f (x 2 ) -f (x 1 ) + θ(i)g(x 2 ) -δ(i) g(x 1 ) + g(x 2 ) . (3)
Define ξ = ∑ 2 j=1 ∑ i∈N j θ(i) as the total demand on the network.

Definitions of Measures for Collusion

In [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF], the authors define the price of collusion as the ratio between the social cost at equilibrium before and after the (worst possible) collusion scenario. We are interested in addition to quantify the effect of collusion on those involved in the collusion. We thus propose several other alternative definitions of price of collusion. Consider a game Γ = (I, {A(i), C i , i ∈ I}) where I is the set of players, A(i) is the set of strategies and C i the cost for player i (which is a function of the actions of all players). For a given multistrategy a = (a(i) ∈ A(i), i ∈ I) and a ′ = (a ′ (i) ∈ A(i), i ∈ I) we define the following:

• a(J) is given by (a( j) ∈ A( j), j ∈ J).

• a(-J) is given by (a( j) ∈ A( j), j J).

• [a ′ (J), a(-J)] is the multistrategy where player j J uses action a( j) and player i ∈ J plays a ′ (i). Let H be a partition of I. It is thus given as a set of disjoint subsets of I whose union is I. We shall call H a collusion pattern. Each h ∈ H will be identified with a player in a new game Γ(H) = (H, {A(h), C h , h ∈ H}). We can view a set of players that collude as a coalition. C h is called (as in coalition games) the imputation for a coalition h.

For discrete games we define for any

h ⊂ I, C[h](a) = ∑ i∈h C a .
Definition 1: Consider a game Γ = (I, {A(i), C i , i ∈ I}) along with a collusion pattern H. a[h] is called a H-equilibrium if it is an equilibrium in the game Γ(H).

Definition 2:

We say that a collusion pattern H is a single collusion if there is some J ⊂ I such that H = H(J) := {J, {i}, i J}. In other words, there is only one coalition that is formed by all i ∈ J merging together. Let S C denote the set of all possible single collusions.

Definition 3: Let a be an equilibrium in a game Γ and let a[H] be a corresponding equilibrium in the game Γ(H). We define

• The individual single collusion-price: we consider the impact of a single collusion, that of all players within a group h acting together as a single player. The collusion pattern is thus H(h).

IS CP(h) = C[h](a) C h (a[H]) .

This ratio measures the harm for a group h of players to collude together. After colluding, they get together at the new equilibrium C h (a[H]). If they did not collude then they would get together C[h](a) at equilibrium. • The individual collusion-price (ICP): we now allow for several colluding groups and define the ICP as the worst degradation over all new coalitions.

ICP(H) = sup h∈H C[h](a) C h (a[H]
) .

• The social single collusion-price:

S S CP(h) = C[I](a) C[I](a[H])

.

where H = H(h). This measures the impact on the whole society of a single collusion among players in h ⊂ I. • The social collusion-price:

S CP(H) = sup h⊂I C[I](a) C[I](a[H])

.

This measures the impact on the whole society of a collusion pattern H. • The single collusion externality-price:

S CEP(h) = C[I \ h](a) C[I \ h](a[H])

.

This measures the impact of a collusion h over the noncolluding players.

• The collusion externality-price:

CEP(H) = sup h⊂I C[I \ h](a) C[I \ h](a[H])
.

This measures the worst degradation over all coalitions on the non-colluding players. We shall use the above definition in cases where the equilibrium is unique both before as well as after collusion. In case of several equilibria, one may define the worst case and the best case ratios (as in the definitions of price of anarchy and of price of stability).

III. The symmetric case, Braess paradox and Collusions

In this section, we observe similar results as in [START_REF] Kameda | A mixed optimum in symmetric distributed computer systems[END_REF] in which authors study in details symmetric systems.

Assume that n = m. Taking the sum over i, we get

x 1 = 2n f (x 2 ) -2n f (x 1 ) + ξg(x 2 ) g(x 1 ) + g(x 2 ) , (4)
which does not depend on d any more! Assume that we have symmetry in the demands as well, in the sense that for every player i 1 ∈ N 1 there is a player in N 2 with the same demand. Since we know that there is a unique equilibrium, we shall derive it by showing that there is an equilibrium when restricting to symmetric ones. In a symmetric equilibrium, x 1 = x 2 = ξ/2. This gives by substituting in (3)

x i 1 = θ(i) 2 - δ(i) 2g(ξ/2)
and

x i 2 = θ(i) 2 + δ(i) 2g(ξ/2)
. The above values of x k j indeed satisfies the positivity assumption provided that d ≤ γ where γ := g(ξ/2)θ(i). If this condition is not satisfied then there is no flow forwarded between one source node to another, i.e. on the link 1-2.

A. Braess-type paradox

It follows from (1) that at equilibrium,

J i (x) = θ(i) f (ξ/2) + d ( θ(i) 2 - d 2g(ξ/2)
)

. we conclude that

∂J i ∂d = θ(i) 2 - d g(ξ/2) ,
which is nonnegative for d ∈ (γ/2, γ). In this region J i decreases as d increases, which is a Braess type paradox. This paradox was obtained in the context of a load balancing network in [START_REF] Kameda | Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers[END_REF].

B. Collusions

Assume that a group K of k ≤ n players among N 1 collude together to become a single player. Assume that at the same time, the set K ′ of players among N 2 corresponding to K (a player in N 2 corresponds to one in N 1 if they both have the same demand) also collude to become one single player. We then have 2(nk + 1) players instead of 2n. Then we observe the following:

• The performance of all players other than the colluding ones is unchanged. • The sum of the performance of the colluding players is also unchanged over the region d ≤ g(ξ/2) min i θ(i). This is the region in which we had mutual forwarding among all pairs of corresponding players in K and K ′ . The mutual forwarding remains after the collusion. • We see however that after the collusion, we still have mutual forwarding in larger region of delays:

d ≤ g(ξ/2) ∑ i θ(i).
Thus there is strict deterioration in the sum of the costs when g(ξ/2)

min i θ(i) ≤ d ≤ g(ξ/2) ∑ i θ(i).
We thus showed that a particular type of collusion in which two sets of players merged into two coalitions, resulted in a worse performance at equilibrium. It is natural to ask whether one can observe deterioration due to collusion when only one group is formed.

IV. Asymmetric Load Balancing Games

The behavior of colluding players was easy to describe in the symmetric case, since we know for symmetric routing games that the costs are also symmetric. To use this tool for the study of collusions, we needed to restrict to collusions that kept the system symmetric. This excluded the situation in which only one group of players collude. To study the latter, we therefore have to go beyond symmetric games, which we do next.

We shall obtain an implicit equation to compute the total equilibrium flow over link 1. This is used in the following section to compute the equilibrium flow in the case of linar costs. Summing over i, in (2) we get

∆ := n+m ∑ i=1 ∂J i (x) ∂x i 1 = (n + m) f (x 1 ) + x 1 g(x 1
)

-(n + m) f (x 2 ) -(ξ -x 1 )g(x 2 ) + d(m -n).
Substituting the flow conservation constraint

x 2 = ξ -x 1 , ∆ = (n + m) f (x 1 ) + x 1 g(x 1 ) -(n + m) f (ξ -x 1 ) -(ξ -x 1 )g(ξ -x 1 ) + d(m -n). Define R(x) = (n + m -1) ∫ x 0 f (s)ds + x f (x), and D(x) = (m -n)xd. Then ∆ is the derivative of J(x) at x = x 1 where J(x) := R(x) + D(x) + R(ξ -x).
Assume that there exists an equilibrium in which all players send strictly positive amount of traffic to both paths available to them. Then the equilibrium flow x 1 satisfies ∆ = 0. In the next section, in order to give explicit expressions of the collusion measures defined in section II, we consider the linear cost function.

A. Linear cost function

By considering the linear cost function, we are able to determine explicitly the new collusion measures. So let us define the following function f (x) = ax. Proposition 1: Considering the linear cost function, the equilibrium rates are described as follows.

• If d > a(m + n + 1) θ(1) 2m + 1 , then (x i 1 ) * = θ(1), ∀i ∈ N 1 , otherwise (x i 1 ) * = θ(i) 2 + d 2a 2m + 1 n + m + 1 . • If d > a(m + n + 1) θ(2) 2n + 1 , then (x i 1 ) * = 0, ∀i ∈ N 2 , otherwise (x i 1 ) * = θ(i) 2 - d 2a 2n + 1 n + m + 1 .
Proof We get from previous results that:

∆ = ax 1 [2(n + m) + 2] -a(n + m)ξ -aξ + d(m -n).
Thus the solution of

∆ = 0 is x * 1 = ξ 2 - d(m -n) 2a(m + n + 1) and hence, x * 2 = ξ 2 + d(m -n) 2a(m + n + 1)
. Substituting in (3) gives:

(x i 1 ) * = θ(i) 2 - δ(i) 2a
2|N -i | + 1 n + m + 1 ,
where |N -i | is the number of players in the other side of the network, i.e.

|N -1 | = |N 2 | = m and |N -2 | = |N 1 | = n. We get ∀i ∈ N 1 , (x i 1 ) * = θ(i) 2 + d 2a 2m + 1 n + m + 1 , and ∀i ∈ N 2 , (x i 1 ) * = θ(i) 2 - d 2a 2n + 1 n + m + 1 .
Given those traffic at equilibrium, we have the following constraints from the positivity assumption: ∀i ∈ N 1 , (x i 1 ) * ≤ θ(i), and ∀i ∈ N 2 , (x i 1 ) * ≥ 0. As we assume through the rest of the paper that the demand for each user on the same side of the network is the same. Then, for all user i ∈ N 1 , (resp. i ∈ N 2 ) the demand for the user i is θ(i) = θ(1) (resp. θ(i) = θ(2)). Then the two previous constraints imply the following one:

d ≤ a(m + n + 1) min{ θ(1) 2m + 1 , θ(2) 2n + 1 } := d max .
If the condition is not satisfied, i.e. d > d max , then we have the two following cases.

• d max := a(m + n + 1) θ(1) 2m + 1 then if d > d max we have ∀i ∈ N 1 , (x i 1 ) * = θ(1). • d max := a(m + n + 1) θ(2) 2n + 1 then if d > d max we have ∀i ∈ N 2 , (x i 1 ) * = 0. • if d > a(m + n + 1) max{ θ(1) 2m + 1 , θ(2) 2n + 1 }, then ∀i ∈ N 1 , (x i 1 ) * = θ(1) and ∀i ∈ N 2 , (x i 1 ) * = 0.
Given the equilibrium rates, the cost of player i ∈ N 1 is:

J i (x * 1 , x * 2 ) = - d 2 2a ( 2m + 1 n + m + 1 ) 2 + dθ(1) 2 + θ(1) aξ 2 .
We observe that this cost is a concave function in d and has a unique maximum for d = d 1 := aθ( 1) 2

( m + n + 1 2m + 1 ) 2 .
Then for d higher than d the cost is decreasing, it is Braess type paradox. Moreover, we can see that d 1 < d max .

We have the similar result for any player i ∈ N 2 . The cost function is given by

J i (x * 1 , x * 2 ) = - d 2 2a ( 2n + 1 n + m + 1 ) 2 + dθ(2) 2 + θ(2) aξ 2 ,
and this function has a unique maximum at d = d 2 := aθ( 2)

2 ( m + n + 1 2n + 1 ) 2 < d max .
Then we observe also in this asymmetric network a Braess paradox.

B. Equilibrium and costs with collusion

We consider that k players in N 1 decide to collude. Then we have nk users in N 1 that do not collude, one collusion with k users from N 1 and m users in N 2 which do not collude as well. The total number of individuals is still n + m but as we see the collusion as an individual, we are faced with a non-symmetric system with m + nk + 1 users. We call the collusion h. For all user i ∈ N 1 \ h, the demand is θ(1), for all user j ∈ N 2 , the demand is θ(2) and for the "collusion" player h the demand is kθ [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF]. We denote by y the amount of traffic of the "collusion" player that uses the link 1-3.

Proposition 2:

The equilibrium rates are given by:

• If d > a n -k + 2 + m 2m + 1 then (x i 1 ) * = θ(1) and y * = kθ(1), ∀i ∈ N 1 \ g, otherwise (x i 1 ) * = θ(1) 2 + d 2a 2m + 1 n -k + 2 + m and y * = kθ(1) 2 + d 2a 2m + 1 n -k + 2 + m . • If d > a n -k + 2 + m 2(n -k + 1) + 1 then (x j 1 ) * = 0, ∀ j ∈ N 2 , otherwise, (x j 1 ) * = θ(2) 2 - d 2a 2(n -k + 1) + 1 n -k + 2 + m .
Proof In order to compute the cost of the individuals that are colluding, we study the atomic game with n-k+1+m nonsymmetric players. We denote by y ∈ [0, kθ [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF]] the amount of traffic sent by the collusion h through the link 1-3. The cost function for the "collusion" player g is:

J h (x, y) = y f (x 1 ) + (kθ(1) -y) f (x 2 ) + (kθ(1) -y)d, where x 1 = ∑ 2 j=1
∑ i∈N j x i 1 + y is the total amount of traffic in the link 1-3, and

x 2 = ∑ 2 j=1 ∑ i∈N j x i 2 + (kθ(1) -y)
is the total amount of traffic in the link 2-3. The cost functions J i (x, y) and J j (x, y), respectively, for a user i ∈ N 1 and for a user j ∈ N 2 are not influenced by the collusion and are given by equations 1 (for i ∈ N 1 and for i ∈ N 2 ). Then the derivatives of these functions are:

∂J i (x, y) ∂x i 1 = f (x 1 ) + x i 1 g(x 1 ) -f (x 2 ) -(θ(i) -x i 1 )g(x 2 ) + δ(i),
where δ(i) = d for i ∈ N 2 and δ(i) = -d for i ∈ N 1 . Moreover we have the derivative for user h:

∂J h (x, y) ∂y = f (x 1 ) + yg(x 1 ) -f (x 2 ) -(kθ(1) -y)g(x 2 ) -d.
Then the summation of all the derivatives ∆ is: 2) is the total amount of traffic in the network. Taking the linear cost function f (x) = ax, we obtain the amount of traffic x * 1 on the link 1-3 at equilibrium and on link 2-3:

∆ = ∑ i∈N 1 ∂J i (x, y) ∂x i 1 + ∑ j∈N 2 ∂J j (x, y) ∂x i 1 + ∂J h (x, y) ∂y = (n -k) ∂J i (x, y) ∂x i 1 + m ∂J j (x, y) ∂x i 1 + ∂J h (x, y) ∂y = (n -k + 1 + m) f (x 1 ) + x 1 g(x 1 ) -(n -k + 1 + m) f (x 2 ) -(ξ -x 1 )g(x 2 ) + d(m -(n -k) -1), where ξ = (n -k)θ(1) + kθ(1) + mθ(2) = nθ(1) + mθ(
x * 1 = ξ 2 - d 2a m -n + k -1 n -k + 2 + m , x * 2 = ξ 2 + d 2a m -n + k -1 n -k + 2 + m .
Given that the derivative of the cost function for each player is equal to zero at equilibrium, we get:

∀i ∈ N 1 \ g, (x i 1 ) * = θ(1) 2 + d 2a 2m + 1 n -k + 2 + m , ∀ j ∈ N 2 , (x j 1 ) * = θ(2) 2 - d 2a 2(n -k + 1) + 1 n -k + 2 + m , and y * = kθ(1) 2 + d 2a 2m + 1 n -k + 2 + m .
Then we have the following cost for any type of player:

J i (x * , y * ) = - d 2 2a ( 2m + 1 n -k + m + 2 ) 2 + dθ(1) 2 +θ(1) aξ 2 , ∀i ∈ N 1 \ g, J i (x * , y * ) = - d 2 2a ( 2(n -k + 1) + 1 n -k + m + 2 ) 2 + dθ(2) 2 +θ(2) aξ 2 , ∀i ∈ N 2 ,
and

C h (x[H]) = J h (x * , y * ) = - d 2 2a ( 2m + 1 n -k + m + 2 ) 2 + kdθ(1) 2 +kθ(1) aξ 2 .
The individual single collusion-price (ISCP) is defined in section II as the ratio between the summation of individual costs without collusion of the players that collude and the global cost of the collusion seen as a single player. If the ISCP is lower than 1, then it means that the collusion is not of benefit to the individuals who want to collude. The ISCP for a single collusion h is expressed by:

IS CP(h) = C[h](x) C h (x[H]
) .

The numerator of the ISCP is the summation of the individual cost J k at equilibrium where there is no collusion, for all user k that will collude in h, i.e.

C[h](x) = ∑ k∈h J k (x * 1 , x * 2 ) = - kd 2 2a ( 2m + 1 n + m + 1 ) 2 + kdθ(1) 2 + kθ(1) aξ 2 .
Then the ISCP is equal to:

IS CP(h) = kd 2 2a ( 2m + 1 n + m + 1 ) 2 - kdθ(1) 2 -kθ(1) aξ 2 d 2 2a ( 2m + 1 n -k + m + 2 ) 2 - kdθ(1) 2 -kθ(1) aξ 2
.

Proposition 3: If the size k of the collusion h is higher than (-1/2 + 1/2 √ 1 + 4(n + m + 1)) 2 , then it is beneficial to the collusion users to collude together; otherwise it is not beneficial to them, i.e.

IS CP(h)

> 1 ⇔ k > (-1/2 + 1/2 √ 1 + 4(n + m + 1)) 2 . Proof IS CP(h) > 1 is equivalent to - kd 2 2a ( 2m + 1 n + m + 1 ) 2 + kdθ(1) 2 + kθ(1) aξ 2 > - d 2 2a ( 2m + 1 n -k + m + 2 ) 2 + kdθ(1) 2 + kθ(1) aξ 2 , for √ k < n + m + 1 n -k + m + 2 := X X + 1 -k . Define X := n+m+1, then IS CP(h) > 1 is equivalent to X √ k- k √ k + √ k -X < 0.
Finally we define u := √ k and then the equation IS CP(h) > 1 is equivalent to u 3 -u(X+1)+X > 0. This equation has the three solutions:

{1, -1/2-1/2 √ 1 + 4X, -1/2+ 1/2 √ 1 + 4X}. We have that -1/2 + 1/2 √ 1 + 4X > 1 because X = n+m+1 > 2.
We are considering the case where u and X = n + m + 2. We consider the continuous function ISCP in order to compute its derivative. Then we have the following derivative:

= √ k > 1. Then if u = √ k ∈ [1, -1/2 + 1/2 √ 1 + 4X[ the polynome u 3 -u(X+1)+X is negative, which is equivalent to IS CP(h) < 1. And if u = √ k > -1/2 + 1/2 √ 1 + 4X, then the polynome u 3 -u(X+1)+X is positive, which is equivalent to IS CP(h) > 1. Thus, IS CP(h) > 1 is equivalent to k > (-1/2 + 1/2 √ 1 + 4(n + m + 1)) 2 .
∂IS CP(k) ∂k = (A + B)A(X -1) 2 (X -3k) (X -k) 3 (A( X -1 X -k ) 2 + kB) 2
.

We have that A(X -1) 2 (Xk) 3 (A( X -1 Xk ) 2 + kB) 2 < 0 and A + B > 0, then, the derivative of the individual single collision price is increasing if and only if k > X 3 . Thus the ISCP is minimized when k = X/3.

Given this result, we have the worst lost of cost induced by a collusion for colluding players which is given by max h (1 -IS CP(h)), that is: Note that this result is an approximation as the size of the collusion is an integer and the ratio (m + n + 2)/3 is generally a real number.

Proposition 5: The optimal collusion size in order to maximize the individual single collusion price is given by:

k * = { 1 if n < (m + 1) 2 , n otherwise.
Proof We have proved in the previous proposition that the ISCP is first decreasing and increasing with the size k of the collusion. Then it is the most beneficial for a colluding player, in terms of ISCP, when all players collude together, i.e.

Fig. 1 .

 1 Fig. 1. Load balancing topology

Proposition 4 : 3 .

 43 The individual single-collusion price is minimized when k = m + n + 2 Proof The individual single collusion price IS CP(k) is defined by the following expression: IS CP(k) = k(A + B)

max h ( 1 -

 1 IS CP(h)) = IS CP( m + n +

k = n. Moreover, this should be satisfied when IS CP(n) > 1. Otherwise the best collusion size is k = 1 because it yields IS CP(1) = 1.

We have IS CP(n) > 1 if and only if: -n (n + m + 1) 2 < 1 (m + 2) 2 , which is equivalent to n > (m + 1) 2 .

In other words, the worst degradation over all coalitions in N 1 , measured with ICP(N 1 ), depends only on n and m. Thus, we have the following result:

Now we look at the impact of a collusion on the whole society, meaning through the social welfare. For doing this, we use the measure of the social single collusion price (SSCP) which is defined as the ratio between the social welfare without collusion and the social welfare when there is a collusion. The social welfare of the system without a collusion is given by:

is the total demand. We have the social welfare when there is a collusion h:

Thus the social single collusion price, SSCP, is expressed by the following ratio:

Finally, we look at the impact of the collusion only on the non colluding users N 1 \ h ∪ N 2 . We use the measure called the single collusion externality price (SCEP) defined in section II which is defined as the ratio between total cost perceived by the non colluding users when there is no collusion and when there is a collusion. The total cost perceived by those users when there is no collusion is given by:

The total cost perceived by those users when there is a collusion is given by:

Thus the single collusion externality price (SCEP) of a collusion h is:

} .

V. Concluding Remarks

Our contribution has been to define different new measures for collusion and to illustrate them through the load balancing routing game. In particular, we have shown that merging into a coalition may be harmful not only for society but also to those who collude.


Alex Boulton

Data-Driven Learning: The Perpetual Enigma

Keywords: authentic, concordancing, corpus, Data-driven learning, DDL, induction, language learning, Tim Johns

published or not. The documents may come

Introduction

In recent decades, electronic corpora have transformed linguistic study almost beyond recognition, in particular enabling vastly improved descriptions of language varieties. In the field of language teaching and learning, a number of researchers (e.g. McCarthy 2008: 564) have hailed this as a truly Kuhnian paradigm shift in many areas, from dictionaries and other resources to syllabus design, course contents and examinations, and even increasing numbers of coursebooks and other materials for both general and specific purposes.

Corpora have multiple potential uses or "affordances", to use the term popularised in applied linguistics by [START_REF] Hafner | Corpus tools as an affordance to learning in professional legal education[END_REF]. One of the more controversial of these is as a language resource for learners themselves. This approach is particularly associated with Tim Johns, who started developing it in the 1980s. He first used the term 'data-driven learning' (DDL) in print in the seminal collection of papers co-edited with his colleague, Philip King, in 1991. 1 The introduction has a clear statement:

All the papers in this issue… describe an application of computers to language-learning that has come to be known as 'classroom concordancing' or 'data-driven learning' (DDL) -the use in the classroom of computer-generated concordances to get students to explore the regularities of patterning in the target language, and the development of activities and exercises based on concordance output. (Johns & King 1991: iii) Nonetheless, the term remains controversial to this day, with researchers applying the label 'DDL' almost at random to a range of activities. This paper is an attempt to clarify the field and associated concepts, and try to answer the question of what constitutes DDL. We begin by looking at Johns' work to see in greater detail what he intended it to mean, then move on to other studies to see how it has been adopted or rejected in different cases. Finally, we discuss the term itself and its implications for a coherent field of research. The title of this paper is a tribute to Johns' 2002 article, "Data-driven learning: the perpetual challenge", in recognition of the inspiring work of this unceasingly innovative researcher and teacher, who died in March 2009.2

Background to DDL

The term 'data-driven learning' derives from computer science, describing software which can learn from new data. Because it was Johns who first adopted it to describe the uses of corpora in language learning in 1991, any discussion of DDL will inevitably rely heavily on his work. However, he was not the first to be interested in the concept. McEnery and Wilson (1997: 12) attribute the first applications of corpora to language teaching to Peter Roe at Aston University in 1969, while Johns himself (1986: 159) refers to work by Antoinette Renouf at Birmingham University in the early 1980s using COBUILD concordances in the language classroom. The earliest paper [START_REF] Johns | Micro-Concord: a language learner's research tool[END_REF] cited along these lines is by Ahmad et al. (1985), who report giving learners access to corpora so they can find multiple examples of language phenomena themselves. But a far earlier publication seems to have come from an entirely different source: in 1980, Sandra McKay in San Francisco published an article in TESOL Quarterly describing the uses of corpus data for teaching verb usage. The learners in her study are provided with multiple extracts (full sentences) along with instructions to list the types of item that occur before and after the key words, categorising them and observing their behaviour, comparing and contrasting patterns, and so on. DDL thus has a number of roots, coming together in the work of Johns as the main populariser.

Nowhere does Johns provide a single, concrete definition of DDL -or rather, he provides many, defining different aspects and elements of it, along with a tremendous variety of activities. This is inevitable given the multiple affordances of language corpora: Johns and King (1991: iii) describe concordancers as being "as useful a tool in their own way as the Swiss army knife", opening up a "wide range of approaches". Johns himself was certainly not dogmatic about what constituted DDL, and particularly concerned that it should be "integrated with older and more familiar methods" (1991a: 3). Indeed, for him "reasoned eclecticism is a perfectly tenable theoretical position", and any instantiation of DDL (or indeed any other approach) is necessarily "dependent not only on the social, cultural and political setting of a particular society at a particular point in time and the development of education within that setting but also on the technology available in the classroom" (Johns 1988a: 13).

At the University of Birmingham3 from 1971 until his retirement in 2001, Johns had been in contact with the many researchers working on the Bank of English monitor corpus and associated COBUILD projects [START_REF] Sinclair | Looking Up: An Account of the COBUILD Project in Lexical Computing[END_REF]. Working with a concordancer convinced him that it was "one of the most powerful tools that we can offer the language user" (Johns 1988a: 15), inspiring the "classroom use of concordances" which: represents rather more than a 'teaching technique' and… can be the basis of a distinctive methodology characterised by the central importance given to the development of the ability of learners to discover things for themselves on the basis of authentic examples of language use. (Johns 1993: 4) The corpus and concordancer allowed him to "cut out the middleman as far as possible and to give the learner direct access to the data" [START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF]: 30) -one of the most widely quoted phrases he ever wrote. It is therefore largely an inductive approach (Johns 1991b: 29), replacing the traditional 'presentation, practice, production' paradigm (the 'three Ps' so familiar to trainee language teachers in the early communicative era) with a new trilogy which he variously named identification, classification, generalisation (Johns 1991a: 4) or research, practice, improvisation (Johns 1997a: 101). Other researchers have since come up with different labels to characterise the learner's use of language corpora, most famously perhaps the 'three Is' of illustration, interaction, induction (Carter & McCarthy 1995: 155;McEnery et al. 2006: 99).

Clearly aware of the radical shift in the underlying philosophy of language teaching, Johns frequently resorted to metaphors to explain them: "The central metaphors embodying the approach are those of the learner as 'linguistic researcher'4 , testing and revising hypotheses, or as a 'language detective', learning to recognise and interpret clues from context ('Every student a Sherlock Holmes')" (Johns 1997a: 101). This gives rise to another of his widely-quoted passages, that "research is too serious to be left to the researchers"5 (1991a: 2). Unfortunately, perhaps, the term 'data-driven learning' did little to clarify matters.

A hermeneutic approach to data-driven learning

Johns wrote on a number of topics before concentrating on DDL, notably in the fields of reading English for specific or academic purposes, and various CALL applications [START_REF] Johns | The communicative approach to language teaching in the framework of a programme of English for academic purposes[END_REF][START_REF] Johns | The text and its message: an approach to the teaching of reading comprehension for students of development in administration[END_REF][START_REF] Johns | The uses of an analytic generator: the computer as teacher of English for specific purposes[END_REF][START_REF] Johns | Text as a vehicle for information: the classroom teaching of reading in ESP[END_REF][START_REF] Johns | An experiment in team-teaching of overseas postgraduate students of transportation and plant biology[END_REF]. Although unconnected to DDL, these papers are helpful in understanding his main concerns in language teaching, with repeated reference to concepts such as induction, problem-solving, puzzling it out, learning by doing, communication and collaboration, as well as the importance of authentic language. A number of later papers are also only tangentially related to DDL, especially describing software [START_REF] Johns | If our descriptions of language are to be accurate… A footnote to Kettemann[END_REF][START_REF] Johns | Multiconcord: The Lingua Multilingual Parallel Concordancer for Windows[END_REF][START_REF] Johns | Four versions of a sentence-shuffling program[END_REF]. In total, Johns' legacy of DDL-related publications resides mainly in nine articles [START_REF] Johns | Micro-Concord: a language learner's research tool[END_REF](Johns , 1988a(Johns , 1991a[START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF][START_REF] Johns | Data-driven learning: an update[END_REF](Johns , 1997a[START_REF] Johns | Kibbitzing one-to-ones[END_REF][START_REF] Johns | Data-driven learning: the perpetual challenge[END_REF][START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF]), a co-edited collection (Johns & King 1991), a number of on-line collections 6 , and a short discussion in a co-edited book [START_REF] Higgins | Computers in Language Learning[END_REF]. For reasons of space it is not possible to go into details of all his papers here; a summary of each individual paper can be found on the present author's homepage. 7 Johns briefly referred to the potential uses of corpora in language learning in [START_REF] Higgins | Computers in Language Learning[END_REF], but it was not until his first major paper on the topic that he gave it any kind of name. This article included the term "classroom concordancing" in the title, but also referred to "data-based learning" in the text (Johns 1988a: 24). "Classroom concordancing" was kept as the title to the 1991 collection of papers. The introduction to this volume also introduced a newer term: "an application of computers to language-learning that has come to be known as 'classroom concordancing' or 'data-driven learning' (DDL)" (Johns & King 1991: iii), with the term 'data-driven learning' also featuring in the titles of both of Johns' own papers in this volume (Johns 1991a[START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF]. If the two terms thus seem to be interchangeable, Johns later (1993: 4) attempted a clarification: "The earlier term Classroom Concordancing described the technique; the new term Data-Driven Learning was coined to emphasise the methodology." However, he was clearly not entirely happy with it: over ten years later (Johns 2002: 107), he referred to it as "an approach… that I have, for want of a better term, named data-driven learning" (emphasis added). Finally, in his last paper (Johns et al. 2008: 495) he referred to "corpus-based language learning". While the concepts were presumably clear in his own mind, finding an appropriate label was more difficult: if Johns had his own doubts, it was perhaps not without reason.

Nonetheless, DDL is the term that has stuck in relation to his work, so merits some discussion. The choice of the word data is provocative: "what is distinctive about the DDL approach… is the principle that the data is primary" (Johns 1991a: 3).

'Data' here crucially refers to corpus data; one might then wonder why he chose 'data' over 'corpus', especially as the former sounds perhaps colder and more scientific. The choice could have been deliberate if he originally wanted to shake others in their complacency, but as corpus linguistics gained ground, he did come back to the more neutral term later [START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF].

The word driven is similarly controversial, especially given that he used 'databased learning' in an earlier publications (1988a: 24) and 'corpus-based learning' in the last (Johns et al. 2008: 495). The crucial difference from the Birmingham perspective was that a corpus-driven approach to language meant trying to put aside all one's previous intuitions and preconceptions in order to look at language afresh only from the evidence of the data, while a corpus-based approach meant using corpus data to test existing ideas (cf. Tognini-Bonelli 2001). Whether in language analysis or pedagogy, the term 'driven' is clearly intended to be more radical -the data are primary and everything else has to bend to that; the more nuanced 'based' means taking what one wants from a corpus but not being strait-jacketed by it. 8 As McCarthy and Carter (2003: 338) put it, "the pedagogic process should be informed by the corpus, not driven or controlled by it," although it is difficult to see Johns disagreeing with this position. In the end, one is forced to agree with McEnery et al. (2006: 8) that "the distinction between the corpus-based vs corpus-driven approaches is overstated." Again, we can only presume that Johns' choice was not arbitrary, and in a typically Sinclairean ( 2004) 'trust the text' frame of mind he wrote of his: obstinate belief that even the most refined expert system would here, at best, come a poor second to the teacher's imperfect human system in selecting examples that truthfully reflect the patterning of an item in the corpus, and that students can work with and learn from. (Johns 1997a: 114) However, it is clear from the many activities he proposed that the teacher's role was crucial in guiding the learner, scaffolding the activities, and mediating the data. He always admitted his print-outs involved "a degree of 'rule-hiding' in the selection of citations, the categories adopted, and the sequencing of citations within each category" (Johns 1991a: 4), and even accepted "editing of concordance data" (Johns 1997a: 114). This is scarcely the radical approach one might expect from the term 'data-driven', and one wonders if the terminological choice was not deliberately provocative: pedagogy would still prevail over ideology.

The concept of learning was very much at the centre of Johns' priorities, generating some quite abstract discussion in his 1988a paper. Learning here is thus contrasted with teaching, though this did not mean DDL could not be used "proactively… in a more traditional teacher-centred setting" (Johns 1991b: 31). He was also convinced that DDL would help students to "learn how to learn" (Johns 1991a: 1) and hence to "become better language learners outside the classroom" (Johns 1991b: 31). In many ways, then, the emphasis is less on the language than on the learner. Furthermore, learning was not his only concern, as he also experimented with using corpora as a reference source for translation (2002) or for helping students to correct their own writing (Johns 1986: 61), culminating in his "kibbitzers" [START_REF] Johns | Kibbitzing one-to-ones[END_REF]). Learning may or may not happen, but is incidental and not the main goal when using corpora (or dictionaries, or any other reference resource) in this way for specific inquiries as and when they arise.

Empirical research: corpora and language learners

So far we have been looking at what Johns seems to have meant by DDL, on the assumption that, as the inventor of the term in this context, his word is final. That said, the essence of the field of corpus linguistics is to describe common usage and meaning rather than to prescribe it ex cathedra. To avoid the trap of etymological fallacy, what it seems to mean to the majority of users has to be taken into consideration.

To identify how the approach has been used by others, this section draws on 61 separate studies looking at some aspect of corpus use for language learners. 9 The definition adopted is necessarily broad, as the aim is to capture the variety of techniques, tasks and procedures used by different researchers, whatever the explicit terminology they use. The survey is limited to empirical evaluations, which tend to provide at least a minimum of background information. The studies were all published in English subsequent to the popularisation of the term DDL in 1991, excluding Johns' own work, and divide into three relatively even-sized groups:

• Type A studies: 19 with a more or less explicit claim to being DDL;

• Type B studies: 23 with at least some reference to Johns' work and/or DDL;

• Type C studies: 19 with no reference at all to Johns or DDL. 10 The objective then is to compare the three types of study to see what they share and where differences may lie. The first section of Table 1 below provides some background information on the context of the studies. Clearly not all elements are relevant: the fact that the majority of all studies featured English as the target language should not be taken as an indication that English is the 'best' language for DDL (though as a language with comparatively few inflections, it may be more suitable than some). Similarly, the overwhelming majority of studies are conducted among students in higher education, but this is presumably in large part simply because that is where the researchers work rather than due to any inherent limitation of DDL. Other cases are less clear-cut: most studies concern learners at relatively advanced levels of language ability, and it has been argued that DDL is not appropriate at lower levels. Johns (1986: 161) designed MicroConcord:

for a particular type of student (adult: well motivated: a sophisticated learner with experience of research methods in his subject area) with particular needs (fairly closely specifiable in terms of target texts) in a particular learning/teaching situation (in which a great deal of emphasis is placed on developing students' learning strategies and on their responsibility for their own learning).

However, DDL should not be ruled out automatically at lower levels, and Johns (1997a) himself reported using DDL in a 'remedial grammar' course for lower-level international students. A number of other studies do attempt it -especially, as Table 9 An evolving list of studies can be found on the author's homepage: Empirical Research in Data-Driven Learning: A Summary, http://arche.univ-nancy2.fr/course/view.php?id=967. 10 There is of course no way of knowing whether the lack of reference to Johns' work or DDL means that the authors were unaware of it, or felt it irrelevant to their present paper, or rejected it outright. Similarly, some of the B Studies mention DDL only to dismiss it or suggest an alternative approach. The discussion is intended only to bring out tendencies.

1 shows, among those with a stronger claim to follow Johns' work -and a number of arguments have been put forward (e.g. Boulton 2009a[START_REF] Boulton | CALL in Second Language Acquisition: New Approaches for Teaching and Testing[END_REF].

The most obvious difference between the three types of study lies in the learners' specialisation, with those citing Johns tending to work more with students majoring in areas other than the target language, with an emphasis on English for specific or academic purposes. The importance of this is reflected in the second part of the table, which shows the main focus of the studies: those presenting it as a separate corpus linguistics course; those focusing on one or more specified language areas (e.g. phrasal verbs, connectors, etc.); those using it for written production (including translation and error-correction) or reading; and a small number of others with mixed aims. There are a number of differences between the three types of study, but two stand out: type A studies are more likely to focus on learning ('language'), while type C ones are more frequently interested in corpus use as a reference resource ('writing' or 'reading'). Although these two different uses of corpora rarely receive explicit discussion or differentiation (though see Landure & Boulton [in preparation]), it is possible that some researchers might shy away from claiming to be DDL if their main interest is not learning as such. The final part of the table lists the main type of support or interface used. Type B and C studies are more likely to require learners to interact with corpus data on computer, either directly or via a software package that includes one or more corpora. Type A studies, on the other hand, are more likely to be providing the learners with printed DDL materials. Looking at the table as a whole, this could be because these studies tend to use corpora for learning (with general language items relevant to the entire class) rather than as a resource (with specific language points generated by individual learners), and the learners are probably in greater need of guidance, due both to their lower overall levels of language proficiency and (possibly, given that they are not language specialists) motivation and sophistication.

It is important to bear in mind that these differences reflect general trends only: any of these elements can feature in any of the study types, thus making any hard-and-fast classification or separation difficult. The same can be said of the corpora and tools involved, and the approaches adopted. Both A and C studies make use of the web as corpus, on-line corpora, locally-built corpora of particular language varieties for specific purposes, large multi-purpose corpora such as the BNC, monolingual and bilingual corpora, and use the same concordancers. Similarly, both types may introduce corpus consultation: a course or integrated to an on-going course; in class, in the computer laboratory or outside; for individual use, pair-work or whole-class activities; proactively in teacher-controlled activities or reactively in response to individual learner queries; using selected samples or an entire corpus; inductively or deductively; in a controlled or almost entirely open 'serendipitous' manner; and so on. To summarise: different researchers do different things with corpora, but the differences are at most tendencies, as virtually every type of activity can be found in various studies whether they call themselves DDL or something else.

Defining data-driven learning

It is apparent that DDL means different things to different people, sometimes in contradiction with Johns' own work. Virtually the only aspect that is transparently essential in all cases is the use of corpus data, and even this is not enough to define DDL. For example, corpora have been used as the basis for course materials such as Touchstone (e.g. [START_REF] Mccarthy | Touchstone 4 ([END_REF]), but the authors' "mediation" makes the corpus origins completely invisible: "Teachers and learners should expect that, in most ways, corpus informed materials will look like traditionally prepared materials" (McCarthy 2004: 15). Few would argue that this is an example of data-driven learning (Boulton forthcoming). DDL may include working with whole texts extracted from a corpus (e.g. [START_REF] Flowerdew | An integration of corpus-based and genre-based approaches to text analysis in EAP/ESP: countering claims against corpus-based methodologies[END_REF]), but using whole texts alone is not what most people would understand by DDL -although [START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF] based DDL activities on the use of a single novel, Swallows and Amazons11 . DDL is frequently associated with truncated concordance lines or KWICs (key words in context), but may feature whole sentences -as used for example by [START_REF] Schmitt | Focus on Vocabulary: Mastering the Academic Word List[END_REF] in their selfproclaimed DDL course Focus on Vocabulary. While there are typically several contexts at a time, in some cases there are only two -again, an absolute minimum requirement seems difficult to justify: Johns' examples of the "one item, many contexts" paradigm (e.g. 1997a: 102) frequently featured as few as three lines. In all of these cases, it seems, to qualify as DDL, corpora must not only be present, but must also have a high profile.

The position taken here is that it is simply not possible to identify any element which is both sufficient and necessary to define an activity as DDL. Certainly it has no monopoly on such apparently key features as induction [START_REF] Schaffer | A comparison of inductive and deductive approaches to teaching foreign languages[END_REF] presents an intriguing study of induction using full texts, in no way an instantiation of DDL) or authentic materials (recommended extensively in the communicative approach, among others). Watertight definitions are often difficult or impossible to establish in the real world; an alternative is to provide a 'prototype' (Aitchison 2003: ch3), an example which is generally perceived as a good exponent of the class; other instantiations may differ in one or more aspects, but the greater the differences, the less likely they are to be considered members of that class. Gilquin and Gries (2009: 6) apply this approach to the concept of a corpus itself, identifying "several criteria that, if met, define a prototypical corpus, but the criteria are neither all necessary nor jointly sufficient."

In the case of data-driven learning, we might propose a prototype such as the following:

• The hands-on use of authentic corpus data (concordances) by advanced, sophisticated foreign or second language learners in higher education for inductive, self-directed language learning of advanced usage.

Yet virtually any part of this description might be absent in a particular case:

• Hands-on: Johns (e.g. 1991aJohns (e.g. , 1991b)), like many other researchers, made extensive use of paper-based materials for DDL, and encouraged the use of generic, reusable "ready-made DDL materials" (1991b: 36) to reach a wider audience (as in the examples on his own websites). He even [START_REF] Johns | Data-driven learning: an update[END_REF] mentioned the practice of "blackboard concordancing", getting learners to identify target items from a page of text and write the concordances on the board -no technology required for learners or teachers. Paper-based materials can provide a gentle "way in" (Johns 1993: 7), and "the amount of help on offer can be gradually reduced until students can be presented with concordance output to investigate independently and unaided" (Johns et al. 2008: 495), rather than imposing the new approach (DDL), new materials (corpora), and new technology (software) all at once (Boulton forthcoming). Furthermore, while hands-on DDL may be a long-term goal to promote autonomous corpus investigation for those with strong specific needs (e.g. Johns 1997b), it is not obvious that this is true for all learners. • Authentic: some (notably Widdowson [e.g. 1998]) have claimed that any texts removed from their original context and function should be considered inauthentic in themselves for teaching purposes; even rejecting this extreme position (e.g. [START_REF] Mishan | Authenticating corpora for language learning: a problem and its resolution[END_REF]), one might doubt the authenticity of isolated concordance lines chosen by the teacher, especially if they are graded, and possibly even edited, or the use of learner corpora (also envisaged by Johns [1986: 158-159]). Furthermore, despite Johns' repeated insistence on the "overriding importance of authentic text" (Johns & King 1991: iv), corpora of simplified data (e.g. of textbooks, exam papers or simplified novels) might still be used in a DDL approach (e.g. [START_REF] Allan | Can a graded reader corpus provide "authentic" input?[END_REF]). • Corpus data: some research focuses on whole texts extracted from corpora (e.g. [START_REF] Braun | From pedagogically relevant corpora to authentic language learning contents[END_REF], or a single large text such as a novel (e.g. [START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF]) or short story [START_REF] Cobb | Can the rate of lexical acquisition from reading be increased? An experiment in reading French with a suite of on-line resources[END_REF]). As discussed above, the language used also has to be overtly extracted from a corpus. • Concordances: in addition to longer texts, or paragraph-or sentence-length extracts, DDL activities may also include study of frequencies, distributions, collocates lists, and so on (e.g. [START_REF] Boulton | Data-driven learning: taking the computer out of the equation[END_REF]). The aim is still to generalise from corpus data. • Advanced, sophisticated: the majority of research to date has focused on advanced learners, a common objection being that it "may be all very well for students as intelligent, sophisticated, and well-motivated as ours…, it would not work with students as unintelligent, unsophisticated and poorly-motivated as theirs" (Johns 1991a: 12). But Johns goes on to say, "what I suspect, however, is that most students given the opportunity to show what they are capable of might be (almost) as remarkable." While noting the prevalence of work with advanced learners, Johns and King (1991: iv) wonder: "How far back towards the beginning could this approach be used?" [START_REF] Yoon | ESL student attitudes toward corpus use in L2[END_REF] find DDL even more successful with intermediate than with advanced learners, and others report benefits with even lower levels (e.g. Boulton 2008a). • Foreign / second language learners: there seems no obvious reason why DDL should not be applied to learning one's first language, such as in work by [START_REF] Sealey | What do you call the dull words? Primary school children using corpus-based approaches to learn about language[END_REF]. It might also be used by language professionals such as translators who do not consider themselves to be 'learners' as such. • Higher education: occasional studies have been conducted outside formal education [START_REF] Cobb | Can the rate of lexical acquisition from reading be increased? An experiment in reading French with a suite of on-line resources[END_REF], independently via the Internet [START_REF] Smith | A corpus query tool for SLA: learning Mandarin with the help of SketchEngine[END_REF], in language centres [START_REF] Allan | Data-driven learning and vocabulary: investigating the use of concordances with advanced learners of English[END_REF]) and in secondary education, including work by [START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF]. • Inductive: induction is certainly a central component of DDL [START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF]), but cannot be considered an ultimately defining element. [START_REF] Cresswell | Getting to "know" connectors? Evaluating data-driven learning in a writing skills course[END_REF] is among those to mention potential deductive uses, comparing corpus data against known or supposed rules to test or refine them, an approach earlier suggested by Johns (1986: 159) himself. However, even in its deductive form it does remain firmly constructivist in outlook, as the learners are not simply given the rules and then told to practise drills. • Self-directed: the freest form of corpus consultation, where learners take on complete responsibility for their learning, has since come to be called "serendipity" learning, most closely associated with [START_REF] Bernardini | Systematising serendipity: proposals for concordancing large corpora with language learners[END_REF]. 12 But there is "a scale from free to controlled" (Johns & King 1991: iii): for learners at lower levels or with fewer specialist needs, the teacher might usefully retain control over some of the decisions, although in a new guise as "research director and research collaborator rather than transmitter of knowledge" (Johns 1988a: 14). Johns produced CALL software and activities that were "'closed' in the sense that the result is known to the teacher in advance" (Johns 1997a: 101), on the principle that "the more complex the program, the more inaccessible it may become" (Johns 1986: 156), and made extensive use of prepared materials for 'proactive ' whole-class use (e.g. 1991a, 1991b). • Language learning: corpus data can also be used as a resource or "informant" (Johns 1991a: 1) as well as explicitly for learning, especially for error-correction or written production in general. Johns mentioned such possibilities early on (1986: 161), developing them into his "kibbitzers" (1993, 1997a) which enable an observer (as in chess [Johns 2002: 111]) to examine the interactions between himself, the concordancer, and learners who came to individual sessions for help with their writing. He developed a parallel concordancer specifically for DDL work for translation as well as for learning (Johns 1993: 7), and made use of translation for "reciprocal learning" [START_REF] Johns | Data-driven learning: the perpetual challenge[END_REF], where learners are paired so that each is a native speaker of the other's target language and collaborate to work on parallel corpora, as well as in his final paper [START_REF] Johns | Integrating corpus-based CALL programs in teaching English through children's literature[END_REF]. It can also be used for testing purposes, particularly in the form of multiple blanked concordances, whether on paper (e.g. [START_REF] Stevens | Concordance-based vocabulary exercises: a viable alternative to gap-filling[END_REF] or in CALL software (e.g. Johns 1997a). • Advanced usage: DDL is often associated with "what is normally untaught and possibly unteachable" (Johns 1991b: 28), on the "'collocational border' between syntax and lexis… [which is where] DDL methods seem to be most effective" (Johns 2002: 109). But DDL has also been used to help with skills work (mainly writing and reading), and the activities proposed in [START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF] include making sentences from fragments for increased coherence, inferring meaning from context, guessing the background situation, constructing new dialogues, and so on. It has frequently been used for vocabulary learning (e.g. [START_REF] Cobb | Breadth and depth of lexical acquisition with hands-on concordancing[END_REF], occasionally for wider grammatical patterns (e.g. Johns 1997a; Boulton 2008b), and even pronunciation [START_REF] Gut | Learner speech corpora in language teaching[END_REF].

To allow for all these exceptions, the only hard-and-fast definition would have to be something like 'language users exploiting language corpora', so vague as to be nearly useless -hence the relevance of a prototype definition. One important corollary of all this is that DDL is not an all-or-nothing affair: its boundaries are fuzzy, and any identifiable cut-off point will necessarily be arbitrary. With first-time users, especially given lower levels of language proficiency, sophistication and motivation, it might well be appropriate to start with a relatively 'weak' form of DDL (near the boundary), gradually moving on to a more 'hard-core' version (at the prototypical centre) as and when necessary. In many cases, the teacher is likely to remain the centre of attention at the start, deciding the language points to study, the corpora and tools to use, the activities, progression, and so on; as the learners become familiar with all of this, they can gradually take on more responsibility for their own learning by deciding these issues for themselves. Such a gradual changeover from a proactive to a reactive approach is truly 'autonomising' in the classic sense intended by Holec (e.g. 1981). It might be easier to adopt a deductive approach initially, testing rules or hypotheses against the data rather than trying to work them out unaided. Carefully-designed activities with known outcomes can give way to more open-ended exploration, especially as learners move from fixed materials (especially print-outs) to hands-on corpus consultation. This can also be a way to make the data more accessible as an alternative to simplifying the corpus itself, as concordance lines can be selected, graded and organised in advance.

Conclusion

Johns frequently referred to DDL as an 'approach', outlining a number of associated techniques; it is not a 'method' in its own right, but can be integrated into various types of courses each with their own methods. In their classic textbook, Richards and Rodgers (2001: 19) make the following distinctions: Approach is the level at which assumptions and beliefs about language and language learning are specified; method is the level at which theory is put into practice and at which choices are made about the particular skills to be taught, the content to be taught, and the order in which the content will be presented; technique is the level at which classroom procedures are described. [emphasis added] In other words, an approach does not give rise to "a specific set of prescriptions and techniques" but "a variety of interpretations as to how the principles can be applied", meaning it can be "revised and updated over time" (Richards & Rodgers 2001: 245). The spirit inherent in the DDL approach is clear: empowering learners to explore language corpora and come to their own conclusions. An enormous variety of techniques can be used within this approach: the absence of any can not be taken to mean that an activity is not DDL -precisely because it is not a method and avoids the dogmatism associated with the level of method. Such criticism is therefore not only unfounded, but also does a disservice to the field as a whole.

One might wonder whether the name one applies is of any real importance, but it has been argued here that the term 'data-driven learning' may in itself be off-putting for some: 'data' sounds cold and clinical (whereas DDL is highly learner-centred), 'driven' sounds uncompromising (whereas DDL is anything but dogmatic), and 'learning' is only one aspect (DDL can also refer to corpus use as a resource for writing or translation, for example). If no label is generally accepted, then the approach as a whole cannot assume a coherent identity, essential if the "'trickle down' from research to teaching" is to turn into the torrent confidently predicted by Leech over a decade ago (1997: 2). A readily-identifiable brand name helps to increase marketability in any sphere, and language pedagogy is no exception: without it, research is perceived as fragmented, reducing its overall visibility. 'Datadriven learning' might or might not be the phrase to take the field further, only time will tell. Other proposals have included '(classroom) concordancing', 'corpus consultation', and 'corpus-based language learning' among others, each also with its relative merits and disadvantages. This is not to denigrate the potential of the approach itself. Johns (1993: 8) claimed it "mirror[ed] the Zeitgeist of the 1990s", but it fits just as well with the postcommunicative movement of the present day which, even in caricature, "turns the school into a house of personal learning and discovery, task-based, collaborative, with process-input, the teacher as guide, and the like" (Decoo 2001: n.p.). The eclectic and non-dogmatic nature of DDL (by whatever name) is fully compatible with communicative language teaching; discovery learning and learning by doing; autonomisation and learning to learn; learner-centredness and individualization; collaborative learning and creativity; task-based and process as well as product orientations; form and meaning in constructivism; with an emphasis on the authentic language of discourse by register / genre. It can be particularly useful in language for specific purposes (including content and language integrated learning), making full use of information and communication technology and thus promoting computer skills.

It seems reasonable then to hope for a bright future where DDL can integrate ordinary classroom practice.

Bibliography

Ahmad, K., G., Corbett & M. Rogers. (1985), 'Using computers with advanced language learners: an example.' The Language Teacher (Tokyo), 9 (3): 4-7.

  Aitchison, J. (2003), Words in the Mind: An Introduction to the Mental Lexicon, Oxford: Blackwell.

Table 1 .

 1 Overview of 61 empirical studies

			A studies	B studies	C studies	AVERAGE
			(n=19)	(n=23)	(n=19)	(n=61)
		English	89%	78%	79%	82%
	background	HEI advanced intermediate low specialists	89% 42% 47% 11% 37%	87% 65% 26% 9% 42%	89% 53% 47% 0% 53%	88% 54% 39% 7% 48%
		non-specialists	52%	30%	37%	40%
		corpus linguistics	16%	30%	0%	16%
	main focus	language writing reading	68% 0% 0%	35% 22% 9%	47% 42% 11%	49% 21% 7%
		miscellaneous	16%	4%	0%	8%
	support	hands-on program paper	47% 11% 42%	74% 22% 4%	79% 21% 0%	67% 18% 15%

Actually, one of his papers in the volume[START_REF] Johns | From printout to handout: grammar and vocabulary teaching in the context of data-driven learning[END_REF]) which included the term had previously appeared in CALL Austria in 1990. Several of his articles were reprinted in various forms, or translated to other languages[START_REF] Johns | Implications et applications des logiciels de concordance dans la salle de classe[END_REF] was a French version of Johns 1988a). More interested in teaching than academic research, he was not the most prolific of writers.

Tributes can be found on the homepage of his old centre at the University of Birmingham (http://www.eisu.bham.ac.uk/timjohns.shtml), and in the International Journal of Corpus Linguistics[START_REF] Scott | In memory of Tim Johns[END_REF].

Specifically the English for Overseas Students Unit (now the English for International Students Unit).

Johns (1988: 13-14) attributes this metaphor to[START_REF] Seliger | The language learner as linguist: of metaphors and realities[END_REF].

Based on the French statesman Clémenceau(Letters and Diaries, 1935:

6): "La guerre! C'est une chose trop grave pour confier à des militaires." (War is too serious a thing to be left to the military.) 6 Virtual DDL Library. http://www.eisu2.bham.ac.uk/johnstf/ddl_lib.htm; EAP page. http://www.eisu2.bham.ac.uk/johnstf/timeap3.htm; Ustí nad Labem DDL Workshop. http://www.eisu2.bham.ac.uk/johnstf/unl_ddl.htm.7 Boulton (n.d.). Tim Johns' Data-Driven Learning: Summaries, http://arche.univ-nancy2.fr/course/view.php?id=967.

Confusingly, McCarthy (e.g. 2008: 566) makes a similar distinction, but with 'corpus-based' as the radical term, and 'corpus-informed' as the more flexible.

Johns had been working on a biography of the author, Arthur Ransome, during his retirement: http://www.allthingsransome.net/.

Johns had himself used the expression "serendipity learning", but referring to a specific activity where pairs of learners are provided with print-outs of different concordances "with the instruction to find as many things as possible in ten minutes that are worth reporting back to the rest of the class"(Johns 1988: 21).