Séminaire Systèmes Complexes – David Fridovich-Keil: Models of noncooperative interaction

⧉ Séminaire Systèmes Complexes • https://bakirtzis.net/seminar Institut Polytechnique de Paris Speaker: David Fridovich-Keil (The University of Texas at Austin) Title: Hierarchical, game-theoretic models of noncooperative interaction Abstract: Hierarchical structure naturally arises in a wide variety of multi-agent scenarios, from supply chain management to vehicle platooning. Unfortunately though, even bilevel problems are notoriously difficult to solve. This talk will review recent progress in two more general, and in some sense complementary, cases. First, we will show that when follower agents have isolated local best responses to leaders’ decisions, we can find local solutions to tree- and forest-structured problems, with complexity scaling polynomially in the problem depth. Second, we will investigate a classical setting which violates this assumption of isolated best responses: lexicographic optimization, where agents optimize for high priority objectives before lower-priority objectives. In this setting, we derive a compact representation of the first-order equilibrium conditions that circumvents the exponential growth in the number of primal and dual variables (with respect to problem depth) that makes existing transcriptions intractable.