AN APPLICATION OF GAME THEORY TO ROUTE SELECTION

An Application of Game Theory to Route Selection DAVID C. COLONY, University of Toledo The problem of alternate route selection is analyzed as a 2-person game against nature. By using data on galvanic skin response, a payoff function is formulated in terms of driver tension. Driver tension increases with traf- fic volume on a freeway but is practically independent of traffic volume on an arterial street. A solution to the problem is given under 4 different criteria for games against nature. If a freeway route and an alternate route on an arterial street are equal in length, the Hurwicz a index indicates that a driver should not select the freeway unless he is at least 62 percent sure of finding good traffic conditions. Application of the minimax-regret prin- ciple yields a diversion curve that indicates that all drivers should select the freeway for a distance ratio less than 0.48, 38 percent should select the freeway for a distance ratio of 1.00, and no drivers should take the freeway if the distance ratio exceeds 2.94. If the driver can estimate a probability distribution for the states of freeway traffic, his optimum strategy can be found by linear programming. A criterion is suggested ~or evaluating the effectiveness of a driver- information system in terms of the regret associated with this optimum strategy and the minimax regret pertaining to the case of complete uncertainty. •GAME THEORY PERTAINS to problems of decision-making under risk or uncertainty. Such risk or uncertainty results from a partial lack of control over the results of a given decision because of conflict of interests among a group of other individuals who also have some partial control over the outcome of their collective actions. The problem of decision-making when the outcomes of one's decisions can be pre- dicted with certainty is a problem of maximizing or minimizing the value of some ob- jective criterion that characterizes the goals sought by the decision-maker. Under the condition of certainty, one is free to manipulate all the parameters of the problem. Risk is introduced when one must take into account the (possibly) conflicting interests of other groups or individuals. In the risk situation one is aware of what these conflict- ing interests or objectives may be and must therefore attempt to protect one against the actions of opponents or to maximize one's return in the face of opposition. Uncertainty is distinguished from risk by the lack of knowledge of the intentions or objectives of one's opponents. Decision-making under uncertainty is often character- ized as a 2-person game in which the decision-maker is pitted against a fictitious player called "nature," a player with no known objectives and no discernible strategy. Game theory is not a descriptive theory in the sense that it attempts to predict the way people behave under given circumstances. It is a conditionally normative theory because it describes the way people should behave if they wish to obtain some stated outcome. It is a static theory in that the objectives and value systems of the players are con- sidered invariant in time. Dynamic aspects of behavior can be introduced in a game theoretic model by permitting successive plays or iterations with the appropriate changes in the payoff functions of the players introduced at the end of each play. Paper sponsored by Committee on Theory of Traffic Flow. 39.

[Audio] The driving task can be regarded as a process of decision-making under risk or uncertainty where the driver faces various conflict situations..

[Audio] Drivers evaluate their experiences on different routes and select an alternate route to minimize driver stress. The objective of minimizing stress is a more significant factor than direct cost or time considerations in selecting an alternate route. The driver's goal is to minimize total stress or tension in a two-person game against nature. The possible states of nature are represented by the levels of service prevailing on the freeway, each generating a different level of driver tension..

[Audio] The relationship between driver stress and time on any trip can be treated as a linear function of time. The total driver stress on the arterial route, A, and on the expressway route, Ei, can be represented by the formula Ei = d/lO [9(sei/Sa) + 1] A (VeilV~}. The Highway Capacity Manual defines six levels of service on freeways, from A to F, during the afternoon peak period. The driver's strategy on the expressway is represented as 0!1 and on the arterial route as 0!2. The values of Ei are arranged in ascending order, with E1 being the smallest and E4 being the largest. If E4 is smaller than A, the driver will experience less tension on the expressway, making the strategy of taking the expressway a strictly dominant strategy. Conversely, if E1 is larger than A, the strategy of taking the arterial route will strictly dominate. For distance ratios between these two values, there will be optimal mixed strategies, where the driver can minimize their stress by taking the expressway sometimes and the arterial route at other times. The value of p, representing the probability of taking the expressway, can be determined using game theory. If the driver has some knowledge of the probability of each state of nature, the solution to this problem lies in determining the value of p..

[Audio] A ROUTE-SELECTION GAME B' B Arterial Linkage s ·::-.. ~ 1:: Arterial~ Linkage A A' Figure 1. Alternate routes. Michaels (1) has shown that drivers evaluate their experiences on different routes and that they will select an alternate route in order to minimize driver stress. His data indicate further that the objective of minimizing stress is a more significant factor than either direct cost or time considerations in selecting an alternate route. Michaels' results form the basis of an attempt to formulate in game theoretic terms a model of traffic distribution between two alternate routes in an urban area. One such alternate will be an arterial street and the other an expressway with arterial linkages at each end of the trip. The driver's objective is to minimize total stress or tension in a 2-person game against nature. The possible states of nature are represented by the levels of service prevailing on the freeway, each of which generates a different Slide 2.

[Audio] For a driver considering taking the freeway route, it is essential to weigh the potential benefits against the uncertainties associated with freeway traffic conditions. By examining the Hurwicz index, we can better understand the probability of encountering favorable traffic conditions. When the freeway route and arterial alternate are equally long, a minimum probability of 62% is necessary for the freeway route to become attractive. Furthermore, this required probability increases significantly when the distance ratio approaches 1.35. It is crucial for drivers to consider these factors when deciding whether to take the freeway route..

[Audio] The minimax-regret criterion can be used to develop a traffic diversion curve. The criterion can be used to find a mixed strategy that will minimize the maximum possible regret. This strategy can be represented as a linear programming problem. The case of partial knowledge of the state of freeway traffic can be solved by transforming it into a linear programming problem..

[Audio] If a driver knows the current state of freeway traffic, he can make an optimal route selection. However, since the state of traffic changes over time, the driver needs to consider the probability distribution of future traffic states when making his decision. The frequency of announcements about the state of freeway traffic affects how well the driver can estimate these probabilities. With more frequent announcements, the driver can better anticipate the future state of traffic and make a more informed decision. On the other hand, if the announcements are infrequent, the driver must rely on his prior knowledge of the traffic state probabilities, which may lead to suboptimal decisions..

[Audio] As we approach the final slide of our presentation, let's take a closer look at the role of time in the context of freeway traffic. It has been observed that during a freeway report, there is a certain time interval where one element of the state probability vector is dominant over all others. This is the time when a driver can make the most of the information and efficiently plan their route. However, as time passes, the state probabilities approach their limiting values and the driver's information becomes stale. This leads to an increase in regret, especially if the driver is relying on inaccurate or outdated information. In such cases, their minimax regret will approach the values calculated for unknown or uncertain situations. To address this issue, we can assign a dollar value to a driver's regret and use it to design efficient information systems. By selecting the appropriate time interval for providing data on the state of freeway traffic, we can ensure that the cost of information is equal to the total regret of potential freeway users. To further evaluate the efficiency of an information system, we can define it as E = 100 ( 1 - R/R* ), where R is the maximum regret associated with the optimum strategy resulting from the state probability vector r(t), and R* is the minimax regret in uncertain situations. Finally, I would like to conclude by mentioning some relevant references that you can refer to for further reading on this topic. These include studies by Michaels, R. D. on driver attitudes, their responses to different highway designs, and the impact of urban streets on driver tension levels..