ISE faculty member Ted Ralphs, in partnership with Oleg Prokopyev at University of Pittsburgh, has won a three-year, half million dollar grant from the Office of Naval Research to study how to more realistically model and solve certain game-theoretic optimization problems. The idea behind the project is to relax the stringent assumptions underlying classical models of human behavior in game theory, which consider all players to be completely rational. Although “rationality” sounds like a reasonable assumption, the technical meaning of “rationality” goes beyond the conversational interpretation, e.g., “rational thinking,” which is usually taken informally to mean thinking that is clear-headed and logical. In the technical interpretation, rationality requires that all decision-makers are equipped to determine a precise optimum to any optimization problem they face. In the real world, however, the sheer complexity of the problems faced by a decision-maker may make it impossible to behave rationally, in this technical sense.
This may not seem crucial, but when this important assumption does not hold, sophisticated algorithms for analyzing classical game-theoretic models may no longer produce good results. Even in the case of a simple leader-follower game in which the leader makes an initial decision and the follower reacts, the leader’s optimal strategy under the assumption that the follower is acting rationally can be very different from the optimal strategy if the follower is instead using a sub-optimal heuristic. The result is that even if the leader is using technically superior algorithmic technology, the false assumption of rationality may lead to the generation of strategies by the leader that are far from optimal.
In this project, Ralphs and his co-PI at University of Pittsburgh are studying how to incorporate various notions of “bounded rationality” that are more appropriate for modeling real-world behavior into efficient algorithms. So-called “interdiction problems,” naturally arising in defense applications, provide a classic example of a leader-follower game in which the leader attempts to disrupt the activities of the follower. In this case, the follower, is, e.g., a smuggler and the leader is a law enforcement agency that must choose which potential smuggling routes to surveil in order to minimize the activity of the smugglers. Counterintuitively, relaxing the standard assumption of rationality may actually make the leader’s problem harder, in a sense, since the behavior of an irrational follower may be more difficult to predict. Thus, one avenue of investigation is how to produce solutions that are more robust against unpredictable behavior by the follower.