The complexity of Nash Equilibria, Local Optima, and Pareto-Optimal solutions

Röglin, Heiko; Vöcking, Berthold

doi:28564

The complexity of Nash Equilibria, Local Optima, and Pareto-Optimal solutions = Die Komplexität von Nash-Gleichgewichten, lokalen Optima und Pareto-optimalen Lösungen

Röglin, Heiko (Author)

2008

Verantwortlichkeitsangabevorgelegt von Heiko Röglin

ImpressumAachen : Publikationsserver der RWTH Aachen University 2008

Umfang160 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2008

Zusammenfassung in engl. und dt. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Vöcking, Berthold (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2008-04-10

Online
URN: urn:nbn:de:hbz:82-opus-23130
URL: https://publications.rwth-aachen.de/record/50046/files/Roeglin_Heiko.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Nash-Gleichgewicht (Genormte SW) ; Pareto-Optimum (Genormte SW) ; Spieltheorie (Genormte SW) ; Ganzzahlige Optimierung (Genormte SW) ; Informatik (frei) ; Lokale Suche (frei) ; TSP (frei) ; Nash equilibrium (frei) ; Pareto optimum (frei) ; game theory (frei) ; local search (frei) ; integer optimization (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Eine Instanz eines kombinatorischen Optimierungsproblems kann durch eine Menge gültiger Lösungen und eine Zielfunktion beschrieben werden, und das Ziel ist es, eine gültige Lösung auszuwählen, die die Zielfunktion optimiert. Viele alltägliche Entscheidungen, mit denen sich Wirtschaftseinheiten konfrontiert sehen, können nicht als kombinatorische Optimierungsprobleme modelliert werden, weil es z.B. mehrere Zielfunktionen gibt, die nicht zugleich optimiert werden können. Weitere Komplikationen entstehen in Situationen, in denen viele eigennützig handelnde Agenten involviert sind und es nicht möglich ist, eine zentral koordinierte Entscheidung zu treffen. Außerdem erweisen sich selbst Entscheidungen, die als kombinatorisches Optimierungsproblem formuliert werden können, unter Standardannahmen der Komplexitätstheorie oftmals als praktisch unlösbar. Diese Schwierigkeiten haben zur Entwicklung einer Vielzahl unterschiedlicher Lösungskonzepte beigetragen. In dieser Arbeit beschäftigen wir uns insbesondere mit Nash-Gleichgewichten, Pareto-optimalen Lösungen und lokalen Optima. Situationen mit eigennützig handelnden Agenten treten häufig im Zusammenhang mit der Allokation knapper Ressourcen auf und Nash-Gleichgewichte sind das vorherrschende Lösungskonzept in solchen Situationen. Dabei handelt es sich um Zustände, die in der Hinsicht stabil sind, dass kein Agent davon profitieren kann, seine momentane Entscheidung zu ändern. Wir beschäftigen uns mit den beiden in der Ökonomik ausführlich untersuchten Modellen der Congestion-Spiele und zweiseitigen Märkte. Das Problem, ein Nash-Gleichgewicht in einem Congestion-Spiel zu berechnen, kann als lokales Suchproblem aus der Komplexitätsklasse PLS formuliert werden. Wir präsentieren einen neuen Ansatz, der die PLS-Vollständigkeit für diverse Klassen von Congestion-Spielen zeigt und zu einer signifikanten Vereinfachung bereits bekannter Reduktionen für Netzwerk-Congestion-Spiele führt. In zweiseitigen Märkten können Nash-Gleichgewichte effizient berechnet werden, es gibt jedoch in vielen Situationen, in denen dieses Modell Anwendung findet, keine zentrale Stelle, die Agenten einander zuordnet. Wir konstruieren Instanzen, die zeigen, dass Koordination notwendig ist, weil unkoordinierte Agenten im Erwartungswert exponentiell viele Schritte benötigen, um ein Gleichgewicht zu erreichen, wenn sie ihre Strategien in einer zufälligen Reihenfolge verbessern. Wir schließen das Kapitel mit der Einführung eines neuen Modells, das sowohl Congestion-Spiele als auch zweiseitige Märkte verallgemeinert. Der zweite Teil dieser Dissertation beschäftigt sich mit bikriteriellen Optimierungsproblemen. Ein Kompromiss, in dem kein Kriterium verbessert werden kann, ohne das andere zu verschlechtern, heißt Pareto-optimal, und die Menge der Pareto-optimalen Lösungen ist ein wichtiges Lösungskonzept für bikriterielle Probleme. Obwohl man in Anwendungen oft nur wenige Pareto-optimale Lösungen beobachtet, existieren für fast alle bikriteriellen Probleme Instanzen mit exponentiell vielen Pareto-optimalen Lösungen. Der Grund für diese Diskrepanz ist, dass theoretische Ergebnisse auf worst-case Instanzen beruhen, die sich stark von typischen Instanzen, die in der Praxis auftreten, unterscheiden. iesem Problem entgegnen wir, indem wir unseren Analysen das semi-zufällige Eingabemodell der geglätteten Analyse zu Grunde legen, in dem ein Gegner eine Eingabe vorgeben kann, die anschließend einer leichten zufälligen Perturbation unterworfen wird. Wir zeigen eine nahezu scharfe polynomielle Schranke für die erwartete Anzahl Pareto-optimaler Lösungen für bikriterielle Optimierungsprobleme. Als weiteres Ergebnis zeigen wir, wie man auf semi-zufälligen Eingaben die Menge der Pareto-optimalen Lösungen effizient erzeugen kann für Probleme, für die diese Menge im Worst-Case in pseudopolynomieller Zeit erzeugt werden kann. Lokale Suche ist nicht nur interessant wegen des Zusammenhangs mit Nash-Gleichgewichten, sondern spielt auch bei zahlreichen Heuristiken für NP-harte Optimierungsprobleme wie z.B. das Problem des Handlungsreisenden (TSP) eine wichtige Rolle. 2-Opt ist eine sehr einfache lokale Suchheuristik für das TSP, die bemerkenswert gute Ergebnisse in Bezug auf Laufzeit und Approximationsgüte erzielt. Wir konstruieren für jede Lp-Metrik eine Familie von zweidimensionalen Instanzen, auf denen 2-Opt exponentiell viele Schritte machen kann, bevor es ein lokales Optimum erreicht. Um dieses Resultat mit den Beobachtungen in der Praxis in Einklang zu bringen, untersuchen wir auch 2-Opt in einem semi-zufällige Eingabemodell. Wir verbessern bekannte average-case Resultate deutlich und zeigen, dass die erwartete Anzahl lokaler Verbesserungen auf semi-zufälligen Eingaben polynomiell ist. Des Weiteren zeigen wir, dass die erwartete Approximationsgüte auf semi-zufälligen Instanzen polynomiell von der Stärke der Perturbation abhängt.

An instance of a combinatorial optimization problem is usually described by an objective function that is to be optimized over a set of feasible solutions. The decisions that economic entities face every day are more complex for various reasons: In many situations, there is more than one objective and one is rather interested in finding the most appropriate trade-off than in optimizing a single criterion. Further complications arise when decisions are made by selfish agents instead of being centrally coordinated, and even decisions that can be modeled as combinatorial optimization problems are often intractable under standard complexity-theoretic assumptions. These difficulties gave rise to a variety of solution concepts, including Pareto-optimal solutions, Nash equilibria, and local optima, which are the topic of this thesis. When it comes to the allocation of scarce resources, decisions are often made by selfish agents. The predominant solution concept in such situations is that of a Nash equilibrium, which is a state in which no agent can benefit from unilaterally changing her strategy. We consider congestion games and two-sided markets, two extensively studied models for resource allocation among selfish agents. For congestion games, we analyze the complexity of computing a pure Nash equilibrium, and we present a new approach that enables us to prove PLS-hardness results for different classes of congestion games. Our approach also yields a short proof for the PLS-completeness of network congestion games for directed and undirected networks. In two-sided markets, pure Nash equilibria can be computed efficiently, but many real-life markets lack a central authority to match agents. This motivates the study of the processes that take place when players consecutively improve their strategies. We demonstrate that coordination is necessary by constructing examples on which uncoordinated agents need in expectation exponentially many steps to reach an equilibrium if they improve their strategies in a random order. We conclude the part about resource allocation among selfish agents by introducing a natural class of resource sharing games that both extends congestion games and two-sided markets. In the second part of this dissertation, we consider optimization problems with two criteria. Solutions that are optimal in the sense that no criterion can be improved without deteriorating the other one are called Pareto-optimal, and the set of Pareto-optimal solutions is an important solution concept for bicriteria optimization problems as it helps to filter out unreasonable trade-offs. Even though in practice for most bicriteria problems the number of Pareto-optimal solutions is typically small, for almost all bicriteria problems, instances exist with an exponentially large Pareto set. The discrepancy between theory and practice arises because worst-case results are overly pessimistic as inputs occurring in practice are often very different from worst-case instances. We study the number of Pareto-optimal solutions in the framework of smoothed analysis, which is a hybrid of worst-case and average-case analysis, in which an adversary specifies an instance that is subsequently slightly perturbed at random. We prove an almost tight polynomial bound on the expected number of Pareto-optimal solutions for general bicriteria integer optimization problems. For certain problems such as the bicriteria spanning tree problem, there are no algorithms known for enumerating the set of Pareto-optimal solutions efficiently in its size. We present a method that allows us to enumerate the set of Pareto-optimal solutions for semi-random inputs in expected polynomial time with a small failure probability for all problems for which this set can be enumerated in pseudopolynomial time. Local search is not only important because computing pure Nash equilibria can be phrased as a local search problem, but it also plays a crucial role in the design of heuristics for various NP-hard optimization problems. In particular, for the famous traveling salesperson problem, local search heuristics like 2-Opt achieve amazingly good results on real-world instances both with respect to running time and approximation ratio. We present, for every p, a family of two-dimensional Lp instances on which 2-Opt can take an exponential number of steps. In order to explain the discrepancy between this worst-case result and the observations in practice, we analyze 2-Opt in the framework of smoothed analysis. We show that the expected number of local improvements on semi-random Manhattan and Euclidean instances is polynomial, improving previous average-case results significantly. In addition, we prove an upper bound on the expected approximation factor with respect to all Lp metrics that depends polynomially on the magnitude of the random perturbation.

Fulltext:
PDF