• search hit 2 of 1836
Back to Result List

Inverse Optimization for Bilevel and Simultaneous Games using Sequential Learning

  • In this thesis, we consider bilevel optimization problems, which are used to model hierarchical, interdependent interactions between two players, a leader and a follower. The leader acts first, anticipating the response of the follower, whose decision is the solution to an optimization problem nested within that of the leader and parameterized by the decision of the former. In addition, we consider mathematical programming games (MPGs), which model simultaneous, non-cooperative interactions between two or more agents, and where each agent solves an optimization problem parameterized by the decisions of the other players. Due to their structure, these models are inherently hard to solve. Further complicating the computation of solutions, the issue of missing or unknown problem data can easily arise, particularly when interacting with other decision-makers. Here, we consider bilevel models in which the follower’s objective function is unknown, and MPGs with unknown players’ objective functions. Nevertheless, while a bilevel or multiplayer game might be challenging to model without exact knowledge about the problem data, the solutions of the interactions between players are usually easily observable in practice. This fact stays at the core of the methods presented in this dissertation and motivates the use of sequentially observed solutions to learn the unknown problem data with an online-learning approach to inverse optimization. For bilevel problems with unknown lower-level objective function we introduce two approaches, which allow the leader to learn the objective of the follower over time. First, we present a multiplicative weights update (MWU) method to emulate the follower’s objective function and prove its convergence. Second, under stronger model assumptions, we introduce a method based on the follower’s KKT conditions, which imputes objective functions that are consistent with the observations. We illustrate the applicability of the two methods on instances of repeatedly played continuous knapsack interdiction problems and bilevel pricing games. Although the theory we present is only related to the lower-level problem, we show empirically that the gained information allows the leader to obtain objective values which tend to those that would be obtained under full information. Furthermore, we consider MPGs with unknown players’ objective functions from the perspective of an external observer. We introduce an MWU-based method, which allows the external observer to iteratively learn objective functions that emulate the decisions of the players. Our case studies on knapsack games show that using this method, the external entity is able to anticipate the decisions of the players and the social welfare of the game.
  • In dieser Arbeit befassen wir uns mit zweistufigen Optimierungsproblemen, die zur Modellierung hierarchischer, voneinander abhängiger Interaktionen zwischen zwei Akteuren – einem Leader und einem Follower – verwendet werden. Der Leader handelt zuerst und antizipiert dabei die Reaktion des Followers, dessen Entscheidung die Lösung eines Optimierungsproblems darstellt, das in das des Leaders eingebettet und durch dessen Entscheidung parametrisiert ist. Darüber hinaus betrachten wir Mathematical Programming Games (MPGs), die simultane, nicht-kooperative Interaktionen zwischen zwei oder mehr Akteuren modellieren und bei denen jeder Akteur ein Optimierungsproblem löst, das durch die Entscheidungen der anderen Akteure parametrisiert ist. Aufgrund ihrer Struktur sind diese Modelle von Natur aus schwer zu lösen. Die Berechnung von Lösungen wird zusätzlich dadurch erschwert, dass leicht das Problem fehlender oder unbekannter Problemdaten auftreten kann, insbesondere bei der Interaktion mit anderen Entscheidungsträgern. Hier betrachten wir Bilevel-Modelle, bei denen die Zielfunktion des Followers unbekannt ist, sowie MPGs mit unbekannten Zielfunktionen der Spieler. Zwar mag die Modellierung eines Bilevel- oder Mehrspieler-Spiels ohne genaue Kenntnis der Problemdaten eine Herausforderung darstellen, doch sind die Lösungen der Interaktionen zwischen den Spielern in der Praxis normalerweise leicht zu beobachten. Diese Tatsache steht im Mittelpunkt der in dieser Dissertation vorgestellten Methoden und motiviert die Verwendung sequenziell beobachteter Lösungen, um die unbekannten Problemdaten mit einem Online-Lernansatz zur inversen Optimierung zu erlernen. Für Bilevel-Probleme mit unbekannter Zielfunktion der unteren Ebene stellen wir zwei Ansätze vor, die es dem Leader ermöglichen, die Zielfunktion des Followers im Laufe der Zeit zu erlernen. Zunächst präsentieren wir eine Methode mit Multiplicative Weights Updates (MWU), um die Zielfunktion des Followers zu emulieren, und beweisen deren Konvergenz. Zweitens führen wir unter stärkeren Modellannahmen eine Methode ein, die auf den KKT-Bedingungen des Followers basiert und Zielfunktionen schätzt, die mit den Beobachtungen konsistent sind. Wir veranschaulichen die Anwendbarkeit der beiden Methoden anhand von Instanzen wiederholt gespielter kontinuierlicher Knapsack-Interdiction-Probleme und zweistufiger Pricing-Probleme. Obwohl sich die von uns vorgestellte Theorie nur auf das Problem der unteren Ebene bezieht, zeigen wir empirisch, dass die gewonnenen Informationen es dem Leader ermöglichen, Zielwerte zu erhalten, die sich denen annähern, die unter vollständiger Information erzielt würden. Darüber hinaus betrachten wir MPGs mit unbekannten Zielfunktionen der Spieler aus der Perspektive eines externen Beobachters. Wir stellen eine MWU-basierte Methode vor, die es dem externen Beobachter ermöglicht, Zielfunktionen iterativ zu erlernen, die die Entscheidungen der Spieler nachbilden. Unsere Fallstudien zu Knapsack-Interdiction-Problemen zeigen, dass die externe Instanz mit dieser Methode in der Lage ist, die Entscheidungen der Spieler und die soziale Wohlfahrt des Spiels vorherzusehen.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ioana Molan
URN:urn:nbn:de:hbz:385-1-29632
Referee:Martin Schmidt, Jan Pablo Burgard, Johannes Thürauf
Advisor:Martin Schmidt
Document Type:Doctoral Thesis
Language:English
Date of completion:2026/10/04
Publishing institution:Universität Trier
Granting institution:Universität Trier
Date of final exam:2026/08/11
Release Date:2026/10/21
Tag:Bilevel Optimization; Inverse Optimization; Mathematical Programming Games; Multiplicative Weights Update Method
Number of pages:V, 118
First page:I
Last page:118
Institutes:Fachbereich 4
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoCC BY: Creative-Commons-Lizenz 4.0 International

$Rev$