You Can't Always Get What You Want: Games of Ordered Preference
Dong Ho Lee, Lasse Peters, David Fridovich-Keil
AI summary
Problem
Existing methods for multi-agent decision-making struggle to handle hierarchical preferences without causing solver infeasibility or ill-conditioning, and single-agent hierarchical techniques do not extend to interactive game settings.
Approach
The authors recursively substitute nested optimization levels with their Karush-Kuhn-Tucker conditions to form Mathematical Programs with Complementarity Constraints, then apply a sequence of tight relaxations to transcribe the entire game into a Mixed Complementarity Problem.
Key results
- Recursive derivation of first-order optimality conditions for nested preference hierarchies
- Development of a relaxation technique to transcribe hierarchical games into Mixed Complementarity Problems
- Demonstration of reliable convergence to generalized Nash equilibria that strictly respect preference priorities
- Superior performance over penalty-based approximation baselines in multi-agent driving scenarios
Why it matters
Enables robust, scalable decision-making for autonomous agents facing prioritized, conflicting goals in interactive multi-agent environments.
Abstract
We study noncooperative games, in which each player’s objective is composed of a sequence of ordered—and po- tentially conflicting—preferences. Problems of this type naturally model a wide variety of scenarios: for example, drivers at a busy intersection must balance the desire to make forward progress with the risk of collision. Mathematically, these problems possess a nested structure, and to behave properly players must prioritize their most important preference, and only consider less important preferences to the extent that they do not compromise performance on more important ones. We consider multi-agent, noncooperative variants of these problems, and seek generalized Nash equilibria in which each player’s decision reflects both its hierarchy of prefer- ences and other players’ actions. We make two key contributions. First, we develop a recursive approach for deriving the first-order optimality conditions of each player’s nested problem. Second, we propose a sequence of increasingly tight relaxations, each of which can be transcribed as a mixed complementarity problem and solved via existing methods. Experimental results demonstrate that our approach reliably converges to equilibrium solutions that strictly reflect players’ individual ordered preferences.