Filipe Barroso

Grégoire Cattan

System to Customize Commentary in a Brain-Computer Interface Environment

published or not. The documents may come   L'archive ouverte pluridisciplinaire


ERME Carl Winsløw
email: winslow@ind.ku.dk

CERME 12 in virtual Bolzano

The Conferences of ERME (European society for Research in Mathematics Education) have been held roughly biannually since 1998. The core of the conference is the thematic working groups (TWG) in which new, related research studies are discussed, based on papers which participants read in advance. While this format has remained almost unchanged since 1998, the scale and scope of CERME have developed considerably over the years: from 120 participants and 7 TWG at CERME 1, to 915 participants and 27 TWG at CERME 12. Moreover, CERME has gone from being a mainly regional congress (with only a few participants from other continents) to being a truly global event in mathematics education research, known for fostering high quality scientific communication, cooperation and collaboration. At CERME12, no less than 48 nations were represented (Table 1).

At the same time, it is evident that CERME12 was a very specialand historically difficultcongress to organize. It was first scheduled for February 3-7, 2021. In May 2020, the ERME board announced its decision to postpone the congress by one year, due to the then roaring outbreak of the COVID-19 pandemic. Indeed, large parts of the worldand most of Europecontinued to experience lockdowns and restrictions that would have made the scheduled congress impossible. Instead, an online Pre-CERME12 event was organized in February 2021, hosted by the Institute of Education at University College London, and made possible by the tireless efforts of the team led by Jeremy Hodgen and Eirini Geraniou (also chair resp. co-chair of the IPC of CERME12). The Pre-CERME12 event allowed the 27 TWGs to meet and prepare for conference, now postponed to 2022.

The biannual General Assembly of ERME was also held during this event. We warmly thank Susanne Prediger for her service as President of ERME from 2017 to 2021! Her leadership also contributed crucially to the organisation of CERME12, and thus to the results presented in these proceedings.

During the summer and fall of 2021, we all continued to plan for CERME12 as an onsite event in Bolzano, Italy. The YESS summer school was held near Bolzano in August, with great success. More than 700 papers and posters were submitted for CERME12 in September. But in November 2021, new and unknown variants of the virus appeared. Their alarming spread forced us to reconsider the situation. Finally, the LOC, the IPC and the ERME board jointly decided that CERME12 would be held as an online congress, as announced in a mail sent to all members of ERME on December 1 st : It is with great sadness that we must communicate a decision which is forced upon us by the current developments of the COVID epidemic in Europe, and which has been taken by the ERME board in full agreement with us: CERME12 will be organized by the Bolzano team as an online conference, on the same dates as originally foreseen. For a long time we hoped for the much desired possibility of having the first CERME in three years as a normal, face to face event. Organizing a virtual CERME -which we will strive to hold as much "CERME spirit" as possible will be a very demanding task, both in terms of finding good technical solutions, and in terms of organizing the programme and preparing the many TWG teams in a good way. Indeed, it took a unique tour de force for all organisers to preparein just two monthsan online version of CERME, based as it is on group work and interaction, rather than on one-way presentations (which are relatively easy to transmit online). These effort was crowned by the best success the new conditions could possibly allow: an online congress with more participants than ever, with virtually no technical problems, and not least with a high level of participant satisfaction.

In the history of ERME, CERME12 will be remembered as a scientific highlight during the long and hard pandemic. First of all, that is due to the plenary speakers and panelists, and to the contributors of papers and posters. Your efforts shine through the quality of the scientific texts offered by these proceedings. ERME, as a society of scholars, was not stoppedhardly delayedby the pandemic, thanks to your ingenuity and unfailing determination to do and share first class research.

The realization of CERME12 was made possible also by the many people who organised the congress, under the difficult conditions alluded to above, namely:

-The Local Organizing committee, led by Giorgio Bolondi and Federica Ferreti, and all of the Bolzano team, including also the technicians who made the online congress run smoothly;

-The International Programme committee, led by Jeremy Hodgen and Eirini Geraniou;

-The leader teams of all 27 Thematic Working Groups.

For all your tireless and unselfish work during the three years between CERME 11 and CERME 12, the community owes you immense and extraordinary gratitude.

And the story goes on: ERME invites all interested researchers to CERME 13 (Budapest , Hungary, July 2023), and after that, to CERME 14 to be held in real Bolzano in February 2025.

Table 1 : The success of CERME12 in numbers -915 participants from 48 countries

 1

	Germany	209	Turkey	15	Iceland	3
	Norway	85	Ireland	13	Lithuania	3
	Italy	81	Czech Rep.	11	New Zealand 3
	Spain	62	Slovakia	11	China	2
	Sweden	62	Chile	9	Colombia	2
	USA	41	Brazil	8	Hong Kong	2
	UK	38	Croatia	8	Poland	2
	Israel	31	Finland	6	Algeria	1
	Netherlands	26	South Africa	6	Egypt	1
	Denmark	24	Switzerland	6	Faroe Islands 1
	France	21	Australia	5	Malta	1
	Austria	20	Malawi	5	Romania	1
	Canada	19	Mexico	5	Russia	1
	Greece	19	Belgium	4	Thailand	1
	Portugal	17	Japan	4	Tunisia	1
	Hungary	15	Cyprus	3	Ukraine	1


Omar Boufous
email: omar.boufous@orange.com

Rachid El-Azouzi
email: rachid.elazouzi@univ-avignon.fr

Mikaël Touati
email: mikael.touati@orange.com

Eitan Altman
email: eitan.altman@inria.fr

Mustapha Bouhtou
email: mustapha.bouhtou@orange.com

Learning a Correlated Equilibrium with Perturbed Regret Minimization

Keywords: Game theory, Correlated equilibrium, Online learning

In this paper, we consider the problem of learning a correlated equilibrium of a finite non-cooperative game and show a new adaptive heuristic, called Correlated Perturbed Regret Minimization (CPRM) for this purpose. CPRM combines regret minimization to approach the set of correlated equilibria and a simple device suggesting actions to the players to further stabilize the dynamic. Numerical experiments support the hypothesis of the pointwise convergence of the empirical distribution over action profiles to an approximate correlated equilibrium with all players following the devices' suggestions. Additional simulation results suggest that CPRM is adaptive to changes in the game such as departures or arrivals of players.

Introduction

Since their introduction [START_REF] Aumann | Subjectivity and correlation in randomized strategies[END_REF] [2] as a solution concept for non-cooperative games, correlated equilibria have gradually emerged as an appealing generalization of Nash equilibria. Correlated equilibria build upon the idea of correlated strategies, allowing for a non-independent randomization over actions by the players. More formally, a correlated equilibrium is defined as an equilibrium of a game extended with a structure defined by a probability space and a collection of player-specific events. Some of these structures known as "canonical" [START_REF] Forges | Correlated equilibria and communication in games[END_REF] lead to an interpretation in terms of a mediator [START_REF] Myerson | Game theory: analysis of conflict[END_REF] drawing an action profile according to a probability distribution and privately suggesting each player its component. After receiving this recommendation, the player chooses her action. It was shown in [START_REF]Correlated equilibrium as an expression of bayesian rationality[END_REF] that the canonical structures are sufficient to generate all correlated equilibrium distributions.

We consider the problem of learning a correlated equilibrium of a noncooperative game with simple rules of behaviour known as adaptive heuristics (e.g. fictitious play, regret minimization procedures) [START_REF] Hart | Adaptive Heuristics[END_REF]. These rules may not be rational in the sense that they may not choose the action maximizing the player's expected utility but may lead to rational outcomes in the long run. Particularly, several adaptive heuristics imply the (almost sure) convergence of the empirical distribution over action profiles to the set of correlated equilibria [START_REF] Hart | Adaptive Heuristics[END_REF][START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF][START_REF]A reinforcement procedure leading to correlated equilibrium[END_REF][START_REF] Foster | Calibrated Learning and Correlated Equilibrium[END_REF] under relatively mild assumptions (e.g. every player may only know her utility function and the history of play). However, no adaptive heuristic implies a pointwise converge (more generally, a stabilization close) to a correlated equilibrium distribution.

The main objective of this paper is to address the latter issue by introducing a new adaptive heuristic called Correlated Perturbed Regret Minimization (CPRM) leading to such results. In CPRM, players adaptively alternate between playing a regret minimization strategy to reduce the distance between the empirical distribution over action profiles and the set of correlated equilibrium distributions and following the suggestions of a device sampling from this distribution. In the long-run, the empirical distribution is expected to stabilize close to a correlated equilibrium with players following the device's suggestion.

Related work

The majority of the literature on learning in games [START_REF] Fudenberg | The Theory of Learning in Games, ser[END_REF] [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] studies the problem of learning pure and mixed Nash equilibria [START_REF] Foster | Regret testing: Learning to play nash equilibrium without knowing you have an opponent[END_REF][START_REF] Young | Learning by trial and error[END_REF][START_REF] Boussaton | On the distributed learning of nash equilibria with minimal information[END_REF][START_REF] Frihauf | Nash equilibrium seeking in noncooperative games[END_REF][START_REF] Germano | Global nash convergence of foster and young's regret testing[END_REF][START_REF] Hart | Uncoupled dynamics do not lead to nash equilibrium[END_REF] with some contributions focusing on the convergence to equilibria satisfying properties such as Pareto efficiency [START_REF] Marden | Payoff-based dynamics for multiplayer weakly acyclic games[END_REF] [START_REF] Pradelski | Learning efficient nash equilibria in distributed systems[END_REF] or welfare maximization [START_REF] Ariel | Average testing and the efficient boundary[END_REF] [START_REF] Marden | Achieving pareto optimality through distributed learning[END_REF].

The problem of learning correlated equilibria has received less attention in spite of a growing interest in the topic and the importance of the solution concept. In [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF], Hart & Mas-Colell use Blackwell's approachability theory [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF] to minimize players' regrets and show convergence of the empirical probability distribution over action profiles to the set of correlated equilibria. Similar guarantees are offered by calibration [START_REF] Foster | Calibrated Learning and Correlated Equilibrium[END_REF] [START_REF] Perchet | Approachability, regret and calibration: Implications and equivalences[END_REF] but none of these procedures guarantee pointwise convergence of the trajectories to equilibrium points. In [START_REF] Greenwald | Correlated q-learning[END_REF], Greenwald et al. presented correlated-Q, a multi-agent reinforcement learning algorithm with an equilibrium selection feature in which a linear program is solved at each iteration to compute the polytope of correlated equilibria. This requires from every player a perfect knowledge of the game being played (payoff and actions of all players involved). In [START_REF] Borowski | Learning to Play Efficient Coarse Correlated Equilibria[END_REF], Borowski et al. proposed an uncoupled learning rule with a public signal such that, in the long-run and as the perturbation term tends to zero, the process spends most of the time at the efficient coarse correlated equilibrium if feasible. It is not shown that the players' joint strategy is an efficient coarse correlated equilibrium at any time. See [START_REF] Hart | Adaptive Heuristics[END_REF][START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF][START_REF] Foster | Calibrated Learning and Correlated Equilibrium[END_REF][START_REF] Marden | Selecting efficient correlated equilibria through distributed learning[END_REF] for other works on learning coarse correlated equilibria. Recent contributions consider learning correlated equilibria in more general dynamic games such as [26] [27] for games in extensive form.

Finally, from an application perspective, correlated equilibria are relevant in engineering [START_REF] Jin | Dynamic task pricing in multi-requester mobile crowd sensing with markov correlated equilibrium[END_REF][START_REF] Hu | A correlated equilibrium based transaction pricing mechanism in blockchain[END_REF]. Particularly, [START_REF] Cigler | Reaching correlated equilibria through multi-agent learning[END_REF] shows an algorithm using a correlation signal to synchronize the players' decisions so that they play a correlated equilibrium. The proposed approach seems to be limited to the considered system.

Outline

In Section 2, we define the model and provide the necessary preliminaries such as the relationship between correlated equilibria and the notion of regret used in CPRM. In Section 3 we show the dynamic of the learning algorithm. In Section 4, we evaluate and discuss numerical performances of our solution and Section 5 concludes this work and shows possible directions of research and improvements.

Preliminaries

Notations

Vectors and tuples are denoted by small bold letters, matrices and random variables are denoted by capital letters. For M ∈ R m×n , m(i, j) denotes the entry in row i and column j and ||M || = max i,j |m(i, j)|.. The i th component of x is denoted x i and x ≥ y means x i ≥ y i for every i. We use calligraphic capital letters for sets and |S| is the cardinality of S. The indicator function of A is denoted 1 A . Table 1 summarizes other notations used in the paper.

Model

We consider a finite non-cooperative game G = (N , (A i ) i∈N , (u i ) i∈N ) such that player i ∈ N has finite set of actions A i . Let a i ∈ A i be a pure action for player i and p i ∈ ∆ (A i ) be a mixed strategy for player i. The set A = i A i is the set of action profiles and A -i = j̸ =i A j is the set of action profiles for players in N \{i}. Players i's utility function is u i : A → R such that u i (a) = u(a i , a -i ) is i's utility for action profile a = (a i , a -i ) ∈ A. Player i's utility for the mixed strategy profile p = (p 1 , . . . ,

p n ) is u i (p i , p -i ) = a∈A i∈N p i (a i )u i (a i , a -i ).

Correlated equilibria and their approximations

An approximate correlated equilibrium is a probability distribution over action profiles such that the expected utility of every player is approximately maximal. Formally, we have the following definition.

Definition 1 (Correlated β-equilibrium, [START_REF] Hart | Adaptive Heuristics[END_REF])

A probability distribution q ∈ ∆(A) is a correlated β-equilibrium if ∀i ∈ N , ∀a i , a ′ i ∈ A i a -i ∈A-i q(a)[u i (a ′ i , a -i ) -u i (a i , a -i )] ≤ β. (1)
The case β = 0 corresponds to the usual case of (an exact) correlated equilibrium [START_REF]Correlated equilibrium as an expression of bayesian rationality[END_REF].

As an example, consider the traffic game and involving two vehicles (players) at an intersection. At each stage, each player can either cross (action "Go") or wait (action "W ait"). When both players cross simultaneously, damage is caused by a collision, both players are penalized and incur a negative utility of (-1, -1). In this game, there are two pure strategy Nash equilibria (W ait, Go) and (Go, W ait) and one Nash equilibrium in mixed strategies

( 1 2 • W ait, 1 2 • Go), ( 1 2 • W ait, 1 2 • Go)
. Furthermore, the probability distribution P(Go, W ait) = P(W ait, Go) = 1/2, P(Go, Go) = P(W ait, W ait) = 0 is a correlated equilibrium.

Table 2: Payoff matrix of the traffic intersection game.

Wait Go Wait (0, 0) (0, 1)

Go (1, 0) (-1, -1)
The pairs of payoffs associated with the Nash equilibria are (0, 1), (1, 0) and (0, 0) respectively. Observe that pure Nash equilibria result in unfair utility vectors. Similarly, the mixed Nash equilibrium is fair but inefficient. Now assume that the game is repeated and that both players can receive recommendations on the action to play before each stage. Particularly, consider a coin toss such that:

if player 1 observes "Head", she plays Wait else she plays Go.

if player 2 observes, "Head" she plays Go, else she plays Wait.

In this configuration, in the long-run, the players play the profile (Wait, Go) and (Go, Wait) 50% of the time each, thus resulting in an average payoff of ( 1 2 , 1 2 )

which is more satisfactory than the three Nash equilibria and corresponds to a correlated equilibrium distribution. The idea of recommendations (i.e. players making decisions using private observations of a single random outcome) as well as the notion of regret that we introduce in the following paragraphs are both used in the solution we propose.

Regret minimization and correlated equilibria

Let h t = (a 1 , . . . , a t ) ∈ A t be the history of action profiles until time t with empirical distribution of play q t such that,

∀a ∈ A, q t (a) = 1 t |{τ ≤ t : a τ = a}| (2)
Following [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF], define the matrix

D t i = (d t i (j, k)) (j,k)∈Ai×Ai , such that d t i (j, k)
is the average payoff difference for player i when playing action k every time j was played.

d t i (j, k) = 1 t τ ≤t:a τ i =j u i k, a τ -i -u i j, a τ -i (3a) = a∈A:ai=j q t (a) [u i (k, a -i ) -u i (a)] (3b)
and the matrix R t i = (r t i (j, k)) j,k∈Ai×Ai such that r t i (j, k) is the regret of player i for the action swap j, k

∈ A i . ∀i ∈ N , ∀j, k ∈ A i , r t i (j, k) = max{0, d t i (j, k)} (4)
The regret r t i (j, k) is the average gain of utility player i could have obtained if he had played k instead of j every time he played j in the past t sequence of moves.

Remark 1. For any β ≥ 0, we have r t i (j, k) ≤ β if and only if d t i (j, k) ≤ β. Hence, we deduce from the definition of d t i (j, k) in Eq. (3b) that r t i (j, k) ≤ β at a given time t if and only if the empirical distribution q t is a correlated β-equilibrium.

The Proposition 1 below shows the equivalence between low regrets and approximate correlated equilibria, Proposition 1 ( [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF]) Let (a t ) t=1,2,... be a sequence of plays (i.e., a t ∈ A for all t) and let β ≥ 0. Then: lim sup t→∞ r t i (j, k) ≤ β for every i ∈ N and every j, k ∈ A i with j ̸ = k, if and only if the sequence of empirical distributions q t converges to the set of correlated β-equilibria.

In [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF], Hart et al. proposed a regret minimizing strategy using the approachability of the negative orthant R |Ai|×|Ai| -by the regret matrix (r i (j, k)) (j,k)∈Ai×Ai . This learning procedure is an application of Blackwell's approachability [START_REF] Blackwell | An analog of the minimax theorem for vector payoffs[END_REF] enabling player i's regret to be minimized i.e.

lim t→∞ d R t i , R |Ai|×|Ai| - → 0 a.s (5)
where d(•, •) is the Euclidean norm. The regret minimization strategy is the following. At any given time t,

-If R t i / ∈ R |Ai|×|Ai| -
, player i chooses an action according to the mixed strategy p t i satisfying Eq. ( 6).

∀j, k ∈ A i , j∈Ai p t i (j)r t i (j, k) = p t i (k) j∈Ai r t i (k, j). (6)
-Else, i plays randomly (i.e. an action drawn from any distribution)

In the next section, we propose a perturbed variant of this process, in which players synchronize as they approach the set of correlated equilibria to stabilize the realized sequence of empirical distribution {q t } t=1,2,... .

Learning algorithm

Rationale

In CPRM, at time t, each player i ∈ N is characterized by an individual state x t i with two components. The first component is called "mood" [START_REF] Young | Learning by trial and error[END_REF] and the second is the empirical distribution q t . In one mood, she implements a regret minimizing strategy (to decrease her regrets and contribute in decreasing the distance to the set of correlated equilibria) and in the other she plays her component of an action profile sampled from q t by a device (thus contributing in stabilizing the sequence {q t } t=1,2,... ).

Device

We assume a device drawing at time t an action profile a t = (a t 1 , ..., a t n ) with probability distribution q t as defined in Eq. ( 2) and recommending to player i the component a t i . By assumption, the device must know q t at t (not necessarily storing the history of play h t ) and must be able to transmit to every player her component in a t . We typically assume that it does not know the players' utility functions.

Players' states and strategies

At time t, player i ∈ N is characterized by a pair x t i = (m t i , q t ) in X i = {asyn, syn} × ∆(A). The first component m t i describes the player's mood at time t which can be synchronous (syn) of asynchronous (asyn). The second component is the empirical distribution of play q t given by Eq. [START_REF]Correlated equilibrium as an expression of bayesian rationality[END_REF]. By definition, the second component is the same for all players. If m t i = syn, then i plays s t i = a t i (sent by the device), else (m t i = asyn) player i plays a realization s t i of the random variable with probability distribution ξ t i such that ξ t i is the stationary distribution of matrix of regrets satisfying Eq. ( 6).

Players' states dynamic

Assume that at time t player i is in state x t i = (m t i , q t ) and that the profile a t is played (some players implementing the regret minimization strategy, others following the device's suggestions depending on their moods). The state x t+1 i of player i at time t + 1 is the realization of a random variable X t+1 i such that,

P(X t+1 i = (m, q)|X t i = x t i , a t ) = P(m t+1 i = m|X t i = x t i , a t )× P(q t+1 = q|X t i = x t i , a t ) (7)
where

P(m t+1 i = m|X t i = x t i , a t ) =            ε ||di(q t )||
if m=syn, and

m t i =asyn 1 -ε ||di(q t )|| if
where d i : ∆(A) → R |Ai|×|Ai| is the function defined in Eq. (3) and

P(q t = q|X t i = x t i , a t ) = 1 {q=f (t,q t ,a t )} (9)
where f : ∆(A) → ∆(A) is the function updating the empirical distribution such that,

∀x ∈ A, f (t, q t , a t )(x) = t t + 1 × q t (x) + 1 t + 1 1 {x=a t } (10)
We show below graphical representations of the mood dynamic.

-If player i is in 'mood' asyn i.e. m t i = asyn, she moves to mood syn with probability ε C0+||di|| ,

x t i = asyn, q t asyn, q t+1 syn, q t+1 ε C 0 +||d t i || 1 -ε C 0 +||d t i ||
-If player i is in 'mood' syn i.e. m t i = syn, she is faced with three possible transitions. The first possibility corresponds to the case where the player experiments with probability ε γ , without taking into account her regrets.

x t i = syn, q t 1 -ε γ ε γ asyn, q t+1 asyn, q t+1 if ||d t i || > β syn, q t+1 if ||d t i || ≤ β
The two other cases deal with the situation where player i does not experiment and monitors her regrets to decide her next move. As long as the regrets are below β, player i keeps following the recommendation of the device, otherwise, the player's mood reverts back to asyn.

We report in Appendix A an implementable version of CPRM algorithm as a pseudo-code.

It can be shown that the stochastic process {X t = (X t 1 , . . . , X t n )} t (modeling the state dynamic and where X t i is the random state of player i at t) induced by CPRM is a perturbed non-homogeneous Markov process on a countable state space. Furthermore, we conjecture that if this process admits an asymptotic stationary distribution and γ > n2 n-1 (C 0 + β), then S = {x ∈ X : ∀i ∈ N , m i = syn, ||d i (q)|| ≤ β} is the only stochastically stable set of states [START_REF] Young | The evolution of conventions[END_REF] and the sequence {q t } t=1,2,... converges implying that in the long-run the players follow the suggestions of the devices drawing action profiles from a correlated βequilibrium distribution. A detailed analysis of this process is beyond the scope of the paper.

Adaptive CPRM

The previous learning dynamic assumes a steady environment, with static game parameters, which is rarely the case in online settings, where a population of players may be dynamically changing. This characteristic is of paramount importance for many applications such as packet routing or auction systems, but it is has not yet been thoroughly investigated in the literature. For instance, the work in [START_REF] Lykouris | Learning and efficiency in games with dynamic population[END_REF] examines a repeated n-player game in which players adapt to the environment. More specifically, each player independently leaves with a certain probability, but is immediately replaced by an arbitrary new player such that the total number of players n remains identical. In our work, the total number of players may evolve with time. We propose an adaptation of CPRM to a dynamic case to deal with arrival and departure of players. In simulations, we demonstrate the efficiency of our method on examples. By assumption, the mediator is aware of the players involved in the game. We describe how the probability distribution used by the mediator for recommending actions is adjusted to the play. Let T 0 be the arrival time player n + 1. Let b n+1 be an arbitrary action in A n+1 . We construct the probability distribution used from T 0 +1 onwards for all profile (a 1 , ..., a n ):

q T0+1 (a 1 , ..., a n+1 ) = q T0 (a 1 , ..., a n ), if a n+1 = b n+1 0, otherwise (11)
Similarly, when a player i leaves at time T 1 , the probability distribution is projected from ∆(

n+1 i=1 A i ) onto ∆( n i=1 A i ) as follows: q T1+1 (a 1 , ..., a n ) = ai∈Ai q T1 (a 1 , ..., a n+1 ) (12)
After each player departure or arrival at a given time T , the scaling factor t used for updating the empirical distribution is re-initialized in the following way:

q t+1 (a) = t-τ t-τ +1 q t (a) + 1 t-τ +1 if a t = a t-τ t-τ +1 q t (a) otherwise (13)
where τ ≥ 0 is a design parameter that is chosen depending on the desired responsiveness of the games to changes in player population. For instance, taking τ = T when a player arrives or leaves at time T essentially means that the players start a new learning phase for the new game, which is independent from the previous learning period. On the other hand, a large value of τ signifies that the updates of the probability distribution are small, thus making the game less prone to rapid changes, and resulting in a slower learning and convergence. The constant τ can therefore be interpreted as the inertia of the learning with respect to changes, making it more or less responsive to arrival and departures of players in the game being played. The other parts of the algorithm remain unchanged.

Numerical results

In this section, we evaluate the performances of CPRM. First, we consider a simple two-players matrix game to compare our solution to other adaptive heuristics such as a regret-minimization based on Blackwell's strategy [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF] and Regret Matching [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF]. Then, we consider arrivals and departures of players in the game to observe how CPRM may adapt and conclude this performance evaluation on a congestion game with larger sets of actions and player-specific cost functions. For all experiments, the parameters in Table 3 were used.

Matrix games

Static setting We first consider the problem of learning a correlated equilibrium for the 3 × 2 matrix game shown in Table [START_REF] Myerson | Game theory: analysis of conflict[END_REF] admitting two mixed Nash equilibria (1/12, 0, 11/12), (5/6, 1/6) and (3/14, 11/14, 0), (5/6, 1/6) with respective utilities (13/3, 73/12) and (13/3, 82/7).

We consider the evolution in time (0 ≤ t ≤ T ) of the empirical probability distribution q t , maximal regrets (||R t i ||) i∈N and players' moods (m t i ) i∈N . Fig. 1a to 2c show the evolution in time of maximal regrets and the empirical distribution over action profiles induced by Regret Matching, Blackwell's regret minimization and CPRM. In Figs. 1, we observe that regrets decrease below the threshold β = 0.05 for each dynamic. This confirms the convergence of three algorithms to the set of β-correlated equilibria (as expected from [START_REF] Hart | A simple adaptive procedure leading to correlated equilibrium[END_REF]). However, if both players apply the Blackwell regret minimization strategy or the Regret-Matching procedure, the regret trajectories do not stabilize implying that the empirical distribution over action profiles does not converge to a correlated equilibrium.

Fig. 1c shows that the regrets induced by CPRM stabilize below the target threshold (even if not converging to zero), which confirms that the empirical distribution approaches the set of correlated equilibrium distributions and may converge. Furthermore, Fig. 2c shows very stable trajectories for the probabilities of each action profile, thus supporting the hypothesis of convergence. This is not the case for the the trajectories induced by the Regret-Matching procedure on Fig. 2a or Blackwell's regret minimization strategy on Fig. 2b which do not stabilize on the graphs and at even larger timescales (not shown).

We provide an example of a sample path generated by CPRM in terms of expected utility in Fig. 3. The plot shows the evolution in time of the pairs (ū 1 (q t ), ū2 (q t )) where ūi (q t ) is the expected utility ūi (q t ) = a∈A q t (a)u i (a) for player i. The gray area represents the feasible pairs of utilities in the game. Starting from the initial action profile (A, D) with utilities (2, 29), the trajectory stabilizes at a point in the vicinity of the convex hull of the two mixed Nash equilibria depicted by the red segment.

Fig. 4 shows the evolution in time of the players' moods as a scatter-plot. In the first thousands time steps, the two players are mostly asynchronous (value "1" on the plot), thus implementing a regret minimizing strategy. Around 4.10 4 time steps, both players are synchronous, thus playing the action profile suggested by the device and drawn from q t . In this regime, asynchronous realizations typically come from the fact that players "explore" regardless of their regrets due to the perturbation ε γ in the dynamic.

Iterations (t) Maximal regrets (|| R t i ||) || R t 1 || || R t 2 || (c)
Fraction of time spent in a correlated β-equilibrium In this section, we consider the impact of the perturbation on the long-run behaviour of CPRM for the previous two-players game. Let q * (ε) be the correlated β-equilibrium experimentally reached with perturbation ε (last distribution in Fig. 2c). In Fig 5, we show the fraction of time the players are synchronous (thus following the suggestions of the device) and the empirical probability distribution implemented by the latter is within a η-neighborhood (taking η = 0.01) to q * (ε). The complementary proportion of time, corresponds either to a distribution at a distance greater than η from q * (ε) or to the case where at least one player explores as a consequence of the perturbation. Fig. 5 is an experimental evidence of the existence of a long-run regime such that both players follow the suggestions drawn from the correlated β-equilibrium q * (ε). Furthermore, the plot shows that the smaller decreasing the perturbation ε implies increasing the proportion of time. This is consistent with the type of convergence expected from the perturbed Markov process and the conjecture stating that in the low perturbations regime the process should spend most the time close to a correlated equilibrium with synchronous players (playing profiles drawn from this distribution).

Iterations (t) Probabilities q t (A, D) q t (A, E) q t (B, D) q t (B, E) q t (C, D) q t (C, E) 1
Dynamic setting Previously, we have assumed that the same stage game is played at every iteration. This is rarely the case in applications such as packet routing in networks where the set of players (or their population) may change over time. In this section, we study the flexibility of CPRM w.r.t. such updates and how the previous convergence results may be impacted as new players join or leave the game and utility functions change. CPRM cannot be used as is and must be slightly adapted to handle the arrival and departure of players (typically, players must update their regret matrices in the regret-minimization strategy ate every arrival or departure to allow for the equilibrium of the ongoing game to be approached). We do not enter the details of this second version of CPRM but show the numerical results demonstrating the potential efficiency to be studied in future works. Assume that players start playing the game in Table 4 expanding into a three player game before evolving later on into a two-player game and eventually reverting back to the same three-player case afterwards as shown in Table 5. In the three-players game, the first two players keep their original sets of actions while the third player chooses the matrix (X or Y ). The first new player joins the game at T 1 = 509583 and leaves at T 2 = 1019541 while the second arrives at T 3 = 1529892. Fig. 6a shows the evolution with time of the maximal regrets of the players while Fig. 6b shows the evolution of probabilities for each profile.

The arrival and departure of a player perturbs other players' regrets (red and blue curves correspond to the initial two players). It appears in Fig. 6a that for each game, the regrets are stabilized below the threshold β (dashed line) on the corresponding time interval. It can also be observed in Fig. 6b that for each game, the probability distributions over action profiles seem to converge on the corresponding time interval. These results show that CPRM may also be used in environments with arrivals and departures as long as each game is played for sufficiently long.

Congestion Game

As a final example of numerical experiment, we consider the problem of learning a correlated equilibrium in a congestion game [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF] (a class of games particularly relevant w.r.t. network applications and resource allocation problems) with player-specific cost functions and larger action sets (the considered example has 108 action profiles) to test how relevant CPRM may be in this setting and its scalability with regards to the number of action and action profiles. In a con- gestion game with player-specific cost functions, each player selects a feasible subset of some resources and "pays" a cost defined as the sum over her selected resources of resource-based costs depending on the resource itself, the player and the total number of players selecting the resource. We consider the case where the resources are edges in a network, each player picking a subset of edges defining a path connecting a player-specific (source, destination) pair of nodes. Formally, this game is defined by the following collection of objects, a network G = (V, E) with vertices and edges, a finite set N = {1, . . . n} of n players, for every player i, a source-destination pair (s i , t i ) ∈ V × V, for every player i, an action set A ⟩ defined as the set of paths connecting source node s i with target t i , for every player i and every edge e ∈ E, a non-decreasing delay function d e i : N → R.

D E A (9, 4, 0) (4, 1, 4) B (8, 0, 1) (6, 7, 2) C (11, 9, 3) (2, 0, 4) X Y
Let f e : × i∈A A i → {0, . . . , N } be the congestion function of edge e such that f e (a) = |{i ∈ N : e ∈ a i }|, i.e. the number of players using edge e. Given a strategy profile a ∈ A, player i has cost c i (a) = e∈ai d e i (f e (a)). Particularly, we consider the 4-player game with graph and pairs defined in Fig. 7 with cost functions d e i (x) = x for all i ̸ = 2 and d e i (x) = x 2 for i = 2 and action sets,

-A 1 = { ′′ BCDEF ′′ , ′′ BDEF ′′ , ′′ BADEF ′′ } -A 2 = { ′′ BCDE ′′ , ′′ BDE ′′ , ′′ BADE ′′ } -A 3 = { ′′ DCB ′′ , ′′ DEF AB ′′ , ′′ DECB ′′ } -A 4 = { ′′ F DE ′′ , ′′ F ADE ′′ , ′′ F ABCDE ′′ , ′′ F ABDE ′′ }
As before, we first have an interest in a constant stage game and then allow for the stage game to change because of arrival and departure of players.

Fig. 8a shows the evolution with time of the empirical distribution q t . Since we cannot show the 108 curves (one per action profile), we plot only the curves of the five action profiles with highest probabilities in the long-term. As in the previous example of the two-players matrix game, the curves support the conjectured convergence of the empirical distribution. This is to be put into perspective with the evolution of regrets shown in Fig. 8b, indicating that this long-run distribution is indeed a correlated β-equilibrium distribution. Then, in the long-run, the players follow a correlated equilibrium routing policy of this game. To conclude, we assume that some players join or leave the congestion game. As commonly considered in network applications, we assume stochastic departures and arrivals following a Poisson process with rate λ = 1/27236. We show the results for a realization of this process such that a player 5 with pair (B, D) arrives at T 1 = 54377 and players 3, 5 and 4 leave at respectively T 2 = 81434, T 3 = 108702 and T 4 = 135882 as shown in Fig. 9. As expected, in the interval 0 ≤ t ≤ T 1 , the regret curves are similar to the case without arrivals and departures of Fig. 8b as the game being played in the considered time frame is the same.

It can be observed from Fig. 10 that in the third, fourth and last phase, the correlated β-equilibrium played is an approximate pure Nash equilibrium as only one profile is played with a probability close to 1. In all cases, regrets in Fig. 9 remain below the approximation threshold β.

Conclusion

In this paper, we considered the problem of learning a correlated equilibrium in finite non-cooperative games with a particular focus on the open problem of convergence of the empirical probability distribution (over action profiles) induced by an adaptive heuristic to a correlated equilibrium distribution. We proposed a new adaptive heuristic, called CPRM, combining regret minimization to approach the set of correlated equilibria and a simple device drawing samples from the empirical distribution. Numerical experiments support the conjecture that approximate correlated equilibrium distributions (the approximation factor being a parameter of the dynamic) with all players following the devices' suggestions are the only stochastically stable states and that the empirical distribution converges point-wise. Additional experiments show that CPRM can be adapted to be compliant with a time-varying game (e.g. arrivals and departures of players, changing utilities). In future research, we plan to prove the conjecture to confirm the results obtained in this paper.

Fig. 1 :

 1 Fig. 1: Evolution of players regrets the three algorithms: a) Regret Matching b) Blackwell-based regret minimization and c) CPRM algorithm.

Fig. 2 :

 2 Fig. 2: Evolution of the empirical distribution over action profiles for the three algorithms: a) Regret Matching b) Blackwell's regret minimization and c) CPRM algorithm.

Fig. 3 :

 3 Fig. 3: Trajectory (in blue) of the expected payoffs starting from the initial action profile (A, D) and reaching a correlated β-equilibrium (close to the red segment). Utilities at mixed Nash equilibria (M N E1 and M N E2) are shown as yellow circles.

2 Fig. 4 :

 24 Fig.4: Evolution of moods of the two players. Points take values 0 (mood "asyn") or 1 (mood "sync"). An artificial scattering is used to facilitate data visualization.

1 Fig. 5 :

 15 Fig.5: Evolution in time of the proportion of time spent in the η-neighbourhood of the correlated β-equilibrium q * (ε) for η = 0.01.

Fig. 6 :

 6 Fig. 6: Evolution of regrets (a) and the empirical distribution over action profiles (b) with arrival and departure of players (at times indicated with vertical dotted lines). The approximate equilibrium threshold is marked with horizontal dashed line on the left figure.

Fig. 7 :

 7 Fig. 7: Network graph of the game (left) and source-destination nodes of each player (right).

Fig. 8 :Fig. 9 :Fig. 10 :

 8910 Fig. 8: (a) Evolution of the empirical distribution over the (five main) action profiles. (b) Evolution of the maximum regret for each player (curves of players 3 and 4 are not plotted because of low regrets and the logarithmic scale).

Table 1 :

 1 Table of notations.

	Symbol	Meaning
	R (resp. Q) Set of real (resp. rational) numbers
	N A ∆(A) q h t	Set of players Joint action space Set of all probability distributions over the set of action profiles A Probability distribution over action profiles in A History of the game up to time t
	Ai ∆(Ai) pi	Player i's action space Set of all probability distributions over Ai Player i's mixed strategy
	pi(ai)	Player i's probability of playing action ai
	ui(•)	Player i's payoff function
	d t i (j, k) r t i (j, k)	Player i's average difference between payoffs of strategies j and k at t Player i's regret of for not choosing action k when action j is chosen at t
	ε	Perturbation parameter
	γ	A parameter defining the order of the perturbation ε
	β	A parameter that defines the approximate correlated β-equilibrium

Table 3 :

 3 Numerical experiments parameters.

		Value	Signification
	β	0.05 Approximation factor
	ε	0.01	Perturbation rate
	γ	5	Perturbation order
	T 5 × 10 5 Number of iterations C0 1 Offset

Table 4 :

 4 Payoff matrix of the 2-player game.

	D	E
	A (2, 29) (16, 7)
	B (4, 7) (6, 13)
	C (4, 4) (6, 6)

Table 5 :

 5 Sequence of stage games considered in the dynamic case. The stage game does not necessarily evolve at every iteration.

		D	E
		A (2, 29) (16, 7)
		B (4, 7) (6, 13)
		C (4, 4) (6, 6)
	D	E	↓	D	E
	A (2, 29, 2) (16, 7, 8)	A (9, 4, 0) (4, 1, 4)
	B (4, 7, 2) (6, 13, 0)	B (8, 0, 1) (6, 7, 2)
	C (4, 4, 1) (6, 6, 5)	C (11, 9, 3) (2, 0, 4)
	X		↓	Y
		D	E
		A (2, 29) (16, 7)
		B (4, 7) (6, 13)
		C (4, 4) (6, 6)
	D	E	↓
	A (2, 29, 2) (16, 7, 8)
	B (4, 7, 2) (6, 13, 0)
	C (4, 4, 1) (6, 6, 5)

A Appendix: Numerical implementation of CPRM

ui k, a τ -iui a τ i , a τ -i h t+1 ← (h t , a t+1 ) end


INVESTIGATING THE LOGICAL ASPECTS OF THE PI-CALCULUS NO ËL

The π-calculus: a nominal process calculus

The π-calculus has been introduced by R. Milner [START_REF] Milner | A calculus of mobile processes (Parts I and II)[END_REF] as a model for communicating processes. This calculus has been stressed by A. D. Gordon [START_REF] Gordon | Notes on nominal calculi for security and mobility[END_REF] to be an example of nominal calculus, as defined by R. M. Needham [START_REF] Needham | Names[END_REF]: "A nominal calculus is a computational formalism that includes a set of pure names and allows the dynamic generation of fresh, unguessable names".

In this formalism, messages are passed along channels each of which has a name; moreover, the names constitute also the possible content of the messages. The dynamic generation of names has founded the concept of mobility, which has spread as a domain of research in itself covering, in addition to the π-calculus, HOπ [START_REF] Sangiorgi | Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms[END_REF], the ambients [START_REF] Cardelli | Mobile ambients[END_REF], the join-calculus [START_REF] Fournet | The Join-Calculus: a Calculus for Distributed Mobile Programming[END_REF], . . . Another recent development in the domain of secure communications makes an essential use of the unguessable character of names, for example in the Spi-calculus [START_REF] Abadi | A calculus for cryptographic protocols: The Spi calculus[END_REF].

Up to miscellaneous variants, the processes of the π-calculus are given in the following syntax, in which ā b .P represents sending a list b of messages on a channel a, then performing continuation P ; a( x).P means receiving on channel a some values which are then substituted for x in continuation P ; operators | and + respectively express parallel composition, and indeterministic choice between two processes; (ν x)P expresses the generation of a list of fresh names x whose knowledge is restricted to P ; and [x = y]P allows execution of P only if names x and y match. Finally, infinite processes are provided by construction D( v) representing a call to a named process having a (possibly recursive) definition D def = (λ x)P : P ::= 0 ā b .P a( x).P P

+ P P | P (ν x)P [x = y]P D( v)
Though closely related in spirit to the λ-calculus, the π-calculus is a calculus of processes. R. Milner [START_REF] Milner | Functions as processes[END_REF] has investigated the relations between these theories, and pointed essential differences between the two. In contrast with the deep investigations of the correspondence between the λ-calculus and proof theory, the main stress as regards the π-calculus is put on methods for proving equivalence between processes. A quite complete account of the present state of the art can be found in [START_REF] Sangiorgi | The π-calculus: a Theory of Mobile Processes[END_REF].

Date: 30 10 2002.

Model-checking the π-calculus

Model-checking deals with Kripke-like relations P |= ϕ between processes and formulas. It was first introduced for finite state automata and temporal logic [START_REF] Emerson | Characterizing correctness properties of parallel programs using fixpoints[END_REF].

It was later used for CCS, using a modal logic HML (for Hennessy-Milner Logic) later improved as the µ-logic described below.

Let us give as an example the syntax of LTL (Linear Temporal Logic). Its formulas are defined as follows:

ϕ ::= tt | ff | a = b | ¬ ϕ | ϕ ∧ ϕ | ϕ ∨ ϕ | ✸ ϕ | ✷ ϕ | ϕ U ϕ | ∀x ϕ | ∃x ϕ
It presents three temporal modalities: ✸ ϕ means that ϕ will happen to be true in the future, ✷ ϕ that it will always be true, and ϕ U ψ that ϕ will remain true until ψ gets true (For sake of simplicity, we do not mention other possible modalities).

A nice tool for model-checking with LTL is the SPIN checker [START_REF] Holzmann | The model checker spin[END_REF] built on the PROMELA language. The distribution of this software involves some samples among which a translation of a celebrated example of a π-calculus process, the cellphone handoff strategy [START_REF] Orava | An algebraic verification of a mobile network[END_REF]. Nevertheless using LTL model-checkers to verify infinite processes remains out of reach at this time.

The µ-logic has different modalities, and involves fixpoint constructors adapted to infinite processes. Its use for the π-calculus has been studied by M. Dam [START_REF] Dam | Model checking mobile processes[END_REF].

The syntax is as follows:

ϕ ::= tt | ff | a = b | ¬ϕ | ϕ∧ϕ | ϕ∨ϕ | A ϕ | [A]ϕ | ∀xϕ | ∃xϕ | Σxϕ | µXϕ | νXϕ
It depends on a set of variables which will be identified with the names in the π-calculus. These names appear in atomic expressions a = b and also in the modalities A and [A] in which A is a set of actions of one of the three forms a, ā (with a any name) and τ . Then we can give sense to an expression P |= ϕ to be understood as "P satisfies ϕ", and we concentrate below on the particular features of this syntax. Satisfaction is understood in a Kripke model-like sense, where the Kripke structure would be the transition tree starting from a process P .

Modalities and quantifiers, in combination, allow to deal with outputs or inputs: P |= [A] ϕ expresses that for any action P α -→P ′ with α ∈ A then P ′ |= ϕ. P |= A ϕ means there is at least one action P α -→P ′ such that α ∈ A and P ′ |= ϕ. We write a(x).P |= [a] ∀x ϕ if for any name n received by P along channel a we have P {n/x} |= ϕ{n/x}; existential quantifier is treated in a similar way, while

P |= [ā]
x ϕ expresses that after any emission

P ā n -→P ′ we have P ′ |= ϕ{n/x}.
Least fixpoint µ and a greater fixpoint ν allow expressing infinite features of the processes.

For example, we can translate the modalities in LTL by writing

✷ ϕ ≡ (ν X)(ϕ ∧ [-]X) and ✸ ϕ ≡ (µ X)(ϕ ∨ ( -tt ∧ [-]X)) (nota- tions [-]
and -are conventional for the case A is the set of all names).

The results of M. Dam led to an implementation incorporated in B. Victor's Mobility Workbench (MWB) [START_REF] Victor | The Mobility Workbench -A tool for the π-calculus[END_REF], one of the scarce model-checkers for the π-calculus.

In collaboration with Y. Dumond, we have investigated the use of the π-calculus associated to the µ-logic for dealing with a case-study proposed at the workshop AFADL'98 [START_REF] Lisi/Ensma | Approches Formelles dans l'Assistance au Développement de Logiciels[END_REF]: the access controller. It consists in modeling the control of a set of doors for a set of buildings in a protected area. Each user attempting to pass a door must be checked to be authorized by entering a personal card into a reader. Various answers using methods such as B, LOTOS, UNITY, LPG, UML, Coq, were given in the AFADL meetings. Our contribution [START_REF] Bernard | Spécification en pi-calcul de l'étude de cas relative au contrôle d'accès[END_REF] led us to verify that the π-calculus enjoys interesting possibilities of modular treatment of complex systems, while the mobility inherent in this calculus allows to take into account intricate changes of configuration.

The method used in our treatment is to associate a process for each entity, such as a door, a card reader, a user, and dynamically add a new process at each attempt of a user to pass a door. The fact that all events are signalled via messages transmitted through a BUS also used for giving opening or closing orders makes it easy to translate the description into the π-calculus. The dynamic creation of a process is made possible by the (ν)-construct in this calculus.

The specifications of the case-study described above were given using a list of LTL formulas. For example, the following formula expresses that if unauthorized user u attempts to enter door a then a is locked:

✷ u.attempts(a) ∧ ¬u.authorized(a) → a.locked
The translation of LTL into the µ-logic provides automatically a specification in this last language.

We tried MWB on the µ-logic specification of the controller, and as expected, this tool is unable to manage a problem of that size. The question remains whether it is possible to devise an efficient model-checker for the π-calculus.It would be interesting to further investigate how infinite processes can be addressed by tools related to LTL such as SPIN, well adapted to deal with concrete verifications of specifications.

Curry-Howard and the π-calculus

The use, in the λ-calculus, of a typing system in which types are formulas in secondor higher-order logic was a the origin of some of the most outstanding results of this calculus. The fact, for a λ-term, to have a type ensures that this term terminates, which is a central property in this theory. Moreover, the Curry-Howard correspondence between proofs in intuitionistic logic and the λ-calculus ensures that, if a specification is expressed by some formula, any proof of this formula provides, by just using the typing rules, a program fulfilling the specification. This allows at a theoretical level to devise means of automatic generation of correct programs, and has led to practical applications such as the typed language ML or the Coq prover.

The π-calculus has been equipped by R. Milner with a typing system called sorts. Made necessary in the polyadic version of the π-calculus [START_REF] Milner | The polyadic π-calculus: a tutorial[END_REF], where during a single communication a list of messages can be transmitted, typing is especially crucial for HOπ, a Higher-Order π-calculus, in which messages can be not only names of channels, but also processes. The sorts associated to channels are their arity, that is, not only the number of messages transmitted together in one communication on this channel, but also in a recursive way, the sort of each message.

Sorts do not supply the π-calculus with a correctness verification tool. The sorting discipline only specifies the properties of channels, while for processes the only possible type is OK -meaning channels are used with the correct arity-which gives no indication about termination or fulfillment of specification. It may be noticed anyway that problems of great importance in the sequential context of the λ-calculus are not the main concern in process calculi: termination is not always a goal and conflicts with liveness properties often looked for.

Several attempts have been made to give the π-calculus more elaborate typing systems. The blue calculus [START_REF] Boudol | The π-calculus in direct style[END_REF] makes a synthesis of the λ-and π-calculi: In addition to a kernel of π we find a λ-abstraction while communication on a channel a is replaced here by a "resource fetching" rule (az 1 . . . z k | a ⇐ P ) → P z 1 . . . z k . This rich language can be typed with a system combining the simple types of the λ-calculus and the sorts of the π-calculus. This type system does not ensure termination, but enjoys the subject reduction property. An inspection of how the typing rules apply to the π-calculus component of the blue calculus makes it appear that the typing reduces here to a sorting discipline.

Another attempt in [START_REF] Yoshida | Strong normalisation in the π-calculus[END_REF], [START_REF] Berger | Sequentiality and the pi-calculus[END_REF] extends the sorting discipline using ideas from the linear logic. It uses a slightly modified on the π-calculus, as here output ā( x).P is bound, leading to a communication rule of the form ā( x).P | a( x).P → (ν x)(P | Q). Typing uses dual I/O modes ↓ (linear input), ↑ (linear output), ! (replicated input) and ? (output to !). This system allows a fully abstract encoding of PCF into the π-calculus, related to the sequential character of the processes which can be typed; a further refinement ensures the strong normalization property as well as confluence.

The two examples cited above have in common that a typing system stronger than the sorts is associated to a sequential calculus, introduced either in addition to, or as a fragment of the process calculus. This raises the question of whether ensuring properties of processes with type systems implies to restrict one's attention to sequential processes. We present in the following a (work in progress) sketch of a possible Curry-Howard correspondence defined directly for the π-calculus.

A characteristic of the π-calculus is to make a balance between local actions and global actions. Thus, in [START_REF] Milner | The polyadic π-calculus: a tutorial[END_REF] R. Milner defines abstractions (λ x) P and a metaconstruct • called "pseudo-application"; we would like to sketch here a system giving a real status to local actions. A logic fitting with such a system should take advantage from having local cuts like in natural deduction and global cuts as one finds in the sequent calculus. A mechanism of explicit substitutions, known to be related to the cut of sequent calculus, can been defined in the π-calculus: we denote it x ✁ A. This construct, not without similarities with the resource fetching of the blue calculus, is accompanied with abstractions and application (now fully integrated in the calculus). Explicit substitutions are processes and can interact with other processes, but for sake of keeping a local character to the calculus, they only modify the head variables of a process.

For giving the π-calculus a Curry-Howard property, due its modularity, we look for some kind of distributed logic. As processes are spread on different locations, each proof associated to a process is also situated in a particular location. Using a property proven at some place supposes therefore a call to that property under a name, in a way suggested by the usual system of references to lemmas or theorems: Lemma A : . . . Using lemma A, . . . We distinguish between theorems, usually supposed to be used many times, and lemmas, considered here as a resource limited to one use.

The typing rules for processes and abstractions are defined in a mutually recursive way. Abstractions and application correspond to the local notion of cut, as in the following example:

if (λ x, y).P : p, q → r and M : p , N : q then (λ x, y).P • (M, N ) : r

To the global cut, whose usual definition uses limited resource, corresponds the communication in the π-calculus. We give below the typing and its intuitive signification in terms of lemma: a(x, y).P : p, q → r : Lemma a: under hyp. p, q then r.

ā M, N : r (where M : p, N : q) : Use lemma a knowing that p and q then r.

Theorems, though closely related to lemmas, are supposed to behave as infinite resources. They are intuitively associated to explicit substitutions. It should be noticed that this choice of representation actually strongly separates theorems from lemmas and relates them in some extent to abstractions.: a ✁ N : p : Theorem a: p. a • M : q (where M : p) : Apply Theorem a using p then q.

These propositions intend to provide a correspondence between processes and what we call a distributed natural deduction. While the sorts provide a static verification tool, we hope the achievement of this work to bring a better grasp on dynamic properties of the calculus.

Conclusion

We have presented the logical properties of the π-calculus under two aspects: modelchecking, and typing. Many motivations exist for adopting a logical point of view: equivalence, security, time, space, locality, mobility. To various approaches correspond the use of various logics: this is even increased by the numerous variants of the π-calculus. Two comments can be given in conclusion: First, few efficient practical realizations have been yet made in this direction; second, it is not so obvious what best choice of a logical system should be made. An interesting idea would be to allow the fixpoints of the µ-logic or modalities of LTL into the syntax of the logic. This is the direction in which the present work is engaged.