Stéphane Durand
email: stephane.durand@inria.fr

Federica Garin
email: federica.garin@inria.fr

Bruno Gaujal
email: bruno.gaujal@inria.fr

Distributed Best Response dynamics with high playing rates in potential games

Keywords: Potential Games, Best Response Dynamics, Distributed Algorithms, Markov Chains

In this paper we design and analyze distributed best response dynamics to compute Nash equilibria in potential games. This algorithm uses local Poisson clocks for each player, and does not rely on the usual but unrealistic assumption that players take no time to compute their best response. If this time (denoted δ) is taken into account, distributed best response dynamics may suffer from overlaps: one player starts to play while another player has not changed its strategy yet. Overlaps may lead to drops of the potential but we can show that they do not jeopardize eventual convergence to a Nash equilibrium. Our main result is to use a Markovian approach to show that the average execution time of the algorithm can be bounded from above by e γ δn log n log log n (1 + o(1)) and from below by δn log n log log n (1 + o(1)), where γ is the Euler constant, n is the number of players and δ is the time taken by one player to compute its best response. These bounds are obtained by using an asymptotically optimal playing rate λ. Our analytic bounds show that this λ is high: λ = log log n-log log log n δ . This induces a large probability of overlap (p = 1 -log log n/ log n). In practice, numerical simulations also show that using high playing rates is efficient, with an optimal probability of overlap p opt ≈ 0.78 up to n = 250. This implies that best response dynamics are unexpectedly efficient to compute Nash equilibria, even in a distributed setting.

Introduction

Potential games have first been introduced in [START_REF] Rosenthal | A class of games possessing pure-strategy Nash equilibria[END_REF]. They are both rampant in applications (routing and/or congestion games are potential games in general, as it was first noticed in [START_REF] Beckman | Studies in the Economics of Transportation[END_REF]) and have been exhaustively studied per se (see [START_REF] Monderer | Potential games, Games and economic behavior[END_REF]). They play a major role in transportation science as well as in computer science [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF][START_REF] Gallager | A minimum delay routing algorithm using distributed computation[END_REF][START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF] and in distributed optimization [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF].

It is well-known that the Best Response Dynamics (BRD) converges to a pure Nash equilibrium in potential games [START_REF] Monderer | Potential games, Games and economic behavior[END_REF]. Here, we study the average execution time of the BRD and its dependence on the order of play of the players (called the revision sequence in the following), in a distributed context. When one uses BRD to compute a Nash equilibrium in potential games in practice, one is confronted with a mixed feeling.

On one hand, BRD with a round robin revision sequence has been proved optimal among all local search algorithms (converges faster than any local search in the strong stochastic sense in the set of all potential games with a uniform distribution), see [START_REF] Durand | Complexity and optimality of the best response algorithm in random potential games[END_REF].

On the other hand, BRD suffers from two main drawbacks when used in a distributed context. Firstly, the impact of the revision sequence on the performance is still unknown: If one replaces the round robin revision by another order of play, the convergence time will certainly grow, but the degradation still needs to be evaluated. This may be critical in cases where round robin among players is hard to implement, such as in distributed cases.

Secondly, convergence of BRD is only guaranteed when players play one at a time. Again, this constraint may hamper performance in a distributed context because electing a single active player at each round also requires costly synchronization between players.

In this paper we provide answers to both drawbacks at the same time. We study the case where the global order of plays results from local Poisson clocks for each player, all with the same rate, denoted λ/n. When all players play according to a local Poisson clock, then they play one at a time almost surely. This property is used in many distributed algorithms to avoid the difficult case of simultaneous actions. In practice, however, the time taken by one player to play cannot be neglected compared with the time gap between two plays. Similarly to what is called collisions in distributed communication protocols, when two players start to play "almost" simultaneously, their plays overlap:

The second player starts playing before the first one has finished, resulting in an incoherent profile of the game.

In this paper we show that although overlaps will cause drops of the potential over time, they will not jeopardize convergence to a Nash equilibrium in finite time. We also show that the convergence time can be computed as a product of a function of the overlap probability and a function of the number of players and that a high probability of overlaps is even desirable to speed up convergence.

To achieve this, we introduce two successive simplifications whose behavior can be compared (using two different coupling schemes) with the best response dynamics over a potential game with n players. These simpler models are called respectively the Intersection-Free approximation (IFA) and the Restart approximation (RST), for reasons explained later. The convergence time of the simplest system (RST) can be evaluated by modeling its behavior by a Markov chain over a hybrid state space (with a continuous and a discrete component).

The expected hitting time of a Nash equilibrium for this Markov chain satisfies a Poisson equation. This Poisson equation can be transformed into an ordinary differential equation with an implicit initial condition whose solution can be computed in integral form. The derivation of the asymptotic behavior of this solution in n (the number of players) is the main technical part of this paper. It shows that the expected execution time for the restart approximation (and hence of BRD) is bounded by E[T BRD ] ≤ e γ δn log(n)/ log log n asymptotically, where δ is the time taken by a player to compute its best response and γ is the Euler constant, when the rate of play (called λ) is chosen appropriately.

This result calls for several comments. First, this is an illustration of the power of the approach used here: using a Markov model of the behavior of a distributed algorithm, based on its invariant state, is precise enough to obtain an upper bound on the time complexity that is comparable with a trivial lower bound of the complexity. Indeed, using the coupon collector problem, it is rather straightforward to see that E[T BRD ] ≥ 1 λ nH n , where H n = n j=1 (1/j) is the nth harmonic number.

Second, this shows that BRD qualifies as an efficient algorithm in practice to compute Nash equilibria in a centralized as well as in a distributed context, even when players do not share any global information and when overlaps occur. The average complexity lower than n log n is in sharp contrast with the worst case complexity of BRD (exponential in n, even for round robin centralized games).

To test the sensitivity of the execution time to the only free parameter (i.e. the rate of the Poisson clock λ), we have run several simulations of games of various sizes. Simulations show that the distribution of computing times are rather tight around the expected value. They also show some robustness of the convergence time with respect to the playing rate λ. This suggests several future improvements of the algorithm such as letting λ vary over time to adjust automatically to the number of players when it is unknown and to speed up convergence. Simulations also show that decreasing the chances of overlaps by reducing the play intensity λ is not a good idea (up to a certain point). Finally, while the analysis of our upper bound is minimized with a overlap probability p ≈ 1 -log log n/ log n (this is surprisingly high), the numerical experiments show that the best overlap probability is around p = 0.78, for any number of players, up to 250.

Random Potential Games

Potential Games and Best Response

A game G def = G(N , A, u) will be a triplet consisting of:

• A finite set of players N = {1, . . . , n};

• A finite set A of actions (or pure strategies) ; The set of actions profiles or states of the game is A n ;

• The players' payoff functions u k :

A n → R, for each k ∈ N .
The number of actions per player is denoted A. We also use a := A -1 the number of alternative actions per player in a given state. The best response correspondence BR k (x) is the set of actions maximizing the payoff for player k under state x:

BR k (x) def = arg max α k ∈A u k (α k ; x -k ) .
A Nash equilibrium (Nash equilibrium (NE)) is a fixed point of this correspondence, i.e., a profile x * such that x * k ∈ BR k (x * ) for every player k.

Definition 1 (Potential games).

A game is a (best response) potential game [START_REF] Voorneveld | Best-response potential games[END_REF] if there exists a function Φ : A n → R such that for any player k and action profile x

BR k (x) = arg max α k ∈A Φ(α k , x -k ) .
To avoid ties we assume that the Best Response is unique:

BR k (x) = arg max α k ∈A Φ(α k ; x -k ).
Ties being of measure zero in the set of random games, they will not affect the average behavior of the players.

We consider an algorithmic version of the Best Response Dynamics driven by a revision sequence, called Best Response Dynamics (BRD) in the following. A revision sequence is an infinite sequence of players chosen according to some 100 rule. We will mostly consider two relatively natural sequences: the round robin sequence, i.e., the cyclic sequence 1,

• • • , n, 1, • • • , n, 1, • • • ,
and an independent and uniformly distributed sequence resulting from the superposition of n independent Poisson point processes (one for each player), all with the same rate λ. Under this random revision sequence, each player is chosen according to a uniform law independently with probability 1/n at each point of the process. The latter will be useful to study the distributed version of the game.

:= R t ; t := t + 1; 4 if x k ∈ BR k (x) then 5 Update strategy for player k to x k ∈ BR k (x); 6 L := ∅; 7 L := L ∪ {k};
In this program (BRD), L is the list of players that have played since the last change of the state x, and it is reset to an empty list every time one player changes its action. As soon as this list reaches size n, the state x verifies the definition of a Nash equilibrium.

The worst case complexity of finding a Nash equilibrium in potential games is PLS complete [START_REF] Fabrikant | The complexity of pure Nash equilibria[END_REF], known to be between P and N P . In the following we focus on the expected execution time of BRD over a random potential game when the potential is chosen uniformly.

Randomization

In the following we will randomize over the potential games over which BRD is used. Since the behavior of BRD only depends on the potential function, we randomize directly over the potential Φ. On one hand, this is the classical average complexity approach when no additional information is known about the games (the same approach is used in [START_REF] Imre | Nash equilibria in random games[END_REF] for 2 player games for example). This yields IID potential for all profiles, as explained below. On the other hand, some may argue that uniformly distributed random games are not generic in some sense and a good performance of BRD on average does not necessarily translate in good performances for "real world" games. In any case, we believe that in the absence of obvious structure in the potential games, uniform distribution over all potentials is a valid randomization.

There are several equivalent ways to do this randomization. The first one is based on the fact that the behavior of the algorithm does not depend on the actual values of the potential of the states but only on the comparisons between them. Therefore, the natural randomization is to consider all possible orderings of the state space A n and pick one uniformly. The number of total orders on A n is the number of permutations on A n , namely (A n )!.

The second (equivalent but much more practical) randomization is the following: The potentials of all states x are chosen independent, identically distributed according to an arbitrary distribution F admitting a density w.r.t. the Lebesgue measure.

Both randomizations are equivalent. Indeed, take any k states x 1 , . . . , x k in A. In both cases, P(Φ(x

1 ) > Φ(x 2 ) > • • • > Φ(x k )) = 1/k!. Now, since
F is increasing over the support of its density, F -1 is well-defined and we get P(Φ(x) > Φ(x )) = P(F -1 (Φ(x)) > F -1 (Φ(x ))). Note that F -1 (Φ(x)) is uniformly distributed on [0, 1]. Therefore, with no loss of generality, one can assume that the potential of all the states are i.i.d., uniformly distributed on [0, 1]. This randomization is used in the following.

Remark Randomizing over the payoffs of all players rather than over the potential (and rejecting those that do not satisfy the potential property) would provide a different randomization. However, this randomization is more difficult to analyze; it is not any more natural than randomizing the potential (especially if players are not homogeneous) and it does not substantially change the average behavior of BRD (this was checked numerically but it is not reported here,because this is out of the scope of this paper).

The average performance of Algorithm 1 under the round robin revision sequence for random games has been analyzed in [START_REF] Durand | Complexity and optimality of the best response algorithm in random potential games[END_REF]. This paper shows that the average execution time of Algorithm 1 to compute a Nash equilibrium is linear in the number of players. Furthermore, the time to reach a Nash equilibrium on random games using BRD with a round robin revision sequence has been shown in [START_REF] Durand | Complexity and optimality of the best response algorithm in random potential games[END_REF] to be stochastically lower than with any other local search algorithm. In the distributed case, a central authority (or an election protocol among the players) is needed to enforce that the order of plays follows a round robin revision sequence. This can be either impossible or very costly. Therefore, it is interesting to investigate other playing sequences, and in particular revision sequences based on individual clocks for all players, that are more adapted to distributed games. This is precisely the focus of our paper.

Distributed Best Response

Let us now consider a distributed version of Algorithm 1 where players act according to individual Poisson clocks with rate λ/n. Apart from this change of the sequence of plays, the algorithm is the same as Algorithm 1: L is the list of players that are satisfied with the current state (they played under the current state and did not change their action). In this distributed version of BRD, one can distinguish two phases. The first phase ends when the last change in the profile occurs (the last time when L is a singleton), at this point the algorithm has reached a Nash equilibrium but does not know it yet. The second phase is the time needed for all players to play and check that their best response in the current state dos not change, thus certifying the Nash equilibrium (this is the time needed for L to grow up to its maximal size, n). We will denote by R (reaching time) the duration of the first phase, and by T (execution time) the total time taken by the two phases. We denote by δ the time taken by one player (say k) to compute its best response, BR k (x), under state x. We assume that this time does not depend on the player nor on the current state, but may depend on a = A -1 the number of alternative actions that a player needs to check before deciding its best response (for example, it could be linear in a). More precisely, if for one player, say k, the clock ticks at time t, then it takes δ amount of time for the player to read the global state x, compute its best response BR k (x), and update its state to x k = BR k (x). We use the classical CREW-PRAM model for this distributed algorithm. The global variables are x and L, accessed by all players in a concurrent read and exclusive write mode. The PRAM model implies than the duration of play δ is constant over all times and all players, even if several plays overlap.

The main difference in the behavior of the distributed version of BRD vs the centralized one, is that the state may not be same for different players when their play overlap.

To make the point clear, let us consider a small example illustrated in Figure 1. The figure shows a time line of a game with three different players (say P 1 , P 2 , P 3 ), each with two possible actions and with clocks ticking respectively at times T 1 , T 2 , T 3 , and their playing duration overlap as in Figure 1. Let us say that the initial state of the three players is (0, 0, 0). Player P 1 plays first and changes its action for a better payoff to x 1 = 1. When player P 2 starts playing, P 1 has already finished its play, so P 2 compares the payoff of (1, 0, 0) with (1, 1, 0). Let us say that its best response is x 2 = 1. Meanwhile P 3 has started 200 playing, because its play overlap with P 2 . Its current state is still (1, 0, 0), so P 3 compares the payoff of (1, 0, 1) with (1, 0, 0). Its best response is, say, x 3 = 1. This means that the state at time T 3 + δ will be (1, 1, 1) whose potential has not been compared with the potential of (1, 0, 0) (so it could be lower). As shown in the previous example, overlaps can be seen as simultaneous plays and therefore the potential may decrease in this case. However convergence to a Nash equilibrium still holds with probability one: Using the Borel Cantelli Lemma, a sequence of round robin plays of arbitrary length and with no overlap will eventually occur, ensuring convergence. Of course it may take a very long time before such an event occurs.

x 3 = 1 δ T 1 T 2 T 3 x 1 = 1 x 2 = 1
Figure 2 shows the evolution of the potential during the execution of Algorithm 2 over one potential game with 50 players. As one can see, potential does not always increase, unlike what happens in the classical centralized case of Algorithm 1. However, convergence occurs eventually (after 60 steps in that case).

Main result

The rest of the paper is devoted to the proof that convergence occurs on average almost as fast with overlaps as when they do not happen (up to a multiplicative constant), as stated in the following theorem.

h(p, n) f (p, n) ≤ C.
The same convention applies to the notation o(f (p, n)), with a constant C = 0.

Theorem 1. The expected execution time of the distributed best response dynamics with Poisson clocks of total rate λ as given in Algorithm 2 satisfies

nH n λ ≤ E[T BRD ] ≤ 1 λ   n 1-p H n-1 + n 1-p + C 1 + C2 n + C 2 G(p,n) n(1-p) 1 -p + 1   G(p, n), (1)
where

G(p, n) = e pH n-1 p -1-p p
, H n is the nth harmonic number, p = 1 -e -δλ is the overlap probability, and C 1 and C 2 are constants.

The following bound can be given for

G(p, n): ∀p ∈ [0, 1], ∀n ≥ 2, G(p, n) ≤ (e(n-1)) p p -1-p p ≤ e(n -1)
. Indeed, the first inequality follows from H n ≤ log(n) + 1, while the second is easily obtained by studying the function f (x) :=

x p p -1-p p -x, noting that f (1) = 0 and f is non-increasing for all x ≥ 1 (since its derivative is f (x) = x -(1-p) -1), so that f (x) ≤ 0 for all x ≥ 1. This bound on G(p, n) yields a first simple bound for E[T BRD ], which is uniform in p: E[T BRD ] ≤ e λ n 2 log(n) + n 2 (1 -p) 2 (1 + o(1)).
More refined bounds can be obtained, as follows. Let us denote by B(n, p) the upper bound given in Theorem 1 (up to the factor 1/λ), namely

B(n, p) :=   n 1-p H n-1 + n 1-p + C 1 + C2 n + C 2 G(p,n) n(1-p) 1 -p + 1   G(p, n).
Its asymptotic behaviour, in different regimes, is the following:

• When p goes to 0, B(n, p) goes to e γ nH 2 n-1 + O(nH n-1 )
. This is a bound on the number of steps before convergence in the ideal case when δ = 0. Actually, a tighter bound can be computed in this case: When p = 0, a direct proof (not reported here) shows that

E[S BRD ] ≤ e γ nH n-1 + O(n).
• When p goes to 1, B(n, p) goes to infinity, as expected: when all plays overlap, convergence in finite time cannot be guaranteed.

• When p ∈ (0, 1) is fixed and n goes to infinity, we have

B(n, p) = e γ p n log(n) + n 1 -p (1 + o(1)).
This is obtained recalling that log(n -

1) + γ + 1 2n ≤ H n-1 ≤ log(n -1) + γ + 1 2(n-1)
, and hence e pHn-1 ≤ (n -1) p e pγ+ p 2(n-1) .

Finally, letting p depend on n yields the following result.

Corollary 1. Under a playing rate that minimizes the upper bound asymptotically, namely λ = log(log(n))-log log log(n)) δ , p = 1 -log(log(n)) log(n) , the average execution time satisfies

δn log(n) log(log(n)) (1 + o(1)) ≤ E[T BRD ] ≤ e γ δn log(n) log(log(n)) (1 + o(1)) ( 2
)
where γ is the Euler constant.

Markovian Approximation and Proof of Theorem 1

This section is devoted to the construction of a Markov model of BRD that leads to the proof of these bounds.

Intersection-Free Approximation (IFA)

The direct analysis of the behavior of BRD over a random potential is difficult because, over time, more and more states have been visited by the algorithm. Thus, its behavior is non-homogeneous in time. To avoid this difficulty, we consider a new model, called the Intersection Free Approximation (IFA) in the following. Under the Intersection Free Approximation, every time a new player (say k) who is not satisfied (in other words, a player not in L) has to compute its best response in a state (say x), it compares Φ(x) with the potential of its a other strategies, as for the original BRD. However in IFA, differently from BRD, all the corresponding potentials will be randomly generated, whether or not those a states have been visited during the previous steps of the algorithm.

The IFA is given in Algorithm 3. The difference with Algorithm 2 is that every time a player plays, it generates the potential of its a alternative actions before computing its best response.

6 if k ∈ L IF A then 7 forall u = x k , Generate Φ(u, x -k ) ∼ Unif[0, 1]; 8 if x k = BR k (x) then 9 L IF A := L IF A ∪ {k} 10 else 11 x k := BR k (x); L IF A := {k}
To illustrate the difference between BRD and IFA, let us consider a simple two-player game with four actions per player, with a random potential. Such a potential is given in Figures 3 and4. They respectively show the behavior of BRD and IFA under the revision sequence 1,2,1,2.

Under BRD, the potential of all states can be generated at the beginning, and the game is played under this fixed value of the potential (here uniform in {0, 1, . . . , 10}).

Under IFA, potentials are generated each time a new player acts. The first difference between the two systems occurs during the second play of player 2: one of the states that it can opt for has already been visited in the past in BRD. The potential of that state is known to be smaller than the current potential. Under IFA, the potential of this state is redrawn a second time, independently of the rest and can lead to a higher potential, as in Figure 4. Let V be the number of visited states whose utility (or potential in the case of IFA) has been evaluated during the execution. (i) The number V BRD of states visited by BRD is smaller than the number V IF A of states visited by the IFA approximation, for the stochastic order.

(ii) The expected number of steps to reach convergence for best response (ES BRD ) and IFA (ES IF A ) verify:

ES BRD ≤ ES IF A + C 1 1 -p G(p, n) + C 2 G(p, n) n(1 -p) + C 2 G(p, n) 2 n(1 -p) 2 ,
where C 1 and C 2 are constants.

The proof is postponed to the Appendix.

Restart Approximation (RST)

Let us now consider the behavior of the IFA Algorithm. It should be clear that its future behavior only depends on the current potential Φ IF A (t) and the current set L IF A (t), as long as there are no overlaps. When an overlap takes place, as seen in Figure 1, the current player will not consider the state computed by the previous player but the state obtained by the latest player with whom it is not overlapping. This makes the behavior of

X IF A (t) def = (Φ IF A (t), L IF A (t))
cumbersome to analyze because it is not Markovian in the potential.

We construct yet another approximation, of the behavior of IF A this time, whose state transition X RST (t

) def = (Φ RST (t), L RST (t)) is different from X IF A (t) = (Φ IF A (t), L IF A (t)
) only when overlaps occur. This approximation will be called a restart version of IFA (denoted RST in the following). At any Poisson point (called t), if the current play overlaps with the previous one, who has been active (i.e. has changed its action), then, under the restart approximation, the state is reset to a uniform potential in [0, 1], disregarding the previously obtained potential and the set L is reset to a single player (the latest one).

More precisely, if X RST (t -) = (Φ, L) and the next player k overlaps the previous play, then, X RST (t) = (U, {k }), where U ∼ Unif[0, 1]. In all other cases, restart behaves exactly as IFA. Note that by definition, |L RST (t)| = 1 if |L IF A (t)| = 1 for all t. Only the current potential differs when both sets are singletons.

The goal of the next Lemma is to compare the behavior of the two systems, and more precisely Φ IF A (t) and Φ RST (t).

Lemma 2. For all t, Φ IF A (t) ≥ st Φ RST (t).
Proof. We compare IFA and RST by coupling the instants of plays of all players (denoted (t k ) k∈N ), the order of play as well as the overlaps in both systems. One can refer to Figure 1 that displays the time line with one overlap.

To avoid cumbersome notations, we will keep the same notations for the original systems and the coupled systems. The proof holds by induction on t k the set of satisfied players is a singleton, as in Figure 1. Up to time t 2 , both systems coincide under the previous coupling. We have Φ IF A (t 1 ) = Φ RST (t 1 ). To deal with the general case directly, let us only use instead the weaker property Φ IF A (t 1 ) ≥ Φ RST (t 1 ), that will propagate by induction.

Under restart, the value of the potential U after any play in overlap (here, at time t 3 +δ) is uniformly distributed in [0, 1]. In IFA, the player acting at time t 2 has changed its action. Therefore the potential Φ IF A (t 2 ) must be higher than the potential Φ IF A (t 1 ). By definition of IFA, this potential is the maximum of a uniformly distributed variables in the interval [0, 1], conditioned by the fact that it is larger than Φ IF A (t 1 ). This implies that Φ

IF A (t 2 ) ≥ st U , U being uniform in [0, 1].
Now let us consider the player acting at time t 3 . It uses the state of the system at time t 2 to compute its best response. If the potential of its best response is not larger than Φ IF A (t 2 ), which happens with positive probability, then this player does not change its action and the state at time t 3 + δ remains the state computed by the previous player: the potential is

Φ IF A (t 3 ) = Φ IF A (t 2 ) ≥ st U .
On the other hand, if the potential of its best response is larger than Φ IF A (t 2 ), then it changes its action and the system reaches a new state where two players act simultaneously, whose potential under IFA Φ IF A (t 0 ), is uniformly distributed in [0, 1]. In total by considering both cases, Φ IF A (t 0 ) ≥ st U . Now, if several overlaps occur in succession, the same type of reasoning concludes that with a positive probability (smaller and smaller as the number of overlaps increases) the potential remains the same as the potential of the first player, which is stochastically larger than a uniform one, and in the complementary case, the potential is newly generated with a uniform distribution.

In all cases, the potential remains stochastically larger than a uniform one, hence larger than the potential under RST. QED.

Corollary 2. The time to reach a full set L is stochastically smaller under IFA than under the restart approximation.

Proof. This result is a direct consequence of the previous lemma. Indeed, the order of play is the same for both systems as well as the occurrence of overlaps and since, at any time, the potentials are comparable, then if L IF A is full at time t, L RST must also be full at the same instant. Therefore, the first times of being full (implying termination in both systems) compare stochastically. QED The construction of the restart approximation ensures that the future behavior of the system under RST only depends on its current state, namely the current potential and the list of satisfied players. It should also be clear that all states with the same number of satisfied players can be aggregated and the behavior remains Markovian, because the next player to play is IID, uniformly distributed among all players and does not depend on the previous plays. Therefore, in the following we focus on the evolution of the couple (Φ(t), |L(t)|) (potential, number of satisfied players).

Complexity of Restart

The sections above show that the average time for the original distributed best response algorithm with Poisson clocks to compute a Nash equilibrium is bounded from above by the time taken under the restart approximation.

The rest of this section is devoted to the computation of the average duration of RST.

Since all players play according to independent Poisson processes with rates λ/n, the global point process of active players (T i ) i∈N , forms a Poisson process with rate λ. In the following we focus on the behavior of the system at those points ( called "instants" in the following).

It should be clear by now that (Φ(T i ), |L(T i )|) is a discrete time Markov chain with a hybrid state space (a discrete component and a continuous one: the state space is 2 N × [0, 1]).

The average hitting time of the set of states {|L| = n)} starting from a state with potential y and k satisfied players (including the current one) is given by a system of Poisson equations derived from a one-step analysis:

Let us denote by s(y, k) the expected instant when a full set of satisfied players is reached (this corresponds to the termination of RST), starting with potential y and k satisfied players. One-step analysis yields the following equations, where p = 1 -e -λδ is the probability that the current play overlaps the previous one (since the playing times of all players form a Poisson process with rate λ). s(y, n) = 0 s(y, i) = 1 + i n s(y, i) + n -i n y a s(y, i + 1)

+ n -i n 1 y au a-1 s(u, 1)du, n > i > 1 s(y, 1) = 1 + n -1 n y a (1 -p)s(y, 2) + n -1 n (1 -p) 1 y au a-1 s(u, 1)du + n -1 n p 1 0 s(u, 1)du + 1 n s(y, 1)
These equations are derived using the behavior of restart. Starting in point (y, i), i > 1, the previous player did not modify its action so overlapping the current action with the previous one will not make any difference. This is why the equation for s(y, i), i > 1 does not depend on overlaps and hence does not involve p. Now, upon a play of a new player (this happens with probability n-i n ), the current profile will not change if this player does not find an action whose potential is above the current potential, namely y. This happens with probability n-i n y a . If the new player finds an action with potential u > y, then the current player becomes the only satisfied player and the potential goes to u. Therefore, the Markov chain jumps to (u, 1). This happens with probability n-i n au a-1 du.

When the starting point is (y, 1), the situation is slightly more complex because overlaps do play a role.

Let us first consider the case with no overlap. This happens with probability 1 -p. In this case, the behavior is similar to the case (y, i), i > 1. Now, when an overlap occurs, the potential is always reset to a uniform potential in [0, 1]. This is precisely the effect of the restart approximation, and it happens with probability n-1 n p. Defining z := y a , s (1) (z, i) := s(z 1 a , i), one gets

s (1) (z, n) = 0; s (1) (z, i) = n n -i + 1 z
s (1) (u, 1) du + zs (1) (z, i + 1);

s (1) (z, 1) = n n -1 + p 1 0 s(u, 1) du +(1 -p) 1 z s (1) (u, 1)du + (1 -p)z s (1) (z, 2).
Rewriting the last equation as

s (1) (z, 1) = p n n -1 + p 1 0 s(u, 1) du + (1 -p) n n -1 + 1 z s (1) (u, 1)du + z s (1) (z, 2)
and telescoping all other equations into it, we obtain the following equation only involving s (1) (z, 1).

s (1) (z, 1) = pn n -1 + +p 1 0 s(u, 1) du + (1 -p) n-2 j=0 n n -j -1 z j + (1 -p) n-2 j=0 z j 1 z s (1) (u, 1) du. ( 3
)
We define S(z) := 1 z s (1) (u, 1)du. Notice that S(0) is the quantity we want to study. Also notice that S (z) = -s (1) (z, 1), so that (3) gives an ordinary differential equation for S(z):

S (z) + (1 -p) [G(z)S(z) + V (z)] + pC 0 + D = 0, where G(z) := n-2 i=0 z i = 1 -z n-1 1 -z , V (z) := n-2 j=0 nz j n -j -1 , C 0 := 1 0 s(u, 1), D := p n n -1 ,
We solve this equation on the interval [0, 1] using the boundary condition S(1) = 0. We obtain:

S(z) = -e -q(z) z 1 ((1 -p)V (u) + pC 0 + D) e q(u) du.
where q(z) := (1 -p)

z 0 G(u) du = (1 -p)
n-1 j=1 z j j . Since q(0) = 0, this gives

S(0) = (1 -p) 1 0 V (u)e q(u) du + (pC 0 + D) 1 0 e q(u) du. ( 4
)
Notice that, for z ∈ [0, 1], z 1 a ≥ z, and hence s(z, 1) ≤ s (1) (z, 1), so that C 0 = 1 0 s(z, 1)du ≤ 1 0 s (1) (z, 1)du = S(0). Replacing this bound in (4), we obtain

(1 -pQ 0 ) S(0) ≤ (1 -p) 1 0 V (u)e q(u) du + n n -1 pQ 0 , (5)
with Q 0 := 1 0 e q(u) du. To study Q 0 , we separate the integral in two terms. The first term is

1-b 0 e q(u) du ≤ 1-b 0 e (1-p) ∞ j=1 u j j du = 1-b 0 (1 -u) p-1 du = 1 -b p p .
The second term is

1 1-b e q(u) du ≤ 1 1-b e (1-p) n-1 j=1 1 j du = be (1-p)Hn-1 .
Hence we have

Q 0 ≤ 1 p - b p p + be (1-p)Hn-1 .
This bound is true for all b ∈ (0, 1). By using the best value for b, namely b = e -Hn-1 , we get

Q 0 ≤ 1 p - 1 -p p e -pHn-1 (6)
and hence 1

-p Q 0 ≥ (1 -p)e -pHn-1 .
In particular, this shows that 1 -pQ 0 ≥ 0 and pQ 0 ≤ 1, and hence from ( 5) we obtain

S(0) ≤ (1 -p) 1 0 V (u)e q(u) du + n n-1 pQ 0 1 -pQ 0 ≤ (1 -p) 1 0 V (u)e q(u) du + n n-1 1 -p e pHn-1 . ( 7
)
To study the numerator of ( 7), we define Q j := 1 0 u j e q(u) du. To bound Q j let us first show that Q j ≤ j j+p Q j-1 . First consider jQ j-1 = 1 0 ju j-1 e q(u) du. Integrating by parts, we have

jQ j-1 = u j e q(u) 1 0 - 1 0 q (u)u j e q(u) du = e (1-p)Hn-1 -(1 -p) n-2 i=0 1 0
u j+i e q(u) du.

Then consider (j + p)Q j = (j + 1)Q j -(1 -p)Q j . For the term (j + 1)Q j we do the same integration by parts as above, and hence we obtain

(j + p)Q j = (j + 1)Q j -(1 -p)Q j = u j+1 e q(u) 1 0 - 1 0 u j+1 e q(u) du -(1 -p) 1 0 u j e q(u) du = e (1-p)Hn-1 -(1 -p) n-2 i=0 1 0 u j+i+1 e q(u) du -(1 -p) 1 0 u j e q(u) du = e (1-p)Hn-1 -(1 -p) n-1 i=0 1 0 u j+i e q(u) du = jQ j-1 -(1 -p) 1 0
u j+(n-1) e q(u) du

We have obtained (j + p)Q j ≤ jQ j-1 , which gives

Q j ≤ j j + p Q j-1 ≤ j =1 + p Q 0 . (8)
We introduce the following technical lemma that is useful to get an explicit bound for Q j .

Lemma 3. For all 0 ≤ p ≤ 1, j =1 +p ≤ (j + 1) -p .
Proof. Let us define the function

F : p → j =1 log + p -p log(j + 1).
Proving the lemma is equivalent to proving that

F (p) ≥ 0 for all p ∈ [0, 1]. The second derivative of F is F (p) = j =1 -1
( +p) 2 , non-positive in [0, 1] implying that F is concave on [0, 1] and hence its minimum is either in 0 or in 1. F (0) = 0 and F (1) = j =1 log +1 -log(j + 1) = -log 1 + log(j + 1) -log(j + 1) = 0, so F is non-negative on [0, 1]. QED Using Lemma (3), and Q j ≤ j =1 +p Q 0 , we obtain

Q j ≤ (j + 1) -p Q 0
We are now ready to find a bound for the numerator in [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF].

(1 -p) n-2 j=0 nQ j n -j -1 ≤ (1 -p)Q 0 n-2 j=0 n n -j -1 1 (j + 1) p = (1 -p)Q 0 n-1 j=1 (n -j) + j n -j 1 j p = (1 -p)Q 0   n-1 j=1 j -p + n-1 j=1 j 1-p 1 n -j   Finally, we notice that n-1 j=1 j -p ≤ n 0 x -p dx = n 1-p 1 -p and n-1 j=1 j 1-p 1 n -j ≤ (n -1) 1-p n-1 j=1 1 n -j = (n -1) 1-p H n-1 .
Putting everything together we get 400

S(0) ≤ n 1-p H n-1 + n 1-p 1 -p + n n -1 e pHn-1 p - 1 -p p ≤ n 1-p H n-1 + n 1-p 1 -p + n n -1 G(p, n), (9)
where G(p, n) = e pH n-1 p -1-p p .

Proof of Theorem 1

Equation ( 9) gives an upper bound for the average number of steps of a Nash equilibrium for the Restart approximation. Using Lemmas 1 and 2, we get an upper bound on the average number of steps taken by BRD to compute a Nash equilibrium.

Let S BRD (resp. S IF A , S RST ) be the number of steps in BRD (resp. IFA, RST) before termination.

E[S BRD ] ≤ E[S IF A ] + C 1 G(p, n) 1 -p + C 2 G(p, n) n(1 -p) + C 2 G(p, n) 2 n(1 -p) 2 ≤ E[S RST ] + C 1 G(p, n) 1 -p + C 2 G(p, n) n(1 -p) + C 2 G(p, n) 2 n(1 -p) 2 ≤   n 1-p H n-1 + n 1-p + C 1 + C2 n + C 2 G(p,n) n(1-p) 1 -p + 1   G(p, n).
The expected time before getting to a Nash equilibrium is given by the formula

E[T BRD ] = 1 λ E[S BRD ],
that follows from Wald's lemma.

Rate Optimization: Proof of Corollary 1

One can choose the playing rate λ (or the overlap probability p) to minimize the expected time needed to obtain a Nash equilibrium. The overlap probability is p = 1 -exp(-λδ), so that λδ = -ln(1 -p).

Since we only know a bound on E[T BRD ], we can instead compute the overlap probability p * (n) that minimizes that bound.

The optimal value can be estimated by differentiating and numerically solving

∂ -1 ln(1-p) B(n,p) ∂p
= 0. This was done using Maple. The behavior of p * (n) as n grows, is displayed in Figure 5. It shows that p * (n) is non-decreasing with n and grows from p * (3) ≈ 0.65 to p * (250) ≈ 0.78. Analyzing the main term in the bound B(n, p), it is direct to show that p * (n) goes to 1 as n goes to infinity.

Since p * (n) does not have a closed form, one can instead minimize the asymptotic behavior of B(n, p). When p is close to 1 and n is large, the dominating terms are n 2p-1 /(1-p) 2 and n/(1-p) on one side and n log n on the other. This suggests choosing p = 1 -log log(n)/ log(n), with a corresponding playing rate satisfying δ λ = log(log(n)) -log log log n. The average execution time under p is now such that

E[T BRD ] ≤ e γ δ n log(n) log(log(n)) (1 + o(n)) (10)
where e γ ≈ 1.78. Finally, it should be clear that in BRD each player needs to play at least once to check if a state is a Nash equilibrium. The coupon collector theorem says that on average nH n plays are necessary before all players have played once. Under rate λ, each play takes 1/ λ units of time on average. This implies that

E[T BRD ] ≥ δ n log(n) log(log(n)) (1 + o(n)).
This ends the proof of Theorem 1 and of its corollary.

BRD with Termination Test

We will now introduce a distributed algorithm using a convergence test that does not rely on the global variable L as before. A similar algorithm was presented in [START_REF] Durand | Distributed best response algorithms for random potential games[END_REF] in the case where players do not take any time to play their best response (this can be seen as the special case of our model with δ = 0 and p = 0). In this algorithm, each player can still access the payoff of its actions but cannot know who is currently satisfied nor the global state of the system. To make termination possible, we let each player, when activated, also initiate a game-wide communication to make a termination test. Let us consider the communication procedures named Termination Test Sender and Termination Test Receiver in Algorithm 4: At every tick of its clock, each player has a probability q of broadcasting a message to every other player. Upon reception of such a message, the receivers interrupt their clock and send an acknowledgment (ack). Once the initial sender gets all the acks, it sends a second message. Upon reception of this second message, each player tests if it needs to change its best response (a player is stable if no change is needed) and sends back its stable/unstable status before restarting its clock. The initial sender receives n confirmations of stability only if the current state is a Nash equilibrium. This global communication operation interrupts the Poisson clock of most players during two broadcasts and the clock of one (random) player for four broadcasts. We denote the average interruption time by σ n . Theorem 2. When using the best value for q, the execution time of Algorithm 4, is Proof.

E[T (4) ] ≤ E[T BRD ] + 2 E[T BRD ]σ n + σ n .
To study the execution time of Algorithm 4, one can separate the complexity of reaching the equilibrium with the complexity of the termination test. The second part is therefore independent of the overlaps and can be inspired from the approach used in the simpler case were overlaps are neglected, as in [START_REF] Durand | Distributed best response algorithms for random potential games[END_REF]. This execution time, denoted T (4) , satisfies

T (4) = W 1 + • • • + W k + kσ n ,
where W i 's are the times elapsed between two consecutive termination tests, and the random number k is the number of termination tests sent before a Nash equilibrium is reached. By construction of the algorithm, the random variables W i 's are independent and identically distributed, according to an exponential law of parameter p λ n . Since W i is independent of the event {k > i}, the expectation of T (4) can be computed with Wald's lemma:

E[T (4) ] = E[k]E[W 1 ] + E[k]σ n . (11)
On the other hand, this time is also the end of the first test after the reaching time of a Nash equilibrium, denoted R (4) . The waiting time W from R (4) has the same exponential distribution as W i 's. Hence we also have T (4) = R (4) +W +σ n .

Since the distributed algorithm uses Poisson clocks, the order of play is exactly as in Algorithm 2. Therefore, E[R (4) ]

≤ (k -1)σ n + E[T BRD ]. This yields E[T (4) ] = E[T BRD ] + E[W ] + E[k]σ n . (12)
By subtracting ( 12) from [START_REF] Imre | Nash equilibria in random games[END_REF], and using

E[W ] = E[W 1 ] = 1 qλ , one gets E[k] = qλE[T BRD ] + 1.
Equation ( 12) becomes E[T (4) ] ≤ E[T BRD ] +

1 qλ + qλE[T BRD ]σ n + σ n .
The best value for q that minimizes the formula above is

q * = 1 λ √ E[T BRD ]σn . Finally, E[T (4) ] ≤ E[T BRD ] + 2 E[T BRD ]σ n + σ n .

QED

In particular, if one uses a classical model for global synchronization on a distributed algorithm (as in [START_REF] Cormen | Introduction to Algorithms[END_REF]), the duration of our two-steps broadcast is of the form σ n = O(log(n)). In this case, the execution time remains asymptotically bounded by the same value as for distributed BRD, namely E[T (4) ] ≤ δCn log(n)(1 + o(1)).

Sensitivity to the Playing Rate

In this part we simulate the behavior of the distributed versions of BRD presented in Algorithms 2 and 4 over a large number of potential games whose potentials are generated uniformly over all possible potential. These simulations are carried to assess tightness of our bound and to study the sensitivity of BRD to the value of its unique parameter, namely λ.

The dependence on λ of the upper bound of the complexity of BRD given in Theorem 1 is explicit. However, the dependence on λ of the actual execution time remains unknown. We have run several experiments to evaluate the best value of λ numerically.

Figure 6 displays simulations of the distributed version of BRD as described in Algorithm 2 with 100 players, with 10 actions each (additional simulations show that the number of actions has no effect on the performance of BRD). For each value of λ, 1000 potential games were generated and the empirical mean reaching time of an equilibrium, R BRD , have been computed, with 95% confidence intervals. The reaching time is hard to compute analytically because it is not a stopping time (it is the last time when that the state changes in BRD). However, it is a more interesting performance to measure than the total execution time T BRD because the last phase (checking that the current state is an equilibrium) is completely equivalent to a coupon collector. First, one can see that the mean reaching time is a relevant performance measure here: The confidence intervals are small. Furthermore, our numerous numerical simulations (not all reported here) never showed extreme outliers, where the execution time behaves as an exponential of the number of players (as suggested by the worst case analysis).

The main interest in Figure 6 is to compute the optimal value for λ. The formula in Section 4.5 says that 1/δ λ = 1.58. On the other hand, the simulation measurements give 1/δλ opt ≈ 0.63. The corresponding values for the overlap probabilities are p ≈ 0.53 for the analytic bound and p opt = 0.78 from measurements. Both values are much larger than what our intuition would have predicted: overlaps are supposed to be bad for convergence. Actually this is not the case: the best situation is when more than two plays out of three are in overlap. The gap with the theoretical bound can be explained: In the restart approximation, each overlap resets the potential to a uniform value in [0, 1]. which basically makes the games start all over again. In the actual behavior of BRD, some overlaps are harmless: even if an overlapping player uses an outdated value for the potential, this potential can still be larger than the potential of all its alternative actions. In this case the player becomes satisfied in spite of the overlap as if it were not overlapping with the previous play.

Figure 6 also shows (in log-log scale) a comparison with the bound given in 500 Theorem 1. One can notice that the gap seems to remain constant in the log scale, suggesting a constant factor in λ between the two curves. The asymptotic slope is one in the log-log plot. This implies that the reaching time becomes linear in 1/λ. This should not be surprising because as λ decreases, the probability of overlap also decreases so that the reaching time of the game becomes linear in the expected inter-playing time (1/λ). Finally, we have checked the dependence of the best rate λ opt on n the number of players. The bound provided in Theorem 1 suggests the λ opt should not depend on n. We have run simulations, all similar to those displayed in Figure 6, with several values of n [START_REF] Fabrikant | The complexity of pure Nash equilibria[END_REF]30,50,70,100,130,160,200,250). In each case, the optimal value λ opt (n) was evaluated numerically (the code and all simulation data are available upon request).

In a nutshell, our experiments show that λ opt does not depend on n: For any n, 1/δλ opt ≈ 0.63 implying p opt ≈ 0.77. However it was very hard to get a good precision on λ opt . Even if these experiments took several days of computations over a modern desktop computer, with 1000 runs for each couple (n, λ), our accuracy on the optimal value of λ opt (n) is between 5% and 10%, depending on the value of n.

On the other hand, the best empirical mean reaching time R opt was easier to evaluate numerically in these simulations and it is reported in Figure 7. A least square regression suggests that R opt = C 5 n p for some constant C 5 , and p coincides almost perfectly with p opt , the probability of overlap under the optimal rate λ opt . Under this numerical model, the total execution time is E[T opt ] = C 5 δn p + 1 λ nH n .

Conclusion

This paper presents an analytic study of the complexity of Best Response Dynamics to compute Nash equilibria of potential games in a distributed setting. On a methodological point of view, it shows the accuracy and the power of the Markovian approach to analyze algorithms: even if our analysis goes through several upper bounds at the model level (IFA and RST) as well as in the calculations, it only introduces a constant factor in the complexity. Simulations suggest that the actual complexity with the best playing rate λ opt is 1/λ opt (nH n + C 5 n p ), where p is the probability of overlap under the optimal rate λ opt . This result also suggests that in spite of its simplicity and greediness, BRD is very efficient to compute Nash equilibria in potential games in a distributed context where no synchronization of the players is possible. Two factors could hamper the performance of BRD in such a setting: random order of plays and overlaps. We show that a random order of plays only introduces a log(n) factor (due to a coupon collector effect) while overlaps introduce a factor 1/(1 -p) (that can be controlled by tuning the rate λ). We claim that BRD should be considered as a serious option to solve distributed games when no additional structure except that of having a potential is available on the game.

response. There are at most A -2 other states that will be visited by the current player. The state obtained after this player has finished computing its best response is a Nash equilibrium if all remaining unsatisfied players agree. There are at most n -1 of them. In total they will explore less that (A -1)(n -1) values in the sequence U . We already know that all these states have a potential below Φ(U (t)). This implies that the state with potential U (t) will also be a stopping state for BRD. This implies that V BRD ≤ V IF A .

Appendix A.2. Number of Steps

Let us consider the number of plays (or setps), denoted S. The number of potentials visited per step under IFA is exactly A-1 while BRD visits A-1-I t new potentials at each step t, where I t is the number of intersections for the current step t, i.e. the number of states visited by the current player that have already been visited in the past. So in total,

S BRD = V BRD + I A -1 ≤ V IF A + I A -1 = S IF A + I A -1 , (A.1)
where

I def = I 1 + • • • + I T BRD is the total number of intersections. Appendix A.3

. Number of Intersections

This section is devoted to studying the number of intersections. We start by decomposing it as a sum over the number M of moves (number of state changes during the execution of the algorithm):

I = M -1 i=0 I(i),
where I(i) is the number of intersections of the current state x(i) (reached after i moves) with all future states, visited at moves i + 1, i + 2, . . . , M .

Let d(x, y) be the Hamming distance between states x and y, namely the number of different coordinates.

Notice that, if the distance d(x i , x j ) is 2, then two intersections are possible with plays in states x j and state x j . When the distance is not 2, no intersection can take place.

By conditioning on the value of M = m (the conditional expectation is denoted E (m) ),

E (m) I = E (m) m-1 i=0 I(i) = m-1 i=0 E (m) I(i) ≤ m-1 i=0 2 E (m) m-1 j=i+1 1 (d(xi,xj )=2) . (A.2)
We study H(k, i) := m-1 j=i+1 1 (d(xi,xj )=2) , namely the number of times the Hamming distance is 2. The evolution of the Hamming distance depends the moves. Let us denote by k t the player that was active at the t-th move. The Hamming distance evolution over the moves depends on the current Hamming distance and on whether the k t -th coordinate of x i is equal or not to the k t -th coordinate of the current state.

We construct a discrete-time Markov chain X t with four states A, B, C, and D, where state A represents distance 1, states B represents distance 2 (with different coordinates), C represent distance 2 with equal coordinates and state D represents distance 3 or more. We choose transition probabilities such that the number of visits to states B and C will be an upper bound on H (2, i).

This chain has the following transition matrix: Explicit computation of π, (P -1π T ) and (P -1π T ) 2 shows that π B + π C = 3 a(n-3) , and that, for some positive constants c 1 ≤ 2 and c 2 , (P -1π T ) max ≤ c 1 and (P -1π T ) 2 max ≤ c 2 /n. This implies that, for all j ≥ 1, (P -1π T ) j max ≤ c 1 (4c 2 /n) (j-1)/2 if j is odd, and (P -1π T ) j max ≤ 4 that M BRD ≤ st M IF A ≤ st M RST . Finally, it is also easy to see that the case q(u) as before.

P = 1 n -1     0 n -1 0 0 1 a 1 -1 a 0 n -2
M (0) = 1 0 ((1 -p)(1 -u n-1 ) + pu)e q(u) du 1 -p 1 0 e q(u) du

≤ (1 -p)Q 0 + pQ 1 1 -pQ 0 ≤ Q 0 1 -pQ 0 .
Using the bound Q 0 ≤ 1 p -1-p p e -pHn-1 , given in [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF],

M (0) ≤ 1

Algorithm 1 :

 1 Best Response Dynamics (BRD) under revision sequence R 1 Input: Game utilities (u k (•)); Initial state (x := x(0)); revision sequence R; Initialize t := 0; List of satisfied customers L := ∅; 2 while size(L) = n do 3 Pick next player k

Algorithm 2 : 5 On each tick of the local clock 6 if k ∈ L then 7 if 8 L := L ∪ {k} 9 else 10 x

 25678910 Distributed BRD (for player k) 1 Input: Game utilities (u k (•)); Initial state (x := x(0)); 2 Initialize t := 0; List of satisfied customers L := ∅; 3 Local clock, ticking w.r.t. a Poisson process with rate λ/n; 4 while size(L) = n do x k = BR k (x) then k := BR k (x); L := {k}

Figure 1 :

 1 Figure 1: Time line of a distributed game when plays overlap

Figure 2 :

 2 Figure 2: The evolution of the potential during the execution of Algorithm 2 up to the time when a Nash equilibrium is reached: Overlaps induce potential drops

Algorithm 3 :

 3 IFA Algorithm (for player k) 1 Input: Initial state (x := x(0)); 2 Local clock, ticking w.r.t. a Poisson process with rate λ/n; 3 List L IF A := ∅; 4 while size(L) = n do 5 On each tick of the local clock

Figure 3 :

 3 Figure 3: Evolution of the potential during BRD, under the revision sequence 1,2,1,2. The grey states have not been visited yet. When the second player plays for the second time, one state (in red) has already been visited.

Figure 4 :

 4 Figure 4: Evolution of the potential under IFA with the sequence 1,2,1,2. When the second player plays for the second time, the potential of state in red is redrawn and can become larger then the current potential.

  the bound on execution time

Figure 5 :

 5 Figure 5: Overlap probability p * (n) minimizes the bound 1 λ B(n, p) on the expected convergence time E[T BRD ].

Algorithm 4 : 2 Input:

 42 Distributed BRD with termination test 1 Function Main algorithm (for player k) Game utilities (u k (•)); Initial state (x := x(0));

Figure 6 :

 6 Figure 6: Mean reaching time of distributed BRD with 100 players (with 95% confidence intervals), as a function of the expected time between two plays (inverse of the playing rate), in log-log scale. Comparison with the analytic asymptotic bound

Figure 7 :

 7 Figure 7: Average reaching time as a function of n (with 95% confidence intervals) and the best fit of the form f (n) = Cn p , when the rate is λopt.

  An upper bound for H(2, i) is obtained by counting the number of visits in states B and C in m -i time steps. As a further upper bound, we haveE (m) H(2, i) ≤ E B (# visits to B before S B ) + E C (# visits to C before S C ), (A.3) where E x (•) denotes the conditional probability E(• |X 0 = x) and S x is a stopping time defined by S x := min{t ≥ m -i s.t. X t = x}. Notice that X t is an irreducible Markov chain, and S x is a stopping time such that E x (S x ) < ∞ and X Sx = x. Hence, by Prop. 3 in [15, Chapter 2],E x (# visits to x before S x ) ≤ π x E x (S x ), (A.4)where π is the stationary distribution of the Markov chain. Then notice thatE x (S x ) = m -i + y [P m-i ] xy E y (T x ), (A.5)where T x is the first hitting time of state x. By Lemma 12 in [15, Chapter 2],π x E y (T x ) = Z xx -Z yx ,where Z := ∞ j=0 (P j -1π T ) is the fundamental matrix of the Markov chain (here 1 denotes a column vector with four ones). Hence, we obtainπ x y [P m-i ] xy E y (T x ) = x [P m-i ] xy (Z xx -Z yx ) = [(I -P m-i )Z] xx . (A.6)Using the definition of Z and the fact that lim j→∞ P j = 1π T (since the Markov chain is irreducible and aperiodic), we obtain(I -P m-i )Z = ∞ j=0 (P j -P j+m-i ) = m-i-1 j=0 (P j -1π T ) = I -1π T + m-i-1 j=1 (P -1π T ) jand hence[(I -P m-i )Z] xx = 1 -π x + m-i-1 j=1 [P -1π T ) j ] xx ≤ -π x + ∞ j=0 (P -1π T ) j max ,(A.7) where • max denotes the maximum modulus of all entries in a matrix. Using equations (A.4)-(A.7) with x = B and x = C, from the bound (A.3) we obtain E (m) H(2, i) ≤ (π B + π C )(m -i -1) + 2 ∞ j=0 (P -1π T ) j max . (A.8)

j 2 - 1 1 - 2 n n -4c 2 .

 21122 (c 2 /n) j/2 if j is even. Hence, 4c 2 /n ,where the last equality is true for n > 4c 2 . Plugging these bounds into (A.8), we obtainE (m) H(2, i) ≤ 3 a(n -3) (m -i -1) + 2 + 2c 1 + 1 Recalling that (A.2) gives E (m) I ≤ 2 m-1 i=0 E (m) H(2, i),we haveE (m) I ≤ 6 a(n -3) m-1 i=0 (m -i -1) + 4 + (4c 1 + 1) n n -4c 2 m. Using m-1 i=0 (m -i -1) = (m -1)m/2 ≤ m 2 /2and deconditioning, we finally obtain

1 y(m 2 1 y(m 2 1 0(m 2 1 0-p 1 0

 12121211 As for the second moment, let m 2 (y, 1) = E(M (y, k) 2 ) denote the second moment of the number of moves, starting with potential y and k satisfied players. One step analysis yields the following Poisson equation, involving both m 2 and m.m 2 (y, n) = 0 m 2 (y, i) = ym 2 (y, i + 1) + (u, 1) + 2m(u, 1) + 1)du, n > i > 1 m 2 (y, 1) = y(1 -p)m 2 (y, 2)+(1 -p) (u, 1) + 2m(u, 1) + 1)du +p (u, 1) + 2m(u, 1) + 1)du By telescoping all m 2 (y, i), i > 1 and using M 2 (z) :=1 z m 2 (u, 1)du, m 2 (y, 1) = (1 -p) (1 -z) + 2M (z)) +p + 2pM (0) + pM 2 (0).This yields an integral form for M 2 (0) M 2 (0 = e q(z) (p + 2pM (0) + (1 -p)(1 -z n-1 ) + 2(1 -p) n-2 j=0 z j M (z))dz 1 e q(u) du

3

  Local clock, ticking w.r.t. a Poisson process with rate λ/n; Update strategy to x k ∈ BR k (x);

	4	repeat
	5	On each tick of the local clock
	15	Send(Stop) to all players;
	16	wait until n acks received;
	17	Send(Test) to all players;
	18	wait until n messages received;
	22	Stop Clock;
	23	Send(Ack) to p;
	24	wait until Test received;
	25	If BR(x) = x k Send(Stable) to sender;
	26	else Send(Unstable) to sender;

6 if x k ∈ BR k (x) then 7 8

With probability q: 9 Call Termination Test Sender; 10 On Reception of Stop 11 Call Termination Test Receiver; 12 until End sent or received ; 13 Function Termination Test, Sender 14 Stop Local clock; 19 if n 'Stable' messages received then Send End; 20 Else Restart local clock; 21 Function Termination Test, Receiver (for player k)

(the next playing instant). Let t 3 the first time that an overlap occurs while

Acknowledgement

This work was supported by the LabEx PERSYVAL-Lab.

Restart Clock;

Appendix A. Proof of Lemma 1

The main idea of the proof is to construct a coupling of BRD and IFA under which they can be compared. To do that, let us consider an infinite sequence U = (U (1), U (2), . . .) of IID random variables, uniformly distributed in [0, 1]. We couple an execution of the original BRD with an execution of IFA as follows. In both executions, each new potential used (or visited) by the algorithm is the next value in the sequence U . This coupling is different from the natural coupling used in Figures 3 and4.

Appendix A.1. Number of visited states

Under this coupling, we will show an almost sure comparison,

Let us consider that the tth state visited by IFA is its final state. This implies that all the values of the potential Φ in the sequence (U (t + 1), U (t + 2), . . . , U (t + (A -1)N ) are all below Φ(U (t)).

Let us assume that after t -1 comparisons with other potentials, BRD has not stopped yet. Then U (t) is used while the current player computes its best Appendix A. [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF]

. Expected Number of Moves

The analysis of the expected number of moves, follows the same path as for the execution time.

First, one needs to show that the number of moves is larger under the IFA approximation. This is done by using the same coupling as for the number of steps. Then, one also needs to show that the number of moves is larger under the Restart approximation. Again, the proof is done by coupling IFA and Restart. By the same coupling argument as in the proof of V BRD ≤ st V IF A , we can show A = 2 is an upper bound on the case where A ≥ 2.

The expected number of moves for Restart satisfies a Poisson equation similar to the equation for the number of steps:

Let us denote by m(y, k) the average number of moves before reaching a Nash equilibrium, starting with potential y and k satisfied players. One-step analysis yields:

By simplifying, we get m(y, n) = 0 m(y, i) = 1 -y + ym(y, i + 1)

We define M (z) := 1 z m(u, 1)du and use telescoping so that the previous equations become a single ordinary differential equation with implicit initial condition M (0):

This equation admits an explicit solution for M (0), using the same function Using the fact that M (z) = 1 z m(u, 1)du, and m(u, 1) is decreasing, we get

where the second inequality uses (A.10).

In conclusion,

(A.12)

Appendix A.5. End of the Proof The proof of Lemma (1) follows directly from Equations (A.9) and (A.1) together with (A.11) and (A.12).


Paola Tubaro
email: paola.tubaro@lri.fr

Emergent relational structures at a "sharing economy" festival

Keywords: Social networks, status, ERGM

How do participants to an event engage with others ? This paper examines the emergent relational structure at a "sharing economy" festival, the 2016 OuiShare Fest. A multi-level network analysis design explores the linkages between participation patterns of the "elite" (speakers) and other participants, to unveil the social processes through which status hierarchies emerge and actors manage ensuing tensions. Newly developed specifications for exponential random graph models reveal a tension between cooperation (among actors with shared thematic interests) and competition for audience, whereby conformism and differential use of reciprocity in attendance relationships generate an informal pecking order.

Introduction

Events such as trade fairs, congresses and festivals contribute to the creation of new markets in the global economy [START_REF] Aspers | Trade shows and the creation of market and industry[END_REF][START_REF] Bathelt | Trade Shows in the Globalizing Knowledge Economy[END_REF]. They do so by bringing stakeholders physically together in one place in "temporary clusters" [START_REF] Bathelt | Between luminaries and meat grinders: international trade fairs as temporary clusters[END_REF] that cut across organizational and geographical boundaries. Networks formed at events are a complement to distant (online) relationships [START_REF] Urry | Social networks, travel and talk[END_REF], heightening participants' awareness of being involved in a common undertaking and enhancing their involvement with one another [START_REF] Anand | Tournament rituals in the evolution of fields: the case of the Grammy Awards[END_REF].

The question of how participants engage with others at an event speaks to the relational standpoint of network science, and scholars have indeed contributed answers especially in the case of trade events, where buyers negotiate commercial agreements with sellers [START_REF] Brailly | Embeddedness as a multilevel problem: a case study in economic sociology[END_REF]. But interactions related to the program of the event, where the goal is to exchange ideas rather than goods, have been less systematically explored. How do participants decide whom to pay attention to, and if they are speakers, how do they attract attention to themselves?

Program-related interactions are ties of attendance -who appears at the talks (or panels, workshops etc.) of whom. Attendance is a way to gain awareness of others, to display one's interest for specific topics, to pay respects to high-profile speakers, to meet like-minded attendees. The more options participants have (with parallel sessions for example), the more their attendance choices are disclosive of individual specificities.

Attendance choices are the hybrid product of institutional constraints (event settings and upstream choices made by the organizers, such as schedule and venue) and of patterns emerging from the autonomous interactions of individual participants. One of the resulting social processes, both formal and informal, is status formation. Attendance is an act of deference: acknowledging the relevance, prestige or importance of the speaker(s). Status is commonly defined as accumulation of acts of deference [START_REF] Podolny | The dynamics of organizational status[END_REF], and can be represented as a network of such acts within a relevant social setting [START_REF] Sauder | Status: insights from organizational sociology[END_REF]. The structure of this network may reveal potential tensions between individual status pursuits and the development of collective undertakings.

This paper maps and analyzes attendance choices at a festival of the "sharing economy". This nascent, still loosely-defined field of economic activity, encompasses a diverse range of participants (from technology start-ups to NGOs and government agencies) and topics (from smart city and blockchain to climate change and the future of work). Because its identity is in the making and interactions between participants may contribute to shaping its future development, the "sharing economy" is an almost ideal setting to study. The event, the OuiShare Fest, took place in Paris yearly from 2013 to 2017. Its relatively large size, global scope and unequaled breadth of outlook gave it prominence, making it a worldwide reference. It was not a marketplace (no commercial transactions going on) but rather an inspirational gathering, built around an ambitiously wide-ranging program and meant to raise awareness and share knowledge:

OuiShare Fest is an interdisciplinary festival that gathers creative leaders, entrepreneurs, movement builders, purpose-driven organizations and communities from across sectors and countries who want to drive systemic and meaningful change 1 .

Focus on a single festival involves a sociological case-study approach, which may seem to depart from the complex systems tradition that typically deals with larger networks. Yet complexity enters the research in a different way. Though small-sized, the network structure under study is very rich with a wealth of attributes derived from the specific build-up of the data, and captured through the tools and concepts of state-ofthe-art "multi-level" network analysis [START_REF]Multilevel Network Analysis for the Social Sciences: Theory, Methods and Applications[END_REF]. Through network richness, I aim to contribute to a growing effort toward a more interdisciplinary network science blending the methods of social science and complex networks [START_REF] Breiger | Scaling down[END_REF].

Multi-level network structures

Speakers embody the attractiveness of the program of an event such as OuiShare Fest. Theirs is a privileged position reserved to a minority [START_REF] Favre | Salons et définition de normes marchandes : le cas de la distribution de programmes de télévision en Afrique sub-saharienne[END_REF] and entitles to, among other things, free entrance throughout the duration of the event. Speakers enjoy high visibility: they all have a profile on the Fest's web page (see below), their talks are advertised in advance to prospective participants, they are live-streamed and live-tweeted, and videos are posted online after the event. They bring prestige and epistemic authority: a well-known speaker attracts attendees and raises the standing of the event. Hence, speakers can be said to be an "elite" among participants.

OuiShare Fest Speakers are diverse in their backgrounds, areas of expertise and political views. They seek the attention of participants, who must choose between up to seven parallel sessions at any one time. These choices can be represented as a network graph whose nodes are individuals and ties indicate attendance. The left panel of Figure 1 sketches the attendee-to-speaker (A2S) attendance network, which has "two-mode" structure in that nodes can be either senders (A) or receivers (S) of ties, but not both. The graph is valued (attendee A i may choose to attend one or more sessions of speaker S j ) and directed (mutual attendance may or may not occur).

It is especially interesting to ask who, from among the elite of speakers, attends (sessions of) whom. Speakers are also participants and, outside the session(s) assigned to them for their talks (or performances, workshops etc.), they can spend their extra time at the event by attending sessions of other speakers. In other words, besides spreading their own message, they may listen to the messages of others. The central panel of Figure 1 is the speaker-to-speaker (S2S) attendance graph, which is valued, directed, and one-mode (any node may be sender and/or receiver of an attendance tie).

Juxtaposed, these two graphs form a richer, "multi-level" network structure A2S2S driven by two different sources of agency (right panel in Figure 1) [START_REF]Multilevel Network Analysis for the Social Sciences: Theory, Methods and Applications[END_REF]. 3 Empirical setting and data I use data from the fourth OuiShare Fest, which took place on 18-20 May 2016 in Paris. With 1505 participants from 50 countries, the event was structured into 139 sessions with different formats (conferences, panels, workshops etc.) involving 258 speakers (in the roles of keynotes, panelists, moderators, performers etc.).

I retrieved attendance choices from the event's software application, "Sched", and additional information from the register of participants kept by the organizers. Sched is an online and mobile tool that allows participants to create a personal profile (with name, photo, organization, job title, self-description), to import contacts (among other participants to the event) from social media such as Twitter and LinkedIn, and most importantly for the purposes of this paper, to put together a personalized schedule of what to attend. The latter function was particularly attractive as no printed version of the program was distributed. Sched attendance choices were visible to all online, and can thus be seen as quasi-endorsements, reminiscent of the "Like" function of some social media platforms 2 .

Of the 1505 attendees of 2016, 733 filled their Sched profiles at least partly. This includes the 258 speakers, who all have at least some profile elements and the session(s) in which they were listed as speakers. All received at least one attendance choice from participants; 88 of them also chose themselves a program of sessions to attend beyond the one(s) in which they were scheduled to speak.

Variables and measures

I aim to explain the one-mode, directed network of speakers choosing to attend other speakers S2S, recoded as a dyadic variable with values for each pair of the 258 OuiShare Fest 2016 speakers. Disregarding self-attendance, it corresponds to 258 × 257 = 66306 dyads. For analytical convenience and without significant loss of information, its values are binarized 3 .

I expect S2S to depend on a set of independent variables, also defined at dyadic level (n= 66306). They operationalize the endogenous and exogenous social mechanisms that according to extant literature, may operate in this setting.

Thematic affinity

A potential driver of speakers' attendance choices relates to their areas of activity and expertise. In general, actors with similar interests and background will easily recognize the value of each other's competences. Having to deal with the same problems, they will acknowledge the same arguments. Research suggests two reasons why thematic affinity may drive attendance choices. First, attending a speaker who is an expert in one's own area can be a way to be comforted in one's stances, to see them indirectly confirmed [START_REF] Centola | Homophily, cultural drift and the co-evolution of cultural groups[END_REF]. Second, it can be part of an effort to (indirectly) affirm the importance of one's own area of interest and to legitimate its place, especially in uncertain situations where inclusion of specific areas or categories is ambiguous or contested [START_REF] Anand | Tournament rituals in the evolution of fields: the case of the Grammy Awards[END_REF].

I map speakers to themes using the categorization proposed by the event organizers, who had assigned each session to either a general category (for sessions such as Fest Opening and Closure) or one of six themes 4 . Formally, this is a dyadic, binary, symmet-ric variable TA (table 1) whose value TA i j = TA ji is 1 if speakers i and j (with i = j) have at least one theme in common (an indicator of affinity), 0 otherwise.

Status

What matters is the status of the receiver, rather than the sender, of attendance choicesthe potential object of others' deference. Hence for each of the 66306 pairs of speakers [i, j], focus is on the status of j. But status is complex because it is both an exogenous and an endogenous factor. Exogenously, status may derive from some given, observable quality of speakers -which prompts others to attend their sessions. To capture this dimension, I retrieve two indicators from speakers' Sched profiles (variable St1: whether they were founders of sharing economy organizations, a highly respected role in this milieu) and from registration information (variable St2: whether they had participated in the 2015 and/or 2014 OuiShare Fest, to denote experience and notoriety, see table 1).

Endogenously, status rankings may result from self-reinforcing processes: for example when individual qualities are not observable, attendance choices may be based on popularity -attending those speakers that others also attend. Over time, this process may amplify initially small quality differences between individuals [START_REF] Manzo | Heuristics, interactions, and status hierarchies: An agentbased model of deference exchange[END_REF]. One measure of popularity is the number of attendees that each speaker received through Sched. I compute this indicator by summing over the attendance choices of all participants with a Sched profile, without distinguishing those among them who were themselves speakers, and those who were not (variable St3, taken on the A2S2S network structure).

Another operationalization of popularity is the number of followers that speakers had on social media, insofar as it was imported into, and made visible through, Sched. Social media matter because Fest participants are heavy users of technologies, interacting online as much as face-to-face. Variable St4 is the count of the number of times each speaker appears as an online contact in the Sched pages of Fest participants, summing over all those (speakers and non-speakers, A2S2S network) who had linked their Sched profiles to their social media accounts.

Popularity effects can also be fully endogenous to the speaker-to-speaker (S2S) network: are there differences in the propensity of individual speakers to be attended by other speakers -independently of the other attendees they might get from the broader population of participants? Differential propensity to receive ties from among the elite may create status disparities regardless of other individual qualities. Formally, it can be modeled through indegree effects, one measure of which are counts of so-called kinstars, defined as a node N and a set of k different nodes O 1 , . . . , O k such that the ties O j , N exist for j = 1, . . . , k (see table 2).

Positional similarity

If two speakers attract essentially the same attendees (whether themselves speakers or not), they will display similar patterns of ties in the attendance network and will therefore occupy similar -in the limit, the same -network positions. Similarity induced by structure is what the literature calls "equivalence" [START_REF] Lorraine | Structural equivalence of individuals in social networks[END_REF], and can be seen as endogenous to the composite A2S2S network (right panel in Figure 1). But then, will speakers with similar multi-level network positions attend each other's talks, or rather avoid each other? A long tradition of research emphasizes how actors with similar ties are likely to be competitors [START_REF] Burt | Social contagion and innovation: Cohesion versus structural equivalence[END_REF] because they depend on the same resources and face the same opportunities -thereby leading to the prediction that they will likely avoid each other.

A commonly used measure of positional similarity is the Jaccard index which, for any two speakers, is defined as the number of common attendees (intersection), divided by the cardinality of the union (sum of the attendees of each of the two speakers, both separately and jointly). Scaling by the size of the union rules out the possibility that similarity scores are affected by the tendency of more prominent speakers to receive more attendees than less-known ones [START_REF] Borgatti | Two-mode concepts in social network analysis[END_REF]. I compute this dyadic variable Ja, which varies between 0 and 1, for each pair of speakers (table 1).

Reciprocity

Reciprocity is the tendency of individuals to send ties to those from whom they receive a tie. It is a plausible social mechanism, whereby people invest in their ties and expect rewards from these investments. Observed in much empirical research, reciprocity may flatten status hierarchies [START_REF] Gould | The origins of status hierarchies: A formal theory and empirical test[END_REF]. Here,it can only be defined endogenously to the S2S network: do speakers attend other speakers who attended their talks?

Reciprocity may also be indirect, if there are different ways in which the balance of what is given and received in a relationship can be satisfying for an individual [START_REF] Block | Reciprocity, transitivity, and the mysterious three-cycle[END_REF]. The question is whether speakers who attend a lot of talks of others, also receive many choices themselves -not necessarily from the same others.

Direct reciprocity can be modeled as the tendency of network structure to be symmetric, while indirect reciprocity can be captured through so-called mixed two-paths, that is, tendency of outgoing and incoming ties to co-occur, involving tendency toward correlation of indegrees and outdegrees (table 2).

Controls

Other potentially relevant factors are participation in the previous edition of the event, 2015, which may facilitate integration of participants (variable T 1), place of residence (distinguishing, for simplicity, France where half of the participants and about 40% of speakers came from, and other countries: variable Fr) and gender (variable Ge). They are originally monadic and taken from the organizers' register. To adapt them to the dyadic structure of the data, I compute an exact match indicator for each variable, to identify pairs of speakers in the same category (for example, both from France).

Exponential Random Graph Model of the attendance network

The observed network structure partly results from exogenous factors -such as epistemic affinity and the observable dimensions of status -and is partly self-sustained through an endogenous tendency to reproduce existing network structures. The number of attendees/followers of a speaker as a measure of status, and the Jaccard index of positional similarity, are feedback effects of the multi-level relational structure A2S2S onto S2S -the latter being a sub-structure of the former. There are also fully endogenous effects of the S2S network onto itself, notably reciprocity (direct and indirect) and indegree effects. The presence of such systematic dependencies between network ties requires explicit modeling and cannot be left to standard statistical inference approaches which assume independence of observations [START_REF] Pallotti | From network ties to network structures: Exponential Random Graph Models of interorganizational relations[END_REF].

Newly developed Exponential Random Graph Models (ERGM) specify the dependence among relations that such micro-mechanisms entail, in addition to modeling the effects of exogenous covariates [START_REF] Robins | Closure, connectivity and degree distributions: Exponential random graph (p*) models for directed social networks[END_REF][START_REF] Snijders | New specifications for exponential random graph models[END_REF]. These models address the dependencies that arise with network data, whereby one node may be involved in multiple relationships with other nodes. They do not only "control for" such dependencies but represent them directly, uncovering specific local (sub-graph) configurations implied by dependence mechanisms, and testing their statistical significance [START_REF] Amati | Social network modeling[END_REF].

ERGM provide a tool for inference with network data, whereby an outcome variable is predicted by several independent variables. Parameter values help identify a probability distribution for all graphs of the same size, and estimates aim at finding the parameter values that best match the observed network structure. This is obtained via Markov Chain Monte Carlo Maximum Likelihood (MCMCML) or other simulationbased techniques [START_REF] Lusher | Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications[END_REF].

Results

Table 3 reports ERGM estimates of a model in which the dependent variable is the network of attendance choices between speakers S2S, based on three broad categories of explanatory factors: exogenous covariates, A2S2Sand S2S-endogenous network dependencies. I do not model outdegree effects but constrain the estimation process to preserve observed outgoing ties (that is, only networks whose outdegrees are the same as those in the data have non-zero probability), to account for the fact that only a specific sub-group of speakers made online attendance choices. The model is estimated with R package 'ergm' in the Statnet suite [START_REF] Handcock | ergm: Fit, Simulate and Diagnose Exponential-Family Models for Networks[END_REF].

Model diagnostics (not reported here) are good. The MCMC sample statistics vary randomly around the observed values at each step and the difference between observed and simulated values of the sample statistics have a roughly bell-shaped, zero-mean distribution indicating stationarity. Comparison of the network statistics measured in the original data and networks simulated from the fitted model [START_REF] Hunter | ergm: A package to fit, simulate and diagnose exponential-family models for networks[END_REF] indicates good fit 5 . Multi-collinearity checks performed as per [START_REF] Duxbury | Diagnosing multicollinearity in Exponential Random Graph Models[END_REF] do not point to major concerns.

Discussion and conclusions

Interpretation of table 3 resembles that of a logistic regression: a large positive (negative) parameter indicates that the corresponding configuration is observed in the network more (less) frequently than what would be expected by chance alone, conditional on the presence of configurations associated with other effects in the data.

Thematic affinity confers self-deference

Thematic affinity is positive and significant: speakers give and receive choices from others with similar interests, and this is true whether their choice is reciprocated ("mutual" effect) or not (i j and ji combinations respectively). Their behavior is highly cooperative provided there is a shared interest: they give back if they receive, but are also happy to give without a return. It follows that, if attendance choices are deference gestures toward another speaker, they also bring benefits to the choice-makers. One reason is that they reinforce their thematic interest and contribute to legitimizing it. In this sense, attendance choices are a way for speakers to promote their ideas beyond their own talks, by publicly displaying interest in thematically similar others.

Preference for novelty over status

Regarding the observable dimensions of status, being founder of an organization does not matter, while surprisingly, experienced speakers are slightly less likely to be attended by other speakers. Negative and significant co-participation the year before magnifies this effect: all other things equal, a returning speaker is less likely than a newcomer to attend the talk of another returning speaker. While this result seems to counter extant evidence that past co-participation facilitates tie formation [START_REF] Brailly | Embeddedness as a multilevel problem: a case study in economic sociology[END_REF], it indicates alignment with OuiShare's explicit orientation towards creativity, innovation, and entrepreneurship, gainst the rigidity of an inherited (albeit recent) past. Preference for what is new and novel and avoidance of long-term involvement offer the advantages of flexibility and openness at the expense of durability and fixed anchors.

Popularity produces conformity

Popularity, as unobservable dimension of status, is operationalized in the A2S2S network by counting number of online followers and number of attendees: the former has no effect while the latter is positive and significant. Within the S2S network, popularity is measured through indegree effects, all significant: two-in-star is positive, meaning that ties are more likely to be directed at nodes that already have an incoming tie, while three-in-star and geometrically weighted indegree distribution, a higher-order effect, are negative, meaning that after accounting for all other model terms, nodes with large numbers of ties are less likely to receive more ties. Taken together, these results indicate that a speaker does not want to be the first to pay deference to another speaker, but does not follow mere popularity either. Distinction from peers is valued, but nobody would go as far as taking the risk of setting entirely new trends. That speakers value distinction while being reluctant to overly-differentiate themselves suggests a form of conformity often observed in middle-status individuals [START_REF] Phillips | Middle-status conformity: theoretical restatement and empirical demonstration in two markets[END_REF], which tends to curb status hierarchies and is suggestively indicative of the position where they perceive the sharing economy to be in today's social structure.

Unreciprocated ties in competition

Direct reciprocity is not significant: attending the talk of someone else does not increase one's odds of being attended. Neither is indirect reciprocity (two-paths) significant: using Sched to choose one's own agenda does not affect the chances of receiving attendance choices by others, so there is no tendency toward correlation of in-and outdegrees. Even more surprising is the finding that speakers go as far as countering reciprocity when they compete for attention of the same third parties: positional similarity has a strong negative effect only on reciprocal ties. Put differently, if speaker i attends speaker j and they attract largely the same attendees, then j is less likely to attend i's talks, than would be the case if i sent no tie to j.

Against an empirical literature suggesting that dislike of symmetry is uncommon [START_REF] Gould | The origins of status hierarchies: A formal theory and empirical test[END_REF], there is an obvious irony in that reciprocity is absent in a festival formed around the premise of sharing. However, as noted in 6.1, there is a significant tendency to reciprocate among speakers who share thematic interests, that is, in collaborative contexts; while a significant tendency not to reciprocate is observed only under competitive conditions. Reciprocity appears to be a flexible instrument to manage one's position in the social structure of the event, whereby speakers use it differentially depending on whether the goal is to secure support for their theme or to get many attendees. They aim to gain individual status, although the overall effect is uncertain -steepening hierarchy if competitive conditions prevail, flattening it if collaborative behaviors dominate.

These results also highlight a tension between what is institutionally structured and what is relationally driven, as the official framing of the event and actual practices do not always align: if individuals enact the drive toward novelty promoted by OuiShare organizers in their choice to attend talks of less experienced and new speakers (see 6.2), competitive conditions lead them to deviate from supposedly shared norms, notably reciprocity. As before, global impact is indeterminate as openness to novelty mitigates status hierarchies, while rejection of reciprocity fuels them.

Along similar lines, thematic affinities have a dual function: while encouraging cooperative behaviors among speakers with shared interests, they may increase competition between representatives of different areas who all aim at recognition and prominence, potentially at the expense of others. Once again, systemic effects are ambiguous.

Under such opposing forces, a status hierarchy appears but because endogenous factors (especially indegree-related effects, see 6.3) do not unequivocally exacerbate it, it remains globally mild. All in all, it seems that the OuiShare Fest elite has not developed strict social norms to regulate deference -perhaps in a way that is best suited to the "sharing economy" whose definition, scope and boundaries are still moving.

Fig. 1 .

 1 Fig. 1. Left: attendee-to-speaker two-mode network A2S, where black dots are speakers, gray dots are non-speaking attendees, and light gray lines are attendance choices. Center: speaker-tospeaker one-mode network S2S, where black dots are speakers, dark gray lines are attendance choices. Right: multi-level combination of both A2S2S.

Table 1 .

 1 Dyadic variables included in empirical model specification: definitions and descriptive statistics. Those in italics are endogenous to the multi-level A2S2S network.

	Variable		Construct	Min	Max	Mean	St.Dev
	Speaker-to-speaker	atten-	Dependent variable 0	1	0.058	0.235
	dance
	TA: Common themes		Thematic affinity	0	1	0.205	0.404
	St1: Founder of organization Status (receiver)	0	1	0.31	0.463
	St2: Experience		Status (receiver)	0	2	0.527	0.753
	St3: Number attendees		Status (receiver)	1	500	117.597 74.414
	St4: Number online followers Status (receiver)	0	63	4.77	10.621
	Ja: Jaccard index		Positional similarity 0	1	0.145	0.119
	T1: Participation previous	Control (match)	0	1	0.314	0.465
	year
	Fr: Residence in France	Control (match)	0	1	0.376	0.485
	Ge: Gender		Control (match)	0	1	0.616	0.487

Table 2 .

 2 Structural

	Variable	Construct	Configuration	Count
	Arc		Directed tie		3898 a
	DR: Reciprocity	Direct reciprocity		266 b
	IR:	Mixed-two-	Indirect reciprocity		60228
	paths
	2I: 2-instar	Indegree effects		40929
	3I: 3-instar	Indegree effects		360677

dependencies to be modeled, representing endogenous feedback effects to the S2S network. Description and count in dataset.

a Network density 0.0588. b Reciprocity rate 7%.

Table 3 .

 3 ERGM Maximum Likelihood estimates. Dependent variable: network of attendance choices S2S, independent variables: covariates and endogenous structural dependency statistics outlined in Table 1 (upper section) and Table 2 (lower section).

	Variable	Estimate	Std. err.	p-value	Signif. a Odds-ratio
	Thematic affinity
	Mutual (TA i j, ji )	0.9118	0.1963	< 1e-04 ***	2.4888
	Upper (TA i j )	0.2904	0.0734	< 1e-04 ***	1.3369
	Lower (TA ji )	0.4507	0.075	< 1e-04 ***	1.5694
	Status
	Receiver founder	0.0606	0.0375	0.106		1.0624
	Receiver experience	-0.057	0.0286	0.0463	*	0.9446
	Receiver No. attendees	0.0098	0.0009	< 1e-04 ***	1.01
	Receiver No. followers	-0.0033	0.0022	0.1334		0.9967
	Positional similarity
	Mutual (Ja i j, ji )	-0.2875	0.0472	< 1e-04 ***	0.7502
	Upper (Ja i j )	0.038	0.2657	0.8861		1.0388
	Lower (Ja ji )	-0.1027	0.2756	0.7094		0.9024
	Controls
	Co-presence past year	-0.1128	0.0431	0.0089	**	0.8934
	Both from France	0.2248	0.0413	< 1e-04 ***	1.2521
	Same gender	0.0437	0.0417	0.2938		1.0447
	Structural dependencies
	Reciprocity
	Direct reciprocity	0.127	0.174	0.4655		1.1354
	Mixed-2-paths	0.0001	0.0008	0.873		1.0001
	Indegree effects
	2-instar	0.0804	0.0091	< 1e-04 ***	1.0838
	3-instar	-0.0034	0.0004	< 1e-04 ***	0.9966
	Gwidegree b	-1.6607	0.3274	< 1e-04 ***	0.19
	a Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
	b Geometrically-weighted indegree distribution controls for higher-level (in)degree effects and
	helps avoid model degeneracy (a common problem with ERGM)
	N = 66306, AIC: -2133, BIC: -1969

OuiShare Fest website, URL: http://ouisharefest.com/

Because physical attendance was not monitored, it cannot be assumed that Sched choices always resulted in actual meetings with the speakers or other attendees.

Only choices outside speakers' own sessions are considered, taking out cases in which attendance is imposed by the organizers (for example, speakers who present in the same panel.

[START_REF] Bathelt | Between luminaries and meat grinders: international trade fairs as temporary clusters[END_REF] These were: "Building Enterprises for the Digital Age", "Digital Institutions and The City", "Education and Personal Development", "Power and Capital in the 21st Century Organization", "The (Present) Future of Work", "Understanding Decentralization and The Blockchain".

Goodness of fit has been calculated for indegree, geodesic distances, shared partner distributions, triad census and and the terms of the original model as recommended in[START_REF] Hunter | ergm: A package to fit, simulate and diagnose exponential-family models for networks[END_REF].