Flavien Balbo
email: flavien.balbo@emse.fr

Neïla Bhouri
email: neila.bhouri@ifsttar.frpinson@lamsade.dauphine.fr

Suzanne Pinson

Bimodal traffic regulation system: a multiagent approach

Keywords: multi-agent systems, urban traffic regulation, bimodal regulation process, Advanced Transit Signal Priority System, microscopic traffic modeling, macroscopic traffic modeling

The development of surface public transportation networks is a major issue in terms of ecology, economy and society. Their quality in term of punctuality and passengers services (regularity between buses) should be improved in order to improve their attractiveness. To do so, cities often use regulation systems at intersections that grant priority to buses. The problem is that each transportation mode has its own characteristics and a dedicated decision support system. Therefore, most of them hardly take into account both public transport vehicles such as buses and private vehicle traffic. This paper proposes a multi-agent model that supports bimodal regulation and preserves monomodal regulation. The objective is to improve global traffic, to reduce bus delays and to improve bus regularity in congested areas of the network. In our approach, traffic regulation is obtained thanks to communication, collaboration and negotiation between heterogeneous agents. We tested our strategy on a complex network of nine junctions. The results of the simulation are presented.

Introduction

The development of surface public transportation networks is a major issue in terms of ecology, economy and society. Traffic jam costs six billions of euros each year. To be more attractive, urban surface public networks must improve their quality in terms of punctuality and vehicle frequency while at the same time they must decrease management costs. Unless the buses operate totally on exclusive or protected rights-of-way, like in the Bus rapid transit approach [START_REF] Zimmerman | Bus rapid transit[END_REF], the quality of surface public transportation service is related to urban traffic.

Without expensive specific infrastructures for buses, an alternative to improve route times of urban public surface transportation (bus, tramways, shuttles, etc.) is to use regulation systems that apply strategies at intersections that grant priority to vehicles. These systems are referred to Advanced Transit Signal Priority Systems (ATSPS) [START_REF] Shalaby | Development, evaluation, and selection of advanced transit signal priority concept directions[END_REF]. They offer one of the most cost-effective approaches to enhance the effectiveness and efficiency of transit operations. The aim of these strategies is to improve the quality of services of public transport vehicles as well as private vehicles that have to cross an intersection. These two types of traffic are referred as bimodal traffic.

Traffic flow can be modeled at a macroscopic level or at a microscopic level following the data used to describe the traffic flow. Microscopic modeling takes into account individual data like the location of each vehicle in order to build a control strategy. This approach is efficient to solve specific traffic problems but is time-consuming and is limited by the availability and cost of these location data. Furthermore, this microscopic model is not well adapted to build real time control strategies for wide urban networks [START_REF] Ling | Automated transit headway control via adaptive signal priority. Special Issue on Modeling for Transit Operations and Service Planning[END_REF]. Macroscopic modeling builds control strategy based on aggregate traffic data like average speed or traffic density. The macroscopic approach is well adapted to regulate a large-scale network but is not adapted to take into account specific needs of vehicles. Furthermore, global representation of bus traffic does not allow more than an indirect consideration of the intervals between buses [START_REF] Bhouri | An intermodal traffic control strategy for private vehicle and public transport[END_REF]. The duality between microscopic and macroscopic models is a wellknown problem in classical control theory used to regulate bimodal traffic (public and private vehicles) [START_REF] Bouamrane | Decision making system for regulation of a bimodal urban transportation network, associating a classical and a multi-agent approaches[END_REF] [25] [START_REF] Papageorgiou | ITS and Traffic Management[END_REF].

Our objective is to build a traffic control strategy for bimodal traffic that takes advantages of microscopic and macroscopic regulation approaches and combines them. Our proposition is a regulation strategy taking into account microscopic data for public vehicle traffic and aggregated data for private vehicle traffic. The main issue is to find the best compromise between individual needs (microscopic regulation objective) and social needs (macroscopic regulation objective).

We propose a multi-agent modeling to process our traffic control strategy. The multi-agent approach is often used to support the design of complex systems where several entities interact on a distributed network and where several decision scales have to be taken into account. This approach is also well adapted to study the effects of individual behavior of an agent on the collective behavior and vice versa. We note that multi-agent systems are increasingly present in the field of traffic regulation and several states of the art have been proposed [START_REF] Bazzan | Opportunities for multiagent systems and multiagent reinforcement learning in traffic control[END_REF] [15] [START_REF] Ferreira | Intelligent agents in decentralized traffic control[END_REF], [START_REF] Kesting | Agents in traffic simulation[END_REF], [START_REF] Li | Cloud computing for agent-based urban transportation systems[END_REF]. Most of the proposals are based on the introduction of multi-agent concepts and processes to improve intersection management i.e. multi-agent learning [START_REF] Bazzan | A review on agentbased technology for traffic and transportation[END_REF], reactive agents [START_REF] Bouamrane | Decision making system for regulation of a bimodal urban transportation network, associating a classical and a multi-agent approaches[END_REF], cooperation [START_REF] Oliveira | Using Cooperative Mediation to Coordinate Traffic Lights: a case study[END_REF], [START_REF] Fehon | Transit signal priority for Silicon Valley bus rapid transit[END_REF], [START_REF] Roozemond | Using intelligent agents for pro-active, real-time urban intersection control[END_REF], [START_REF] Vasirani | A market-inspired approach to reservation-based urban road traffic management[END_REF], multi-agent simulation [START_REF] Kosonen | Multi-agent fuzzy signal control based on real-time simulation[END_REF] or distributed constraint satisfaction problem [START_REF] Mizuno | Urban Traffic Signal Control Based on Distributed Constraint Satisfaction[END_REF]. For ex-ample, in [START_REF] Vasirani | A market-inspired approach to reservation-based urban road traffic management[END_REF], the regulation system is related to traffic assignment using negotiation between vehicles and intersections. However, the above modeling approaches are either partial or too simple to take into account the complexity of bimodal traffic regulation strategies. In order to integrate several control strategies and two levels of control, i.e. microscopic and macroscopic control, we propose a multi-agent modeling of this complex regulation system. Our proposition adapts individual behaviors of buses given by bus agents to collective behavior of vehicles given by aggregate data and vice-versa.

The paper is organized as follows. The second section presents the state of the art of advanced transit signal priority systems. The third section gives a global overview of our proposal from the notions of the domain to multi-agent modeling. The fourth section details how each regulation process is executed i.e. mono and bimodal processes. The fifth section provides the detailed results of the simulation tests carried out on the Jade platform. Finally, we conclude in the sixth section.

State of the art

The first Urban Traffic Control (UTC) system where used to coordinate traffic light on the thoroughfares of the route network. A good survey of the main characteristics of these systems can be found in [START_REF] Daganzo | A headway-based approach to eliminate bus bunching: Systematic analysis and comparisons[END_REF]. Since the 70 th , UTC systems were adapted to include a Transit Signal Priority (TSP) module [START_REF] Furth | Conditional Bus Priority at Signalized Intersections: Better Service Quality with Less Traffic Disruption[END_REF], becoming what is called Advanced Transit Signal Priority Systems (ATSPS).

The use of ATSPS is efficient when traffic is light or when it needs to improve a single congested bus route or buses on cross streets resulting in shorter travel times for buses [START_REF] Kosonen | Multi-agent fuzzy signal control based on real-time simulation[END_REF]. However, they present several pitfalls: longer travel time for crossing traffic and irregular intervals for prioritizing buses at traffic lights in congested conditions. This implies irregular arrival at bus stops, often in bunches. To cope with this problem, operators hold buses at control points to stay on schedule [START_REF] Daganzo | A headway-based approach to eliminate bus bunching: Systematic analysis and comparisons[END_REF]. Won time when crossing lights will be then followed by a holding time at the control point. This action leads to time loss for private cars as well as buses. Reducing the time of bus journey, although very important, is not enough for operating a route. It is just one of the primary factor considered by public transport operators.

To take into account public transport vehicle specificity, another type of regulation system was developed: TRSS (Transportation Regulation Support Systems). TRS systems follow a micro-regulation based approach, i.e. an approach that models the behavior of each bus [START_REF] Balbo | Using intelligent agents for Transportation Regulation Support System design[END_REF], [START_REF] Balbo | Dynamic modeling of a disturbance in a multi-agent system for traffic regulation[END_REF], [START_REF] Belmonte | Ontologies and agents for a bus fleet management system[END_REF], [START_REF] Cazenave | Monte-Carlo Bus Regulation[END_REF]. Unfortunately, TRS systems have the same weaknesses as ATSPS, namely they remain focused on their own regulation issues. The private vehicle traffic flow, that follows a macroscopic model, is hardly taken into account by TRSS. Consequently, we will not focus on this type of system.

Our proposition is based on ATSPS strategies in which we have integrated a bimodal process. In [START_REF] Shalaby | Development, evaluation, and selection of advanced transit signal priority concept directions[END_REF] a comparison of advanced transit signal priority concepts is presented. The authors identified four strategies:

1. Passive priority: this regulation strategy, called macroscopic regulation, takes into account theoretical bus timetables [START_REF] Vincent | Busactuated signal control at isolated intersections --Simulation studies of bus priority[END_REF], [START_REF] Wood | Using SCOOT weightings to benefits strategic routes[END_REF]. This strategy is static and not well adapted to the dynamicity of the traffic. For instance, the priority is given to a bus even if it is already beyond the intersection.

2. Active priority: the location of a bus at an intersection is the event that gives priority to its lane [START_REF] Benevelli | Evaluation of a bus preemption strategy by use of computer simulation[END_REF], [START_REF] Boillot | The real-time urban traffic control system CRONOS, algorithm and experiments[END_REF], [START_REF] Dion | Evaluation of potential transit signal priority benefits along a fixed-time signalized arterial[END_REF], [START_REF] Skarbadoni | Real-Time Monitoring and Control on Signalized Arterials[END_REF]. This priority is automatic and does not take into account the bus timetable. Therefore, the priority can be given to a bus that is already ahead of schedule the consequence being useless delays to non-priority traffic.

Conditional Active Priority:

The priority is given to a bus according to its deviation from the schedule [START_REF] Fehon | Transit signal priority for Silicon Valley bus rapid transit[END_REF], [START_REF] Kimpel | Analysis of transit signal priority using archived TriMet bus dispatch system data[END_REF]. This solution limits the number of buses running ahead of schedule and decreases the useless delays of non-priority traffic. Nevertheless, reducing time of bus journey, although very important for operating a route, is not the only factor taken into account by public transport operators whose obligation is to provide a good service to passengers and to respect bus schedules. Keeping regular intervals between buses strategy is another important issue for transit agencies.

4. Adaptive Priority: in this strategy, the objectives to adjust the traffic signal plan are both to keep regular intervals between buses and to reduce the total bus delay in a lane [START_REF] Chang | Bus preemption under adaptive signal control environments[END_REF] [16] [START_REF] Ling | Automated transit headway control via adaptive signal priority. Special Issue on Modeling for Transit Operations and Service Planning[END_REF]. We chose this promising strategy as the control strategy of our system.

To cope with the drawbacks of previous control systems, we have developed a new model for traffic light management giving priority to buses. In [START_REF] Bhouri | An intermodal traffic control strategy for private vehicle and public transport[END_REF], we gave a previous version of this system with early results. The present paper improves this first work giving a fully integrated system called BDSS (Bimodal Decision Support System)

Bimodal Decision Support System: a global overview

This section gives a global overview of our proposal. We begin with notions of the domain followed by the description of the functional architecture of our bimodal regulation model: we integrate a new decision component called BDSS that links two monomodal regulation decision systems called AVM and UTC (see next section). Finally we describe our multi-agent modeling of these two systems.

Notions of the domain

In our model, the urban network is represented by an oriented graph G= (I, A). The nodes {I} represent the intersections and the arcs {A} represent the lanes that connect the intersections. Two intersections can be connected by one or several arcs depending on the number of lanes on the thoroughfare.

An intersection is specified by the set E of arcs that enter it and the set S of arcs that leave it. Entering arcs are used by corresponding traffic streams (veh/h). Two compatible streams can safely cross the intersection simultaneously else they are called antagonistic. A signal cycle is a repetition of the basic series of signal combinations at a junction; its duration is called time cycle. A stage (or phase) is a part of the signal cycle, during which one set of streams has right of way (r.o.w.) (Fig. 1).

An arc a i corresponds to a lane. It is characterized by static information such as its length L i (in meters), its capacity C i (maximum number of vehicles on arc a i in private car unit, PCU), its saturation output D i which is the maximum exit output from the given arc (in PCU/second), and dynamic information i.e. the number of vehicles N i on the arc (in PCU), the state of the traffic lights at the extremity of the arc (green or red). If the light is green, the vehicles on the arc can depart. By private car unit (PCU), we mean that all vehicles on the arc are converted to their equivalent in private vehicles, for example a bus is 2.3 PCU depending on its length, a truck can be 2.3 or 4 PCU and so on.

Buses on the network are grouped into bus routes. Each bus route contains all bus vehicles which have the same origin, the same destination and that serve a number of predefined commercial bus stops at regular time intervals. The time spent by a bus at a commercial stop is equal to the pre-set time for passengers to mount, plus additional time to regulate the interval, if required.

A constant lost time (or intergreen) of a few seconds is necessary between stages to avoid interference between antagonistic streams of consecutive stages. There are four factors for acting on traffic conditions: the split factor, the time cycle factor, the offset factor and the stage specification factor. 3the offset factor is the stage difference between cycles for successive intersections that may give rise to a "green wave" along an arterial. The specification of the offset strategy should ideally take into account possible vehicle queue formation.

4the stage specification factor is the specification of the optimal number and constitution of stages. For complex intersections involving a large number of streams, the stage specification is a nontrivial task that can have a major impact on intersection capacity and efficiency. To avoid awarding a period of a green oversized, the set of streams having the same volume in term of vehicle number, and having no conflict situations as regards to safety, are gathered in one stage.

The new bimodal strategy that we propose is based on the first two factors, the last two ones are defined by the regulator prior to the control strategy.

Functional modeling of our Bimodal Decision Support System

Even if private vehicles and buses use the same lanes, they have been and often still are regulated by independent systems. Private vehicles are regulated through control strategies executed by the Urban Traffic Control (UTC) system and buses are regulated by means of the Automatic Vehicle Monitoring (AVM) system that is included in a more general systems called TRSS (Transportation Regulation Support System) [START_REF] Balbo | Using intelligent agents for Transportation Regulation Support System design[END_REF][2]. Recent interest in intermodal management as a tool to slow down the progression of private vehicle use encourages the development of multimodal systems. This leads to a research field on multimodal platforms offering services and tools for traffic operators as well as improvement of public transport services by extending Urban Transit Control (UTC) systems with Transit Signal Priority (TSP) (or bus priority). Among the known multimodal platforms, we can cote CLAIRE-SITI [START_REF] Scemama | CLAIRE-SITI, public and road transport network management control, a unified approach[END_REF], ENTERPRICE [START_REF] Riegelhuth | The ENTERPRICE project: a step towards information and mobility management[END_REF], MOBINET [START_REF] Kellermann | MOBINET: Intermodal traffic management in Munich control centre development[END_REF]. Their main objective is to develop an integrated multimodal system in order to assemble heterogeneous components into an integrated and fully operational system. They make it possible the interaction between monomodal systems such as TRS and UTC systems.

As shown in Fig. 2, the functional architecture of our Bimodal Decision Support System (BDSS) is based on these two systems. The AVM and UTC systems keep their initial functionality: following a monomodal process, they collect the on-line data and apply the regulation procedures related to their transportation mode. For instance, the AVM system com-pares the actual positions of buses (captured by sensors) with their theoretical positions given by preregistered timetables in order to detect disturbances and to apply regulation procedures. In this way, the vehicles running ahead of timetable or running late are regulated.

In a bimodal process, data are used by the BDSS to modify traffic regulation procedures given by the UTC without modifying the AVM behavior. The objective of BDSS is to compute new traffic lights plans taken into account requests of buses.

Multi-Agent Modeling

In order to integrate these different systems, we propose a multi-agent modeling of all the regulation components. We propose to integrate agent-based models of AVM, UTC and BDSS in a same model following the functional architecture presented in section 3.2. More precisely, that means that the monomodal process is executed by agents as well as the bimodal process (Fig. 3). This modeling leads to an integrated and homogeneous proposal. The advantage of this approach is the possible comparison of different regulation scenarii by the activation or deactivation of behaviors without a biais introduction of another regulation system. As a microscopic modeling, BAs represent buses that circulate from one arc to another on their route according to their theoretical schedule. They halt at commercial stops, halt at red lights and execute the regulation procedure. The objective of each Bus Agent is to minimize time spent at traffic lights in order to minimize journey time. BAs can only provide a local view of their environment. More precisely, they can only know if they are ahead or late given a theoretical schedule and thus decide to apply what is called logic of punctuality (buses can decide to accelerate or to slow down). This local optimization carried out by Bus Agents can have a negative impact on the route (i.e. formation of bus queues or gap of buses) which has a negative impact on their regularity. To tackle this problem, we propose an agent, called Bus Route Agent, which has a global view of the BAs and which can control and modify their behavior in order to guarantee an efficient and regular service on a route. There are as many BRAs as routes. The interaction between the agents related to buses on the network ensures a monomodal microregulation process of the bus network. Traffic regulation process is based on a macroscopic modeling of vehicles. Each intersection is represented by one IA and several SA. The number of SAs is given a priori by experts according to the intersection topology. The traffic signal plan is elaborated thanks to the collaboration between the IA and the corresponding SAs. Each SA determines the optimal green light split to clear the waiting vehicles on the arcs related to the stage. The aim of the IA is to manage the conflicts between SAs. Thus, whatever the complexity of the intersection is (and its physical configuration), it is managed by a set of Stage Agents interacting with the Intersection Agent in order to develop a plan of actions for the traffic light.

c)

Bimodal Decision Support System (BDSS). By definition, there is a bimodal regulation process when the choice of the regulation procedure takes into account the constraints of two networks. In our proposal, the bimodal regulation process is initiated by a Bus Agent which wants priority and is processed by the Intersection Agent.

The Intersection Agent adapts the plan of traffic lights according to two criteria: 1) the need of the corresponding Stage Agents, which is based on a macroscopic modeling of the global traffic and 2) the priority requests of Bus Agents which are related to the microscopic modeling of buses. The Intersection Agent is therefore the key agent of our architecture.

Mono-modal regulation process.

In this section, we detail the behavior of agents that are related to the monomodal and/or bimodal regulation process. Our proposition being focused on the bimodal regulation process, the monomodal regulation processes have been simplified. For instance, the bus network regulation process is limited to one regulation procedures: a bus waits a computed holding time at a commercial stop if it is ahead in order to eliminate bus bunching. However, since our regulation model is independent of the bimodal regulation process, this regulation model is general, i.e. other regulation procedure could be added as in [START_REF] Balbo | Using intelligent agents for Transportation Regulation Support System design[END_REF] or several traffic regulation strategies can be processed. The novelty of our proposition is that it supports bimodal regulation and preserves monomodal regulation.

Bus network regulation process.

The role of the Bus Route Agent is to supervise Bus Agents so as to prevent a local level regulation and the creation of bus queues (Fig. 4). In order to execute its behavior, the BRA keeps the following data: 1) the set of arcs traveled by the bus on its route; 2) The set of stops on the route, for each stop, its position, and the distance separating it from the next stop; 3) The set of buses on the route; 4) The frequency of buses introduced onto the route.

The interaction between a Bus Route Agent and a Bus Agent begins when approaching a stop A i , The BA j informs the associated BRA with the travel time tt j taken to run the distance that separates the two stops A i-1 and A i . Then the BRA compares tt j to the travel time spent by its preceding bus tt j-1 and consequently decides whether the bus j is ahead or late.

Then this last one calculates the duration of the regulation interval and sends it to the BA. At the stop, the BA must wait during the passenger loading time plus the potential regulation time, before leaving the stop.

Traffic network regulation process

At the end of each cycle, a new traffic signal plan has to be computed. It determines the duration of the green light and the ranking of each stage. The objective is to maximize the capacity of the intersection.

The plan is calculated through the collaboration between the Intersection Agent (IA) and the Stage Agents (SAs). Fig. 5 gives a global overview of the interaction protocol. The IA plays the role of a manager in supervising the SAs that act as participants. The IA uses the following static data:

1) The set of possible values of the traffic light cycle, 120 seconds is the maximum value allowed to the traffic light signal cycle in our system;

2) The lost time i.e. the period of orange or all red. The all red light is a period during which all the arcs from the same intersection have a red light in order to clear the center of the intersection and thus prevent accidents. This fixed period, in conformity with the architecture of the intersection, does not depend on the length of the cycle. It is fixed here to a two second period after each stage;

3) The set of stages of the intersection.

The first part of the protocol is the following: IA sends a message request to the SAs asking them for the time necessary to clear all the vehicles from their stages, beginning at time t for a given traffic light signal cycle duration. Then, each SA computes the desired duration of green light T s (formula 1) and an index I s (formula 3) that measures the urgency of the stage.

The optimal duration of green light (T s ) is computed by the following formula:

= max ,… {T } (1) T = + . ( 2
)
where m is the number of entering arcs at this stage, T i the time necessary to clear arc i, L i the length (in meter) of arc i, V i the average speed (in meter/second) on arc i, N i the number of vehicles (public and private) expressed in private car unit (PCU) and D i the saturation of arc i (PCU/h). The first part of formula 2 ( ) expresses the time needed to evacuate the already formed queue at the traffic light and the second term expresses the time needed to evacuate vehicles entering the arc after the beginning of the green, assuming that they arrive at regular intervals.

When computing the cycle, the IA ranks the stages as in [START_REF] Ferreira | Intelligent agents in decentralized traffic control[END_REF], such that the most congested arcs of the intersection and those which have the greater number of buses are served first. To model this decision, we introduce the urgency index of a stage computed by each SA. This urgency index takes into account the number of buses and the saturation level of the lane with the number of private vehicles through N i and C i the capacity of the lane. This is a bimodal index computation.

) (

0 i i b m i w s e e I + = ∑ = (3)
with w i =N i /C i ∈[0,1] a parameter that indicates the degree of congestion of the arc (when the arc is totally congested, w i =1), b i the number of buses on arc i, m the number of arcs entering at stage j and e the Euler constant.

The higher the index of urgency of a stage is, the greater its urgency is. We can notice that if there are several buses on arc i (if b i > 1), the term e bi is dominant and therefore gives priority to stages with buses; on the contrary, if b i =0, the term e wi is dominant and the degree of congestion, including private vehicles, is then taken into account.

The SA sends the result of its computation to the IA and waits for its decision. If the sum of the opti-mal duration of green light received by the IA is less than the cycle duration (noticed ∆t) then the SA proposals are accepted else a conflict has to be solve. A conflict may appear because each SA computes its optimal green light duration as the time needed to evacuate vehicles on its arcs without taking into account the constraints of the other SAs. The conflict is solved if the SAs accept to reduce the duration of their green light. The consequence for these SAs is that some arcs become saturated (there is not enough time to evacuate the vehicles). The following conflict resolution protocol based on the iterated Contract Net Protocol (second part of the protocol, figure 5) enables IA and SAs to find a solution minimizing the number of saturated arcs:

1-IA initializes cost c: c=1 (c is the number of arcs which will get a penalty if the stage reduces its duration).

Bimodal regulation process

In order to minimize the time spent at traffic lights, Bus Agents request priority when they are late. In our proposal, this regulation procedure is a bimodal regulation procedure that involves AVM and UTC systems. Remember that all buses have to provide a reg-ular service and avoid bus queues. In other words, the frequency of buses passing commercial stops must remain constant. Therefore, at an intersection when there are several buses from different routes requesting priority, the priority has to be given to the most disrupted route thanks to regularity criteria on a same route. To do so, AVM ranks bus requests. Moreover, the priority should not have negative consequences on the urban traffic. Consequently, the UTC has to compute a new traffic signal plan taking into account the bus request. Therefore the bimodal regulation process is the result of the interaction between a BA (the initiator), its BRA (the AVM part) and the IA (the UTC part). Fig. 6 gives a summary of the general interaction protocol between a Bus Route Agent, a Bus Agent and an Intersection Agent.

In the next sections we first detail how the BAs compute their requests then we explain how the IA takes the requests into account and adapts the traffic signal plan.

Bus request

A late BA approaching an intersection sends a request to its BRA with the value of its delay. The BRA informs the BA with its level of priority that is a function of the predecessor bus delay: the greater the delay is, the higher the priority is.

To request priority, the BA has to compute a timewindow when its request has to be satisfied. On entering arc i at t 0 , the BA retrieves information from the arc (the number of vehicles that precede it, the length, capacity, and exit output of the arc). With these data, the BA computes a time-space request that is transmitted to the IA in order to prevent an eventual stop at the red light at the next intersection.

Let R be the requested interval, R contains the interval [t b , t e ], with t b and t e the beginning and ending times of the request interval.

The computation of t b is carried out as follows: the bus enters the arc at t 0 and finds N v vehicles ahead of it, the vehicles move to the traffic lights lane to wait for the green light thus forming a queue of length Q (Fig. 7). In order to continue along its route, the queue of vehicles has to be cleared before it arrives. The green light should thus be granted at the arc at the instant:

t b = t 0 + T -T Q (5)
with T the time necessary for the bus to cover the distance D between the beginning of the arc and the end of the queue, and T Q the time necessary to clear queue Q.

The value of t e is computed with the addition to t b of a constant given by traffic experts. Given these values, a reservation request is specified as follows: R = (t b , t e , a i , a j, Priority), with a i the arc where the bus is located and a j the next arc to be traveled by the bus. This request is sent to the IA managing the intersection (Fig. 6). IA's behavior is presented in the next section.

Traffic light plan adaptation

To compute its answer, the Intersection Agent (IA) uses two types of dynamic data. The first is related to the traffic signal plan: it specifies the order of the stages as well as the duration of each stage and is dynamically computed as explain in section 4.2. The second is the list of received reservation requests from Bus Agents.

When the IA receives a request from a BA, it finds the SA associated thanks to the recorded a i and a j values and replaces them by the SA identification.

The request is then recorded in its database. Two solutions exist to modify a traffic signal plan following a priority request by a Bus: 1) extension or reduction of a stage (delay or advance), without exceeding the maximal duration of a stage; 2) introduction of a new stage into the plan.

Since several buses can request priority at the same time, the Intersection Agent has to solve conflicts. It is explained using the following example (Fig. 8) in which the intersection has a plan with four stages (P 1 to P 4 ) and two antagonistic bus requests (R 1 and R 2 ). In this example, in the initial traffic signal plan, the order of stages is P 2 during 20 seconds, P 1 and P 3 during 30 seconds each and finally P 4 during 20 seconds. At time t 1 , the IA receives a first request R 1 (P 2 , t 3 , t 4 , 2) which means that bus #1 is asking for stage P 2 . It needs a green light at this stage during the interval [t 3 ,t 4 ] and it has a priority index of "2". The IA doesn't plan this request immediately but waits until the start time t 3 . R 1 is computed at time t 3 (start time) and not at time t 1 (received time), because during this delay, the IA may receive other reservations. In this example, at time t 2 , it receives another reservation, R 2 from bus #2 which has a level of priority equal to 4 and requests the stage P 4 . Since it is not possible to satisfy both requests because they involve overlapping stages (P 4 and P 2 ), the IA gives the stage to the bus with the highest priority index R 2 , i.e. bus #2. This planning process is fundamental to regulate bus intervals.

Experimentation and results

To test our proposal, we have developed a Multi-Agent System prototype on the JADE 1 platform (Java Agent Development Framework). JADE offers Java middleware based on a peer-to-peer architecture with 1 jade.tilab.com/ the overall aim to provide a runtime support for agents.

The prototype network (Fig. 9Erreur ! Source du renvoi introuvable.) consists of 9 intersections and 50 arcs. Each arc is 300 meter long. Most of the network sections have one lane except for sections I1-I2 and I2-I3 which have 2 lanes in the same direction. Each lane is considered as an independent arc. The saturation flow, which is the maximum exit output of the arcs, is considered the same for each arc and equal to 0.5vehicle/second. The network has 12 entries. At each entry, the simulation platform generates vehicles with different frequency going from 1 vehicle generated every 5 seconds (720 veh/h) to 1 vehicle generated every 10 seconds (360 veh/h) which is a standard for an urban network. Most intersections are working on two stages, except for intersections I2 and I3 which have three stages.

We consider two bus routes on the network: BR1 and BR2. A Bus route is defined by : -The identification of the arcs. In our example, Bus Route BR1 consists of arcs {23, 10, 4, 11, 35, 31} (see Fig. 10) -The identification of commercial bus stops (i.e.

A11 stop, A12 stop, etc.), the arc on which they are situated, their position on the arc (i.e. A11 stop is situated at 100 meter from the beginning of arc 23, A12 is situated at 150 meters from the beginning of arc 10, etc.) and their control waiting time, which is the strategic waiting time imposed to buses by the Bus Route Agent at the corresponding commercial stop (in our example, the successor bus vehicle must wait for 30 seconds at bus stop A12 Fig. 10) The frequency of generated buses. It is equal to 50 seconds on Bus Route 1 (Fig. 10) and to 40 seconds on Bus Route 2.

In the next section we present a comparison between our bimodal strategy (called MAS Strategy) and two other strategies: 1) Fixed Time Strategy: the duration of all stages is fixed; 2) Without Priority Strategy: the duration of stages is dynamically computed (section 4.2) but buses do not request priority. These delays correspond to the sum of time lost by buses (resp. vehicles) during stops at traffic lights. Figure 11.a shows that, on the simulation period, the MAS strategy improves bus travel time (cumulated bus delays) by 85% compared to the Fixed Time Strategy whereas the Without Priority Strategy improves buses traffic by only 76%. Figure 11.b shows interesting results: Without Priority Strategy and MAS Strategy give same cumulated delays for private vehicles. They both improve vehicles delays by 30%. Thanks to the MAS Strategy, the average delay (lost time) of buses is equal to 23 seconds, when it is equal to 2.6 minutes with the Fixed Time Strategy. Considering these two results, we can conclude that MAS Strategy is the best one since it improves significantly bus traffic as well as private vehicles traffic, and, using bus priority, helps traffic regulation.

Simulation results at junction level

In this section, we study the MAS Strategy at a microscopic level: the intersection level. We choose I2 and I3 intersections (see Figure 9). Each of them has 3 stages (see figure 14). As for I2, bus routes use arcs which need different stages: Bus Route 2 needs the stage S2_1 however Bus Route 1 needs either S2_2 or S2_3 to cross the intersection I2. This means that these two bus lines are conflicting if two buses at the same time ask for priority. Intersection I2 will have to solve a conflicting situation as explained in Section 6.

As for I3, both bus routes can cross the intersection either when S3_1 or S3_2 have the right of way. The two buses are not conflicting. So we can expect better time to cross the intersection. 1 gives the average travel time for vehicles on BR1, first between bus stops A12 and A13, showing the impacts of the three strategies on intersection I2 traffic, and then between stops A13 and A14, showing the situation on intersection I3. For vehicles on BR2, travel time is measured between a23 and a24 and then between a22 and a23. One can notice that the MAS strategy improves bus travel time even for intersection I3, whereas as explained before, buses can cross I3 on two stages among the three ones available and hence can cross quickly. We can also notice that MAS Strategy succeeds to suppress the delays on this intersection, as if there is no congestion, the minimum time needed to travel the 300 meters separating the two bus stops a22 and a23 is 27 seconds. On intersection I2, where buses can run only on one stage, benefits of MAS Strategy on travel time are more important. They are equal to 27% for BR1 and 28% for BR2. Figure 12 (respectively Figure 13) gives bus delays for BR1 (respectively BR2) buses at junction I2 and I3. The X axis represents the bus numbers generated by the simulation. We can see on these figures that another advantage of MAS strategy is that it preserves regularity of travel time (delays stay nearly constant) across these intersections.

Stages of Intersection I2

Strategies TT(s) Gain TT(s) Gain TT(s) Gain TT(s) Gain

Conclusion

In this paper, we have proposed a bimodal traffic regulation system based on a multi-agent system. Unlike other approaches, our model takes into account both public transport vehicles such as buses and private vehicle traffic and studies the regulation in a whole network. The objective of this research is to improve global traffic, to reduce bus delays and to improve bus regularity in congested areas (keeping regular interval between buses) of the network. In our approach, traffic regulation is obtained thanks to communication, collaboration and negotiation between heterogeneous agents at different levels of abstraction and at different level of granularity (microscopic vs macroscopic level). Firstly, we have shown that classical methods of traffic regulation present several weaknesses. Secondly, we have presented our multi-agent model that supports bimodal regulation and preserves monomodal regulation. Following a multimodal point of view, our multi-agent system computes dynamically traffic signal plans and at the same time ensures bus network regulation. When bimodal regulation is needed, our multi agent system computes traffic signals plans based on the real-time traffic situation and on priority given to buses. Thirdly, we have run a simulation prototype on the JADE platform. The results show that our MAS strategy with priority improves both buses travel time and buses regularity. Our results also show that this bimodal MAS strategy improves buses as well as private vehicles traffic and reduces bus delays. Further work needs to be done: a more realistic network should be defined in the simulation run and more validation and testing should be undertaken with the definition of several indicators. It would also be interesting to have more testing to find Pareto front and multi-criteria optimization in order to get equilibrium between public transport delays and private traffic delays.

Fig. 1 :

 1 Fig. 1: Example of an intersection with 3 stages1the split factor is the relative green duration of each stage (as a portion of the time cycle) that should be optimized according to the demand of the involved streams and, in our context, as regard to bus priorities 2the cycle factor: a longer time cycle increases the intersection capacity because the proportion of the constant lost time becomes accordingly smaller. On the other hand, a longer time cycle may increase vehicle delays in under-saturated intersections due to a longer waiting time during the red phase.3the offset factor is the stage difference between cycles for successive intersections that may give rise to a "green wave" along an arterial. The specification of the offset strategy should ideally take into account possible vehicle queue formation.4the stage specification factor is the specification of the optimal number and constitution of stages. For complex intersections involving a large number of streams, the stage specification is a nontrivial task that can have a major impact on intersection capacity and efficiency. To avoid awarding a period of a green oversized, the set of streams having the same volume in term of vehicle number, and having no conflict situations as regards to safety, are gathered in one stage.The new bimodal strategy that we propose is based on the first two factors, the last two ones are defined by the regulator prior to the control strategy.

Fig. 2 :

 2 Fig. 2: Bimodal Decision Support System Architecture

Fig. 3 :

 3 Fig. 3: Multi-agent modeling of a bi-modal regulation process

  b)Urban Traffic Control (UTC) system. Two types of agent ensure the monomodal regulation of the traffic network: Stage Agent (SA) and Intersection Agent (IA).

Fig. 4 .

 4 Fig. 4. Supervision of bus agents by the bus route agent.

Fig. 5 .

 5 Fig. 5. AUML traffic signal plan calculation protocol

Fig. 6 .

 6 Fig. 6. General interaction protocol

Fig. 7 .

 7 Fig. 7. Reservation of green light duration by a bus

Fig. 8 .

 8 Fig. 8. Example of a traffic signal plan and its modification

Fig. 9 .

 9 Fig. 9. The simulated network

Fig. 10 .

 10 Fig. 10. Definition of Bus Route 1 6.1. Simulation results at network level Figures 11 gives simulation results of the three strategies. Fig 11.a shows the recorded delays for buses with the three control strategies and Fig 11.b shows the same kinds of curves for private vehicles.

Fig. 11 .

 11 Fig. 11.a. Buses cumulated delays

Fig. 12 .

 12 Fig. 12.a. Buses travel time on BR1 on Intersection 2

Fig. 14 .

 14 Fig. 14. Stages of I2 and I3 and arcs used by buses

Table 1 :

 1 Average travel time (TT) between the two bus stops around the junctions I2 and I3 for BR1 and BR2. TT is expressed in seconds

Table


domain: info.info-au math spi sdv

text:
Pierre Bernhard
email: pierre.bernhard@inria.fr

Marc Deschamps
email: marc.deschamps@univ-fcomte.fr

Céline Savard

Sylvain Béal Marc Deschamps

On dynamic games with randomly arriving players

Keywords: Dynamic game, Bernoulli process of entry, Oligopoly JEL classification : C72, C61, D21, L13

We consider a dynamic game where additional players (assumed identical, even if there will be a mild departure from that hypothesis) join the game randomly according to a Bernoulli process. The problem solved here is that of computing their expected payoff as a function of time and the number of players present when they arrive, if the strategies are given. We consider both a finite horizon game and an infinite horizon, discounted game. As illustrations, we discuss some examples relating to oligopoly theory (Cournot, Stackelberg, cartel).

Introduction

In most strategic interactions analysis the set of players is known and common knowledge. But there are some situations where neither the players, nor the designer or public authority, nor the theorist know how many players are in a game. As an illustration, consider the three situations below:

Example 1 Imagine the case of a company that commits a violation of competition rules (which identically affects consumers) in a country where consumers can take joint action in court to recover the amount of their losses. The legal system chosen by the country as part of a joint action works as follows: in the first period a consumer enters the court, in the second period the judge analyses the case. If he finds it justified, he evaluates the total harm done1 , and imposes a reimbursement and a payments schedule for each month of a third period. But during that third period, more complainants may apply to join the action, given that the judge will not approve more than one per month. The monthly reimbursement is then shared equally among all complainants approved at that time. What is the first consumer-victim expected payoff according to the fact that he does not know how many victims will participate in the joint action as each victim can alternatively choose to never suit or suit individually the company?

Example 2 Consider the case of a city where the authorities issue a number of permits to individuals so that they can transport by car, for a fee, people in the city. There are k individuals who have such an authorization. Then, thanks to technological innovation, a company is able to transform every willing motorist driver into a transporter of people for fee. How much individuals k who have the permission of the city can expect, knowing that they do not know how many motorists will be turned into drivers?

Example 3 Suppose that a French rich entrepreneur decides to create the "René and Gisèle Foundation" to promote the research in game theory. This foundation, thanks to the proceeds of a charitable donation, appoints a benevolent research director (free of conflicts of interest) to share each month equally a sum of 100.000 euros between all scientific projects in game theory which she has examined and fond valuable. As the entrepreneur and the research director want to provide a long term support, they decide to never abandon the funding of a project that she had already selected. After the beginning of the foundation, where k ≥ 1 projects could have been selected, each month, due to administrative procedures, only one new project could be added to the foundation's public list of selected projects (which mentions the date of arrival in the list of each selected project). How much the m -th selected project can expect to have?

The goal of this paper is to provide a general mathematical framework for computing the payoff of players in a dynamic game with clone players randomly arriving at each step of time in a Bernoulli process. The paper is organized as follows: in the next section we expose the theoretical related literature and explain how we contribute to the question of games with an unknown number of players. In section 3, we formulate the problem, propose a model and give the expected payoff of finite (Theorem 1) and infinite (Theorem 2) horizon game, that is the expected payoff for each player. Then in Section 4 we provide some examples from oligopoly theory where this framework and results could be used to find expected payoff and static equilibria. Section 5 concludes by underlining the limits and questions of our framework which are left for future research.

Related literature

It is well known that the usual-textbook game theory toolbox is in the the "fixed-n" paradigm and so provides directly no solution to problems where there is a degree of uncertainty on the number of players in a game. Indeed, in Bayesian games, the uncertainty is on the type of each other player's, that is on their private information about their characteristic represented by a random variable for each player. So there is no uncertainty on the number of players in the game, the uncertainty is on their characteristics. Moreover to extend Bayesian games to games with unknown number of players raises conceptual and modelling issues that could not be overcome. However, to the best of our knowledge, there exists currently in game theory two ways to directly manage the question of uncertainty on the number of players in a game.

The first strain of literature, which is the oldest one, is the study of games where the active competing players is not common knowledge. This issue has taken two forms (see [START_REF] Levin | Auctions with uncertain number of bidders[END_REF]). The first form models the number of active players with a stochastic process on a set of potential players. It means that the active players is a subset of the common knowledge potential players, which implies that each player has a private information (he is active or not). The timing of this kind of game is usually in four-step: 1/ nature chooses which players will be active (and whose those will be passive), 2/ each player observes only his own situation, 3/ the active players choose their strategies, and 4/ payoffs are received. The common knowledge information is the set of potential players and the probability distribution used by the nature to assign a role to each player. The second form endogenizes the entry process. In this setting, at first, there is no player in the market. Then, there is the assumption that each potential player (the total set of which is common knowledge) has a privately known and different cost to entry on the market, and each of them must decide to participate or not into the game. These two kinds of models are useful in a great number of cases. For example, consider the situation of an appointment of Dean at a University, the applicants do not know how many persons will apply even if they perfectly know how many persons can apply (the set of Professors in the University). It is also the case, for example, in online auction sites where the number of registers is known and the number of bidders for each product is ex ante unknown.

Seminal articles in this line of literature are [McAfee and McMillan, 1987a] and [Matthews, 1987] which demonstrate that some results of auction theory could be sensitive to the assumption that there is a stochastic number of bidders, which means that the set of real bidders is not common knowledge whereas the set of potential bidders is. They also allow the bidders to have different priors on how many bidders are present as long as these priors are Bayesian consistent. From the design policy point of view these articles open the question wether the seller had an interest to reveal (or conceal) the number of actual bidders and their identities. In [START_REF] Piccione | A simple model of expert and non expert bidding in first price auctions[END_REF] the number of potential bidders is common knowledge but some of them are experts (bidders with private information) and some are nonexperts (bidders with no private information), and it is the number of experts which is uncertain for the seller and the other buyers. [START_REF] Münster | Contests with an unknown number of contestants[END_REF] offers a study of rent-seeking contests with an unknown number of competing contestants where all players are risk neutral or have constant absolute risk aversion. Complementing to the pure risk approach, [START_REF] Salo | Ambiguity aversion in first-price sealed bid auctions[END_REF] and [START_REF] Levin | Auctions with uncertain number of bidders[END_REF] propose models where bidders are adverse to the ambiguity generated by the lack of information about the number of rivals in the auction. On the entry process endogenous side, [Samuelson, 1985] finds that policies to limit the number of bidders may be welfare improving. When a first-price sealed bid auction is used and bidders can enter upon paying an entry cost, [McAfee and McMillan, 1987b] show that the seller should not impose a reserve price higher than his own valuation and that the optimal number of bidders enter. More recently, there has been investigations on environmental topics as in [START_REF] Rubio | An infinite-horizon model of dynamic membership of international environmental agreements[END_REF] or [START_REF] Breton | A dynamic model for international environmental agreements[END_REF]Keoula, 2012].

The more recent other strain of literature is games with population uncertainty, where the real number of players in the market is not common knowledge. But the number of players really in the game is supposed to be drawn from a random variable, whose probability distribution and mean are commonly known. Players have to choose their strategies before the player set is revealed. Among these games, a special attention has been served to the sub-class called Poisson games, where the number of players N is a random variable that follows a Poisson distribution with mean n (so N = k with the probability e -n n k k! ), and each player's type is then drawn independently from some fixed probability distribution. More generally, in extended Poisson games the expected population sizes and players' utility functions may depend on an unknown state of the world. In this case there is a two-stage structure: first a random state variable is drawn from some given distribution, and then a Poisson game is played. In theses games, each player's belief about the number of other players and their types is the same with the prior distribution of the total number of players and their types (property called by Myerson environmental equivalence). It has been show that Poisson games modelling has very nice mathematical features, subsume Bayesian games with consistent priors and open a fertile field of research. To illustrate the nature of questions solved by it [De Sinopoli and Pimienta, 2009] introduces the following simple and clear story: "A player is sitting at home and faces two possible alternatives, either she goes out to some social event, or she stays home. She does not know how many players are facing this same disjunctive, but she knows that this number is a Poisson random variable with parameter n. If she goes out and meets somebody she receives a payoff equal to 1. If she meets nobody or decides to stay home, she gets a payoff equal to 0. Every player faces these same two options and has the same preferences". This type of modelling was introduced by [START_REF] Myerson | Population uncertainty and Poisson games[END_REF], [Myerson, 1998a], [Myerson, 2000] and [Milchtaich, 2004]. See also [De Sinopoli et al., 2014] for a more recent account. It seems particularly well adapted to elections (where each voter does not know what is the real number of voters, see Myerson's works) or some kind of auctions. [Makris, 2008] proposes to model the coordination problem as a Poisson game and investigates the conditions under which a unique equilibrium is selected. In [Ritzberger, 2009] it is shown that with population uncertainty, two competitors are not enough to eliminate all profits in equilibrium and have competition in a Bertrand game. Recently, [ Östling et al., 2011] proposes an application of Poisson game to a LUPI game (lowest unique positive integer wins lottery), in order to study a lottery called Limbo introduced by the governmentowned Swedish gambling monopoly Svenska Spel on January 29, 2007.

By contrast with these two lines of literature, the spirit of our paper is a dynamic framework where the number of players involved varies with time, and to study the expected payoff of each player in situations where nobody knows ex ante the set of real players at each period after the beginning and at the end of the game (finite case), or at each period of the game (infinite case). The only information that are common knowledge before the game actually starts in our setup are the size of the market, the number of incumbents and that there is a random entry at each period of time according to a Bernoulli process of known parameter. Once the game is going, the actual number of players present at each stage is also common knowledge at that stage. So there is no asymmetric information in our model. We will consider a clone economy, i.e an economy where the incumbents and the new entrants are perfectly identical. Even though there is an equilibrium at each step, our aim at this stage will not be to define a dynamical equilibrium, but to compute the expected payoff to the players when their strategic behaviors are given. Therefore we have a sequence of static equilibria, but not a dynamic equilibrium. (See nevertheless appendix D).

In the rest of the literature on games, but with a fixed number of players, we may find some kinship of our theory with repeated games, since the folk theorem, for instance, involves an infinite sequence of plays with the same strategies, as we do. But there, it is the same set of players who play again and again. The fact that in the present theory, the payment matrices vary from step to step is reminiscent of stochastic games, see e.g. [START_REF] Neyman | Stochastic games[END_REF] or, more recently, the special issue [START_REF] Nowak | Special issue on stochastic games[END_REF]. However, we are not, at this stage, able to prove a result about a stationary dynamic equilibrium, as often found in that strain of literature.

Finally, the literature the closest to our theory that we are aware of may be that of piecewise deterministic systems [Davis, 1985, Haurie et al., 1994], although this is not in a game theoretic framework. But we may consider the stochastic arrivals of players as stochastic jumps in the dynamic system, which is deterministic between two jumps. We show in appendix D how that theory could be put to use to compute a dynamic equilibrium. But at this stage, applying these ideas to concrete examples seems out of reach.

Model

The family of problems we are investigating could have two forms. As in our examples 1 and 3, there are cases where the dynamic game has an end which corresponds to a finite horizon. There are also cases, as in our example 2, where the dynamic game has no finite end-time or, more realistically, where the end-time is unknown for the players, which corresponds to the infinite horizon case. We will study these two types of games successively.

We consider a discrete time, multistage game where time t is an integer varying from t 1 to T (finite horizon), or from 0 to ∞ (infinite horizon). We assume that additional players may arrive only one at each discrete instant of time, this with a probability p and independently from other arrivals (a Bernoulli process), and let t m be the first stage where there are m players, i. e. the stage when player number m arrives.

Usually, in a dynamic game there is a state x(t) ∈ R n whose dynamics are driven by the actions a i (•) of the players, according to some given law

x(t + 1) = f (t, x(t), a 1 (t), a 2 (t), . . . a n (t)) , x(t 1 ) = x 1 .
Then the payoff of each player is

Π i = T t=t 1 L i (t, x(t), a 1 (t), a 2 (t), . . . , a n (t)) .
If the a i are mixed strategies, then L i is a mathematical expectation.

However, here the emphasis is not on the strategies but on computing an expected payoff when the strategies are assumed identical for all players, and known as a function of the number m of players present, the state, and current time. In that case, a sufficient description of the state is the sequence {t n } n≤m of past arrival times, and current time t. As a consequence, we may dispense with the explicit dynamics, and write the payoff as a function of these variables. We also assume that the players are identical not only in their strategy choices, but also in their per stage payoff. (The latter justifies the former. We will however see a marginal deviation from that hypothesis in our examples.) Their payoffs will only differ because of their different arrival times.

Notation Let τ 1 = t 1 , and for m ≥ 2, τ m = (t 2 , . . . , t m ) ∈ N m-1 , and therefore τ m+1 = (τ m , t m+1 ). Let L m (τ m , t) be the per stage payoff of each player when m players are present. Let also m(t) be the number of players present at time t .

We introduce the further notation M 1 (t) = L 1 (t), and, for m ≥ 2,

T m (t) = {τ m | t 1 < t 2 < • • • < t m ≤ t} , M m (t) = τm∈Tm(t)
L m (τ m , t) .

(in the infinite horizon case, we will use t 1 = 0). For example,

M 2 (t) = t t 2 =t 1 +1 L 2 (t 2 , t) , M 3 (t) = t-1 t 2 =t 1 +1 t t 3 =t 2 +1 L 3 (t 2 , t 3 , t) .
We may provide a graphical representation of what is going on. All possible entrance histories, for a finite horizon, can be represented on a tree as in figure 1. Time is shown on the bottom line. At each instant of time, and at each node of the tree for that instant, we draw a branch going up if a new player enters at that time instant, going down if nobody enters. We have chosen t 1 = 0, shown four time steps, and labelled the nodes with the number of players present upon reaching this node (during the time step ending there). We have noted over each branch the per stage payoff of each player during the corresponding time step.

An history is represented by a path from the root of the tree (to the left) to a leaf. The payoff for that history is the ("horizontal") sum of the per stage payoffs noted on each branch of its path (τ m is denoted with a list of time instants between curly braces). For each m and t, M m (t) is the ("vertical") sum of the L m of stage t, i.e. the sum of the markings of the branches of the stage beginning at t reaching a node labelled m.

One can read on this graph that:

M 1 (0) = L 1 (0) , M 1 (1) = L 1 (1) , M 2 (1) = L 2 ({1}, 1) , M 1 (2) = L 1 (2) , M 2 (2) = L 2 ({1}, 2) + L 2 ({2}, 2) , M 3 (2) = L 3 ({1, 2}, 2) , M 1 (3) = L 1 (3) , M 2 (3) = L 2 ({1}, 3) + L 2 ({2}, 3) + L 2 ({3}, 3) , M 3 (3) = L 3 ({1, 2}, 3) + L 3 ({1, 3}, 3) + L 3 ({2, 3}, 3) , M 4 (3) = L 4 ({1, 2, 3}, 3) . ✲ t 0 1 2 3 s 0 ✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪ ✪ L 1 ( 0 ) 1 ❝ ❝ ❝ ❝ ❝ ❝ ❝ ❝ L 1 ( 1 ) 1 ★ ★ ★ ★ ★ ★ ★ ★ L 2 ( { 1 } , 1 ) 2 ❛ ❛ ❛ ❛ ❛ ❛ ❛ ❛ L 1 ( 2 ) 1 ✦ ✦ ✦ ✦ ✦ ✦ ✦ ✦ L2 ( { 2 } , 2 ) 2 ❛ ❛ ❛ ❛ ❛ ❛ ❛ ❛ L 2 ( { 1 } , 2 ) 2 ✦ ✦ ✦ ✦ ✦ ✦ ✦ ✦ L3 ( { 1 , 2 } , 2 ) 3 ❵ ❵ ❵ ❵ ❵ ❵ ❵ ❵ L 1 (3 ) 1 ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ L2 ({ 3} , 3) 2 ❵ ❵ ❵ ❵ ❵ ❵ ❵ ❵ L 2 ({ 2} , 3) 2 ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ L3 ({ 2, 3} , 3) 3 ❵ ❵ ❵ ❵ ❵ ❵ ❵ ❵ L 2 ({ 1} , 3) 2 ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ L3 ({ 1, 3} , 3) 3 ❵ ❵ ❵ ❵ ❵ ❵ ❵ ❵ L 3 ({ 1, 2} , 3) 3 ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ L4 ({ 1, 2, 3} , 3) 4
Caption:

L m (τ m , t): per stage payoff m: number of players τ m : sequence of past arrival times t: current time Figure 1: The events tree

Finite horizon

To better take into account the different arrival times of the players, we introduce an explicit discount factor r ≤ 1, and write the payoff of the n-th player arrived as

Π n (τ n ) = T t=tn r t-tn L m(t) (τ m(t) , t) .
Both m(t) and τ m are random variables. Hence we let

Π e n (τ n ) = EΠ n .
We will prove the theorem:

Theorem 1 The expected payoff of the discrete time, finite horizon game for player 1 is

Π e 1 = T t=t 1 [r(1 -p)] t-t 1 t-t 1 +1 m=1 p 1 -p m-1 M m (t) .
(1)

We observe that thus the dependence of the per stage payoff on the sequence of arrival times has been lumped into the sequence of M m . This is directly related to the fact that, for a Bernoulli process, at the number m of positive events given, all sequences of m arrival times share the same (conditional) probability. Accordingly, the dependence of the expected payoff on the per stage probability of arrival p is through the probabilities p m-1 (1 -p) t-t 1 -m+1 of having m -1 arrivals between t 1 + 1 and t.

The fact that Π e 1 is decreasing in p, necessarily true, is not obvious in the formula (it depends on the evaluation of the M m to be seen further down). Yet, it appears clearly that the limit expected payoff as p goes to zero is just

Π e 1 = T t=t 1 r t-t 1 L 1 (t) ,
as the term m = 1 only remains in the sum over m.

Proof of the theorem The proof of the theorem is given in appendix A.1. It is based upon a rather classical backward induction argument, and interchanges of orders of summations in the resulting formulas.

We may also write the equivalent formula for the payoff of the m-th arriving player. We need to introduce extra notation. For 1 ≤ m < k:

τ k m = (τ m+1 , . . . , τ k ) , T k m (t m , t) = {τ k m | t m < t m+1 < • • • < t k ≤ t}. and M m m (τ m , t) = L m (τ m , t) and M k m (τ m , t) = τ k m ∈T k m (t) L k (τ m , τ k m , t) .
Given m and t m , the maximum possible number of players is m + T -t m . By a computation similar to the one leading to the theorem, we get:

Corollary 1 The payoff of the m-th arriving player, given the sequence of arrival times τ m , is

Π e m (τ m ) = T -tm ℓ=0 p 1 -p ℓ T t=tm+ℓ [(1 -p)r] t-tm M m+ℓ m (τ m , t) ,
or, equivalently

Π e m (τ m ) = T t=tm [(1 -p)r] t-tm t-tm ℓ=0 p 1 -p ℓ M m+ℓ m (τ m , t) .
(2)

Infinite horizon

The same set up is used to consider the game with an infinite horizon, i.e. a payoff

Π 1 = ∞ t=0 r t L m(t) (τ m(t) , t) .
We need two new definitions:

Definition 1 The sequence of functions {L m } is said to be 1. uniformly bounded if it has a uniform bound, denoted L:

∃L > 0 : ∀t ∈ R + , ∀m ∈ N , ∀τ m ∈ T m (t) , |L m (τ m , t)| ≤ L ,
2. exponentially bounded if each L m is uniformly bounded, but that bound is allowed to vary exponentially with m:

∃L > 0 : ∀t ∈ R + , ∀m ∈ N , ∀τ m ∈ T m (t) , |L m (τ m , t)| ≤ L m .
The relationship of these properties depends on the position of L with respect to 1:

Remark 1

1. If the sequence {L m } is uniformly bounded, it is also exponentially bounded, thus uniformly bounded is a stronger property than exponentially bounded. Indeed, let L be the uniform bound, the sequence is exponentially bounded by

L m if L > 1, by 1 m = 1 if L ≤ 1.
2. If the sequence {L m } is exponentially bounded by L m with L < 1, it is also uniformly bounded by L. However, if L > 1, it may not be uniformly bounded.

We prove the following theorem:

Theorem 2 If the sequence {L m } is exponentially bounded by L m and r < 1/L, or if it is uniformly bounded, then the expected payoff of the infinite horizon game is given by

Π e 1 = ∞ t=0 ((1 -p)r) t t+1 m=1 p 1 -p m-1 M m (t) .
(3)

Proof The proof, given in appendix A.2, is via taking the limit in formula 1, and carefully checking that the infinite series converge.

We derive the following consequences:

Corollary 2

• If the sequence {L m } is exponentially bounded by L m with 1 ≤ L < 1/r, then |Π e 1 | ≤ L 1 -rL ,
• if the sequence {L m } is uniformly bounded by L, then

|Π e 1 | ≤ L 1 -r ,
• if the L m are constant and equal to L, and p = 0, then

Π e 1 = L 1 -r .
We may similarly extend formula (2) to an infinite series, which converges under the same conditions:

Corollary 3 The infinite horizon payoff of the m-th arriving player is, under the same conditions as in theorem 2:

Π e m (τ m ) = r tm ∞ t=tm ((1 -p)r) t-tm t-tm ℓ=0 p 1 -p ℓ M m+ℓ m (τ m , t) .

Applications to oligopoly theory

We consider identical firms entering a market. The game will be played over an infinite horizon, with a discount factor r. We investigate four different market structures, differing in the type of equilibrium -cartel or competitive à la Cournot-hypothesized at each stage, and in the behavior of the incumbents and of the new entrant each time one arrives. The four possible market structures will be called "cartel-cartel", "cartel-Stackelberg", "Cournot-Cournot", and "Cournot-Stackelberg", and will be explained in more detail below.

The per stage profits for the various equilibria considered are computed in the appendix B.

4.1 Cartel-cartel, or equally sharing a fixed revenue flux

In this simple case, the incumbents form a cartel, and each arriving new firm enters the cartel. If the optimum per stage profit feasible by a lone player on this market is c, we have L m (τ m , t) = c/m. We assert Theorem 3 In the cartel-cartel market structure, the expected payoff to the first player is

Π e 1 = c pr ln 1 + pr 1 -r . ( 4
)
We are therefore able to get a closed form formula. It exhibits the limit expected payoff Π e 1 = c/(1 -r) as p goes to zero, and Π e 1 → ∞ as r → 1 for fixed p. That it is decreasing with p can be seen in the fact that the function

x → ln(1 + x)/x is decreasing for x ∈ [0, 1]. Proof of theorem 3 The cardinal of the set T m (t) is |T m (t)| = t m -1 = t! (m -1)!(t -m + 1)! we obtain M m (t) = c t! m!(t -m + 1)! = c t + 1 t + 1 m ,
and hence, applying formula (3),

Π e 1 = c ∞ t=0 r t (1 -p) t 1 t + 1 t+1 m=1 t + 1 m p 1 -p m-1 = c pr ∞ t=0 r t+1 (1 -p) t+1 t + 1 1 + p 1 -p t+1 -1 .
It suffices to recognize the identity, for x < 1:

∞ n=1 x n n = -ln(1 -x)
to conclude the proof.

It is possible to compute the expected payoff of the m-th arriving player, but we see little hope of simplifying it beyond the sheer repetition of the formula:

Π e m (τ m ) = cr tm-t 1 ∞ t=tm [r(1 -p)] t-tm t-tm ℓ=0 1 m + ℓ (t -t m )! ℓ!(t -t m -ℓ)! p 1 -p ℓ ,
or the slightly more appealing formula, that exhibits the independence of Π e m from τ m :

Corollary 4 The payoff of the m-th arriving player in the cartel-cartel market structure is

Π e m (τ m ) = cr tm-t 1 ∞ n=0 r n n! n ℓ=0 1 m + ℓ p ℓ ℓ! (1 -p) n-ℓ
(n -ℓ)! .

Cartel-Stackelberg

In this market structure, in the absence of a new entrant, firms form a cartel. However, whenever a new firm enters the market, the incumbents still play as a cartel, but act as leaders imposing their strategy on the new entrant who acts as a follower, in a Stackelberg scheme. The table in the appendix shows that we may equivalently assume that the incumbents do not take immediate notice of the new entrant, or do not take it seriously, and continue with the same production level as before.

After a first step in that configuration, the new entrant joins the cartel for the rest of the game. It is not its best interest. But it may be coerced to do so by the other players who threat to revert otherwise to an all Cournot-Nash equilibrium. As soon as m > 6, they incur a loss in doing so, but not as much as the new entrant. It is therefore a credible threat. The difference with the cartel-cartel time structure is displayed by the simple time diagrams of Figure 2, where we have assumed, for clarity, that t m-1 < t m -1, i.e. there was no new entrant at time t m -1.

✲ t m -1 players t m m players t m +1 Cartel (m -1) Cartel (m) Cartel (m) or (m+1) ✲ t m -1 players t m m players t m +1 Cartel (m -1) Stackelberg (m-1 vs 1) Cartel (m) or Stackelberg (m vs 1)
According to the table in the appendix, we have, for some positive number c:

L m (τ m , t m ) = c 2(m -1) , ∀t ∈ [t m + 1, t m+1 -1] , L m (τ m , t) = c m .
We state the following theorem:

Theorem 4 The expected payoff of the cartel-Stackelberg scheme for the first player is

Π e 1 = c 1 + 2 -p 2p ln 1 + pr 1 -r .
Although slightly more complicated than in the cartel-cartel scheme, this formula shares with the former one most of its characters: a closed form formula, exhibiting even more clearly its decreasing character with p, and converging to V = c/(1-r) as p → 0, and V → ∞ as r → 1.

Proof The proof, given in appendix A.4 involves a careful analysis of the combinatorics of the problem, and application of the previous formulas.

Finally, the payoff to the m-th arriving player at time t m can be derived from the corresponding formula of the simple sharing problem, just correcting for the fact that at its first step, it earns c/4 rather than c/m.

Corollary 5

The payoff of the m -th arriving player in the cartel-Stackelberg market structure is

Π e m (t m ) = r tm-t 1 c 4 - c m + c ∞ n=0 r n n! n ℓ=0 1 m + ℓ p ℓ ℓ! (1 -p) n-ℓ
(n -ℓ)! .

Cournot-Cournot

We now assume that at each time step, the firms compete in a Cournot fashion.

With reference to the diagrams of Figure 2, we now have that of Figure 3

L m = C (m + 1) 2 .
We also assume a discount factor r as in the above theory. A direct application of the general theory leads to Theorem 5 The expected payoff of the first player in the Cournot-Cournot market structure is

Π e 1 = C ∞ t=0 r t (1 -p) t t n=0 p 1 -p n t! (t -n)!n! 1 (n + 2) 2 .
(5) This is not a very appealing formula. Yet, it is easy to program, even on a spreadsheet, to get a numerical approximation, computing the terms recursively. Write

u(t) = r t (1 -p) t , v n (t) = p 1 -p n t! (t -n)!n! 1 (n + 2) 2 , Π e 1,C = C ∞ t=0 u(t) t n=0 v n (t) ,
and compute the u and v n according to the recursions u(0) = 1, v 0 (t) = 1/4, ∀n > t, v n (t) = 0, and, for n ≤ t, t ≥ 1:

u(t) = r(1 -p)u(t -1) , v n (t) = p 1 -p n + 1 n + 2 2 v n-1 (t -1) + v n (t -1) .
Computing up to the fiftieth term, with r = .8, we found, for p = 1/4, Π e 1,C = .822 C, for p = 1/2, Π e 1,C = .625 C, and for p = 3/4, Π e 1,C = .508 C. (To get the same precision, the computation requires the more terms that p is smaller. With 50 terms, for p = 0, we get Π e 1,C = 1.249986 instead of the theoretical 1.25. These computations were performed on a spreadsheet LibreOffice.)

Cournot-Stackelberg scheme

We consider a scheme similar to that of the cartel-Stackelberg, but where firms compete à la Cournot-Nash instead of forming a cartel, both in the absence of a newcomer, and within the group of incumbents when a new firm enters the market. As in the cartel-Stackelberg structure, the behavior of the incumbents may be explained as ignoring the newcomer at the first step. Then (as soon as m ≥ 2), all players profit from a reversal to the all Cournot-Nash equilibrium.

The time diagram is now as in Figure 4 ✲ t m -1 players

t m m players t m +1 Cournot (m -1) Stackelberg (m-1 vs 1) Cournot (m) or Stackelberg (m vs 1)
L m (τ m , t m ) = C 2m 2 , ∀t ∈ [t m + 1, t m+1 -1] , L m (τ m , t) = C (m + 1) 2 .
The analysis is completely similar to that of the cartel-Stackelberg scheme, replacing the L m as necessary, and leads to the following theorem:

Theorem 6 Let Π e 1,C be the Cournot expected payoff (5). The expected payoff of the Cournot-Stackelberg scheme for the first player is

Π e 1,CS = r(2 -p) 2 Π e 1,C + C .
We may notice that the relationship of this formula to the preceding one is the same as the corresponding one in the cartel case. It preserves the same properties as outlined above.

Conclusion

In this paper, we have analyzed a model where there is, for everyone, an unknown number of players. We have assumed that all the players are clones (since they adopt the same strategy and had the same payoff at each period of time) and that demand market and entry device (Bernoulli process) are common knowledge. Players' payoff differ from each other only due to the time during which they are in the market. In this setting we are able to calculate the payoff of each player in finite and infinite horizon games. Four simple examples in microeconomics show that the theory is indeed operative. The formulas obtained are not very simple, but they allow for efficient numerical implementations.

Yet, we may point out a set of weaknesses of the theory, each of which points to possible further investigations.

• We are limited to a clone economy. Dealing with an unlimited number of players, the game has to be anonymous. But we might want to have several classes of players, such as done in many studies of population uncertainty and anonymous games.

• To keep with the simple formulas of the Bernoulli process, we impose a constant entry probability p. It would be more realistic to have it depend on the number of players already on the market, as the benefit of entry decreases with that number. This is chiefly true in our examples where the size of the market is constant. This would lead to exceedingly complex formulas, hardly implementable, except may be if we let p be a constant up to a certain number of players and drop to zero afterward.

• In our four examples, the players' per stage payoff depend on the number of players, and only very mildly on the sequence of past arrival times. (In the one-step Stackelberg games, where we need to distinguish the case t = t m from the case t > t m .) A more complex dependence such as alluded to at the beginning of section 3, say because a resource is consumed by the players, requires, to remain manageable by our theory, that it be explicit enough to let us compute the sums M m . A rather severe restriction on the models we are able to deal with.

• We do not allow for players randomly leaving the market. Yet, in many applications, this would be more realistic.

But as it is, the theory can probably be used as a Rubinstein "fable" ( [Rubinstein, 2006, Rubinstein, 2012]) to investigate some real life economic problems.

For m ≤ T -t 1 and a compatible τ m , we have

J m (τ m ) =              T t=tm r t-tm L m (τ m , t) if t m+1 > T , t m+1 -1 t=tm r t-tm L m (τ m , t) + r t m+1 -tm J m+1 (τ m , t m+1 ) if t m+1 ≤ T .
Now, t m+1 > T with a probability (1 -p) T -tm , and the occurrence of a given t m+1 ≤ T has a probability p(1 -p) t m+1 -tm-1 . Hence, writing t + for t m+1 :

Π e m (τ m ) = (1 -p) T -tm T t=tm r t-tm L m (τ m , t) + T t + =tm+1 p(1-p) t + -tm-1 t + -1 t=tm r t-tm L m (τ m , t) + r t + -tm Π e m+1 (τ m , t + ) .
Introduce the notation q = 1 -p. Interchanging the order of summation,

Π e m (τ m ) = q T -tm T t=tm r t-tm L m (τ m , t)+ T -1 t=tm r t-tm L m (τ m , t) T t + =t+1 pq t + -tm-1 + T t + =tm+1
pq t + -tm-1 r t + -tm Π e m+1 (τ m , t + ) .

Using classical formulas for the sum of a geometric series, and regrouping terms we obtain for m ≤ T -t 1 :

Π e m (τ m ) = T t=tm q t-tm r t-tm L m (τ m , t) + pr t m+1 -tm Π e m+1 (τ m , t + 1) ,
being agreed that Π e m+1 (τ m , T + 1) = 0. A more useful form of this formula for the sequel is as follows:

Π e m (τ m ) = T t=tm (qr) t-tm L m (τ m , t)+ p q T t m+1 =tm+1 (qr) t m+1 -tm Π e m+1 (τ m , t m+1 ) , (6)
where the second term of the right hand side is absent if

t m = T . Remark 2 It is a not-so-easy calculation to check that, if L m (τ m , t) ≤ L and Π e m+1 (τ m , t m+1 ) ≤ (T -t m+1 + 1)L, then this formula implies, as it should, Π e m (τ m ) ≤ (T -t m + 1)L.
A hint about how to make the above check is as follows: in the second term of the formula, write

T t=tm+1 q t-tm (T -t + 1) = T -t m + 1 -(1 -p) d dp T t=tm+1 (1 -p) t-tm ,
and use the classic formula for the sum of the (finite) geometric series.

We use formula ( 6) recursively: write first Π e 1 as a function of Π e 2 , and using again the same formula substitute for Π e 2 as a function of Π e 3 , and again for Π e 3 as a function of Π e 4 . Then interchange the order of the summations, placing them in the order t, t 2 , t 3 , t 4 . In the following formula, every time the lower bound of a sum is larger than the upper bound, the term is just absent. We obtain

Π e 1 = T t=t 1 (qr) t-t 1 L 1 (t 1 , t) + p q T t=t 1 +1 (qr) t-t 1 t t 2 =t 1 +1 L 2 (t 1 , t 2 , t) + p q 2 T t=t 1 +2 (qr) t-t 1 T t 2 =t 1 +1 t t 3 =t 2 +1 L 3 (t 1 , t 2 , t 3 , t) + p q 3 T t 2 =t 1 +1 T t 3 =t 2 +1 T t 4 =t 3 +1 (qr) t 4 -t 1 Π e 4 (t 1 , t 2 , t 3 , t 4 ) .
Continuing in the same way up to m = T -t 1 + 1, we obtain

Π e 1 = T -t 1 m=1 p q m-1 T t=t 1 +m-1 (qr) t-t 1 M m (t) + p q T -t 1 (qr) T -t 1 L T -t 1 +1 (T ) .
The last term can be identified as the term m = T -t 1 + 1 of the first sum, as the range of t in the embedded (second) sum is limited to t = T , and we have seen that

L T -t 1 +1 (T ) = M T -t 1 +1 (T ).
It suffices now to shift m by one unit to obtain the formula

Π e 1 = T -t 1 +1 m=1 p 1 -p m-1 T t=t 1 +m-1 [(1 -p)r] t-t 1 M m (t) .
And interchanging a last time the order of the summations, formula (1). Remark 3 As a consequence of formula (1), if for some fixed L, for all m, τ m and

t, L m (τ m , t) = L, then Π e 1 = [(1 -r T -t 1 +1 )/(1 -r)]L (whose limit as r → 1 is (T -t 1 + 1)L), and if L m (τ m , t) ≤ L, then Π e
1 is bounded above by that number.

A.2 Proof of theorem 2

We start with formula (1) where we set t 1 = 0, and recall by a superscript (T ) that it is a formula for a finite horizon T , the horizon we want to let go to infinity:

Π e 1 (T ) = T t=0 (1 -p) t r t t+1 m=1 p 1 -p m-1 M m (t) .
The only task left to prove the theorem is to show that the series obtained as T → ∞ converges absolutely. To do this, we need an evaluation of M m (t). Observe that the cardinal of the set T m (t) is simply the combinatorial coefficient

|T m (t)| = t m -1 = t! (m -1)! (t -m + 1)! . As a consequence, if |L m | ≤ L m , we have |M m (t)| ≤ t m -1 L m and t+1 m=1 p 1 -p m-1 M m (t) ≤ t+1 m=1 p 1 -p m-1 |M m (t)| (7) ≤ t+1 m=1 t m -1 p 1 -p m-1 L m (8) = L p 1 -p L + 1 t . (9)
Therefore,

(1 -p) t r t t+1 m=1 p 1 -p m-1 |M m (t)| ≤ Lr t (pL + 1 -p) t .
The series converges absolutely provided that r p(L -1) + 1 < 1 , which is always true if L ≤ 1, and ensured for all p ≤ 1 if rL < 1. This proves the theorem for the case exponentially bounded.

In the case uniformly bounded, with |L m | ≤ L, we obtain similarly

|M m (t)| ≤ t m -1 L and (1 -p) t r t t+1 m=1 p 1 -p m-1 |M m (t)| ≤ Lr t (1 -p) t p 1 -p + 1 t = Lr t ,
and the series is always absolutely convergent.

A.4 Proof of theorem 4

We aim to apply formula (3). The term t = 0 requires a special treatment: the only term in the sum over m is m = 1 and M 1 (0) = L 1 (0) = c. For t > 0, we have three cases: 1. For m = 1, there has not been any new entrant, therefore L 1 (t) = c. 2. For 1 < m < t + 1, we sum first over the τ m such that t m < t, i.e. τ m ∈ T m (t-1), then over the τ m such that t m = t; there the sum is over the values of τ m-1 ∈ T m-1 (t -1). 3. For m = t + 1, there have been new entrants at each time step. Therefore L t+1 (τ t+1 , t) = c/2t. We summarize this in the following calculation:

for m = 1 , M 1 (t) = c = c (t -1)! (m -1)!(t -m + 1)! 1 m , for 1 < m < t + 1 , M m (t) = τm∈Tm(t-1) c m + τ m-1 ∈T m-1 (t-1) c 2(m -1) = c (t -1)! (m -1)!(t -m + 1)! 1 m + c (t -1)! (m -2)!(t -m + 1)! 1 2(m -1)
,

for m = t + 1 , M t+1 (t) = c 2t = c (t -1)! (m -2)!(t -m + 1)! 1 2(m -1)
.

We therefore obtain, for t > 0:

t+1 m=1 p q m-1 M m (t) = t m=1 p q m-1 (t -1)! (m -1)!(t -m)! c m + 1 2 t+1 m=2 p q m-1 (t -1)! (m -2)!(t -m + 1)! c m -1 = 1 + p 2q t m=1 p q m-1 (t -1)! (m -1)!(t -m)! c m .
Finally, summing over t as in formula (3), without forgetting the term t = 0,

Π e 1 = c + 1 + p 2q ∞ t=1 r t q t t m=1 p q m-1 (t -1)! (m -1)!(t -m)! c m .
It suffices to take out one power of rq from the sum over t, shift the summation index by one unit, recognize the expected payoff of the simple sharing scheme and replace it by formula (4) to prove the theorem.

B Static equilibria

We consider n identical firms (a clone economy) sharing a market with a linear inverse demand function, linking the price P to the total production level Q as P = b -aQ .

Production costs have been lumped into b and so doing normalized at zero. We compute the optimal production level Q, and resulting price P and profit Π of each firm for various equilibria.

B.1 Cartel

In a pure cartel, firms behave as a single player, only sharing the optimal production level equally among them. Let Q be that level. The profit of the (fictitious) single player is

Π = Q(b -aQ) = -a Q - b 2a 2 + b 2 4a .
Hence the optimal production level is Q = b/(2a), to be equally divided among the firms, as well as the profit Π = b 2 /(4a). The price is then P = b/2, and the individual production level q and profit Π i are

q = b 2an , Π i = b 2 4an .

B.2 Cartel-Stackelberg

We investigate the case where n -1 firms form a cartel, behaving as a leader vis à vis one firm acting as a follower. Let q L be the quantity produced by each incumbent, q F that of the follower. Hence Q = (n -1)q L + q F . The follower's profit is

Π F = q F [b -a(n -1)q L -aq F ] = -a q 2 F - b a -(n -1)q L q F hence Π F = -a q F - 1 2 b a -(n -1)q L 2 + a 4 b a -(n -1)q L 2 .
Therefore, the optimal reaction curve q F as a function of q L is

q F = 1 2 b a -(n -1)q L .
With such a strategy, each incumbents' profit is

Π L = q L b -a(n -1)q L - 1 2 b - 1 2 a(n -1)q L ) = - a(n -1) 2 q 2 L - b a(n -1) q L = - a(n -1) 2 q L - b 2a(n -1) 2 + b 2 8a(n -1)
.

Therefore, the optimal production level of each incumbent and their profit are

q L = b 2a(n -1) , Π L = b 2 8a(n -1)
.

Placing this back into the optimal follower's reaction curve, its production level and profit are

q F = b 4a , Π F = b 2 16a .
and the price of the commodity is P = b/4. All these results will be summarized in a table in the last section.

B.3 Cournot-Nash

We have n identical firms competing à la Cournot. The Cournot-Nash equilibrium is obtained as follows. Let q be the individual production level, therefore Q = nq, and P the resulting price:

P = b -naq .
The individual profit of player i is

Π i = q i [b -a(q i + (n -1)q)] = -a q i - 1 2 b a -(n -1)q 2 + a 4 b a -(n -1)q 2 .
It follows that the optimum q i is

q i = 1 2 b a -(n -1)q ,
but we seek a symmetric equilibrium where q i = q, and therefore

q = b (n -1)a .
Placing this back into the law for P , we find

P = b (n + 1) , Π = b 2 a(n + 1) 2 .

B.4 Cournot-Stackelberg

We finally consider n -1 firms competing à la Cournot-Nash within their group, producing a quantity q L each, but that group behaving as a leader vis à vis a single follower, producing a quantity q F . We therefore have

P = b -a(n -1)q L -aq F .
The calculations are similar to the previous ones. The follower's profit is therefore

Π F = -a q 2 F - b a -(n -1)q L q F = -a q F - 1 2 b a -(n -1)q L 2 + a 4 b a -(n -1)q L 2 . Hence q F = 1 2 b a -(n -1)q L , Π F = a 4 b a -(n -1)q L 2 .
With this strategy,

P = 1 2 b -a(n -1)q L = 1 2 b -a(n -2)q L -aq i
Consequently, for player i, one of the leaders,

Π i = - a 2 q 2 i - b a -(n -2)q L q i = - a 2 q i - 1 2 b a -(n -2)q L 2 + a 8 b a -(n -2)q L 2 .
It follows that

q i = q L = 1 2 b a -(n -2)q L ⇒ q L = b an , Π i = a 8 b a -(n -2)q L 2 ⇒ Π i = b 2 2an 2 ,
while P = b/(2n), and

q F = b 2an and Π F = b 2 4an 2 .

B.5 Summary

We regroup the results of these calculations in the following table:

Market structure # of firms Quantity Price Profit Cartel n b 2an b 2 b 2 4an Cartel-Stackelberg n 3b 4a b 4 each leader n -1 b 2a(n -1) b 2 8a(n -1) follower 1 b 4a b 2 16a Oligopoly à la Cournot n b a(n + 1) b (n + 1) b 2 a(n + 1) 2 Cournot-Stackelberg n b(n + 1/2) an b 2n each leader n -1 b an b 2 2an 2 follower 1 b 2an b 2 4an 2

C Complexity

In this appendix, we undertake to count the number of arithmetic operations involved in computing Π e 1 for a finite horizon by four different methods: (direct) path enumeration, backward dynamic programming, path enumeration and forward dynamic programming, and use of formula (1). To ease the calculations, we let t 1 = 1, so that T is the number of time steps. We shall refer to the tree of Figure 1. If we assume no regularity in their definition, the data is made of the collection of all L m (t), t = 1, . . . , T , that is as many numbers as there are branches in the tree, i.e. T t=1 2 t-1 = 2 T -1 numbers. As all must be used, there is no way in which a general method could involve less than that number of arithmetic operations. Therefore, we expect a complexity of the order of 2 T (of the order of 10 6 for T = 20, and 10 15 for T = 50, a completely unrealistic case !), and the difference between methods can only be in the coefficient multiplying that number.

C.1 Path enumeration

The tree counts 2 T -1 paths from the root to a leaf. Let ν ∈ [1, 2 T -1 ] number them. We denote by π ν the path number ν, and let m ν be the number of player present at the end of path π ν . Each path has a probability of being followed

P(π ν ) = p mν -1 (1 -p) T -mν . Let L ν (t) denote the L n (τ n , t) on path π ν . Each path involves a payoff Π 1 (π ν ) = T t=1 L ν (t) .

And we have

Π e 1 = 2 T -1 ν=1 P(π ν )J(π ν ) . (10)
A direct method of evaluating Π e is therefore as follows:

1. compute the P(π(ν)) for each ν. The computation of each involves T -2 multiplications2 . Therefore that step involves 2 T -1 (T -2) arithmetic operations. 2. Compute the Π(π ν ). Each involves T -1 additions, therefore this step involves 2 T -1 (T -1) arithmetic operations. 3. Compute Π e 1 according to formula (10), involving 2 T -1 multiplications and as many additions (-1), that is 2 T operations. Therefore the total number of arithmetic operations is

N = 2 T -1 (T -2 + T -1 + 2) = (T - 1 2 )2 T ,
that is of the order of T 2 T .

C.2 Dynamic programming (DP)

Denote the nodes of the tree by the sequence σ(t) of t indices, 0 or 1, the 1 denoting the times when an arrival occurred, a branch sloping up in our figure . (All sequences σ(t) begin with a one.) The possible successors of a given σ(t) are (σ(t), 0) and (σ(t), 1), that we denote as

σ(t + 1) = (σ(t), i(t)) , i(t) ∈ {0, 1} .
Denote by L(σ(t)) the L m of the branch reaching the node σ(t).

C.2.1 Backward DP

Let V (σ(t)) be the expected future payoff when at node σ(t). It obeys the dynamic programming equation

V (σ(t)) = p[L(σ(t), 1) + V (σ(t), 1)] + (1 -p)[L(σ(t), 0) + V (σ(t), 0)] ,
and Π e 1 = V (root) = V (1) + L 1 (1). There are thus four arithmetic operations to perform at each node of the tree (not counting the leaves), that is

N = 4 T t=1 2 t-1 = 4 × (2 T -1)
arithmetic operations, i.e. of the order of 4 × 2 T .

C.2.2 Path enumeration and forward DP

This is a variant of the path enumeration method (10) on two counts:

1. Compute once each probability p m-1 (1 -p) T -m and store it. This costs T (T -2) arithmetic operations. 2. Compute the Π(π ν ) according to the forward dynamic programming method Π(σ(t -1), i(t -1)) = Π(σ(t -1)) + L(σ(t -1), i(t -1)) . This is one addition at each node of the tree, i.2. 2 T operations. It remains to implement formula (10), using 2 T arithmetic operations, for a total of 2 T +1 + T (T -2). This is of the order of 2 × 2 T .

C.3 Using the M m (t)

We rewrite formula (1) as

Π e 1 = T t=1 t m=1 p m-1 (1 -t) t-m M m (t) . (11)

C.4 Conclusion

Our theory gives the fastest algorithm for this general "unstructured" case, half as many algebraic operations as in the next best. But of course, its main advantage is elsewhere, in allowing one to take advantage of any regularity in the definitions of the L m , and also in allowing for closed formulas for the infinite horizon case. Formula (4) is a typical example.

A general remark is that going from the "direct" method, in T 2 T arithmetic operations to one with a constant coefficient, in a typical computer science tradeoff, we trade computer time for storage space. However, if the L m need to be stored as data (as opposed to being given by some explicit formula), then in all the faster methods, they are used only once so that their memory space can be re-used for intermediate results.

D Dynamic Nash equilibrium

We have stressed that, in our applications, we seek an equilibrium at each time step. But our process is then a sequence of static equilibria, not a dynamic equilibrium. As stated in the main body, our theory does not address the determination of a dynamic equilibrium. In the finite horizon case, it is possible to extend the theory to encompass a dynamic equilibrium, computed retrogressively à la Isaacs, using (a discrete time parallel of) the theory of piecewise deterministic systems.

(See [Sworder, 1969, Davis, 1985, Haurie et al., 1994]). But we see little applicability of that extended theory. We give a short account of it here for the sake of completeness.

Let U (t) be a set of possible decisions at time t for the (identical) players. We consider situations where the focal player, say player 1, uses the decisions a(t) ∈ U (t), and all other players decisions b(t) ∈ U (t). This suffices according to Isaacs' tenet of transition (Bellman's optimality principle), because all players present at a given time face the same game problem regarding the future, regardless of when they arrived. Let α(t) be the sequence of decisions u(s) of player 1 from s = t 1 up to s = t -1, and β(t) the sequence of decisions of all other players, also up to time t -1. (And for t ≤ t 2 , we set b(t) = nil.) Let L m (τ m , α(t), a, β(t), b, t) be the per stage payoff of the players. (It could also depend on α(t) and β(t).) Instead of the expected payoff Π e m , introduce a family of Value functions V m defined for t ≥ t m :

V m (τ m , α(t), β(t), t) .

Nash equilibrium strategies a ⋆ (•) must satisfy the maximum being reached at a = a ⋆ . This recursion, initialized at V m (•, •, •, T ) = 0 , may theoretically allow one to compute the Value functions V m and the equilibrium decisions.

V
Of course, this simplifies if the dependence of the L m on τ m , α and β is through a state equation such as hinted at at the beginning of our section 3. But even so, we see little applicability of that theory. One exception might be in the very un-natural case of an infinite horizon problem with such a state living in a finite dimensional (or better: finite) space, where U is constant, and where the L m are of the form L m (α(t), a, β(t), b, t) = r t s m L(x(t), a 1 , a 2 , . . . , a m ) .

Let V m (x(t), t) = r t s m W m (x). Then the above equation takes the form of a modified Shapley equation:

W m (x) = max a∈U L m (x, a, a ⋆ , . . . , a ⋆ ) + prsW m+1 (f (x, a, a ⋆ , . . . , a ⋆ ))

+ (1 -p)rW m (f (x, a, a ⋆ , . . . , a ⋆ ) .

Figure 2 :

 2 Figure 2: The time diagrams of the Cartel-Cartel (top) and Cartel-Stackelberg (bottom) market structures

Figure 3 :

 3 Figure 3: The time diagram of the Cournot-Cournot market structure

Figure 4 :

 4 Figure 4: The time diagram of the Cournot-Stackelberg market structure

  m ({α(t), a ⋆ (t)}, {β(t), a ⋆ (t)}, t) = max a∈U (t) L m (τ m , α(t), a, β(t), a * (t))+ pV m+1 ({τ m , t}, {α(t), a}, {β(t), a ⋆ (t)}, t + 1) + (1 -p)V m (τ m , {α(t), a}, {α(t), a ⋆ (t), t + 1) .

On the one hand, in a joint action, this country chooses to charge the total harm to the liable party. On the other hand, it allows each victim not to prosecute, prosecute individually or collectively. It thus follows that the liable party can be led to pay several times the damage which she caused: these are punitive damages.

we count powers as a sequence of multiplications

C.3.1 Computing the M m (t)

The first task is to compute the collection of M m (t). For each t, there are 2 t-1 L m (t) to combine in t terms, that is 2 t-1 -t additions. There is no computation for the steps 1 and 2. The total number of additions there is therefore

We set

We compute them according to the following method:

Counting the arithmetic operations, this leads to T -1 multiplications to compute the u 1 (t), and to

multiplications to compute the rest of the u m (t). That is for this step

Finally, there are T (T +1)/2 terms in formula ( 11), each involving a multiplication and an addition, i.e. T (T + 1) arithmetic operations (minus one addition) Summing all steps, this is

i.e. of the order of 2 T arithmetic operations, half as many as in the best DP method.