The ϵ-equilibrium in transportation networks

The ϵ-equilibrium in transportation networks

FUZZY sets and systems ELSEVIER Fuzzy Sets and Systems 68 (1994) 195 202 The e-equilibrium in transportation networks Zhiwei Zhao Department o[" El...

395KB Sizes 1 Downloads 15 Views

FUZZY

sets and systems ELSEVIER

Fuzzy Sets and Systems 68 (1994) 195 202

The e-equilibrium in transportation networks Zhiwei Zhao Department o[" Electrical Engineering, Utah State University, Logan. UT 84322-4120, USA

Received July 1993:revised March 1994

Abstract

The principle of traffic equilibrium (Wardrop, 1952) demands that the trip makers have enough knowledge of transportation networks, which needs to be attained by accumulating experiences for a long time. Because of the complexity of traffic situation in the networks, the route choice decisions for trip makers are, however, not always optimal objectively. As a consequence, it is impossible to strictly attain Wardrop equilibrium. In this paper, a new concept of equilibrium, e-equilibrium is proposed under the realistic assumption, i.e., the fuzzy road information and random route choices, e-equilibrium in the network is discussed by adopting fuzzy set theory, mixed stochastic Games and Brouwer fixed point theorem in topological space. The conclusion is that there is e-equilibrium in the real transportation network and this e-equilibrium has some deviations from the strict Wardrop equilibrium. The notion of e-equilibrium extends the traditional notion of network equilibrium. It shows that traffic flow in the network converges to a region rather than to the points. Keywords: Fuzzy information; Transportation networks; Wardrop equilibrium; e-equilibrium; Game theory

1. Introduction

It was pointed out [13] that there exists the traffic flow patterns of equilibrium in transportation networks and under the state of its equilibrium, each trip maker chooses the least cost path between his origin and destination in such a way that no trip maker can change his trip route on his own so as to reduce his travel cost. Wardrop equilibrium has been widely used as a principle to traffic assignment in transportation networks, the detailed discussion on its properties can be found in the literature [4, 12]. In fact, equilibrium is a phenomenon which exists in many self-organizing systems• Equilibrium in economic system is a typical example of equilibrium phenomenon which has been studied extensively. The equilibrium in economic system, called Walras equilibrium, means the market condition in which quantity supplied and quantity demanded are equal. Interested readers about this matter can consult in the literature [1, 7, 1 1]. Both Wardrop equilibrium and Walras equilibrium are optimal patterns• Wardrop equilibrium is also an optimal state in terms of travel cost of trip makers and network utilization. Walras equilibrium is also an optimal state according to the supply side, the demand side and resource utilization. On the other hand, game theory is the mathematical study of conflict situations. The optimal strategies in game theory is called Nash equilibrium strategies, which can be stated as follows: a game is in Nash equilibrium (a set of strategies, one 0165-0114/94/$07.00 © 1994 ElsevierScience B.V. All rights reserved SSDI 0165-01 14(94)00205-3

196

Z. Zhao / Fuzzy Sets and Systems 68 (1994) 195 202

pathl

Do

pth3

B

y

0

m r-c

Fig. 1. A trip from A to B.

r

r-~c

R

Fig. 2. A symmetrytriangle fuzzynumber f.

for each player) if no player can unilaterally increase his payoff by changing his strategies, given that all other players are playing their Nash equilibrium strategies. The above definition of Nash equilibrium is for pure strategies, but it is easy to extend to the situations in mixed strategies [2, 8, 10]. Now, it is straightforward for us trying to use game theory to model the equilibrium problems. In fact, Walras equilibrium has been successfully cast in a game-theoretic mold [7]. Up to now, Wardrop equilibrium principle is valid only if every user is completely familiar with the transportation networks and traffic situations, and therefore, can make a deterministic optimal path choice. The behavior of such users must be reasonable in order to not make errors in choosing path. In reality, however, it is very difficult to have the traffic situations at one's finger tips. Human perception and intuitive judgment play a central role in route choices. Therefore it is impossible to have a precise estimation of the trip cost available to many paths. We consider that the trip cost is a fuzzy notion. Because of the difference among trip makers, a trip maker does not make deterministic and optimal decision but rather adopts the stochastic choice which he or she feels satisfactory for path choosing under the expected traffic situations in a network (constraint satisfaction in terms of traffic situations). From the point view of game theory, this characteristic suggests that a game played by trip makers in mixed strategies, instead of pure strategies is appropriate. This means that the trip maker's fuzzy perception for travel cost causes random behavior in route choices. Thus, we deal with two kinds of uncertainties here, fuzziness and randomness. There are some articles about the relationship between fuzzy sets and probability in the literature [5, 14 16]. Fig. 1 is a simple traffic network consisting of one pair of origin-destination, ~ree paths from A to B, and t~, t2, t3, as the travel time in terms of fuzzy numbers on three paths, are 50, 55, 52, respectively. The detailed discussion on fuzzy triangle number arithmetic can be found in [9]. Suppose all fuzzy numbers are the symmetry triangle fuzzy numbers, Fig. 2 is the illustration of a symmetry triangle fuzzy numbers 7, assuming the widths for tl, t2, t3 in Fig. 1 is 5, 4, I, respectively, then we try to find the best path from A and B. In this case, we cannot simply pick up pathl as the best path because of fuzziness. Let us compare the travel time for the three paths, tl-t3=~0-~2

=(45,50,55)-(51,52,53)=(-6,-2,1),

t, - t2 = ~0 - ~5 = (45,50,55)-(51,55,59) = ( - 6 , - 5 , - 4), t2 - t3 = ~5 - ~2 = (51,55,59)- (51,52,53) = (0,3,6). Obviously, path2 is not the best path, but path3 cannot be excluded as a candidate for the best path. As the result, the equilibrium state cannot be strictly attained. The purpose of this paper is to explore e-equilibrium in transportation networks under the circumstances of fuzzy road information and consequently, the random route choices taken by trip makers. In Section 2, the model of route choices is built by means of the game theory and at the same time we consider the travel cost

Z. Zhao / Fuzz)' Sets and Systems 68 f1994~ 195 202

197

of trip makers as fuzzy numbers. As the result, the problem of route choices is transformed into a noncooperative mixed fuzzy game. The implication of e is given. In Section 3, the existence of e-equilibrium is proved by means of Brouwer fixed point theorem. A conclusion of the e-equilibrium is given in Section 4.

2. The model of game theory in networks Let G = (Q, A) be a directed network, where Q is a set of OD pair and A is a path set. In order to discuss e-equilibrium, we introduce game theory [4]. There is a state between each O D pair in the network and there is an interaction among states. If we regard such interaction as prior experience information which is used for players (i.e. trip makers) to choose the strategies, the interaction can be classified into the payoff function rather than have the direct influence on the state. Therefore, we might as well consider that the states are independent each other. In this way, we can choose any one of O D pairs in Q as a noncooperative game 7".' T= (N,',S,},~N,{It,]i~N),

(1)

where N = (1,2 ..... n), Si is a strategy set of the ith player (trip maker), and Hi is a payoff function of the ith player. In the game T, there are several players, every player has a strategy set Si (i = 1,2 ..... n) Si = (q] ,q2 ..... qT'),

(2)

M i = (1,2 . . . . .

(3)

mi) ,

S = $1 x S 2 x ... x S i x ... x S , =

It(S1

.J,' S 2 . j . . . . . .

S i , j . . . . . . Sn.j,,)l Si.j, • Si, i • N, Ji • M i } .

(4)

For the state S, every player has a payoff function Hi(S), HI(S) is a fuzzy function here. The different strategies (i.e. paths) for which players choose can obtain the different costs:

where C is the estimated cost for the player i to choose path, r is real number greater than 0. As the introduction pointed out that, because of the complexity of the situation in transportation networks, C cannot be precisely obtained, therefore C is regarded as a fuzzy variable and Hi(S) is a fuzzy function. Because of the fuzzy characteristics of Hi(S) and player's some psychological influences owing to other factors, players may make decision with random factor, the randomness is incarnated by that C is a random variable, Thus the player i will choose the path Sij according to the probability Plj in an attempt to maximize HI(S). Although, we use traditional noncooperate game framework using probability measure, it bears different meaning. The mixed strategy in game theory is introduced as a way out of the difficulty when a game has no solution in terms of the pure strategy. In our model, however, the probability combination of the pure strategy is not intend to solve the technique difficulty. As mentioned earlier, we think the random behavior of trip makers in choosing paths is inherently caused by fuzziness in acquiring road information and then the payoff Hi(S) is fuzzy function. Hence, what we discuss is a mixed fuzzy game T*, its state is: S* = I~I S*, i

(6)

1

S * = {Pi = ( P i l , P i 2 . . . . . Pij . . . . . Pi,.i)} ,

(7)

mi

2 j

Pij = 1, 1

Pij >~ O, j • M i ,

(8)

Z. Zhao / Fuzzy Sets and Systems 68 (1994) 195-202

!,98

where S* is ( m i - 1) dimension simplex in the ml dimension Euclidean space. Because Pi is a probability measure which is defined on S*, the mixed and expanded payoff function is measurable fuzzy function which is defined in the state space S* = I~I S*,

(9)

i=l

Hi" I] s*

(10)

-~ ~ ( ~ ) ,

i=l

Za(~) is a family of fuzzy subsets of R, R = {xl - ~ ~< x ~< + ~ } . Under the mixed strategy, the payoff function of the player is Hi(p) = Hi(pl,P2,

= ~

~

Pn)

...,

"'" ~ Hi(ql,q2 ..... q . ) f i P j ( q j ) .

ql ~S~ q2~S~

qnES~

(ll)

j= 1

For convenience, we have following definitions: P dlPl = (P,,PE, ..., P'i, ..., P,),

(12)

P = (P~,P2 ..... P~..... P,).

(13)

This means that player i has in p replaced the strategy Pi by P'i.

Hi(p II qi) = E

E

"'"

q l ~ S l* q26S2*

E

E

* ql i~ S*i i qi+l • Si+l

"'" Z Hi(q) f i pj(qj). qneS*n

Definition 2.1. A mixed strategy p = ( P l , P2, ...,

(14)

j= 1

j~=i

Pn) is fuzzy

equilibrium if and only if

Hi(p IIPl) ~- Hi(p),

(15)

for Vi E N, and Ple S*. Thus, we may obtain the following theorem. Theorem 2.1. A mixed 9ame p = (Pl,P2 ..... p,) is fuzzy equilibrium, if and only if for Vi ~ N, and j E Mi, then

H,(p II qi) ~ Hi(p).

(16)

Proof. For Yp~ e S*, by multiplying both sides of the equation above by p~(q~) and summing over ql, we obtain left-hand side = ~ H,(p Jrq,)P'i(q,) = H,(p IIP3,

(17)

q~eS*~

(18)

~' P~(qi)'Hi(p),

right-hand side -

#u is denoted as membership function of fuzzy number u, and/~i as nonfuzzy number Hi. #z,,s-p tq,m,tp)(Z) =

sup

inf

{~p,(qOHi(p)(pi(qi)I~(p))}

(19)

Z='~-~q ,~., s.p.(q t t)~li(p)q-eS? z Pi(qi) ~ 0

=

sup inf ~tl~n,tp)(nitp));

(20)

[ti(p) qieS*

= #u,~p~(/~i(p)),

(21)

Z. Zhao / Fuzzy Sets and Systems 68 (1994) 195 202

199

when Pi(qj) = O,

3 j ~ mi

(22)

yields ll,, iqj~n,~pl(Z) = 0.

(23)

Thus, /1,-~,, i~.p'
(24)

Therefore, we have p'i(qi)Hi(p)-- Hi(p).

(25)

Hence Hi(p II P'i) ~ Hi(p).

(26)

Finally, we obtain the conclusion

Hi(p [I qi) ~ Hi(p) This is end of the proof. Let X be a metric space and d be metric in X. d:XxX

~R.

(27)

It is easy to prove that d is continuous. Let A ~ X is a fuzzy set, the z-level set of A is defined by A~={x:ItA(X)>~c~},

~{0,1],

Ao = {x: t~A(X) > 0 } ,

(28) (29)

where /~ is the closure of set B. Definition 2.2. Let M(x) be a family of the all fuzzy sets in the metric space X. For A , B ~ ~ ( x ) , ~ ~ [0, 1] define P~(A,B) =

inf

d(x,y),

(30)

x~A~,yEB,

D~(A, B) = dist(A~, B~),

(31)

D ( A , B ) = supD~(A,B),

(32)

ct

where d is a metric, and dist is Hausdorff distance, that is, for arbitrary nonempty compact sets W, U in X, dist( W, U ) = max I s u p inf d ( x , y ) , s u p inf d ( x , y ) l ) [ xEW y~U yEU x~W #

~33)

and D(A, B) is the distance between A and B. Definition 2.3. A mixed fuzzy game of nonalliance is e-equilibrium, if and only if Vi 6 N, j 6 Mi, e, ~> 0, then

D( Hi(p II qu), Hi(P) ) <~ e.

(34)

200

Z. Zhao / Fuzz), Sets and Systems 68 (1994) 195 202

In this game, every player is not supposed to be excessively intelligent, or super rational person of knowing-all.

3. Existence of e-equilibrium Lemma 3.1. I f x~ is compact convex set of metric space S~, then X = I]~= ~X i is compact convex set of product space S = [I"= 1 Si. Proof. First, we prove compactness. Suppose mapping U = S --* S~, based on partial and extension mapping in topological space, if Ux : X -~ Sg is a mapping, then P = U 1 : X --* X~ is also mapping. The compactness can be attained according to Tychonoff's theorem in product space. Next, we prove that X = ~ I / n _ 1 X i is a convex set. Suppose W, U ~ X, W = (W1 . . . . . Wi . . . . . W,), U = (U1 . . . . . Ui . . . . . U,), Wi, Ui E Xi (i ~ N). Let Z=2W+(1-2)U,

2 e [0, 1],

(35) (36)

Z i = / ~ W / -t- (1 - 2 ) U ~ ,

since Xi is convex set, Z e X

=

I~i"X i is guaranteed, therefore X is a convex set.

[]

In the Section 2, the mathematical definition of e-equilibrium has been given. Now we deduce a e,equilibrium principle in transportation networks as follows.

The e-equilibrium principle in transportation networks. There exists the traffic flow patterns of e-equilibrium in transportation networks and under the state of its e-equilibrium no user believes that changin9 his trip route on his own may very effectively reduce his travel cost.

Proof. We prove its existence under the model framework which is built in last section. For every player i e N, his pure strategy set is Si and his mixed strategy set is S*, S* is (mi - 1) dimension simplex of m; dimension Euclidean space.

Vp e S* = f i S*.

(37)

i=1

Let t~ij(p) = m a x { D ( H ( p II qi), H ( p ) ) - e,O},

i ~ N, j ¢ Mi, qi e S*.

(38)

Obviously, ~,j(p) >~ O.

(39)

Pij -I- ~ij(P) fiij = 1 + Y~'~=, ~bik(p)

(40)

Let

Z. Zhao

Fuzzy

Sets and Systems 68 (19942 195 202

201

by summing over j, we obtain mi

ffij =

j=l

Pij + t~ij(P)

i:l

1

mi q-~k=llllik(P )

= 1 At- Enj'i 1 [/lij(P }

(41) (42)

1 + 2~"-, ~//ik(p) = I,

(43)

therefore, fii = (/~i~ ..... Pij . . . . . Pi,,,) is a probability measure on S*. p = (Pl ..... /~i ..... fin) is the function of previous probability measure p = (Pl ..... Pi ..... p,)./~ = f ( p ) . It is easy to prove that D ( H ( p II qi), H(p)) is continuous. Thereupon, ~ij' S* --* [0, oc ) is continuous mapping, hence, f : S* ~ S* is continuous. According to Lemma 3.1, S* is compact convex set, basing on B r o u w e r fixed point theorem, there exists pO = f ( p O ) , i.e.,

!30 ~ ~iJ(pO) pO = 1 + - ~ * 7~/k(Po)

= ~'ij(Po)/> 0,

(44) (45)

if ~bij(P°) > O, then mz

pO + PI} Z ~ik(P °) = pO + ~,j(pO) k

(46)

1

reduces to rn

Pl} ~. ~',k(P°) = ~b~j(P°).

(47)

k=l

If pO = 0, then ~qj(pO) = 0, but this contradicts with the assumption, therefore, ~,b~j(p°) = O. In this way, a e-equilibrium state can be obtained, i.e.,

D( H(P ° !l qi),H(P°)) ~< ~:.

(48)

This is the completion of proof.

4. Conclusion The notion of e-equilibrium extends the traditional network equilibrium as the result of relaxing the demand for accuracy in acquiring road information in transportation networks. It puts emphasis on the satisfactory decision which is always adopted by decision makers rather than the optimal decision which is hard to attain in reality. Because of the complexity of real traffic situations in transportation networks, perception of road information for the trip makers is actually, in fuzzy notion, and consequently, the trip makers make random rather than deterministic decisions for their route choices. Thus, it is impossible for trip makers to choose the optimal paths, as the result, there is e-equilibrium in the real transportation networks and this e-equilibrium has some deviations from the strict Wardrop equilibrium. The framework we have used above is noncooperative game on the probabilistic measure, i.e., in mixed strategies, thus, every player (trip maker) suppose to be a risk taker in the networks. It has been shown that traffic flow in the network converges to a region rather than to the points under e-equilibrium. Note that what we have discussed above is analysis of dominant collective behavior in the system consisting of massive active individuals, i.e., the

202

Z. Zhao / Fuzzy Sets and Systems 68 (1994) 195 202

trend of the system development, just like the equilibrium models used in conventional Wardrop equilibrium in transportation networks, economic equilibrium, and even statistical physics, we did not discuss the exceptional individual behavior (irrational choices or mistakes) the trip makers might take. The most important goal of intelligent vehicle highway systems (IVHS) is to reduce the uncertainty for drivers in estimating travel cost of available routes, and have drivers choose the optimal routes as far as possible, in other words, make traffic pattern from e-equilibrium to approach Wardrop equilibrium. We should remember we never expect that the information system in IVHS become a crystal ball for us to eliminate the uncertainties in estimating travel cost in transportation networks.

References Ill [2] [3] [4] [5] [6] [7] [8] [9]

M. Alligham, General Equilibrium (Wiley, London, 1975). T. Basar and G.J. Olsder, Dynamic Noncooperative Game Theory (Academic Press, London, 1982). C. Berge, Topological Spaces (Oliver and Boyd, Edinburgh, 1963). S. Dafermos, Traffic equilibrium and variational inequalities, Transportation Sci. 14 (1980) 42-54. B.R. Gaines, Fuzzy and probability uncertainty logics, Inform. and Control 38 (1978) 154-169. S. Heilpem, Fuzzy mappings and fixed point theorem, J. Math. Anal. Appl. 83 (1981) 566-569. R. Henn and O. Moeschlin, Mathematical Economics and Game Theory (Springer, Berlin, 1975). A.J. Jones, Game Theory: Mathematical Models of Conflict (Wiley, West Sussex). A. Kaufmann and M.M. Gupta, Fuzzy Mathematical Models in Engineering and Management Science (North-Holland, Amsterdam, 1985). [10] R.B. Myerson, Game Theory Analysis of Conflict (Harvard University Press, Cambridge, 1991). [l l] T. Rader, Theory of General Economic Equilibrium (Academic Press, London, 1972). [12] M.J. Smith, The existence, uniqueness and stability of traffic equilibria, Transportation Res. Part B 13 (1979) 295 404. [13] J.G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. Civil Engineers Part 2, 1 (1952) 325-378. [-14] R.R. Yager, A foundation for a theory of possibility, J. Cybernetics l0 (1980) 177 204. [15] L.A. Zadeh, Probability measures of fuzzy events, J. Math. Anal. Appl. 23 (1968) 421-427. [16] L.A. Zadeh, Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems ! 0978) 3 28.