Computer Science – Computer Science and Game Theory
Scientific paper
2008-10-14
Computer Science
Computer Science and Game Theory
13 pages
Scientific paper
Given a network with a continuum of users at some origins, suppose that the users wish to reach specific destinations, but that they are not indifferent to the time needed to reach their destination. They may have several possibilities (of routes or deparure time), but their choices modify the travel times on the network. Hence, each user faces the following problem: given a pattern of travel times for the different possible routes that reach the destination, find a shortest path. The situation in a context of perfect information is a so-called Nash equilibrium, and the question whether there is such an equilibrium and of finding it if it exists is the so-called equilibrium assignment problem. It arises for various kind of networks, such as computers, communication or transportation network. When each user occupies permanently the whole route from the origin to its destination, we call it the static assignment problem, which has been extensively studied with pioneers works by Wardrop or Beckmann. A less studied, but more realistic, and maybe more difficult, problem is when the time needed to reach an arc is taken into account. We speak then of a dynamic assignment problem. Several models have been proposed. For some of them, the existence of an equilibrium has been proved, but always under some technical assumptions or in a very special case (a network with one arc for the case when the users may chose their departure time). The present paper proposes a compact model, with minimal and natural assumptions. For this model, we prove that there is always an equilibrium. To our knowledge, this imply all previous results about existence of an equilibrium for the dynamic assignment problem.
Meunier Frédéric
Wagner Nicolas
No associations
LandOfFree
Dynamic assignment: there is an equilibrium ! does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic assignment: there is an equilibrium !, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic assignment: there is an equilibrium ! will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-591702