Ulrich Faigle
email: faigle@zpr.uni-koeln.de

Michel Grabisch
email: michel.grabisch@univ-paris1.fr

Values for Markovian Coalition Processes

Keywords: coalitional game, coalition formation process, exchange economy, Markov chain, Shapley value JEL Classification: C71

, where the classical Shapley value leads to counterintuitive allocations. The Markovian process value avoids these drawbacks and provides plausible results.

Introduction

The Shapley value is an allocation scheme for both TU-and NTU-games that is widely applied in economics (see, e.g., [START_REF] Van Den Brink | Component efficient solutions in line-graph games with applications[END_REF]; [START_REF] Bergantiños | A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems[END_REF]; [START_REF] Liggett | The asymptotic Shapley value for a simple market game[END_REF]; van den Brink et al. (forthcoming), and a list of references in [START_REF] Aumann | On the non-transferable utility value: a comment on the Roth-Shafer examples[END_REF][START_REF] Aumann | Value, symmetry, and equal treatment: a comment on Scafuri and Yannelis[END_REF]). Its success can be explained by the fact that it always exists and obeys generally accepted rationality axioms. Nevertheless, there are realistic situations where it produces strikingly counterintuitive results, as pointed out by, e.g., [START_REF] Roth | Values for games without sidepayments: some difficulties with current concepts[END_REF], [START_REF] Shafer | On the existence and interpretation of value allocation[END_REF], [START_REF] Scafuri | Non-symmetric cardinal value allocations[END_REF]. The two latter references describe situations in exchange economies where a player with no initial endowment obtains positive consumption of each good at the equilibrium value allocation and the latter is not in the core. Moreover, [START_REF] Scafuri | Non-symmetric cardinal value allocations[END_REF] point out that players with identical utility functions and endowments might be treated unequally. As judiciously remarked by [START_REF] Aumann | On the non-transferable utility value: a comment on the Roth-Shafer examples[END_REF], similar counterintuitive examples exist for other notions in game theory (e.g., Nash equilibrium and core). Yet, one would not want to abandon them.

On the other hand, counterintuitive examples can become starting points towards more general notions and shed new light on existing theory. An examination of the various comments on Roth's and Shafer's examples by [START_REF] Aumann | On the non-transferable utility value: a comment on the Roth-Shafer examples[END_REF] and [START_REF] Hart | Endogenous formation of coalitions[END_REF] suggests in particular that the key point is knowing what agent is allowed/supposed to meet with what other agent -and in what order1 . Hart and Kurz approach this issue by imposing some coalition structure and neglect the dynamic aspect of time (or order). In constrast, our approach focuses on the latter by introducing the model of a coalition process that evolves in time. We will demonstrate that this notion permits a very flexible definition of the Shapley value, which we call (Shapley) process value, and may avoid the undesirable features exhibited in Shafer's and Scafuri and Yannelis' examples. Observe that the time dimension is already implicit in Shapley's work on cooperative solution concepts (cf. Shapley (1953b)). Let v be the characteristic function of some TU-game on the set N of agents. To assess the average contribution of a given agent i ∈ N towards the total benefit v(N ), Shapley lets his agents enter an originally empty room one by one until the grand coalition N is assembled. The contribution of i is the marginal difference v(S ∪ i)v(S) with respect to the set S already present. Taking all possible ways for this to happen (i.e., all total orders on N ) into account, one can compute the average contribution of i. So Shapley models a particular coalition process (or scenario) whose evolution is restricted to the sequential addition of single agents until the grand coalition N is formed. Shapley's approach was later generalized to the model of so-called probabilistic values [START_REF] Weber | Probabilistic values for games[END_REF] and random values (Faigle and Voss, forthcoming).

The Shapley-Weber view is quite narrow: First, why should the computation consider all possible orders? Second, why should agents enter just one by one, and why is nobody allowed to leave the room? The latter question raises another one: Why should the process terminate with the grand coalition?

The aim of our current investigation is to ideally drop any such restriction on scenarios and to admit a priori any sequence of coalitions 23 . Two questions then arise. First: For what reasons should a coalition S evolve into another coalition T ? Second, since an all-comprehensive model would be too loose to study: What kind of scenarios should the model admit?

Our model is motivated by the idea that acting and interacting agents form coalitions where they gain individually from the cooperation. The cooperation may result from individual preferences of agents on coalitions (like in hedonic games) or from certain individual utility functions, or simply from the characteristic function v itself4 . These details are not our concern, however. We just assume some hidden and unknown mechanism to exist and cause these preferences, which leads us to the second question. We assume that the process evolves in discrete time steps and that we usually have neither complete information nor certainty about the coalition status at a given time t. We model this situation by a probability distribution p(t) on 2 N that arises from an initial state p(0) and evolves according to a memory-less Markov chain5 on the set 2 N of "ground states" (i.e., possible coalitions).

We then turn to the problem of establishing a Shapley-type value for such a process, that is, of evaluating the average (or expected) contribution of a player. We introduce two different definitions for a Shapley process value and provide axiomatizations for both of them. Interestingly, our axioms are quite close to the classical ones given by Shapley and thus shed some (new) light on them.

The paper is organized as follows. We motivate our approach in Section 2 with well-known examples from exchange economies that exhibit undesirable features of the classical Shapley value. We show how our approach can flexibly avoid these drawbacks. We then enter details in Section 3. We introduce Markovian coalition processes and give three examples of such processes, including the classical Shapley paradigm. Section 4 provides two different (Shapley) process values and illustrates them on the examples of Section 3. Axiomatizations of the two values are established in Section 5.

Most of the proofs are deferred to the Appendix. For easier notation, our exposition will often omit braces around singletons.

A motivating example in exchange economies

An exchange economy consists of a set N = {1, . . . , n} of agents, a commodity space R l + and initial endowments ω i ∈ R l + as well as individual utility functions u i : R l + → R for the agents i ∈ N . Given the non-negative vector λ = (λ 1 , . . . , λ n ), the exchange economy gives rise to the TU-game (N, v λu ), where

v λu (S) := max xi∈R l + i∈S λ i u i (x i ) subject to i∈S x i = i∈S ω i
associates with the coalition S ⊆ N the maximum λ-weighted utility the agents in S can achieve by exchanging their commodities.

The vector tuple {x i } i∈N is said to be a (cardinal) value allocation if some non-trivial λ = (λ 1 , . . . , λ n ) ∈ R n + exists such that (λ 1 u 1 (x 1 ), . . . , λ n u n (x n )) is the Shapley value of the TU-game (N, v λu ). Under mild hypotheses, [START_REF] Shafer | On the existence and interpretation of value allocation[END_REF] has proved that a value allocation always exists.

2.1 Example 1 [START_REF] Hart | Endogenous formation of coalitions[END_REF] Assume the exchange economy involves three agents and two commodities ("left gloves" and "right gloves") and hence l = 2. Where ǫ is a small quantity, the next table summarizes the data:

agent initial endowment utility function 1 (1 -ǫ, 0) min(x, y) 2 (0, 1 -ǫ) min(x, y) 3 (ǫ, ǫ) x+y 2
Agents 1 and 2 are looking for pairs of gloves, while agent 3 is just interested in the leather. λ = (1, 1, 1) is easily seen to yield

v λu ({1}) = v λu ({2}) = 0, v λu ({3}) = ǫ v λu ({1, 2}) = 1 -ǫ, v λu ({1, 3}) = v λu ({2, 3}) = 1 + ǫ 2 v λu ({1, 2, 3}) = 1 with Shapley value Sh 1 (v λu ) = Sh 2 (v λu ) = 5 12 (1 -ǫ), Sh 3 (v λu ) = 1 6 (1 + ǫ).
Consequently,

5 12 (1 -ǫ), 5 12 (1 -ǫ) , 5 12 (1 -ǫ), 5 12 (1 -ǫ) , 1 6 (1 + ǫ), 1 6 (1 + ǫ)
is a cardinal value allocation with λ = (1, 1, 1). Let us comment on this solution.

Observe first the following: Given the utility functions and the initial endowments, the above approach yields a unique solution, despite the fact that one could imagine different outcomes depending on how the agents meet. This is well illustrated in Aumann's description (see footnote 1), and we will come back to this issue later.

Notice furthermore that the solution is not in the core of the game: Coalition {1, 2} can block it by proposing the allocation

( 6 12 (1 -ǫ), 6 12 (1 -ǫ), (ǫ, ǫ)),
which provides a feasible and strictly greater utility for agents 1,2. So this approach does not satisfy coalitional rationality in general. Moreover, the solution is counterintuitive in the sense that agent 3, who started with (ǫ, ǫ), ends up with about 1/6 of the goods -even when ǫ → 0.

The agents 1 and 2, being rational and aware of the disadvantage of the solution above, want to avoid it. Hart and Kurz write: "What can 1 and 2 do? By forming a "union" (thus inducing the coalition structure {{1, 2}, {3}}), they eliminate the possibility that 3 will be able to "catch" one of them "alone". [...] However, after deciding to form a coalition, they do not "leave" the game but rather bargain with 3, [...] which will improve everyone's outcome.".

The preceding story gives a simple example of what we call a coalition formation process: Agents 1 and 2 are initially alone. They decide to form a coalition and finally join with agent 3. We view coalition formation processes as (Markovian) stochastic processes, whose realizations are scenarios. Roughly speaking, scenarios are sequences of coalitions of "active" players, starting from some coalition and ending in some terminal coalition (though not necessarily the grand coalition as in the present example)6 . By "active players", we mean agents who can bargain together. Hence we distinguish between agents in the game and outside the game. Only those in the game can bargain. In the present situation, we have two possible scenarios (denoting {1, 2} by 12, etc.):

S 1 : ∅ -1 -12 -123 S 2 : ∅ -2 -12 -123
They are taken to be equiprobable as there is no reason to favor one of the agents. The underlying Markov process for these scenarios is depicted in the figure below (numbers on arrows indicate transition probabilities and are omitted when the transition is certain).

∅ 2 1 12 123 1/2 1/2
Note that the scenarios in the classical view of Shapley correspond to all possible orders in which players enter the game. Hence in the present situation, we would would also have to include these 4 scenarios:

S 3 : ∅ -1 -13 -123 S 4 : ∅ -2 -23 -123 S 5 : ∅ -3 -13 -123 S 6 : ∅ -3 -23 -123
However, they are clearly ruled out by the fact that agents 1 and 2 want to avoid any bargaining with 3 before they engage in the coalition {1, 2}.

It remains to compute a Shapley-like value for our two scenarios. Proceeding exactly as in the classical situation, we compute the marginal contribution of each agent in the two scenarios S 1 , S 2 . We find

φ S1 1 (v λu ) = v λu (1) = 0, φ S1 2 (v λu ) = v λu (12) -v λu (1) = 1 -ǫ, φ S1 3 (v λu ) = v λu (123) -v λu (12) = ǫ φ S2 1 (v λu ) = 1 -ǫ, φ S2 2 (v λu ) = 0, φ S2 3 (v λu ) = ǫ. Hence averaging yields φ 1 (v λu ) = 1 -ǫ 2 = φ 2 (v λu ), φ 3 (v λu ) = ǫ
and thus the following value allocation with λ = (1, 1, 1):

1 -ǫ 2 , 1 -ǫ 2 , 1 -ǫ 2 , 1 -ǫ 2 , ǫ, ǫ .
This solution avoids the drawbacks of the previous one. First, it is in the core since no coalition can block it. Second, it is more natural than the previous solution, in particular with view on the allocation of agent 3. Third, it is more flexible since not necessarily unique. More precisely, it is unique once the process is fixed. But one may consider different processes in order to model different "stories". The above process follows exactly the description of the story of Hart and Kurz. However, we may consider it as too simplistic, and envisage some possibility for agent 3 to "catch" agent 1 or 2 alone with some probability p. This story would yield the following process: Its scenarios are (under the previous notation) S 1 , S 2 , S 3 , S 4 with probabilities (1p)/2, (1p)/2, p/2, p/2 respectively. We find

φ S3 1 = 0, φ S3 2 = 1 -ǫ 2 , φ S3 3 = 1 + ǫ 2 , φ S4 1 = 1 -ǫ 2 , φ S4 2 = 0, φ S4 3 = 1 + ǫ 2 ,
so that the computation of the expected value leads to

φ 1 = φ 2 = 1 -ǫ 2 1 - p 2 , φ 3 = p 2 (1 -ǫ) + ǫ.
Again, this defines a cardinal value allocation {(φ 1 , φ 1 ), (φ 2 , φ 2 ), (φ 3 , φ 3 )}, which is not necessarily in the core, however. For p = 0 we recover the previous process while p = 1/2 produces φ 3 = (1 + 3ǫ)/4. This relatively high value reflects the following aspect: If agent 3 can bargain with 1 or 2, he must have a better "utility producing technology" than agents 1 or 2 and thus a higher intrinsic value.

2.2 Example 2 [START_REF] Scafuri | Non-symmetric cardinal value allocations[END_REF])

We turn to Scafuri and Yannelis' example of an undesirable "unequal treatment effect" and explain how our approach can circumvent it very easily 7 . There are again three agents, two commodities, the utility functions

u 1 (x, y) = u 2 (x, y) = 1 2 x ρ + 1 2 y ρ 1/ρ , u 3 (x, y) = 1 2 x β + 1 2 y β 1/β ,
7 see also the discussion of [START_REF] Aumann | Value, symmetry, and equal treatment: a comment on Scafuri and Yannelis[END_REF] with 0 ≤ ρ < β ≤ 1, and initial endowments ω 1 = (1, 0), ω 2 = (0, 1) and ω 3 = (0, 0). Since

( 1 2 x β + 1 2 y β ) 1/β ≥ ( 1 2 x ρ + 1 2 y ρ ) 1/ρ ,
the present example is similar to the previous one in the sense that the Shapley value will yield an allocation where agent 3 receives a positive amount, which therefore cannot be in the core.

Let us now add a fourth agent with same utility and endowment as agent 3 but with unequal weights:

λ 1 = λ 2 = λ 3 = 1 and 0 ≤ λ 4 < 1 2 ((1/ρ)-(1/β)) .
Notice that the the utility of player 4 is less than those of agents 1 and 2:

λ 4 1 2 x β + 1 2 y β 1/β < 1 2 x ρ + 1 2 y ρ 1/ρ .
The associated TU-game has the characteristic function

v λu (1) = v λu (2) = 1 2 1/ρ , v λu (3) = v λu (4) = 0, v λu (13) = v λu (23) = 1 2 1/β v λu (14) = v λu (24) = 1 2 1/ρ , v λu (12) = 1, v λu (34) = 0 v λu (123) = v λu (124) = v λu (1234) = 1, v λu (134) = v λu (234) = 1 2 1/β .
Agents 3 and 4 are substitutes: They have the same utility function and initial endowment. We speak of unequal treatment if substitute agents are allocated differently. Observe that the Shapley value treats 3 and 4 unequally:

Sh 3 (v λu ) = 1 3 1 2 1/β - 1 2 1/ρ , Sh 4 (v λu ) = 0 Sh 1 (v λu ) = Sh 2 (v λu ) = 1 -Sh 3 (v λu ) 2 .
Our methodology avoids the unequal treatment effect: As agents 3 and 4 are substitutes, it seems reasonable for them to play symmetric rôles in the "story". That is, agents 1 and 2 still want to form a coalition before meeting either agent 3 or 4. This implies the following process:

∅ 1 2 12 124 123 1234 1/2 1/2 1/2 1/2
There are four equiprobable scenarios:

S 1 : ∅ -1 -12 -123 -1234 S 2 : ∅ -1 -12 -124 -1234 S 3 : ∅ -2 -12 -123 -1234 S 4 : ∅ -2 -12 -124 -1234
It is easy to see that

φ Si 3 = φ Si 4 = 0, i = 1, . . . , 4
so that the allocations to agents 3 and 4 are symmetric (and null).

By modifying the process and altering the symmetry between agents 3 and 4, it is possible to introduce some unequal treatment. For example, we may consider some scenario S where agent 3 meets agent 1 or 2 alone with some probability, e.g., ∅ -1 -13 -123 -1234.

We would then have φ S 3 = 1 2 1/β -1 2 1/ρ , while φ S 4 is still 0. Interestingly, even a scenario like S ′ = ∅ -1 -14 -124 -1234 would lead to φ S ′ 4 = 0. This is because the "utility producing technology" of agent 4 (due to the condition on λ 4 ) is weaker than the one of agent 3. Nevertheless, we recognize the flexibility our approach bears on these benchmark examples.

Markovian coalition processes

Let N := {1, . . . , n} be a finite set of players/agents and denote by 2 N the family of all subsets ("coalitions") S ⊆ N . Viewing the formation of a coalition as a process that evolves over discrete time, a realization (or scenario) of a coalition (formation) process is a sequence (string) of (possibly repeated) coalitions

S = S 0 S 1 • • • S k • • • .
No special assumption on S is made for the moment. Purely formally, in full generality, the process starts in some "empty state" at time t = 0 and then moves to some coalition S 1 ⊆ N at time t = 1. In most applications, however, the process starts naturally at ∅, so we will usually consider simply S 0 = ∅, and call it a normal process 8 . Moreover, in order to account for incomplete information, we treat the evolution from one step to the next one as a random event. If the process has attained the coalition S at time t -1, we denote the probability of the transition S → T , i.e., for reaching T at time t, by u (t-1) S,T .

8 The distinction between and ∅ may appear artificial at this stage. However, it is necessary since it may happen that ∅ is an absorbing state, i.e., no more transition is possible from this state. This will be the case in Example 3.1.3.

In the present investigation, we concentrate exclusively on processes whose transition probabilities u (t-1) S,T are independent of t and denote theses therefore simply by u S,T . So the transitions are characterized by the transition matrix

U := [u S,T ] S,T ⊆N . If S = S 0 S 1 • • • S k
is a finite scenario of a normal coalition process with transition matrix [u S,T ], the probability Pr(S) of the occurrence of S is easily computed. Setting Pr(S 0 ) := 1, we have:

Pr(S 0 S 1 • • • S k ) = Pr(S 0 )u S0,S1 • • • u S k-1 ,S k = k i=1 u Si-1,Si .
(1)

Observe that a transition matrix U with coefficients u S,T is row-stochastic, that is, u S,T ≥ 0 and T ⊆N u S,T = 1 holds for all S ⊆ N .

We refer to a coalition process with a time independent transition matrix U as being Markovian.

Examples

Shapley-Weber processes

Our first example shows that the classical paradigm of Shapley is captured by our framework. We define a Shapley-Weber process as a normal Markovian coalition process whose transition probabilities u S,T have the Shapley-Weber property:

(SW) u N,N = 1 and u S,T = 0 unless S = T \ i holds for some i ∈ T .

A Shapley process is a special Shapley-Weber process whose transition probabilities u S,T satisfy the condition

(S) u S,T = 1 n-|S| if S = T \ i holds for some i ∈ T .
In the case n = 3, the transition matrix U of the associated Shapley process is (with blanks indicating zeroes):

U = ∅00 100
00 1/3 1/3 00 1/3 00 00 123 1/2 1/2 1/2 1/2 1 1/2 1/2 1 1 1 3 7 7 7 7 7 7 7 7 7 5
The scenarios of Shapley-Weber processes correspond to the n! maximal chains

∅ = S 0 ⊂ S 1 ⊂ • • • ⊂ S n-1 ⊂ S n = N
of coalitions. In the special case of a Shapley process the scenarios are equiprobable with the probabilities Pr(S 0 , . . . , S n ) = 1/n!.

Shapley processes underlie the classical coalition formation model of Shapley (1953a), while general Shapley-Weber processes provide the framework for Weber's theory of probabilistic values [START_REF] Weber | Probabilistic values for games[END_REF]. The so-called weighted Shapley value, introduced in Shapley (1953b), is a special instance of a probabilistic value (see also [START_REF] Kalai | On weighted Shapley values[END_REF]) and hence also captured by our model.

The Metropolis process

A Shapley process in the strict sense is independent of a particular characteristic function v : 2 N → R that might be defined on the collection 2 N of possible coalitions, while the Shapley-Weber model offers some flexibility to allow random transitions S → T whose probabilities u S,T depend on v(S) and v(T ). [START_REF] Metropolis | Equations of state calculations by fast computing machines[END_REF] have proposed a process for statistical sampling, which can be viewed as a Markovian coalition process in our context and takes a given function v : 2 N → R into account. The Metropolis process M is defined as follows:

-Choose a "temperature" θ > 0, and start from ∅.

-Suppose the current coalition is S. The next coalition T is chosen as follows:

(i) Select i ∈ N at random and set

T := S ∪ i, if i ∈ S S \ i, if i ∈ S.
Set δ(S, T ) := v(T )v(S) and move to T if δ(S, T ) > 0. (ii) If δ(S, T ) ≤ 0, move to T with probability e δ(S,T )/θ , and stay in S with probability 1e δ(S,T )/θ .

The corresponding state transition matrix is given by

u M,θ S,T =      1 n • min{1, e δ(S,T )/θ }, if T is of the form S ∪ i or S \ i 0, if T = S not of this form 1 -R =S u S,R , if T = S.
Clearly, the transition depends on v and on the temperature θ. One sees that a favorable transition (i.e., towards a higher value of v) is always carried out. But unfavorable transitions can occur, too. This is to model a farsighted process in which a momentary loss may prove beneficial later9 . The two limiting cases θ → ∞ and θ → 0 are of interest. In the first case, the process can never remain in the same state (the diagonal is zero) and every unfavorable transition is executed, while in the second case, no such transition is carried out.

We illustrate these two extreme cases for n = 3 with v being strictly monotonic:

U M,∞ = ∅00 100
00 1/3 1/3 00 1/3 00 00 123 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1/
00 1/3 1/3 00 1/3 00 00 123 1/3 1/3 1/3 1/3 1/3 1/3 2/3 1/3 1/3 1/3 1/3 2/3 1/3 2/3 1/3 1 3 7 7 7 7 7 7 7 7 7 5
Note that the Metropolis process with θ → 0 and v being strictly monotonic resembles the Shapley process but is different because of the diagonal.

Observe for θ → ∞ that the cardinality of the current S is odd (resp., even) at an odd (resp., even) time t. Therefore, the process oscillates between these two families of coalitions and does not converge.

In contrast, when θ → 0 and v is strictly monotonic, the process converges to N with probability 1. But unlike in the Shapley process, convergence will not necessarily occur in n steps. If v is not monotone but v(N ) > v(S) holds for all S ⊂ N , the Metropolis process at low temperature converges to N with high probability. In all other cases, the Metropolis process will not converge to the grand coalition and thus differs substantially from the Shapley process. A general result is given below (see Theorem 1).

A voting model with influence

Imagine N to represent a set of voters who have to make a yes/no decision. Let us assume that each voter has an inclination to vote yes or no (initial opinion state at time t = 0) but may change the opinion over time due to the mutual influence in a phase of discussion among the voters. Denote the set of 'yes' voters at time t by S(t) and assume that the evolution of S(t) is Markovian. In this case, the evolution is not dictated by (the characteristic function of) some game v on N , but by the power of mutual influence. Let us detail an example which is a simplification of the Confucius model of society presented in [START_REF] Hu | On authority distributions in organizations: equilibrium[END_REF] and considered also in (Grabisch and Rusinowska, 2009, forthcoming). There are four players in the original model: The king, the man, the wife and the child. Morevoer, there are three rules:

(i) The man follows the king.

(ii) The wife and the child follow the man. (iii) The king should respect his people.

While the first two rules lead to an immediate implementation into an influence model, the third rule is less clear and can be interpreted in different ways.

Intuitively, it says that the king should give up his project or plan if a majority of the people opposes it.

For ease of calculation, let us simplify the model and merge wife and child into one player. Our Markov process (let us call it the Confucius process C) is best represented by the digraph on Figure 1 (values on edges indicate the probability of transition, and absence of value means probability 1; players are numbered as follows: king=1, man=2, wife=3). It is easy to see that there are

∅ 3 1 2 12 13 23 123 1/2 1/2
Fig. 1 The digraph Γ of the Confucius process two classes where the process terminates, namely {123} (everybody says 'yes') and {∅} (everybody says 'no'). These are the two consensus situations and the process terminates in one of these in at most 4 steps. (Note that is not natural here to start the process from the coalition ∅ ⊆ N but rather from the formal initial state .)

Markov chains and random walks

More abstractly, we can view a Markovian coalition process as a stochastic process (X t ) with the output alphabet Σ = 2 N or, equivalently, as a random walk on the set 2 N . Since the transition matrix U = [u S,T ] of the random walk is constant over time, (X t ) is a homogeneous Markov chain. Σ = 2 N is the set of states of the Markov chain. Let Pr{X t = S} be the probability that the random walk has attained the coalition S at time t and consider the vector p(t) := [p S (t)] S⊆N of probabilities p S (t) := Pr{X t = S}. Then the following relation is well-known from the theory of Markov chains (and easy to verify):

p(t) = p(t -1)U = • • • = p(0)U t .
With U, we associate its (directed) transition graph Γ , whose vertices are the elements S ∈ 2 N (hence coalitions) and there is a directed edge from S to T if and only if u S,T > 0.

Convergence

We say that the Markov chain (X t ) converges if the probability distribution

z := lim t→∞ p(t)
exists and recall some basic facts on the convergence of Markov chains. The classes of a Markov chain are the strongly connected components of Γ , that is, sets of states C ⊆ 2 N such that, for any pair (S, T ) of distinct states S, T ∈ C, there is a directed path from S to T in Γ and C is maximal with this property. Hence, the classes C 1 , . . . , C k partition 2 N .

A class C is said to be transient if there exists an edge (S, T ) with S ∈ C and T / ∈ C and terminal (or recurrent) otherwise. A terminal class C i is aperiodic if the greatest common divisor of the length of all cycles in C is 1 and periodic otherwise. Now the following facts are given:

-If there is a unique terminal aperiodic class, the Markov process terminates in this class, and the probability vector z = lim t→∞ p(t) of the states/coalitions in this class is the unique probability distribution z with the property z = z Ũ where Ũ is the submatrix of U corresponding to the coalitions in the terminal class.

-If the unique terminal class is periodic, lim t→∞ p(t) does not exist, but the Cesaro average lim t→∞

1 t (p(1) + p(2) + • • • + p(t)
) exists, and is found as above.

-If there are several terminal classes, the process terminates in one of these classes.

Notice that the Cesaro average always exists, and coincides with the limit distribution if the latter exists.

Recall that a Shapley-Weber process attains N and terminates in n steps. So {N } is the unique terminal class. More generally, every Markovian process with an acyclic transition graph Γ has singleton terminal classes and stops in one of them after at most n steps. Concerning the Metropolis process, the following result is well-known (and easy to show).

Theorem 1 Assume 0 < θ < ∞. Then the Metropolis process converges to the probability vector z (θ) with the 2 n components z

(θ) S = e v(S)/θ Z θ , where Z θ := S∈2 N e v(S)/θ .
For the proof of Theorem 1, one only has to check that the transition graph of a Metropolis process is strongly connected and has some loops, and that the probability vector z with the components z (θ)

S satisfies zU = z, which is straightforward.

The probability distribution z (θ) is known as a Boltzmann-Gibbs distribution in physics and in information theory.

Entropy

Given any v : 2 N → R, we associate with the probability distribution p on 2 N its expected value

E(v, p) := S∈2 N v(S)p S .
In the special case of Boltzmann-Gibbs distributions, straightforward computation shows:

lim θ→0 E(v, z (θ) ) = max S∈2 N v(S).
Recalling the entropy of p to be the parameter

H(p) = - S∈2 N p S log p S ,
it is a well-known fact in information theory that the Boltzmann-Gibbs distribution maximizes the entropy with respect to a prescribed expected value in the following sense:

Theorem 2 Let min S∈2 N v(S) < ξ < max S∈2 N v(S)
be a prescribed parameter. Then there exists a unique θ = θ(ξ) > 0 such that

E(v, z (θ) ) = ξ and H(z (θ) ) = max{H(p) | E(v, p) = ξ}. (2)
In the context of Markovian coalition formation, the Boltzmann-Gibbs distribution thus has some remarkable properties:

-If the process converges and we know the expected value ξ of v in the limit but have no further information on the limiting distribution, we should go on the assumption that the latter is the corresponding Boltzmann-Gibbs distribution (Theorem 2). -If the Metropolis process is carried out with a "small" θ > 0, then we can expect the formation of a coalition with a high v-value in the limit (equation 2).

4 Values for coalition processes

Scenarios and scenario-values

When the transition graph of the Markov chain has no cycles, the process clearly stops after a finite number t ≤ 2 N of steps. In this case, terminal classes reduce to terminal coalitions. Moreover, all sequences (scenarios) from some initial coalition to a terminal one can be enumerated and their probability of occurrence computed by (1). Often, however, cycles exist and scenarios may be infinite even when the process eventually converges to some terminal coalition. No enumeration is thus possible unless one decides to limit (truncate) the sequence at some time t and to consider the sequences from some initial coalition to some coalition reachable at time t. One may then want to let t tend to infinity, provided the limit exists. As a consequence, we can focus on finite sequences and establish our framework for this case. We will address the (much more tricky) infinite case Section 4.2.

Let us consider a transition matrix U, some time point t, and the set S(U, t) of all scenarios produced by U of length at most t. It is important to note that k < t for a scenario S = S 0 S 1 • • • S k in S(U, t) means that S k is a terminal coalition. In the case k = t, the scenario could continue at time points beyond t. Moreover, when for all scenarios a general bound T on the length of any scenario exists (i.e., when the transition graph is acyclic), we have S(U, T ) = S(U, t) for all t ≥ T .

We set S(U) := S(U, ∞) and let G denote the set of all games on N . We introduce also S, the set of all finite sequences of coalitions

S 0 S 1 • • • S k • • • , S i ∈ 2 N ,
and S 0 can be any set in 2 N or the symbol (formal "empty" state), setting v( ) = 0 10 . Following [START_REF] Grabisch | A coalition formation value for games in partition function form[END_REF], we specify the following concepts:

-A scenario-value is a mapping ψ : G → R n×S . Components of ψ(v) are denoted by ψ S i (v) for scenario (or sequence) S and player i. We call ψ S (v) the scenario-value for scenario (or sequence 11 ) S.

-A value is a mapping Ψ : G → R n . The value induced by the Markov chain U and the scenario-value ψ is

Ψ (v) := S∈S(U) π S ψ S (v), (3)
where π S is the probability of occurrence of scenario S. Since the value depends on the Markovian process, we call it a process value.

The expression (3) is not necessarily well-defined for an infinite process and it may be useful to restrict oneself to scenarios of length at most t:

Ψ (t) (v) = S∈S(U,t) π S ψ S (v).
We will come back to the convergence problem in Section 4.2. Let us now introduce two particular scenario-values.

So consider the scenario S = S 0 S 1 • • • S t . We define the Shapley I scenariovalue by

φ S i (v) := k|i∈S k ∆S k+1 v(S k+1 ) -v(S k ) |S k+1 ∆S k | , ( 4
)
10 The set S is larger than the set of finite scenarios since beginning by ∅ or is not requested. We do this mainly for mathematical convenience, particularly for our axiomatizations (see Section 5.1, the concatenation axiom). Anyway, the scenario-values we propose (see (4), ( 5)), are well-defined on S. 11 In the whole section, it is understood that all statements related to scenario-values are valid for all finite sequences, not only finite scenarios.

where ∆ denotes the symmetric difference (i.e., A∆B = (A ∪ B) \ (A ∩ B)). The Shapley II scenario-value is defined as

φ S i (v) := k|i∈S k ∆S k+1 1 |S k ∆S k+1 |! P from S k to S k+1 (v(S ′ P ) -v(S P )) (5)
where P from S to T is any shortest path from S to T in 2 N , and (S P , S ′ P ) is the (unique) edge of P such that i ∈ S P and i ∈ S ′ P or the converse 12 . Both of these scenario-values offer a natural interpretation in terms of marginal contribution to coalitions (when i enters or leaves). In Shapley I, the principle of insufficient reason is used, while in Shapley II, we "complete" the sequence by adding the "missing" edges, considering that in one step, only one player can leave or enter the coalition. Either value generalizes the classical Shapley value and coincides with it when |S k ∆S k+1 | = 1 holds for all k. Although the first one is simple and natural, the second one will prove to have better properties. The next example illustrates the definition.

Example 1 The following scenario arises from the Confucius process (see Section 3.1.3): S = ∅ → 1 → 2 → 13 → 12 → 123. We obtain:

φ S 1 = v(1) + 1 2 v(2) -v(1) + 1 3 v(13) -v(2) φ S 2 = 1 2 v(2) -v(1) + 1 3 v(13) -v(2) + 1 2 v(12) -v(13) φ S 3 = 1 3 v(13) -v(2) + 1 2 v(12) -v(13)) + (v(123) -v(12) φ S 1 = v(1) + 1 2 -v(1) + (v(2) -v(12)) + 1 6 v(1) + 2(v(13) -v(3))+ 2(v(12) -v(2)) + (v(123) -v(23)) φ S 2 = 1 2 v(2) + (v(12) -v(1)) + 1 6 -2v(2) + (v(1) -v(12)) + 2(v(13) -v(123)) + (v(3) -v(23)) + 1 2 (v(12) -v(1)) + (v(123) -v(13)) φ S 3 = 1 6 2(v(13) -v(1)) + v(3) + (v(123) -v(12)) + 2(v(23) -v(2)) + 1 2 (v(1) -v(13)) + (v(12) -v(123)) + (v(123) -v(12)).
Figure 2 helps in the computation of φ S i .

12 See Example 1 for an illustration. By "shortest path", we mean a sequence of coalitions such that between two subsequent coalitions there is exactly one leaving or entering player. For example, a shortest path from 12 to 234 is 12-123-23-234. The number of shortest paths from S to T is clearly |S∆T |! (see Figure 2).

A scenario-value ψ is efficient if i∈N ψ S i (v) = v(S t ) -v(S 0 ) (6)
is true for every scenario S = S 0 S 1 • • • S t and every game v ∈ G. By extension, the process value induced by an efficient scenario-value is said to be efficient too.

Lemma 1 The scenario values Shapley I and Shapley II are efficient.

Proof The claim is trivially true for t = 1. Arguing by induction, we consider any scenario

S = S 0 S 1 • • • S t S t+1 and let S ′ = S 0 S 1 • • • S t . Then we have φ S i = φ S ′ i + v(St+1)-v(St) |St+1∆St| , if i ∈ S t ∆S t+1 φ S ′ i , otherwise
for any i ∈ M and hence

i∈M φ S i (v) = i∈M φ S ′ i (v) + v(S t+1 ) -v(S t ) = v(S t+1 ).
Similarly we find

φ S i = φ S ′ i + 1 |St+1∆St|! P from St to St+1 (v(S ′ P ) -v(S P )), if i ∈ S t ∆S t+1 φ S ′ i , otherwise.
Now, by the efficiency of the classical Shapley value applied to the Boolean lattice [∅, S t ∆S t+1 ] we obtain

i∈M φ S i (v) = i∈M φ S ′ i (v) + v(S t+1 ) -v(S t ) = v(S t+1 ).

Infinite scenarios

If the graph has cycles or loops, infinite scenarios occur and the value may not converge. Observe, however, that loops do not matter as they induce a zero marginal gain. Moreover, it is easy to see that cycles can be dropped from the computation of Shapley I and II values if, at each time step, there is only one player entering or leaving.

Formally, let us say that a scenario without loops and cycles is simple and denote by S * (U) the set of simple scenarios. Observe that simple scenarios are of finite length. So S * (U) is a finite set. Furthermore, we call two scenarios equivalent if they are identical up to cycles or loops. If S is a simple scenario, we denote by [S] its equivalence class (with respect to a given U). Then we have:

Proposition 1 Assume that |S k ∆S k+1 | = 1 holds for all transitions from S k to S k+1 in U. Then, Shapley I and Shapley II values are

Φ(v) = S∈S * (U) π [S] ψ S (v), where π [S] = S ′ ∈[S] π S ′ .
In the general case, it is difficult to draw any conclusion. We therefore assume in the rest of this section that the value in question is either Shapley I or II or is a value ψ whose scenario-value has the form

ψ S = S k S k+1 ∈S δ S k S k+1 for any scenario S = S 0 S 1 S 2 • • • .
Recall that the process may end in some aperiodic terminal class, possibly reduced to a singleton (terminal state), or in some periodic class, in which case no convergence occurs. Consider a simple (and therefore finite) scenario S 0 terminating in terminal state S with scenario-value φ 0 (v) := φ S0 (v) and probability π 0 . Let S 1 be an equivalent scenario that differs from S 0 by the addition of a cycle C which the scenario traverses 1 time. Similarly, let S 2 , S 3 , . . . be identical to S 1 but with the cycle traversed 2,3, . . . times and the infinite scenario S := lim k→∞ S k .

Let δ(v) := φ S1 (v)φ 0 (v) be the increment of the value obtained by running through the cycle once and therefore

φ S k (v) = φ 0 (v) + kδ(v).
If δ(v) > 0, then φ S clearly tends to infinity. Now, consider the node T where the process has the choice whether or not to enter the cycle. Then the probability η of transition from T to the next node in the cycle (i.e., to enter the cycle) is strictly less than 1. We have π S1 = ηπ 0 , and more generally π S k = η k π 0 .

Hence lim k→∞ π S k = 0 results and the contribution of S 0 , S 1 , . . . , S in Ψ (v) remains finite. Indeed,

∞ k=0 π S k φ S k (v) = ∞ k=0 π 0 η k (φ 0 (v) + kδ(v)) = ∞ k=0 π 0 η k φ 0 (v) + ∞ k=0 kπ 0 η k δ(v) = φ 0 (v)π 0 1 1 -η + δ(v)π 0 η (1 -η) 2 .
The result of finiteness for any number of cycles added, or if strongly connected components are added, holds essentially because the probability to enter a cycle or a strongly connected component is strictly less than 1 (otherwise, the scenario would not end in the terminal state S). However, the exact computation of

∞ k=0 π S k φ S k (v) could be quite involved.
If the terminal class is not a singleton, the value becomes infinite when the process enters a cycle without leaving it (then η = 1). Note, however, that this cannot be the case if the class is aperiodic. Nor is necessarily the case when the class is periodic (see below the example of the Metropolis process with θ = ∞). Nevertheless, one general way to circumvent this difficulty is the Cesaro average

Ψ (v) := lim t→∞ 1 t t k=1 Ψ (k) (v).
Notice, however, that this limit yields counterintuitive results if there is a terminal state reachable in a finite number of steps and a periodic class: The contribution of the former will be zero in the Cesaro limit.

Still another approach is possible for terminal classes which are not reduced to singletons. As explained in Section 3.3, even for periodic classes, it is possible to compute the limit probabilities p S for each state S in a terminal class. One could simply put, as an approximation to the value,

Ψ (v) = C p C S k ,S k+1 ∈C δ S k S k+1 p S k u S k ,S k +1 ,
where C is any non-singleton terminal class, p C the probability to terminate in C, and δ S k S k+1 the increment in the value when passing from S k to S k+1 . The idea behind it is this: Since scenarios spend an infinite amount of time in these terminal classes, the contributions before reaching terminal classes can be neglected.

Examples

We turn to the computation of the (Shapley) process values for examples given in Section 3.1. 13 23 1 2 3 2 1 123 1 3 123 1 2 3 1 2 123 2 3 123 1 2 3 1 3 123 2 3 123 [START_REF] Weber | Probabilistic values for games[END_REF]. Conversely, let ψ be a probabilistic value induced by a probability distribution π on the set of maximal chains from ∅ to N . We can compute the probability of an edge (S, T ) with S = T \ i for some i ∈ T :

∅ 1 2 3 ∅ 12 13 ∅ 12 23 ∅
π(S, T ) = C∋(S,T ) π(C)
where C denotes a maximal chain. Then choosing transition probabilities u S,T ∼ π(S, T ) proportionally (i.e., normalizing the row sums to 1), we obtain a Shapley-Weber process with probabilistic value induced by π.

Example 3 (Metropolis process) Since |S k ∆S k+1 | = 1 both values coincide. Let us consider the case where θ → 0 first. Clearly, there is only one terminal coalition which is 123. We know that M 0 and S differ only by the diagonal (i.e., loops in Γ ) and it is easy to see that loops have no rôle in the computation. Therefore we regain the classical Shapley value.

Consider now the case θ → ∞. There is no convergence and the process oscillates between coalitions of odd and even cardinalities (2 N is a periodic terminal class). Yet, the process is symmetric for all players. So it suffices to compute φ 1 (v) (expressions for φ i (v), i = 1, can be obtained by a simple permutation). Figure 3 gives the set of scenarios when t = 3. Let us apply Proposition 1, since we are in the case of one entering or leaving player at each step. Observe that there are only 3 types of simple scenarios:

S 1 = ∅ -1, S 1,12 = ∅ -1 -12, S 1,12,123 = ∅ -1 -12 -123
and the others (S 2 , S 3 , S 1,13 etc.) arise by permutation. We have

ψ S1 1 = v(1), ψ S2 1 = ψ S3 1 = 0, ψ S1,12 1 = ψ S1,13 1 = v(1) ψ S2,12 1 = v(12) -v(2), ψ S3,13 1 = v(13) -v(3), ψ S2,23 1 = ψ S3,23 1 = 0
Observe that we obtain the classical Shapley value for the simple scenarios of length 3. It remains to compute the probability of each equivalence class. At time step t, there are 3 t equiprobable scenarios. Therefore, computing their probabilities amounts to enumerating them. There is only one scenario equivalent to S 1 , namely the scenario

∅-1-∅-1-• • • . Therefore π [S1] = 1/3 t = π [S2] = π [S3] .
Consider now S 1,12 . We must have coalition 1 at t = 1, then there are two choices for t = 2, either ∅ or 12. Again at t = 3, 1 is only one choice, i.e., we are in the situation as at t = 2. This shows that the probability of scenarios of length t equivalent to S 1,12 is, for t ≥ 2

π [S1,12] = 2 ⌊t/2⌋ -1 3 t ,
where the "-1" accounts for the scenario equivalent to S 1 . The same holds for all scenarios that are equivalent to one of the 6 simple scenarios of length 2.

Then the probability of any scenario equivalent to one of the 6 simple scenarios of length 3 is by complementarity:

π [S1,12,123] = 2 ⌊t/2⌋+1 + 1 3 t-1 . Observe that t → ∞ yields lim t→∞ π [S1] = 0, lim t→∞ π [S1,12] = 0, etc., lim t→∞ π [S1,12,123] = 1 6 .
In conclusion:

-The classical Shapley value is the limit of the Shapley I and II values of the Metropolis process for t → ∞.

Example 4 (Voting model with influence) We compute the values Shapley I and II for the Confucius process. Since scenarios need not begin with the empty set we start with and randomly pass next to any set in 2 N . Here are all the maximal scenarios with their probability of occurrence:

S 1 → ∅ π S1 = 1/8 S 2 → 1 → 2 → 3 → ∅ π S2 = 1/16 S 3 → 1 → 2 → 13 → 12 → 123 π S3 = 1/16 S 4 → 2 → 3 → ∅ π S4 = 1/16 S 5 → 2 → 13 → 12 → 123 π S5 = 1/16 S 6 → 3 → ∅ π S6 = 1/8 S 7 → 12 → 123 π S7 = 1/8 S 8 → 13 → 12 → 123 π S8 = 1/8 S 9 → 23 → 13 → 12 → 123 π S9 = 1/8 S 10 → 123 π S10 = 1/8
We have:

φ 1 (v) = 1 16 φ S2 1 (v) + φ S3 1 (v) + φ S5 1 (v) + 2φ S7 1 (v) + 2φ S8 1 (v) + 2φ S9 1 (v) + 2φ S10 1 (v) φ 2 (v) = 1 16 φ S2 2 (v) + φ S3 2 (v) + φ S4 2 (v) + φ S5 2 (v) + 2φ S7 2 (v) + 2φ S8 2 (v) + 2φ S9 2 (v) + 2φ S10 2 (v) φ 3 (v) = 1 16 φ S2 3 (v) + φ S3 3 (v) + φ S4 3 (v) + φ S5 3 (v) + 2φ S6 3 (v) + 2φ S7 3 (v) + 2φ S8 3 (v) + 2φ S9 3 (v) + 2φ S10 3 (v)
and similarly for the Shapley I value. Skipping lengthy but straightforward calculations, we find:

φ 1 (v) = 1 48 3v(1) + v(2) + 3v(12) + 8v(13) -3v(23) + 2v(123) φ 2 (v) = 1 48 -3v(1) + 4v(2) + 3v(3) + 12v(12) -4v(13) + 2v(123) φ 3 (v) = 1 48 -5v(2) -3v(3) -15v(12) -4v(13) + 3v(23) + 26v(123) φ 1 (v) = 1 16 4v(1) + (v(12) -v(2)) + 3(v(13) -v(3)) + 2(v(123) -v(23)) φ 2 (v) = 1 16 5(v(12) -v(1)) + 4v(2) + (v(3) -v(23)) + 2(v(123) -v(13) φ 3 (v) = 1 16 (v(1) -v(13)) + 3(v(23) -v(2)) + 2v(3) + 6(v(123) -v(12))
As expected by efficiency, one can verify that

3 i=1 φ i (v) = 3 i=1 φ i (v) = 5 8 v(123),
corresponds to the probability of 5/8 to reach 123 and 3/8 to reach ∅.

The comparison with the classical Shapley value φ S is interesting:

φ S 1 (v) = 1 6 2v(1) + (v(12) -v(2)) + 2(v(123) -v(23)) + (v(13) -v(3)) φ S 2 (v) = 1 6 (v(12) -v(1)) + 2v(2) + 2(v(123) -v(13)) + (v(23) -v(3)) φ S 3 (v) = 1 6 2(v(123) -v(12)) + (v(13) -v(1)) + (v(23) -v(2)) + 2v(3)
Terms are basically the same for Shapley II, however their coefficients differ.

On the other hand, Shapley I has no clear structure. Let us illustrate the idea with numerical values and suppose that v(S) is the power of S for constructing a palace. Assume that no individual player can construct a palace alone and that the wife has little skill to do this so that the power values are

v(1) = v(2) = v(3) = 0, v(12) = 8, v(13) = v(23) = 1, v(123) = 10.
The classical Shapley value now yields

φ S 1 (v) = φ S 2 (v) = 27 6 , φ S 3 (v) = 6 6 = 1.
The king and the man have the same power as they are symmetric players.

According to the influence rules, however, the king should have much less power since he needs the approval of his people to construct a palace. With our model we find

φ 1 (v) = 29 16 , φ 2 (v) = 67 16 , φ 3 (v) = 14 16 .
Here the king has less then half of the power of the man, which reflects much more the reality. The computation of Shapley I, on the other hand, leads to seemingly counterintuitive assessments:

φ 1 (v) = 49 48 , φ 2 (v) = 112 48 , φ 3 (v) = 139 48 .

Axiomatizations

We denote by ψ : G → R n×S a scenario-value, where S is the set of finite sequences of coalitions (see Section 4.1).

Basic axioms

Let S = S 1 • • • S q , S ′ = S ′ 1 • • • S ′ r be two sequences in S. They are concatenable if S q = S ′
1 , in which case their concatenation is the sequence

S ⊕ S ′ := S 1 • • • S q S ′ 2 • • • S ′ r .
Concatenation (C): Let S, S ′ be two concatenable sequences. Then

ψ S⊕S ′ = ψ S + ψ S ′ .
The shortest sequences are those of length 1, which we will denote by S → T , for some S, T ∈ 2 N . We call them simply transitions. The concatenation axiom tells us to restrict attention to transitions. Indeed,

ψ S = t-1 k=0 ψ S k →S k+1 for every sequence S = S 0 S 1 • • • S t .
Time Reversality for transitions (TR): Let S → T be a transition.

Then

ψ S→T = -ψ T →S . A player i is said to be inactive in a transition S → T if either i ∈ S ∪ T or i ∈ S ∩ T (in more compact form, if i ∈ S∆T ). More generally, i is inactive in a sequence S if either i ∈ S or i ∈ S.
Inactive players in transitions (IP):

If i is inactive in S → T , then ψ S→T i (v) = 0 for any game v.
Irrelevant Coalitions (IC): Let v, v ′ be identical on a sequence S.

Then ψ S (v) = ψ S (v ′ ).
Axioms (C), (TR), (IP) and (IC) are "new" in cooperative game theory 13 . They reflect the idea of a scenario but do not reflect the properties of v. We introduce now more classical axioms which depend on v.

Efficiency for transitions (E): For any transition S → T and game v, we have

i∈N ψ S→T i (v) = v(T ) -v(S)
.

By (IP), (E) reduces to i∈S∆T ψ S→T i (v) = v(T ) -v(S)
. Also (C) and (E) imply the efficiency on a sequence, which was introduced in (6).

Linearity for transitions (L): v → ψ S→T (v) is a linear operator for any transition S → T .

(C), (L) and (IC) imply a representation as a linear combination with real coefficients a i S,S :

ψ S i (v) = S∈S a i S,S v(S). (7)
Symmetry for transitions (S): For any i ∈ N , any transition S → T and any permutation σ on N , one has

ψ S→T i (v) = ψ σ(S)→σ(T ) σ(i) (v • σ -1 ).
We study the effect of symmetry on transitions.

Lemma 2 Let S → T and S ′ → T ′ be two transitions. Then there exists a permutation σ such that σ(S ′ → T

′ ) = S → T if and only if |S \ T | = |S ′ \ T ′ |, |T \ S| = |T ′ \ S ′ |, and |S ∩ T | = |S ′ ∩ T ′ |. Proof The only if part is obvious. Since |S \ T | = |S ′ \ T ′ |, there exists a permutation σ ′ such that S \ T = σ ′ (S ′ \ T ′ ).
Similarly, there exist σ ′′ , σ ′′′ such that T \ S = σ ′′ (T ′ \ S ′ ) and S ∩ T = σ ′′′ (S ′ ∩ T ′ ), and since S \ T , T \ S and S ∩ T are disjoint, there exists a common permutation σ for all three together, and σ(S ′ → T ′ ) = S → T .

For the following, it is convenient to introduce the signature of a transition S → T as the parameter

τ (S → T ) := (|S \ T |, |T \ S|, |S ∩ T |).
13 However, (IP) is close to the classical carrier axiom.

Axiomatization of the Shapley I scenario-value

Proposition 2 Under (L), (IC), (IP) and (S) we have for any transition S → T

ψ S→T i (v) =      a τ (S→T ),1 v(S) + a τ (S→T ),2 v(T ), if i ∈ S \ T b τ (S→T ),1 v(S) + b τ (S→T ),2 v(T ), if i ∈ T \ S 0, otherwise,
for some real coefficients a τ (S→T ),1 , a τ (S→T ),2 , b τ (S→T ),1 , and b τ (S→T ),2 . Moreover, (TR) implies

a τ (S→T ),1 = -b τ (T →S),2 , a τ (S→T ),2 = -b τ (T →S),1 .
(See the Appendix for the proof.)

We introduce another axiom that expresses some symmetry between leaving and entering players. It says that the contribution of a leaving player i (in S \ T ) is the same as that of any entering player j (in T \ S), provided they are symmetric, i.e., v(K ∪ i) = v(K ∪ j) holds for all K ⊆ N \ {i, j}. In other words, there is no reason to weigh one higher than the other 14 . (See the Appendix for the proof.) Axiom (SEL) is debatable. Indeed, one could think of a skew symmetric property instead:

ψ S→T i = -ψ S→T j for i ∈ S \ T and j ∈ T \ S.
This modified axiom, however, would not induce a value. As a closer look at the proof reveals, one would obtain

a m,k,l,1 = a k,m,l,2 , a m,k,l,2 = a k,m,l,1 and a m,k,l,1 = - 1 m -k a m,k,l,2 = 1 m -k ,
14 Observe however that under (S) and (IC) the assumption of symmetry is unnecessary as soon as |S \ T | or |T \ S| is greater than 1. Indeed, under symmetry of i and j in v, (S) and (IC) imply that if i, j ∈ S \ T then ψ S→T i = ψ S→T j , and similarly for T \ S. In other words, players in S \ T or T \ S are indistinguishable.

and therefore a k,m,l,i = -a m,k,l,i for i = 1, 2. Observe that the value is undefined if |S \ T | = |T \ S| holds. Note furthermore that Shapley II does not fulfill (SEL).

The counterintuitive nature of (SEL) explains why this value induces results that are difficult to explain (see Example 4) and shows that it should not be used in practice, despite of its simple appearance .

Axiomatization of the Shapley II scenario-value

Recall that i ∈ N is a null player for v if v(S ∪ i) = v(S) for all S ⊆ N \ i. Let us introduce a null axiom like in the classical framework.

Null axiom for transitions (N): Every is a null player i obtains ψ S→T i (v) = 0 relative to every transition S → T .

Proposition 3 Assuming (L), (S), and (N), every transition S → T yields Proof Under (L) and (S), (N) implies for any null player i ∈ S \ T :

ψ S→T i =      K⊆N \i a τ (S→T ),τ (S→T |K∪i) (v(K ∪ i) -v(K)), if i ∈ S \ T K⊆N \i b τ (S→T ),τ (S→T |K∪i) (v(K ∪ i) -v(K)), if i ∈ T \ S 0,
0 = ψ S→T i (v) = K⊆N \i v(K) a ′ τ (S→T ),τ (S→T |K) + a τ (S→T ),τ (S→T |K∪i) .
Since there is no restriction on v(K), we find

a ′ τ (S→T ),τ (S→T |K) = -a τ (S→T ),τ (S→T |K∪i) , ∀K ⊆ N \ i. (8)
We introduce another symmetry axiom for entering and leaving players. We say that players i, j ∈ N are antisymmetric (relative to v) if

v(K) -v(K \ i) = v(K ∪ j) -v(K), ∀K ⊆ N \ j, K ∋ i v(K) -v(K \ j) = v(K ∪ i) -v(K), ∀K ⊆ N \ i, K ∋ j.
In a more compact form, we stipulate for any K ⊆ N \ i, j: In contrast to axiom (SEL), (ASEL) expresses a more natural symmetry between leaving and entering players. The axiom says that if i leaves the coalition and j enters, their contribution is complementary and of equal magnitude, provided they are antisymmetric in the sense that the loss induced by one leaving equals the gain induced by the other entering.

v(K ∪ i) -v(K) = v(K ∪ ij) -v(K ∪ i) v(K ∪ j) -v(K) = v(K ∪ ij) -v(K ∪ j).
Theorem 4 A scenario-value satisfies (C), (L), (IP), (E), (S), (N) and (ASEL) if and only if it is the Shapley II scenario-value.

(The proof is given in the Appendix.)

We make some final comments.

φ S→T i (v) = φ S i (v S , S∆T ), ∀i ∈ S∆T.
(iii) The inverse function Γ -1 S provides a convenient way to translate classical values (Shapley, Banzhaf, etc.) into their counterparts in coalition processes. It should thus be not too difficult to axiomatize them following the same philosophy. (iv) A last important question: Why do we need two symmetry axioms? It is easy to see that v-antisymmetric players i, j in S → T become classical v Ssymmetric players in S∆T . Because of the signature, the symmetry axiom allows only the exchange of players that are both in S \ T or in T \ S, or in S ∩ T . The exchange of players from S \ T to T \ S requires something more, namely the antisymmetric axiom ASEL. Since players in S ∩T do not matter, the conjunction of (S) and (ASEL) is equivalent with the classical symmetry axiom.

Concluding remarks

We have introduced the model of coalition processes that extends Shapley's classical paradigm for the justification of his value. A normal coalition process starts from ∅. There is no other restriction imposed on the sequence of coalitions, which we call scenarios. We show that a coalition process is best represented as a Markov chain and we give three important examples of such process: The Shapley-Weber process, the Metropolis process and voting under influence (e.g., the Confucius process).

We have formalized and axiomatized two process values, Shapley I and Shapley II, for the evaluation of the average contribution of individual players in a given coalition process. The computations of these values for our three examples and axiomatizations suggest that Shapley II, although more complicated than Shapley I, has nicer properties and is more intuitive. Both values coincide on coalition processes where only one player can leave or enter a coalition at each step.

We have shown that our process value can be easily applied to exchange economies, where it leads to allocations that are more satisfactory than the ones based on the classical Shapley value.

Finally, we stress that our function Γ S provides a mechanism for translating any value or power index defined in the classical setting into our framework. Thus Banzhaf values, Coleman indices, etc. and in particular values arising from voting under influence can be meaningfully defined for coalition processes. By (L), (IC) and ( 7), any transition S → T and permutation σ yields

ψ S→T i (v) = a i S→T,S v(S) + a i S→T,T v(T ) ψ σ(S→T ) σ(i) (v • σ -1 ) = a σ(i) σ(S→T ),σ(S) v(S) + a σ(i) σ(S→T ),σ(T ) v(T ).
Applying (S), we find

a i S→T,S = a σ(i) σ(S→T ),σ(S) (9)
and similarly for a i S→T,T , for any σ, S, T and i. By Lemma 2 we see that a i S→T,S , a i S→T,T can be replaced by a i τ (S→T ),1, , a i τ (S→T ),2 respectively. Now suppose that σ(S) = S and σ(T 9) implies a i τ (S→T ),1 = a j τ (S→t),1 for any i, j ∈ S , and the analogous equality for i, j ∈ T . Since all players in S ∩ T and outside S ∪ T are inactive, the result follows from axiom (IP).

) = T . Then i ∈ S ⇒ σ(i) ∈ S, i ∈ T ⇒ σ(i) ∈ T , i ∈ S ∩ T ⇒ σ(i) ∈ S ∩ T , and i ∈ S ∪ T → σ(i) ∈ S ∪ T . Therefore, (
Finally, if (TR) holds, we have ψ S→T i = -ψ T →S . Since active players are the same in S → T and in T → S, we obtain for

i ∈ S \ T a τ (S→T ),1 v(S) + a τ (S→T ),2 v(T ) = -b τ (T →S),1 v(T ) -b τ (T →S),2 v(S)
which, together with the case i ∈ T \ S, yields the desired result by identification.

Proof of Theorem 3

The if-part is left to the reader. Since (C) is satisfied, it suffices to derive an expression for transitions.

ψ S→T i (v) = v(T ) -v(S) = i∈S\T a m,k,l,1 v(S) + a m,k,l,2 v(T ) - i∈T \S a k,m,l,2 v(S) + a k,m,l,1 v(T ) = v(S) ma m,k,l,1 -ka k,m,l,2 + v(T ) ma m,k,l,2 -ka k,m,l,1 .
Since this holds for any v, we obtain the system

ma m,k,l,1 -ka k,m,l,2 = -1 ma m,k,l,2 -ka k,m,l,1 = 1. Axiom (SEL) implies a m,k,l,1 v(S) + a m,k,l,2 v(T ) = -a k,m,l,2 v(S) -a k,m,l,1 v(T )
for any v where there are two symmetric players i, j with i ∈ S\T and j ∈ T \S.

If |S \ T | or |T \ S| > 1 we may put freely v(S) = 0 or v(T ) = 0, which implies a m,k,l,1 = -a k,m,l,2 , a m,k,l,2 = -a k,m,l,1
for any m, k, l such that m = 1, k = 1. If |S\T | = |T \S| = 1, then S = (S∩T )∪i and T = (S ∩ T ) ∪ j, which implies v(S) = v(T ). This yields a 1,1,l,1 + a 1,1,l,2 = -a 1,1,l,1a 1,1,l,2 = 0 and hence the above relation holds also for m = k = 1. Substituting into the above system yields

a m,k,l,1 = - 1 m + k = a k,m,l,1 a m,k,l,2 = 1 m + k = a k,m,l,2 .
9 Proof of Theorem 4

The if-part is left to the reader. Since (C) is satisfied, it suffices to derive an expression for transitions. Under (L), (IP) (S), (N), axiom (E) implies:

i∈N ψ S→T i (v) = v(T ) -v(S) = i∈S\T K⊆N \i a τ (S→T ),τ (S→T |K∪i) (v(K ∪ i) -v(K)) + i∈T \S K⊆N \i b τ (S→T ),τ (S→T |K∪i) (v(K ∪ i) -v(K)) = K⊆N v(K) k l a τ,k l ,kr ,kc,k0 + k r b τ,k l ,kr ,kc,k0 -(l -k l )a τ,k l +1,kr ,kc,k0 -(r -k r )b τ,k l ,kr +1,kc,k0 ,
with the following notations:

τ (S → T ) =: τ , |S \ T | =: l, |T \ S| =: r, |S ∩T | =: c, |K| = k, τ (S → T |K) = (k l , k r , k c , k 0 ), with k 0 = k-k l -k r -k c = |K \ (S ∪ T )|.
Let us drop also the subindex τ since it is present everywhere. This gives by identification: la l,0,c,0rb l,1,c,0 = -1 (10) -la 1,r,c,0 + rb 0,r,c,0 = 1 (11)

k l a k l ,kr,kc,k0 + k r b k l ,kr ,kc,k0 -(l -k l )a k l +1,kr ,kc,k0 -(r -k r )b k l ,kr +1,kc,k0 = 0, ∀K = S, T. (12)
1. Suppose that S ⊂ T holds, i.e., τ = (0, ts, s). Then l = k l = 0, r = ts, c = s, and (10), (11) yield b 0,1,s,0 = 1 t-s and b 0,r,s,0 = 1 t-s , and the remaining equations become: So it remains to examine the case where all K satisfy K ∩ (T \ S) = ∅ and K ⊇ T \ S (i.e., 0 < k r < ts). We prove by induction that b 0,kr+1,kc,k0 = 0 holds for all 0 < k r < ts and k c , k 0 , except for k c = s, k 0 = 0, i.e., for K = S ∪ L with ∅ = L ⊂ T \ S, where b 0,kr+1,s,0 = k r ! (ts) • • • (tsk r ) .

For k r = 1, we have b 0,1,kc,k0 -(r -1)b 0,2,kc,k0 = 0.

From ( 13) we get b 0,1,kc,k0 = 0 except if (k c = s, k 0 = 0), which entails b 0,2,kc,k0 = 0 for all k c , k 0 except b 0,2,s,0 = 1 (t-s)(t-s-1) , the expected result. Assume that the assumption is true up to k r and compute the case k r + 1, assuming k r + 1 < ts. We find (k r + 1)b 0,kr+1,kc,k0 -(rk r -1)b 0,kr+2,kc,k0 = 0 By the assumption, the first term vanishes for all k c , k 0 , except for k c = s and k 0 = 0. This implies the second term to vanish except when b 0,kr+2,s,0 = (k r + 1)! (ts) • • • (tsk r )(tsk r -1) .

Therefore, the expression of ψ S→T i becomes

ψ S→T i (v) = K⊇S K⊆T \i (t -s -k r -1)!k r ! (t -s)! (v(K ∪ i) -v(K)),
which is the expression of the Shapley value for a game on the set T \ S.

2. The case T ⊂ S is analyzed similarly.

3. It remains to settle the case where S \ T = ∅ and T \ S = ∅ hold. Take any i ∈ S \ T and j ∈ T \ S. We have for any

K ⊆ N \ i, j v(K ∪ i) -v(K) = v(K ∪ ij) -v(K ∪ i) whenever i, j are antisymmetric in v. The coefficient of v(K ∪ i) -v(K) in ψ S→T i (v)
v(K ∪ j) -v(K) = v(K ∪ ij) -v(K ∪ j)
we deduce a τ (S→T ),τ (S→T |K∪i,j) = -b τ (S→T ),τ (S→T |K∪j) . These relations being valid for any K ⊆ N \ i, j and any i ∈ S \ T , j ∈ T \ S, we deduce the system a k l ,kr,kc,k0 = -b k l ,kr +1,kc,k0 , 1 ≤ k l ≤ l, 0 ≤ k r ≤ r -1 a k l +1,kr,kc,k0 = -b k l ,kr ,kc,k0 , 0 ≤ k l ≤ l -1, 1 ≤ k r ≤ r, for 0 ≤ k c ≤ c, 0 ≤ k 0 ≤ n-|S ∪T |, with the above conventions. Substituting in ( 10), ( 11) we obtain a l,0,c,0 = -1 l + r , a 1,r,c,0 = -

1 l + r . ( 15
)
Substitution into (12) leads to (k l + rk r )a k l ,kr,kc,k0 -(k r + lk l )a k l +1,kr ,kc,k0 = 0 (16)

with the restriction 1 ≤ k l ≤ l -1, 1 ≤ k r ≤ r -1. For the remaining cases, we get:

-(l + k r )a 1,kr ,kc,k0 + (rk r )a 1,kr+1,kc,k0 = 0, k l = 0, 0 ≤ k r ≤ r (17) (k l + r)a k l ,0,kc,k0 -(lk l )a k l +1,0,kc,k0 = 0, 1 ≤ k l ≤ l -1, k r = 0 (18) k l a k l ,r,kc,k0 -(lk l + r)a k l +1,r,kc,k0 = 0, 1

≤ k l ≤ l -1, k r = r (19)
(l + rk r )a l,kr ,kc,k0k r a l,kr-1,kc,k0 = 0, k l = l, 0 ≤ k r ≤ r, (20) where in the above 4 equations, coefficients a l,0,c,0 and a 1,r,c,0 are excluded: this precisely concerns equation ( 17) with (k r = r, k c = c, k 0 = 0), equation ( 18) with (k l = l -1, k c = c, k 0 = 0), equation ( 19) with (k l = 1, k c = c, k 0 = 0), and equation ( 20) with (k r = 0 or 1, k c = c, k 0 = 0). We claim that all coefficients corresponding to K \(S ∪T ) = ∅ (i.e., k 0 > 0) or K ⊇ (S ∩ T ) (i.e., k c < c) vanish. Suppose then that k 0 > 0 and k c < c is given. From (20) with k r = 0, we deduce a l,0,kc,k0 = 0. Substitution in (18) with k l = l -1 yields a l-1,0,kc,k0 = 0. Successive application of (18), again with k l = l -2, . . . , 1, yields a k l ,0,kc,k0 = 0, 1 ≤ k l ≤ l.

Since a l,0,kc,k0 is also present in (20) with k r = 1, we have a l,1,kc,k0 = 0. Now, in (16), a l,1,kc,k0 is present with (k l = l -1, k r = 1), which yields a l-1,1,kc,k0 = 0. Applying again ( 16) with k l = l -2, . . . , 1 we deduce a k l ,1,kc,k0 = 0, 1 ≤ k l ≤ l. a l,1,kc,k0 is present also in (20) with k r = 2. Proceeding as above we get a k l ,2,kc,k0 = 0, 1 ≤ k l ≤ l.

This can be done until k r = r in (20), which gives a l,r,kc,k0 = 0. Then (19) has to be used with k l = l -1 and so on. This yields a k l ,r,kc,k0 = 0, 1 ≤ k l ≤ l.

In summary, a k l ,kr ,kc,k0 = 0 holds for 1 ≤ k l ≤ l, 0 ≤ k r ≤ r, 0 ≤ k c < c and 0 < k 0 ≤ n -|S ∪ T |, and our claim is proved. Therefore, for i ∈ S \ T , the value reduces to

ψ S→T i (v) = K⊆(S∪T )\i K⊇S∩T
a l,r,c,k l +1,kr,c,0 (v(K ∪ i)v(K)).

Note that a l,r,c,k l +1,kr ,c,0 can be simplified into a l,r,c,k l +1,kr . If we apply the mapping Γ S defined above, this coefficient depends solely on |S∆T | and |S∆K|, and thus reduces to a l+r,l-k l -1+kr . Therefore, we obtain

ψ ∅→S∆T i (v) = K⊆(S∆T )\i
a l+r,k+1 (v S (K ∪ i)v S (K)).

Observe that this can be seen as a value for the classical game v S on S∆T , satisfying linearity, the classical null axiom and symmetry. Moreover, through Γ S , efficiency (E) turns into classical efficiency. Therefore, it must the classical Shapley value φ S∆T i (v S ). Since we have the equality φ S→T i (v) = φ S∆T i (v S ) already observed to hold, the proof is complete as the case i ∈ T \ S proceeds similarly.

Fig. 2

 2 Fig. 2 Scenario S completed for computing the Shapley II value. Boldface figures indicate nodes of the scenario

Fig. 3

 3 Fig. 3 Set of scenarios S(U M,∞ , 3)

.

  Symmetry for entering/leaving players (SEL): If S, T ⊆ N are coalitions with S \ T = ∅ and T \ S = ∅, any pair i ∈ S \ T , j ∈ T \ S of symmetric players yields ψ S→T i = ψ S→T j Theorem 3 A scenario-value satisfies (C), (L), (TR), (IP), (IC), (E), (S) and (SEL) if and only if it is the Shapley I scenario-value.

  otherwise, where τ (S → T |K) := (|(S \ T ) ∩ K|, |(T \ S) ∩ K|, |S ∩ T ∩ K|, |K \ (S ∪ T )|), and a τ (S→T ),τ (S→T |K∪i) and b τ (S→T ),τ (S→T |K∪i) are real coefficients.

  Antisymmetry for entering/leaving players (ASEL):If i ∈ S \ T and j ∈ T \ S are antisymmetric, then ψ S→T i (v) = -ψ S→T j (v)holds for any sequence S → T .

  (i) Shapley II uses fewer axioms than Shapley I. Neither (TR) nor, more importantly, (IC) is needed. A substantial part of the proof is devoted to infer (IC) from the other axioms, which was not possible for Shapley I. So the axiomatization of Shapley II is close to the classical axiomatization of the Shapley value for TU-games: Linearity, null axiom, symmetry and efficiency. The need of two symmetry axioms is explained below. Observe also that (IP) is similar to the carrier axiom, which sometimes replaces the null axiom. Therefore, (N) and (IP) play similar but complementary rôles. (ii) The proof uses the maps Γ S (K) := K∆S and v S (K) := v(K∆S) for a given transition S → T which leads to an interesting aspect of the symmetry properties. Observing Γ S (S) = ∅ and Γ S (T ) = S∆T , the Shapley II value on S → T amounts to the classical Shapley value φ S on S∆T :

  Assuming (L), (TR), (IP), (IC) and (S), and setting m := |S\T |, k := |T \S| and l := |S ∩ T | efficiency implies:

  i∈N

k

  r b 0,kr,kc,k0 -(rk r )b 0,kr +1,kc,k0 = 0, ∀K = S, T.If K ∩ T \ S = ∅, this reduces to b 0,1,kc,k0 = 0, ∀k c , k 0 (13)except the case (k c = s, k 0 = 0), which corresponding to S. Similarly, K ⊇ T \S yields b 0,t-s,kc,k0 = 0, ∀k c , k 0 , (14) except in the case (k c = s, k 0 = 0), which corresponds to T .

  is a τ (S→T ),τ (S→T |K∪i) , while b τ (S→T ),τ (S→T |K∪ij) is the coefficient of v(K ∪ij)-v(K ∪i) in ψ S→T j (v). By (ASEL) we have ψ S→T i (v) = -ψ S→T j (v) for any such v, which implies a τ (S→T ),τ (S→T |K∪i) = -b τ (S→T ),τ (S→T |K∪ij) .Similarly, from the relation

This is salient in Aumann's description of Roth's example. Roth involves three players who must share 1. Acting alone, each player can secure 0. If players 1 and 3, or

and

3, form a coalition, then 3 gets 1p, and the other players get p, with p < 1p. If 1 and 2 form a coalition, they get 1/2 each. The grand coalition would use a random device for picking a 2-person coalition and then dividing as above. Aumann supplies the following story: "Suddenly the phone rings in 1's home; 3 is on the line with an offer [....] Then 1 realizes that if he does so, and if 3 manages to get in touch with 2 before he (1) does, then he won't get anything at all out of the game [...]". For Shafer's example and its view by Hart and Kurz, where similar sentences can be found, we give a description in Section 2.

The notion of a coalition process is not far from that of coalition formation in a very literal sense. However, most work on coalition formation (see, e.g., the survey[START_REF] Hajduková | Coalition formation games: a survey[END_REF])) deals with partitions (i.e., coalition structures) and is concerned more with stability[START_REF] Breton | Stable partitions in a model with group-dependent feasible sets[END_REF][START_REF] Xue | Coalitional stability under perfect foresight[END_REF] and the question why coalitions form (due to preferences of players etc.) rather than how they form (mathematical properties of coalition evolution).

Note that the aspects of time and structure coincide in Shapley's model, where the scenarios are exactly the maximal chains from ∅ to N in (2 N , ⊆). Our approach treats these as independent aspects.

An example of a different nature arises from a situation where voters are asked for a yes/no decision with initial set S of yes-voters. After some discussion, some players may change their mind, so that a different set T of yes-voters arises and a new discussion takes place etc. (cf. Example 3.1.3 below)

In the field of coalition formation, a related Markov approach is taken by[START_REF] Konishi | Coalition formation as a dynamic process[END_REF].

As will be detailed later, scenarios may be of infinite length, perhaps not even converging to some terminal state.

This process has been applied in(Faigle et al., forthcoming) to public regulation policies, with similar conclusions.

Acknowledgements We would like to thank Nicholas Yannelis for pointing our attention to exchange economies and for stimulating discussions on the topic.