Road Pricing Design Based on Game Theory and Multi-agent Consensus

Nan XiaoXuehe Wang Lihua Xie Tichakorn Wongpiromsarn Emilio Frazzoli Daniela Rus

I.INTRODUCTION

TRAFFIC congestion causes significant efficiency losses,wasteful energy consumption and excessive air pollution.This problem arises in many urban areas because of the continual growth in motorization and the difficulties in increasing road capacity due to space limitations and budget constraints.As a result,traffic management that aims at maximizing the efficiency and effectiveness of road networks without increasing road capacity becomes increasingly crucial.A case study on the traffic system in California shows that transportation pricing such as congestion pricing,parking pricing,fuel tax pricing,vehicle miles of travel fees and emissions fees can better manage the transportation system to a great extent[1].As another example,the electronic road pricing(ERP)system in Singapore charges motorists when they use certain roads during the peak hours in order to maintain an optimal speed range for both expressways and arterial roads[2−3].The road pricing system is typically implemented for two main objectives.First,it is designed to affect the routechoice behaviors.For example,the charges on expressways motivate motorists to use alternative,less congested,arterial roads even though it comes at the cost of extra travel time.Second,road pricing is enforced on many of the roads in the city area in order to refrain the motorists from using those roads during the peak hours as no alternative route with cheaper rate is possible.Hence,a significant portion of the motorists will either turn to public transportation or rearrange their schedules to avoid entering the city during the peak hours.A comprehensive review of the design and evaluation of road pricing schemes can be found,for example,in[4−5].Note that each motorist usually selects his or her trip routing and trip timing behavior by myopically optimize his or her own utility as a function of road price.At the same time,each motorist may collectively communicate with his or her friends and neighbors on traffic situation from time to time.Therefore,game theory and consensus theory provide a natural framework for road pricing design.

Game theory deals with strategic interactions among multiple players,where each player tries to maximize his or her own utility[6−7].It is applied in a broad array of areas including economics,social science,engineering,etc.For any non-trivial game,the utility of each player depends on choices or actions of at least one other player and generally of all the players.Nash equilibrium,a fundamental concept in the realm of noncooperative game theory,is defined as the action pro file of all players where none of the players can improve his or her utility by a unilateral move.It essentially characterizes the user optimal situation,where the utility function of every myopic player reaches a local optimum.

In this paper,we consider repeated games where in each stage,the players are allowed to choose their actions based on the available information.Generally,players need to learn the underlying structure of the game by observing the decisions made by other players,especially when players have only limited or even no knowledge of their opponents′utilities.Fictitious play and its variants are classical learning processes studied extensively in the literature.In a standard fictitious play,each player computes the empirical frequencies of the observed decisions and assumes that all other players make decisions independently according to those empirical frequencies[8].Several counterexamples show that fictitious play needs not converge[9−10].However,it has been proved by using a Lyapunov stability approach that convergence is possible under some non-singularity conditions if we have either a zero-sum game,an identical interest game,or a twoplayer/two-move game[11].It is also known that the empirical frequencies generated by fictitious play of a potential game converge to a mixed strategy Nash equilibrium[12].One obvious shortcoming of fictitious play is that when the number of players is large,it is computationally infeasible to obtain the best response for each player,since the best response of a player depends on a mapping over a joint action space of other players.See Section II for more details.

As a variant of fictitious play,a joint strategy fictitious play(JSFP)alleviates the informational and computational burden of standard fictitious play by introducing a utility updating process for each player[8,13].Different from standard fictitious play,in the JSFP,each player assumes that all other players make decisions jointly according to their joint empirical frequencies.Also see Section II for more details.In the case of the JSFP with inertia,the convergence to a pure strategy Nash equilibrium is established for all generalized ordinal potential games[13].

Note that in the realm of noncooperative game theory[7],no cooperation is allowed among the players.In contrast,the selection of actions is done collectively with full trust in the realm of cooperative game theory,e.g.,consensus.For a group of agents,consensus means to reach an agreement on a quantity of interest which depends on the state of every agent[14].There has been a lot of research on discretetime consensus.Consensus conditions and convergence speed for discrete-time multi-agent networks with fixed topology were explored in[14].Necessary and suf ficient conditions on consensus over random networks were provided in[15−16].In[17−18],discrete-time average-consensus under switching network topologies was analyzed.Further,the work in[19−20]gave consensus convergence rates in dynamically changing environments.

In[21],a continuous-time distributed protocol was proposed to estimate the number of active players at each stage.Under this structure,a best response path algorithm was established for a finite noncooperative game.Such an algorithm generated a sequence of joint decisions obtained by a single player′s unilateral improvement from previous stage which eventually converged to a Nash equilibrium.Furthermore,a discretetime consensus protocol under a fixed network topology was designed in[22]to estimate the percentage of active players and allow the best response strategy to converge to a unique Pareto optimal Nash equilibrium.However,these results can only be applied to binary strategies.

The contributions of this paper can be summarized as follows.First of all,we present a new variant of fictitious play called average strategy fictitious play(ASFP)and prove its convergence for a congestion game under some reasonable assumptions.Note that the computational burden of each player in the JSFP mainly comes from the utility updating process and increases with the number of possible actions.The ASFP proposed in this paper reduces the computational burden of the JSFP by getting rid of the utility updating process.In the ASFP,each player only obtains a weighted running average of all other players′actions and assumes that the total number of other players choosing one action is equal to the weighted running average corresponding to this action.In addition,we formulate a multiple choices congestion game under random networks,and a consensus protocol is implemented to estimate the number of players selecting each resource without the system surpervisor′s broadcasting.The convergence property of underlying congestion game with or without broadcasting is established.

Secondly,we apply the results to the road pricing problem.The road pricing system is typically implemented for affecting motorists′route choices[23−24]and trip timing choices[3,28].We formulate the trip timing problem as a congestion game.Congestion game as a special case of potential game was f i rst introduced in[26],where a collection of homogeneous agents had to choose from a finite set of alternatives and the payoff of a player depended on the number of players choosing each alternative.Different from[26],players′utilities are heterogeneous in this paper.

Preliminary results of this paper were reported in[27−28].The remainder of the paper is organized as follows.Section II summarizes a series of notations and some pertinent work,and also provides the model setup of this paper.Sections II and III establish the theoretical framework of this paper.The structure and the convergence property of the ASFP with broadcasting is given in Section II.In Section III,a consensus protocol is introduced and the convergence to a pure Nash equilibrium is also proved.In Section IV,the results are applied to the design of road pricing scheme,and simulations based on the real traffic data in Singapore are also included.Finally,Section V concludes the paper and discusses the future work.

II.NOTATIONS,RELATED WORK,AND MODEL SETUP

Consider a repeated finiteN-player game with the set of players N={1,2,···,N}over consecutive stagest=0,1,2,···.For anyi∈N,−idenotes the complementary set N{i}.The action of playeriat stagetis denoted byxi(t)∈Xi,andXiis the action set.For the rest of the paper,argumenttmay be omitted when no confusion is caused.Letx=(xi,x−i)represent the action pro file of all the players.Herex−iis the pro file of player actions other than playeri,and similar notation will be used for other vectors as well.The utility received by playeriis denoted byUi(xi,x−i)or simplyUi(x).

The definition of potential game is given as follows[12].Note that if a game admits a potential function,then all players tend to jointly optimize the potential function.

Definition 1.A finiteN-player game with utility functionsU1(x),U2(x),···,UN(x)is called a potential game if there exists a potential function Φ(x)such that for everyi∈N,

for all possible.

AnN-tuple of action variablex∗constitutes a(pure strategy)Nash equilibrium[7],if for all possiblei∈N,xi∈Xi,

It is well known that every potential game has at least one pure strategy Nash equilibrium,since a global maximum point of the potential function should be one Nash equilibrium[12].

The standard fictitious play is an iterative learning process incorporating the empirical frequencies of opponents′actions without assuming any information of other players′utilities[8].Denoteas the empirical P frequency of playerichoosing actionup to staget−1.HereI{·}is the indicator function.Every player assumes that other players make decisions randomly and independently according to those empirical frequencies,then the expected utility for playerichoosingis

Let every player select an action that maximizes the expected utility(3)at every stage.Then the empirical frequencies generated by fictitious play converge to a mixed strategy Nash equilibrium in all potential games[12].However, fictitious play is computationally infeasible for large-scale games,since choosing an action for playeriat every stage depends on a mapping over a joint spaceX−i.

In the JSFP,the empirical frequencies of the joint actions of other players,defined as,are tracked by playeri.Every player assumes that other players make decisions randomly and jointly according to the above empirical frequencies.The expected utility for playerichoosingbecomes

It turns out that the expected utility in the JSFP can be calculated recursively as[13]

Thus,the JSFP reduces the computational burden of standard fictitious play.The convergence of the JSFP was also addressed for all generalized ordinal potential games in[13].

In this paper,we consider a congestion game where the action of playeriat stagetis chosen from a finite collection of common resources R={r1,r2,···,rM}.For the ease of the presentation,we limit our attention to a single choice case,i.e.,the cardinality ofxi(t)∈R is 1.However,the results presented here can be further extended to a multiple choices case.It is assumed that the utility received by playerican be divided into two parts as

where

is the number of players choosing resourcexi.In(6),V1i(xi)represents the fixed utility received by playerifor using resourcexi,anddenotes the utility part due to the congestion of players using the same resource.Different from the congestion game introduced in[26],players′utilities are heterogeneous in(6).

III.CONVERGENCE ANALYSIS WITH BROADCASTING

In this section,a system supervisor is assumed which broadcasts information about the overall system to every player at each stage.We introduce the ASFP to further reduce the computational burden of the JSFP by getting rid of the utility updating process(5),and then analyze its convergence property.

A.ASFP

The procedure of the ASFP is described as follows.At the initial staget=0,every player picks up an action arbitrarily from R.Then at any staget≥1,the system supervisor recordsnrl(x(t−1))for alll=1,2,···,M,and computes its weighted running average recursively as

whereλ∈(0,1]is a constant weight on the newest information.In the ASFP,the above weighted running averageis broadcasted by the system supervisor to every player at the beginning of staget≥1.For playeri∈N,it is easy to obtain the following quantity

whereand.Note thatrepresents the weighted running average of the number of players choosing resourcerlexcept for playeriup to staget−1.Furthermore,in the ASFP,every playeri∈N makes a presumption that the total number of other players choosing resourcerlat stagetis equal to the weighted running average.In this situation,the predicted utility for playerichoosing∈R at stagetis given by

and the set of actions as the best response of playeriis defined as

Remark 1.Different from the JSFP,the utility updating process(5)is avoided in the ASFP,and thus the burden for information processing of each player is reduced especially when the number of resources to be chosen from is large.

Next,given the best response setfor every playeriat every staget≥1,we will study convergence of the ASFP.

B.Convergence Analysis

The convergence property of the ASFP is established via two steps.First,we will prove the existence of a set of Nash equilibria for the congestion game.After that,we will show that players′actions generated by the ASFP with some kind of inertia converge to one of Nash equilibrias almost surely.

The following proposition shows that the congestion game defined above is a potential game;thus,it inherits the desirable property of potential game regarding the existence of a pure strategy Nash equilibrium.

Proposition 1.A congestion game with utility functions given in(6)is a potential game with the potential function

and it has at least one pure strategy Nash equilibrium.

Proof.For the case:,condition(1)obviously holds.For the case:,we have

i.e.,condition(1)is satis fied.The proof is completed since every potential game has at least one pure strategy Nash equilibrium[12].□

For the simplicity of the analysis,we make the following assumption on the utility induced by congestion.Its validity will be further justified in Section V on transportation modeling.

Assumption 1.The utility part induced by congestion in(6)is linear with respect to the number of players selecting the same resource,i.e.,

wherea,bare constant parameters.

Following the idea in[13,29],some sort of inertia,which plays an important role in the convergence analysis,is introduced in players′decision making process.In the presence of inertia,playeri∈N stays with the previous action,i.e.,xi(t)=xi(t−1),if there is no opportunity for utility improvement,i.e.,otherwise,he or she chooses an action from the setwith probabilityξi(t)and still stays with the previous action with probability 1−ξi(t).The absorption property of Nash equilibria in the ASFP with inertia is shown in the following lemma.

Lemma 1.Consider a congestion game with utility functions given in(6).Under Assumption 1,if the action pro filex(t)of all players generated by the ASFP with inertia is a pure strategy Nash equilibrium at staget,andfor everyi∈N,thenx(t+τ)=x(t)for any positive integerτ.

Proof.First note that

After substituting(8)into(9),we have

It follows that

Based on the condition,we have for all,

In addition,x(t)is a pure strategy Nash equilibrium,therefore for all,

It follows from(16)that for all,

i.e.,Then we can obtain thatx(t+1)=x(t)based on players′inertia.The rest of the proof follows by induction.□

Two technical assumptions are essential to convergence analysis of the ASFP:one on players′willingness to optimize the predicted utility,and the other on players′difference between any two distinct strategies.

Assumption 2.For every playeri∈N and for every staget≥1,there exist constantsδ1andδ2such that

Assumption 3.For every playeri∈N,

for all possible

As the main result of this paper,the convergence property of the ASFP is provided in the next theorem.

Theorem 1.Consider a congestion game with utility functions given in(6)and broadcasting.Under Assumptions 1～3,the action pro file of all players generated by the ASFP with inertia is convergent to a pure strategy Nash equilibrium almost surely.

Proof.According to(16),ifx(t)is repeatedTtimes,i.e.,x(t)=x(t+1)=···=x(t+T−1),then

Forλ∈(0,1],there exists a suf ficiently largeTindependent oftsuch that,where BRi(x−i(t))is defined as the best response of playeriwith respect to the action pro file of other playersx−i(t),i.e.,

Note that the probability of the above event is at least(1−δ2)N(T−1),and under Assumption 3 the cardinality of BRi(x−i(t))is 1.Ifx(t)is a pure strategy Nash equilibrium,then the proof is completed based on Lemma 1.Otherwise,there exists at least one playerjsuch that.If playerjswitches its action toand all other players stay with their previous actions,i.e.,,andx(t+T)is repeatedTtimes,thenfor a sufficiently largeT.The corresponding probability is at leastδ1(1−δ2)NT−1.According to Proposition 1,we have Φ(x(t))＜Φ(x(t+T)).Again,ifx(t+T)is a pure strategy Nash equilibrium,we are done.Otherwise,we can continue the above argument and construct a sequence of action pro files asx(t),x(t+T),···,x(t+KT)such that

Note that the cardinality of the decision space of all players isMN,which is finite.In addition,there always exists at least one pure strategy Nash equilibrium for the underlying congestion game.Therefore,there exists a finiteK＜MNsuch thatx(t+KT)is a pure strategy Nash equilibrium.In summary,we can conclude thatx(t+KT)is a pure strategy Nash equilibrium withK＜MNand with a positive probability at least(1−δ2)N(T−1){δ1(1−δ2)NT−1}K.That is to say,the probability of the event that the action pro file of all players generated by the ASFP with inertia reaches a pure strategy Nash equilibrium after finite stages is nonzero.Then,it follows from the absorption property proved in Lemma 1 thatx(t)converges to a pure strategy Nash equilibrium almost surely.□

Remark 2.As we can see from the proof of Theorem 1,if there are multiple Nash equilibria for the underlying game,then the action pro file may converge to a pure strategy Nash equilibrium corresponding to only a local maximum point of the potential function.Note that this kind of phenomenon also motivates the research work on inef ficiency of equilibria[30],which can be one of our future directions.

IV .CONVERGENCE ANALYSIS WITH MULTI-AGENT CONSENSUS

In this section,we turn to consider the case without the system supervisor.In this situation,no information on the overall system is collected or broadcasted.A discrete-time consensus protocol is formulated for individual players to estimate the percentage/number of players choosing each resource,and then the convergence property of players′action pro file is also analyzed.

A.Consensus Protocol

Note that the main purpose of multi-agent consensus for individual player is to estimatenrl(x(t))defined in(7),or equivalentlynrl(x(t))/N,by using only local information obtained from neighboring players.The consensus process is repeated during every stage,and thus we take one stagetas an example in this section without loss of generality.

Suppose that the whole time interval of stagetis further divided into several short time intervalsk=0,1,2,···,K.At each short time intervalk,playerirandomly exchanges information withNi(k),a subset of its whole neighbor set Ni.Letdenote the set of all possible undirected graphs consisting of the node set N and an edge setE⊂N×N,in which the necessary conditions for non-oriented pair(i,j)∈E,i/=jarei∈Njandj∈Ni.As stated above,at each short time intervalk,the network is chosen fromrandomly,independent of other short time intervals.We denote the graph atkasGN(k)={N,E(k)}∈and the corresponding neighbor set of playeriasNi(k)={j:(i,j)∈E(k)}∪{i}.LetL(k)be the symmetrical Laplacian matrix associated withGN(k)and useLij(k)to denote thei,jentry ofL(k).Note thatGN(k)may not be connected and some agents may be isolated as they may leave the system randomly.For an isolated agentiatk,its neighbor set isNi(k)={i}.In addition,the union of the undirected graphsGN(k),k=0,1,···,K,is said to be jointly connected,if there exists an undirected path between each pair of nodes[20].

Writesi(t)=[si1(t)si2(t)...siM(t)]′,wheresij(t)=1 ifxi(t)=rj,otherwisesij(t)=0.Note thatsi(t)is available to playeriat the beginning of staget.For the single choice case studied in this paper,we have.Motivated by the protocol introduced in[21]for the case of binary strategies,a linear protocol is given by

whereα(k)∈(−1/∆(k),0)and∆(k)=maxi(Lii(k)).In fact,yi(k)can be regarded as a local estimation vector of the percentage of players choosing each resource.

By considering thel-th element ofyi(k)Nas an estimate ofnrl(x(t)),the ASFP presented in Section III-A can still be applied.

B.Convergence Analysis

Based on the consensus theory[14,20],we can easily obtain the following results.

Lemma 2.The protocol described by(24)satisfies that fork=0,1,2,···,K,

Lemma 3.If there exists aKsuch that the union of the undirected graphsGN(k),k=0,1,···,K,is jointly connected,then the protocol described by(24)achieves average consensus exponentially fast,which indicates that for any∈＞0,there exists a finite integerK≥1 such that

Based on the above two lemmas and following the similar line of proof as in Theorem 1,we can derive the result below.

Proposition 2.Suppose that there exists aKsuch that for each staget,the union of the undirected graphsGN(k),k=0,1,···,K,is jointly connected,and the number of short time intervalsK+1 is suf ficiently large.Consider a congestion game with utility functions given in(6)and without broadcasting.Under Assumptions 1～3,the action pro file of all players generated by the ASFP with inertia and the consensus protocol in(4)is convergent to a pure strategy Nash equilibrium almost surely.

V.APPLICATION TO ROAD PRICING DESIGN

Suppose that a group of people with one origin and one destination are planning to travel during a given period(e.g.,7:30am～9:30am)on a daily basis.There areM1parallel routes connecting the origin and the destination,and the given time period is divided intoM2time intervals.In this case,the common resources contain both trip routing and trip timing choices withM=M1M2.In the following text,we focus on motorists′trip timing behavior by settingM1=1.

A.Trip Timing Without Road Price

For the problem of trip timing,a collection of time intervals is considered as the set of resources to be chosen by every road user.Without road price,each driver decides his or her departure time by taking the average travel speed and his or her own preferred departure time into account.Suppose thatnri(x)is the number of vehicles on the road choosing departure time intervalriand the length of the road isLr.A common assumption in the area of transportation theory is that the average travel speed is a linear function of traffic density,i.e.,nri(x)/Lr;see,e.g.,[31−32].In this case,we set the utility partsV1i,V2in(6)as

whereis the preferred departure time of driveri,andαi,a,bare constant parameters.Note thatis the time difference between actual and preferred departure times,andαi≤0 may be different for different road users.In addition,since the average travel speed is always decreasing with respect to the number of vehicles on the road,we havea＜0.

For the case with broadcasting,the road manager(i.e.,the system supervisor)monitors the traffic flows in the traffic system,and thus the weighted running average defined in(8)can be computed by the road manager.The weighted running average actually describes the crowdedness of the road during each time interval based on the historical traffic situation.Suppose that the road manager broadcasts(8)to every driver.Then,the above trip timing problem fits within the congestion game formulated in Sections 1 and 2.Moreover,if every driver generates his or her action based on the ASFP with inertia,then the convergence of the action pro file of all drivers is ensured under the conditions of Theorem 1.

For the case without broadcasting,individual driver exchanges information on traffic situation with his or her friends and neighbors randomly in order to estimate the number of drivers selecting each departure time interval.Then,the consensus protocol given in Section IV can be used.

B.Trip Timing Under Dynamic Road Pricing

Assume that the road price determined by the road manager is adopted to achieve some kind of social goal and it is charged when the driver enters the road.We consider the case where the road price is a function of the number of vehicles on the road and the utility function(6)is modified into

wherep(nxi(x))is the road price to be designed,andc＜0 is an additional parameter.We can derive the following result.

Theorem 2.If the road price is set according to

then the congestion game with utility functions given in(29)is a potential game with the potential function

Proof.Forin(31)andwe have

Note that

Based on(29)and(30),we can obtain that forx1i/=x2i,

The rest proof follows similarly to Proposition 1.□

Note that the pricing scheme given in(30)is dynamic.In addition,in(31)represents the overall utility of all road users in the absence of road price,and thuscan be considered as a social welfare to be maximized by the system supervisor.According to Remark 2,the action pro file generated by the ASFP with inertia may converge to a local maximum point of.However,starting from the same set of initial conditions,the proposed pricing strategy can always improve the overall utility compared to the case without road pricing;see next subsection for a case study of Singapore.

C.Case Study of Singapore

We take Church Street,Singapore(Fig.1)as an example.

Fig.1.Map of Church Street,Singapore.

The Land Transport Authority(LTA)of Singapore and the Comfort Taxi Company provided us with loop counts and taxi data for the month of August 2010,respectively.The loop counts record the number of vehicles passing through all inductive loop detectors,and the taxi data contain the information on the changing of Taxies′GPS location with respect to time.The average travel speed can be computed based on the taxi data,and the traffic flow is given by the loop counts.Then,the traffic density can be calculated as the ratio of the traffic flow to the average travel speed.The relationship between average travel speed and traffic density for Church Street is plotted in Fig.2,which is approximately linear.

The length of Church Street is about 0.3 kilometers,then we can derivea=−0.798km/h/vehicle,b=48.835km/h in(28).

Suppose that there are 200 road users using Church Street from 7:30am to 9:30am everyday.In the simulation,the value ofαi,i=1,2,···,500,is randomly generated according to a uniform distribution within the interval[−150,−50],while,i=1,2,···,500,is randomly generated according to a triangular distribution within the interval[7:30am,9:30am]and with a peak at 8:00am.In practice,the distribution ofαiandmay be determined via household survey,which is out of the scope of this paper.We divide the time horizon[7:30am,9:30am]into 8 non-overlapping intervals,i.e.,M=8.Each interval has a length of 0.25 hours.

For the case with pricing scheme in(30),the action pro file of all players generated by the ASFP with inertia is still convergent to a pure strategy Nash equilibrium as shown in Fig.4.Starting from the same set of initial conditions,the overall utility for the case without road price is=3266.3 and for the case with pricing scheme(30)is=3407.9.It can be observed that the proposed pricing strategy improves the overall utility of all players.By comparing Fig.3 with Fig.4,we can see that the proposed road pricing scheme actually shifts a portion of people from relatively more congested time intervals to less congested ones.

Fig.2.Relationship between average travel speed and traffic density for Church Street,Singapore.

Fig.3 and Fig.4 provide the number of vehicles selecting each departure time interval over stage/dayt=0,1,2,···without and with road price,respectively.We first consider the case without road price.As we can see from Fig.3,the action pro file of all players generated by the ASFP with inertia is convergent,and we can further check that the convergent point is a pure strategy Nash equilibrium.

Fig.3.Number of vehicles in each departure time interval without road price over day t=0,1,2,···.

VI.CONCLUSIONS

In this paper,for the case with broadcasting,the so-called average strategy fictitious play has been introduced for largescale repeated congestion games.It avoids the utility updating process in joint strategy fictitious play studied in[13].For the case without broadcasting,a consensus protocol has been given for individual agent to estimate the percentage of players choosing each resource.The convergence property of underlying congestion game with or without broadcasting has been established,and the results have been applied to road pricing design to achieve socially local optimal trip timing.Future work includes the conditions for the uniqueness of Nash equilibrium,and other forms of broadcasted information,e.g.,coordinated actions/signals.

Fig.4.Number of vehicles in each departure time interval under pricing scheme(30)over day t=0,1,2,···.

ACKNOWLEDGEMENT

The authors acknowledge the contribution of Sejoon Lim and Javed Aslam on data processing,and thank Keyou You for insightful discussions.The authors would also like to thank the Land Transport Authority of Singapore and the Comfort Taxi Company for the data collected from loop detectors and taxis.

REFERENCES

[1]Deakin E,Harvey G,Pozdena R,Yarema G.Transportation Pricing Strategies for California:An Assessment of Congestion,Emissions,Energy,and Equity Impacts,Technical Report,UCTC,No.434,Transportation Center,University of California,USA,1996

[2]Menon A.ERP in Singapore:a perspective one year on.Traff i c Engineering and Control,2000,41(2):40−45

[3]Olszewski P,Xie L T.Modelling the effects of road pricing on traf fic in Singapore.Transportation Research Part A:Policy and Practice,2005,39(7−9):755−772

[4]Tsekeris T,VoβS.Design and evaluation of road pricing:state-of-the-art and methodological advances.Netnomics,2009,10(1):5−52

[5]Button K J,Verhoef E T.Road Pricing,Traff i c Congestion and the Environment:Issues of Ef ficiency and Social Feasibility.Cheltenham,UK,and Northampton,MA:Edward Elgar Publishing,1998

[6]Gibbons R.A Primer in Game Theory.New York:FT Prentice Hall,1992

[7]Basar T,Olsder G J.Dynamic Noncooperative Game Theory(Second edition).Philadelphia:Society for Industrial and Applied Mathematics,1999

[8]Fudenberg D,Levine D.The Theory of Learning in Games.New York:MIT Press,1998

[9]Shapley L.Some topics in two-person games.AdvancesinGameTheory,1964,52:1−29

[10]Jordan J S.Three problems in learning mixed-strategy Nash equilibria.Games and Economic Behavior,1993,5(3):368−386

[11]Shamma J S,Arslan G.Uni fied convergence proofs of continuous-time f i ctitious play.IEEE Transactions on Automatic Control,2004,49(7):1137−1142

[12]Monderer D,Shapley L.Potential games.Games and Economic Behavior,1996,14(1):124−143

[13]Marden J,Arslan G,Shamma J.Joint strategy fictitious play with inertia for potential games.IEEE Transactions on Automatic Control,2009,54(2):208−220

[14]Olfati-Saber R,Fax J A,Murray R M.Consensus and cooperation in networked multi-agent systems.Proceedings of the IEEE,2007,95(1):215−233

[15]Tahbaz-Salehi A,Jadbabaie A.A necessary and sufficient condition for consensus over random networks.IEEE Transactions on Automatic Control,2008,53(3):791−795

[16]Qu Z H.Cooperative Control of Dynamical Systems.New York:Springer,2009

[17]Kingston D B,Beard R W.Discrete-time average-consensus under switching network topologies.In:Proceedings of the 2006 American Control Conference.Minneapolis,MN:IEEE,2006.3551−3556

[18]Ren W,Beard R W.Distributed Consensus in Multi-Vehicle Cooperative Control:Theory and Applications.New York:Springer,2008

[19]Cao M,Morse A S,Anderson B D.Reaching a consensus in a dynamically changing environment:a graphical approach.SIAM Journal on Control and Optimization,2008,47(2):575−600

[20]Cao M,Morse A S,Anderson B D.Reaching a consensus in a dynamically changing environment:convergence rates,measurement delays,and asynchronous events.SIAM Journal on Control and Optimization,2008,47(2):601−623

[21]Bauso D,Giarr´e L,Pesenti R.Consensus in noncooperative dynamic games:a multiretailer inventory application.IEEE Transactions on Automatic Control,2008,53(4):998−1003

[22]Bauso D,Giarr´e L,Pesenti R.Distributed consensus in noncooperative inventory games.European Journal of Operational Research,2009,192(3):866−878

[23]Patriksson M.The Traf fic Assignment Problem:Models and Methods.Utrecht:VSP,1994

[24]Como G,Savla K,Acemoglu D,Dahleh M,Frazzoli E.Robust distributed routing in dynamical flow networks-Part II:strong resilience,equilibrium selection and cascaded failures.IEEE Transactions on Automatic Control,2013,58(2):333−348

[25]Wongpiromsarn T,Xiao N,You K Y,Sim K,Xie L H,Frazzoli E,Rus D.Road pricing for spreading peak travel:modeling and design.In:Proceedings of the 17th International Conference of Hong Kong Society for Transportation Studies.Hong Kong,China:The Hong Kong Institution of Engineers,2012.291−298

[26]Rosenthal R.A class of games possessing pure-strategy Nash equilibria.International Journal of Game Theory,1973,2(1):65−67

[27]Xiao N,Wang X H,Wongpiromsarn T,You K Y,Xie L H,Frazzoli E,Rus D.Average strategy fictitious play with application to road pricing.In:Proceedings of the 2013 American Control Conference.Washington,DC,USA:IEEE,2013.1920−1925

[28]Wang X H,Xiao N,Wongpiromsarn T,Xie L H,Frazzoli E,Rus D.Distributed consensus in noncooperative congestion games:an application to road pricing.In:Proceedings of the 10th IEEE International Conference on Control and Automation.Hangzhou,China:IEEE,2013.1668−1673

[29]Ben-Akiva M,De-Palma A,Kaysi I.Dynamic network models and driver information systems.Transportation Research Part A:General,1991,25(5):251−266

[30]Roughgarden T.Potential functions and the inefficiency of equilibria.In:Proceedings of the 2006 International Congress of Mathematicians.Madrid,Spain:European Mathematical Society,2006.1071−1094

[31]Bell M,Iida Y.Transportation Network Analysis.New York:John Wiley&Sons,1997

[32]Garavello M,Piccoli B.Traffic Flow on Networks.Portage Ave,Palo Alto,CA:American Institute of Mathematical Sciences,2006