Search

Network flows can be used to model numerous real world applications, such as flows in physical networks like electrical, gas, or water networks, flows in traffic networks, or flows of goods in logistic networks. More precisely, many of these applications can be modeled either as minimum cost flows or equilibria of network games, sometimes even both. In this thesis, we study the computational complexity of computing these flows and develop algorithms solving this task. In contrast to the basic static flow models that are widely studied in the literature, we mainly focus on parametric flow models. In particular, we consider settings where the demands, i.e., the external in- and outflow rates, are parametrized by a one-dimensional value. The solution to a parametric flow problem is no longer one static flow but a function mapping the parameter to a static flow satisfying the respective demands. The parametric model allows to analyze the sensitivity of static flows with respect to the in- and outflow. This thesis is subdivided into two parts. The first part is concerned with the minimum cost flow problem with convex costs, with and without parametric demands. We characterize optimal solutions via optimal potentials, analyze the parametric minimum cost flows and its derivatives, and develop an output-polynomial algorithm that can compute solution functions to the parametric minimum cost flow problem for piecewise quadratic cost functions. We extend the algorithm such that it can also be used to approximate the parametric solution for the minimum cost flow problem with more general, convex costs. Since our algorithms can handle the undirected and directed setting, it can be applied to many real-world problems. In a computational study, we test two different algorithms for the computation of parametric minimum cost flows on several traffic and gas instances and find that the algorithms are also applicable in practice. In the second part, we study the parametric computation of Nash equilibria in an atomic splittable congestion games, a special form of network congestion games. We characterize equilibria and show that their computation is a PPAD-complete problem. As a byproduct of our analysis, we also obtain algorithms for the parametric and non-parametric computation of equilibria in atomic splittable congestion games., Netzwerkflüsse können zur Modellierung zahlreicher Anwendungen verwendet werden, zum Beispiel für Flüsse in physikalischen Netzwerken wie Strom-, Gas- oder Wassernetzen, Flüsse in Verkehrsnetzwerken oder Warenflüsse in logistischen Netzwerken. Genauer gesagt können viele dieser Anwendungen entweder als minimale Kostenflüsse oder Gleichgewichte von Netzwerkspielen modelliert werden, manchmal sogar beides. In dieser Arbeit untersuchen wir die Komplexität der Berechnung dieser Flüsse und entwickeln Algorithmen für deren Berechnung. Im Gegensatz zu statischen Flussmodellen, die in der Literatur häufig untersucht werden, konzentrieren wir uns hauptsächlich auf parametrische Flussmodelle. Insbesondere betrachten wir Modelle, bei denen die Nachfragewerte an den Knoten, das heißt die externen Ein- und Ausflussraten, durch einen eindimensionalen Wert parametrisiert sind. Die Lösung eines parametrischen Flussproblems ist nicht mehr ein statischer Fluss, sondern eine Funktion, die jeden Parameter auf einen statischen Fluss für die entsprechende Nachfragen abbildet. Das parametrische Modell erlaubt es, die Sensitivität von statischen Flüssen in Bezug auf den Ein- und Ausfluss zu analysieren. Diese Arbeit gliedert sich in zwei Teile. Der erste Teil befasst sich mit dem minimalen Kostenflussproblem mit konvexen Kosten, sowohl mit und ohne parametrische Nachfragen. Wir charakterisieren optimale Lösungen über optimale Potentiale, analysieren die parametrischen minimalen Kostenflüsse und ihre Ableitungen und entwickeln einen output-polynomialen Algorithmus, der Lösungsfunktionen für das parametrische minimale Kostenflussproblem für stückweise quadratische Kostenfunktionen berechnen kann. Wir erweitern den Algorithmus, sodass er auch zur Approximation von parametrischen Lösungen für das minimale Kostenflussproblem mit allgemeineren, konvexen Kosten verwendet werden kann. Da unsere Algorithmen sowohl für ungerichtete als auch für gerichtete Netzwerke geeignet ist, kann er auf viele reale Probleme angewendet werden. In einer Rechenstudie testen wir zwei verschiedene Algorithmen auf mehreren Verkehrs- und Gasinstanzen und zeigen, dass die Algorithmen auch in der Praxis anwendbar sind. Im zweiten Teil untersuchen wir die parametrische Berechnung von Nash-Gleichgewichten in atomaren, teilbaren Auslastungsspiele (atomic splittable congestion games), einer speziellen Form von Netzwerkstauspielen. Wir charakterisieren Gleichgewichte und zeigen, dass ihre Berechnung ein PPAD-vollständiges Problem ist. Als Nebenprodukt unserer Analyse erhalten wir auch Algorithmen für die parametrische und nicht-parametrische Berechnung von Gleichgewichten.

In this paper, we study N-player Colonel Blotto games with incomplete information about battlefield valuations. Such games arise in job markets, research and development, electoral competition, security analysis, and conflict resolution. For M Ï N + 1 battlefields, we identify a Bayes-Nash equilibrium in which the resource allocation to a given battlefield is strictly monotone in the valuation of that battlefield. We also explore extensions such as heterogeneous budgets, the case M È N, full-support type distributions, and network games. Revised version, February 2021

This work analyzes the minimum tollbooth problem in atomic network congestion games with unsplittable flows. The goal is to place tolls on edges, such that there exists a pure Nash equilibrium in the tolled game that is a social optimum in the untolled one. Additionally, we require the number of tolled edges to be the minimum. This problem has been extensively studied in non-atomic games, however, to the best of our knowledge, it has not been considered for atomic games before. By a reduction from the weighted CNF SAT problem, we show both the NP-hardness of the problem and the W[2]-hardness when parameterizing the problem with the number of tolled edges. On the positive side, we present a polynomial time algorithm for networks on series-parallel graphs that turns any given state of the untolled game into a pure Nash equilibrium of the tolled game with the minimum number of tolled edges., publishedVersion

This thesis is concerned with a certain class of algorithms for the solution of constrained optimization problems and generalized Nash equilibrium problems in Hilbert spaces. This class of algorithms is inspired by the alternating direction method of multipliers (ADMM) and eliminates the constraints using an augmented Lagrangian approach. The alternating direction method consists of splitting the augmented Lagrangian subproblem into smaller and more easily manageable parts. Before the algorithms are discussed, a substantial amount of background material, including the theory of Banach and Hilbert spaces, fixed-point iterations as well as convex and monotone set-valued analysis, is presented. Thereafter, certain optimization problems and generalized Nash equilibrium problems are reformulated and analyzed using variational inequalities and set-valued mappings. The analysis of the algorithms developed in the course of this thesis is rooted in these reformulations as variational inequalities and set-valued mappings. The first algorithms discussed and analyzed are one weakly and one strongly convergent ADMM-type algorithm for convex, linearly constrained optimization. By equipping the associated Hilbert space with the correct weighted scalar product, the analysis of these two methods is accomplished using the proximal point method and the Halpern method. The rest of the thesis is concerned with the development and analysis of ADMM-type algorithms for generalized Nash equilibrium problems that jointly share a linear equality constraint. The first class of these algorithms is completely parallelizable and uses a forward-backward idea for the analysis, whereas the second class of algorithms can be interpreted as a direct extension of the classical ADMM-method to generalized Nash equilibrium problems. At the end of this thesis, the numerical behavior of the discussed algorithms is demonstrated on a collection of examples., Die vorliegende Arbeit behandelt eine Klasse von Algorithmen zur Lösung restringierter Optimierungsprobleme und verallgemeinerter Nash-Gleichgewichtsprobleme in Hilberträumen. Diese Klasse von Algorithmen ist angelehnt an die Alternating Direction Method of Multipliers (ADMM) und eliminiert die Nebenbedingungen durch einen Augmented-Lagrangian-Ansatz. Im Rahmen dessen wird in der Alternating Direction Method of Multipliers das jeweilige Augmented-Lagrangian-Teilproblem in kleinere Teilprobleme aufgespaltet. Zur Vorbereitung wird eine Vielzahl grundlegender Resultate präsentiert. Dies beinhaltet entsprechende Ergebnisse aus der Literatur zu der Theorie von Banach- und Hilberträumen, Fixpunktmethoden sowie konvexer und monotoner mengenwertiger Analysis. Im Anschluss werden gewisse Optimierungsprobleme sowie verallgemeinerte Nash-Gleichgewichtsprobleme als Variationsungleichungen und Inklusionen mit mengenwertigen Operatoren formuliert und analysiert. Die Analysis der im Rahmen dieser Arbeit entwickelten Algorithmen bezieht sich auf diese Reformulierungen als Variationsungleichungen und Inklusionsprobleme. Zuerst werden ein schwach und ein stark konvergenter paralleler ADMM-Algorithmus zur Lösung von separablen Optimierungsaufgaben mit linearen Gleichheitsnebenbedingungen präsentiert und analysiert. Durch die Ausstattung des zugehörigen Hilbertraums mit dem richtigen gewichteten Skalarprodukt gelingt die Analyse dieser beiden Methoden mit Hilfe der Proximalpunktmethode und der Halpern-Methode. Der Rest der Arbeit beschäftigt sich mit Algorithmen für verallgemeinerte Nash-Gleichgewichtsprobleme, die gemeinsame lineare Gleichheitsnebenbedingungen besitzen. Die erste Klasse von Algorithmen ist vollständig parallelisierbar und es wird ein Forward-Backward-Ansatz für die Analyse genutzt. Die zweite Klasse von Algorithmen kann hingegen als direkte Erweiterung des klassischen ADMM-Verfahrens auf verallgemeinerte Nash-Gleichgewichtsprobleme aufgefasst werden. Abschließend wird das Konvergenzverhalten der entwickelten Algorithmen an einer Sammlung von Beispielen demonstriert.

This thesis is concerned with the solution of control and state constrained optimal control problems, which are governed by elliptic partial differential equations. Problems of this type are challenging since they suffer from the low regularity of the multiplier corresponding to the state constraint. Applying an augmented Lagrangian method we overcome these difficulties by working with multiplier approximations in $L^2(\Omega)$. For each problem class, we introduce the solution algorithm, carry out a thoroughly convergence analysis and illustrate our theoretical findings with numerical examples. The thesis is divided into two parts. The first part focuses on classical PDE constrained optimal control problems. We start by studying linear-quadratic objective functionals, which include the standard tracking type term and an additional regularization term as well as the case, where the regularization term is replaced by an $L^1(\Omega)$-norm term, which makes the problem ill-posed. We deepen our study of the augmented Lagrangian algorithm by examining the more complicated class of optimal control problems that are governed by a semilinear partial differential equation. The second part investigates the broader class of multi-player control problems. While the examination of jointly convex generalized Nash equilibrium problems (GNEP) is a simple extension of the linear elliptic optimal control case, the complexity is increased significantly for pure GNEPs. The existence of solutions of jointly convex GNEPs is well-studied. However, solution algorithms may suffer from non-uniqueness of solutions. Therefore, the last part of this thesis is devoted to the analysis of the uniqueness of normalized equilibria., Die vorliegende Arbeit beschäftigt sich mit der Lösung von kontroll- und zustandsbeschränkten Optimalsteuerungsproblemen mit elliptischen partiellen Differentialgleichungen als Nebenbedingungen. Da die zur Zustandsbeschränkung zugehörigen Multiplikatoren nur eine niedrige Regularität aufweisen, sind Probleme dieses Typs besonders anspruchsvoll. Zur Lösung dieser Problemklasse wird ein augmentiertes Lagrange-Verfahren angewandt, das Annäherungen der Multiplikatoren in $L^2(\Omega)$ verwendet. Für jede Problemklasse erfolgt eine Präsentation des Lösungsalgorithmus, eine sorgfältige Konvergenzanalysis sowie eine Veranschaulichung der theoretischen Ergebnisse durch numerische Beispiele. Die Arbeit ist in zwei verschiedene Themenbereiche gegliedert. Der erste Teil widmet sich klassischen Optimalsteuerungsproblemen. Dabei wird zuerst der linear-quadratische und somit konvexe Fall untersucht. Hier setzt sich das Kostenfunktional aus einem Tracking-Type Term sowie einem $L^2(\Omega)$-Regularisierungsterm oder einem $L^1(\Omega)$-Term zusammen. Wir erweitern unsere Analysis auf nichtkonvexe Probleme. In diesem Fall erschwert die Nichtlinearität der zugrundeliegenden partiellen Differentialgleichung die Konvergenzanalysis des zugehörigen Optimalsteuerungsproblems maßgeblich. Der zweite Teil der Arbeit nutzt die Grundlagen, die im ersten Teil erarbeitet wurden und untersucht die allgemeiner gehaltene Problemklasse der Nash-Mehrspielerprobleme. Während die Untersuchung von konvexen verallgemeinerten Nash-Gleichsgewichtsproblemen (engl.: Generalized Nash Equilibrium Problem, kurz: GNEP) mit einer für alle Spieler identischen Restriktion eine einfache Erweiterung von linear elliptischen Optimalsteuerungsproblemen darstellt, erhöht sich der Schwierigkeitsgrad für Mehrspielerprobleme ohne gemeinsame Restriktion drastisch. Die Eindeutigkeit von normalisierten Nash-Gleichgewichten ist, im Gegensatz zu deren Existenz, nicht ausreichend erforscht, was insbesondere eine Schwierigkeit für Lösungsalgorithmen darstellt. Aus diesem Grund wird im letzten Teil dieser Arbeit die Eindeutigkeit von Lösungen gesondert betrachtet.

We characterise the entire set of symmetric stationary Markov-perfect Nash equilibria (MPE) in a differential game of public good investment, using the canonical problem of climate change as an example. We provide a sufficient and necessary condition for MPE and show how the entire set of MPE is constructed. The equilibrium in continuous strategies, unique in our context, is Pareto-dominated by any other equilibrium. If a Pareto- undominated steady state exists, it is sustained by trigger-like strategies, with deviations above and below the steady state leading to different re- sponses. We extend the theory of differential games to deal with payoffs under discontinuous strategies. Our methods work under general functional forms.

We use queuing-related behavior as an instrument for assessing the social appeal of alternative cultural norms. Specifically, we study the behavior of rational and sophisticated individuals who stand in a given queue waiting to be served, and who, in order to speed up the process, consider switching to another queue. We look at two regimes that govern the possible order in which the individuals stand should they switch to the other queue: a regime in which cultural convention, social norms, and basic notions of fairness require that the order in the initial queue is preserved, and a regime without such cultural inhibitions, in which case the order in the other queue is random, with each configuration or sequence being equally likely. We seek to find out whether in these two regimes the aggregate of the behaviors of self-interested individuals adds up to the social optimum defined as the shortest possible total waiting time. To do this, we draw on a Nash Equilibrium setting. We find that in the case of the preserved order, the equilibrium outcomes are always socially optimal. However, in the case of the random order, unless the number of individuals is small, the equilibrium outcomes are not socially optimal.

This thesis is concerned with a class of general-purpose algorithms for constrained minimization problems, variational inequalities, and quasi-variational inequalities in Banach spaces. A substantial amount of background material from Banach space theory, convex analysis, variational analysis, and optimization theory is presented, including some results which are refinements of those existing in the literature. This basis is used to formulate an augmented Lagrangian algorithm with multiplier safeguarding for the solution of constrained optimization problems in Banach spaces. The method is analyzed in terms of local and global convergence, and many popular problem classes such as nonlinear programming, semidefinite programming, and function space optimization are shown to be included as special cases of the general setting. The algorithmic framework is then extended to variational and quasi-variational inequalities, which include, by extension, Nash and generalized Nash equilibrium problems. For these problem classes, the convergence is analyzed in detail. The thesis then presents a rich collection of application examples for all problem classes, including implementation details and numerical results., Die vorliegende Arbeit handelt von einer Klasse allgemein anwendbarer Verfahren zur Lösung restringierter Optimierungsprobleme, Variations- und Quasi-Variationsungleichungen in Banach-Räumen. Zur Vorbereitung wird eine erhebliche Menge an Grundmaterial präsentiert. Dies beinhaltet die Theorie von Banach-Räumen, konvexe und variationelle Analysis sowie Optimierungstheorie. Manche der angegebenen Resultate sind hierbei Verfeinerungen der entsprechenden Ergebnisse aus der Literatur. Im Anschluss wird ein Augmented-Lagrange-Verfahren für restingierte Optimierungsprobleme in Banach-Räumen präsentiert. Der Algorithmus wird hinsichtlich lokaler und globaler Konvergenz untersucht, und viele typische Problemklassen wie nichtlineare Programme, semidefinite Programme oder Optimierungsprobleme in Funktionenräumen werden als Spezialfälle aufgezeigt. Der Algorithmus wird dann auf Variations- und Quasi-Variationsungleichungen verallgemeinert, wodurch implizit auch (verallgemeinerte) Nash-Gleichgewichtsprobleme abgehandelt werden. Für diese Problemklassen werden eigene Konvergenzanalysen betrieben. Die Dissertation beinhaltet zudem eine umfangreiche Sammlung von Anwendungsbeispielen und zugehörigen numerischen Ergebnissen.

We study noncooperative models with two agents and several voluntarily contributed public goods. We focus on interior equilibria in which neither agent is bound by non negativity constraints, establishing the conditions for existence and uniqueness of the equilibrium. While adding-up and homogeneity hold, negativity and symmetry properties are generally violated. We derive the counterpart to the Slutsky matrix, and show that it can be decomposed into the sum of a symmetric and negative semidefinite matrix and another the rank of which never exceeds the number of public goods plus one. Under separability of the public goods the deviation from symmetry is at most rank two.

Although there exist learning processes for which the empirical distribution of play comes close to Nash equilibrium it is an open question whether the players themselves can learn to play equilibrium strategies without assuming that they have prior knowledge of their opponents' strategies and/or payoffs We exhibit a large class of statistical hypotheses testing procedures that solve this problem Consider a finite stage game G that is repeated infinitely often At each time the players have hypotheses about their opponents' repeated game strategies They frequently test their hypotheses against the opponents' recent actions When a hypotheses fails test a new one is adopted Play is almost rational in the sense that at each point of time the players' strategies are є -best replies to their beliefs We show that at least 1 - є of the time t these hypotheses testing strategies constitute an є-equilibrium of the repeated game from t on; in fact the strategies are close to being subgame perfect for long stretches of time Further all players for whom prediction matters ie whose best responses depend on the opponents' behavior learn to predict within є.

We show that the efficient allocation of production capacity can turn a competitive industry and downstream market into an imperfectly competitive one. Even though downstream firms have symmetric production technologies, the downstream industry structure will be symmmetric only if capacity is sufficiently scarce. Otherwise it will be asymmetric, with one large fat capacity-hoarding firm and a fringe of smaller lean and fit firms, so that Tobin`s Q varies inversely with firm size. This is so even if the number of firms is infinitely large. As demand or input quantity varies, the industry may switch between symmetric and asymmetric phases, generating predictions for firm size and costs across the business cycle. Surprisingly, an increase in available capacity resulting in such a switch can cause a reduction in total output and consumer surplus.

In this paper the problem of optimal derivative design, profit maximization and risk minimization under adverse selection when multiple agencies compete for the business of a continuum of heterogenous agents is studied. The presence of ties in the agents' best-response correspondences yields discontinuous payoff functions for the agencies. These discontinuities are dealt with via efficient tie--breaking rules. In a first step, the model presented by Carlier, Ekeland & Touzi (2007) of optimal derivative design by profit-maximizing agencies is extended to a multiple--firm setting, and results of Page & Monteiro (2003, 2007, 2008) are used to prove the existence of (mixed-strategies) Nash equilibria. On a second step we consider the more complex case of risk minimizing firms. Here the concept of socially efficient allocations is introduced, and existence of the latter is proved. It is also shown that in the particular case of the entropic risk measure, there exists an efficient "fix--mix" tie-breaking rule, in which case firms share the whole market over given proportions., 34 pages and 6 figures

Quasilinear preferences on a public good and a numeraire good are limits of preferences where both goods are normal. The set of equilibria of the voluntary contribution (or private provision) game is easily characterized under quasilinearity by: top valuators aggregately contribute their common stand-alone contribution, whereas non-top valuators contribute nothing. Because, as long as preferences are randomly selected, there will typically be a single top valuator, it follows that, typically, the equilibrium is unique, with all players but one contributing nothing, hence “free riding” in the sense of the ordinary English usage of the expression. The upper-hemicontinuity of the Nash equilibrium correspondence implies that this is also the case when both goods are strictly normal, but the wealth effects on the public good are small.

Howard (J Econ Theory 56: 142-159, 1992) argues that the Nash bargaining solution is not Nash implementable, as it does not satisfy Maskin monotonicity. His arguments can be extended to other bargaining solutions as well. However, by defining a social choice correspondence that is based on the solution rather than on its realizations, one can overcome this shortcoming. We even show that such correspondences satisfy a stronger version of monotonicity that is even sufficient for Nash implementability.

Der Nobelpreis für Wirtschaftswissenschaften 2007 wurde an Leonid Hurwicz, Eric S. Maskin und Roger B. Myerson für Ihre grundlegenden Beiträge zur Mechanismus-Design-Theorie vergeben. Worin liegt der Erfolg der Mechanismus-Design-Theorie begründet? Was sind ihre Perspektiven?

Recent healthcare reforms have sought to increase efficiency by introducing managed care (MC) as an alternative to conventional care. This article proposes an institutional change designed to let German consumers choose between the two settings through directing payments from the Federal Health Fund to social health insurers (SHIs) or to specialized MC organizations (MCOs). A game involving a SHI, a MCO, and a representative insured (RI) is analyzed. In a 'threeplayer/three-cake' game the coalitions {SHI, MCO}, {MCO, RI}, and {SHI, RI} can form. Players' possibility to switch between coalitions creates new outside options, causing the bilateral Nash bargaining solution to be replaced by the so-called von Neumann-Morgenstern triple.

Nash recibió el premio Nobel de economía por dos aportes fundamentales: la distinción entre juegos cooperativos y no cooperativos, y el concepto de solución básico para juegos no cooperativos. Myerson indica que este equilibrio es el concepto de solución básico de teoría de juegos dado que, como señala Nash, los juegos cooperativos se pueden reducir a un juego no cooperativo más amplio agregando la negociación previa. El equilibrio de Nash puede verse también como equilibrio de Cournot-Nash porque fue originalmente formulado por Cournot en un modelo de oligopolio, aunque al ser una aplicación específica esto es discutido. El problema fundamental, sin embargo, fue que el análisis de Cournot llevó a polémicas interminables sobre cómo se llega al equilibrio. Otro aporte fundamental de Nash, en mi opinión, es resolver esto con su interpretación racionalista, donde los jugadores conocen la estructura del juego y usan la solución para predecir el equilibrio. Nash introduce así las expectativas racionales. Alternativamente, ofrece una interpretación adaptativa cuando los jugadores no conocen la estructura de juego pero ajustan sus estrategias para maximizar sus pagos, algo anticipado por Cournot al analizar la elasticidad de demanda. La teoría de juegos evolutiva desarrolla esta segunda interpretación. En suma, Nash no solo fue extraordinario como matemático sino como economista.

We consider a class of perfect information unanimity bargaining games, where the players have to choose a payoff vector from a fixed set of feasible payoffs. The proposer and the order of the responding players is determined by a state that evolves stochastically over time. The probability distribution of the state in the next period is determined jointly by the current state and the identity of the player who rejects the current proposal. This protocol encompasses a vast number of special cases studied in the literature. These special cases have in common that equilibria in pure stationary strategies exist, are efficient, are characterized by the absence of delay, and converge to a unique limit corresponding to an asymmetric Nash bargaining solution. For our more general protocol, we show that subgame perfect equilibria in pure stationary strategies need not exist. When such equilibria do exist, they may exhibit delay. Limit equilibria as the players become infinitely patient need not be unique.

We study a structural model of R&D alliance networks in which firms jointly form R&D collaborations to lower their production costs while competing on the product market. We derive the Nash equilibrium of this game, provide a welfare analysis and determine the optimal R&D subsidy program that maximizes total welfare. We also identify the key firms, i.e. the firms whose exit would reduce welfare the most. We then structurally estimate our model using a panel dataset of R&D collaborations and annual company reports. We use our estimates to identify the key firms and analyze the impact of R&D subsidy programs. Moreover, we analyze temporal changes in the rankings of key firms and how these changes affect the optimal R&D policy.

Unilateral carbon policies are inefficient due to the fact that they generally involve emission reductions in countries with high marginal abatement costs and because they are subject to carbon leakage. In this paper, we ask whether the use of carbon tariffs—tariffs on the carbon embodied in imported goods—might lower the cost of achieving a given reduction in world emissions. Specifically, we explore the role tariffs might play as an inducement to unregulated countries adopting emission controls of their own. We use an applied general equilibrium model to generate the payoffs of a policy game. In the game, a coalition of countries regulates its own emissions and chooses whether or not to employ carbon tariffs against unregulated countries. Unregulated countries may respond by adopting emission regulations of their own, retaliating against the carbon tariffs by engaging in a trade war, or by pursuing no policy at all. In the unique Nash equilibrium produced by this game, the use of carbon tariffs by coalition countries is credible. China and Russia respond by adopting binding abatement targets to avoid being subjected to them. Other unregulated countries retaliate. Cooperation by China and Russia lowers the global welfare cost of achieving a 10% reduction in global emissions by half relative to the case where coalition countries undertake all of this abatement on their own.

In this thesis we study smoothness properties of primal and dual gap functions for generalized Nash equilibrium problems (GNEPs) and finite-dimensional quasi-variational inequalities (QVIs). These gap functions are optimal value functions of primal and dual reformulations of a corresponding GNEP or QVI as a constrained or unconstrained optimization problem. Depending on the problem type, the primal reformulation uses regularized Nikaido-Isoda or regularized gap function approaches. For player convex GNEPs and QVIs of the so-called generalized `moving set' type the respective primal gap functions are continuously differentiable. In general, however, these primal gap functions are nonsmooth for both problems. Hence, we investigate their continuity and differentiability properties under suitable assumptions. Here, our main result states that, apart from special cases, all locally minimal points of the primal reformulations are points of differentiability of the corresponding primal gap function. Furthermore, we develop dual gap functions for a class of GNEPs and QVIs and ensuing unconstrained optimization reformulations of these problems based on an idea by Dietrich (``A smooth dual gap function solution to a class of quasivariational inequalities'', Journal of Mathematical Analysis and Applications 235, 1999, pp. 380--393). For this purpose we rewrite the primal gap functions as a difference of two strongly convex functions and employ the Toland-Singer duality theory. The resulting dual gap functions are continuously differentiable and, under suitable assumptions, have piecewise smooth gradients. Our theoretical analysis is complemented by numerical experiments. The solution methods employed make use of the first-order information established by the aforementioned theoretical investigations., In dieser Dissertation wurden die Glattheitseigenschaften von primalen und dualen Gap-Funktionen für verallgemeinerte Nash-Gleichgewichtsprobleme (GNEPs) und Quasi-Variationsungleichungen (QVIs) untersucht. Diese Gap-Funktionen sind Optimalwertfunktionen von primalen und dualen Umformulierungen eines GNEPs oder QVIs als restringiertes oder unrestringiertes Optimierungsproblem. Für gewisse Teilklassen von GNEPs (Spezialfall von `player convex' GNEPs) und QVIs (`generalized moving set case') sind diese primalen Gap-Funktionen überall stetig differenzierbar, für allgemeine GNEPs und QVIs jedoch nicht. Weitere Untersuchungen der Stetigkeit und Differenzierbarkeit ergaben, dass die primalen Gap-Funktionen unter geeigneten Bedingungen, abgesehen von Sonderfällen, in allen lokalen Minima der entsprechenden primalen Umformulierung differenzierbar sind. In dieser Dissertation wurden außerdem duale Gap-Funktionen für bestimmte Klassen von GNEPs und QVIs entwickelt, indem die primalen Gap-Funktionen basierend auf einer Idee von Dietrich (H. Dietrich: A smooth dual gap function solution to a class of quasivariational inequalities. Journal of Mathematical Analysis and Applications 235, 1999, pp. 380--393) als Differenz zweier gleichmäßig konvexer Funktionen dargestellt wurden und auf diese beiden Funktionen die Toland-Singer-Dualitätstheorie angewendet wurde. Es stellte sich heraus, dass diese dualen Gap-Funktionen stetig differenzierbar sind und unter geeigneten Bedingungen sogar stückweise stetig differenzierbare Gradienten besitzen. Die Ergebnisse in dieser Dissertation wurden durch numerische Berechnungen für diverse Testprobleme mittels bekannter Optimierungsverfahren erster Ordnung unterstützt.

Biconcavity is a simple condition on inverse demand that corresponds to the ordinary concept of concavity after simultaneous parameterized transformations of price and quantity. The notion is employed here in the framework of the homogeneous-good Cournot model with potentially heterogeneous firms. The analysis leads to unified conditions, respectively, for the existence of a pure-strategy equilibrium via nonincreasing best-response selections, for existence via quasiconcavity, and for the uniqueness of the equilibrium. The usefulness of the generalizations is illustrated in cases where inverse demand is either “nearly linear” or isoelastic. It is also shown that commonly made assumptions regarding large outputs are often redundant.

We propose the minimum approval mechanism (MAM) for a standard linear public good environment with two players. Players simultaneously and privately choose their contributions to the public good in the first stage. In the second stage, they simultaneously decide whether to approve the other's choice. Both contribute what they choose in the first stage if both players approve; otherwise, both contribute the minimum of the two choices in the first stage. The MAM implements the Pareto-efficient allocation in backward elimination of weakly dominated strategies (BEWDS) and is unique under plausible conditions. Contributions in the MAM experiment overall averaged 94.9%. The data support BEWDS rather than subgame perfect Nash equilibria. Quantifying subjects' responses to the questionnaire showed that the majority of subjects in the MAM found a heuristic or an algorithm named diagonalization and supported the notions of minimax regret and iterated best response, all of which mimic BEWDS outcomes.

We call a correspondence, defined on the set of mixed strategy profiles, a generalized best reply correspondence if it (i) has a product structure, (ii) is upper hemicontinuous, (iii) always includes a best reply to any mixed strategy profile, and (iv) is convex-and closed-valued. For each generalized best reply correspondence, we define a generalized best reply dynamics as a differential inclusion based on it. We call a face of the set of mixed strategy profiles a minimally asymptotically stable face (MASF) if it is asymptotically stable under some such dynamics and no subface of it is asymptotically stable under any such dynamics. The set of such correspondences (and dynamics) is endowed with the partial order of pointwise set inclusion and, under a mild condition on the normal form of the game at hand, forms a complete lattice with meets based on pointwise intersections. The refined best reply correspondence is then defined as the smallest element of the set of all generalized best reply correspondences. We find that every persistent retract (Kalai and Samet 1984) contains a MASF. Furthermore, persistent retracts are minimal CURB (closed under rational behavior) sets (Basu and Weibull 1991) based on the refined best reply correspondence. Conversely, every MASF must be a prep set (Voorneveld 2004), based again, however, on the refined best reply correspondence.

In a number of large, important families of finite games, not only do pure-strategy Nash equilibria always exist but they are also reachable from any initial strategy profile by some sequence of myopic single-player moves to a better or best-response strategy. This weak acyclicity property is shared, for example, by all perfect-information extensive-form games, which are generally not acyclic since even sequences of best-improvement steps may cycle. Weak acyclicity is equivalent to the existence of weak potential, which unlike a potential increases along some rather than every sequence as above, as well as to the existence of an acyclic scheduler, which guarantees convergence to equilibrium by disallowing certain (improvement) moves. A number of sufficient conditions for acyclicity and weak acyclicity are known.

The purpose of this paper is to introduce a novel family of games related to congested networks. Traffic routing has been extensively analyzed from the non-cooperative aspect. A common assumption is that each individual optimizes his route in the network selfishly. However looking at the same network from a different scope in some cases we can find some actors that are responsible for the majority part of the traffic. From the point of view of these actors cooperation is indeed an inherent possibility of the game. Sharing information and cooperation with other agents may result in cost savings, and more efficient utilization of network capacities. Depending on the goal and employed strategy of the agents many possible cooperative games can arise. Our aim is to introduce and analyze these wide variety of transferable utility (TU) games. Since the formation of a coalition may affect other players costs via the implied flow and the resulting edge load changes in the network, externalities may arise, thus the underlying games are given in partition function form.

We present an economic experiment on network formation, in which subjects can decide to form links to one another. Direct links are costly but being connected is valuable. The gametheoretic basis for our experiment is the model of Bala and Goyal (2000). They distinguish between two scenarios regarding the flow of benefits through a network, the so-called 1-way and 2-way flow model. Our main results show that the prediction based on Nash and strict Nash equilibrium works well in the 1-way flow model but fails largely in the 2-way flow model. We observe a strong learning dynamic in the 1-way flow model but less so in the 2-way flow model. Finally, costs of a direct link have a positive impact on the occurrence of (strict) Nash networks in the 1-way flow model but a negative impact in the 2-way flow model. In our discussion on possible explanations for these results we focus on strategic asymmetry and asymmetry with respect to payoffs. We find that the latter asymmetry, i.e., payoff inequity, plays an important role in the network formation process.

Common tax competition models suggest that welfare states will undercut each other's tax rate to attract taxpayers and keep welfare recipients at bay. This will lead to a zero-taxation outcome in the absence of migration costs or other barriers to migration. This paper develops a two-country framework with mobile altruistic taxpayers and immobile welfare recipients. It shows that under the assumption of taxpayers motivated by warm glow altruism, tax competition leads to unique pure strategy Nash equilibria in taxation which are different from zero given sufficiently strong altruistic preferences. If countries are asymmetric with respect to the number of welfare recipients, pure altruism and inequity aversion preferences support additional unique pure strategy Nash equilibria in which the country with the fewer poor attracts more taxpayers and sets higher taxes. This implies that rich countries may benefit from tax competition.

The basic model of the literature on self-enforcing international environmental agreements is a model of autarkic countries. We extend that model by international trade and investigate its impact on the performance of Nash coalitions and on their stability, in particular, in a general equilibrium framework. First we characterize the performance of coalitions and non-coalition countries with regard to emissions and welfare and compare business as usual with the coalition-fringe scenario. In qualitative terms, the results in our free-trade model turn out to be the same as in the basic model for quadratic functional forms. In our model with international trade countries influence the terms of trade with their choice of policy and they make strategic use of that terms-of-trade effect. We find, however, that in the quadratic version of our model - as in the basic model - stable coalitions consist of no more than two countries. Finally, we explore the outcome of trade liberalization by moving from autarky to free trade. Although the coalition steps up its mitigation effort, world emissions rise which may be referred to as a green paradox of trade liberalization. Trade liberalization turns out to be bad for the environment as well as for the coalition countries' welfare and the aggregate welfare of all countries; it reduces the range of profitable coalitions, and it even tends to hamper the formation of stable coalitions.

The paper provides a theoretical foundation for the empirical regularities observed in estimations of wage consequences of overeducation and undereducation. Workers with more education than required for their jobs are observed to suffer wage penalties relative to workers with the same education in jobs that only require their educational level. Similarly, workers with less education than required for their jobs earn wage rewards. These departures from the Mincer human capital earnings function can be explained by Nash bargaining between workers and employers. Under fairly mild assumptions, Nash bargaining predicts a wage penalty for overeducation and a wage reward for undereducation, and further predicts that the wage penalty will exceed the wage reward. This paper reviews the established empirical regularities and then provides Nash bargaining results that explain these regularities.

This paper analyzes efficient pricing at a congested airport dominated by a single firm. Unlike much of the previous literature, we combine a dynamic (bottleneck) model of congestion and a vertical structure model that explicitly considers the role of airlines and passengers. We show that when a Stackelberg leader interacts with a competitive fringe, charging the congestion toll that is derived for fully atomistic carriers to both leader and fringe yields the first-best outcome. This holds regardless of the leader's internalization of congestion in the unregulated equilibrium, and regardless of the assumed demand substitution pattern between firms. This result implies that the financial deficit under optimal pricing may be less severe than what earlier studies suggest. Finally, we show that there are various alternative toll regimes that also induce the welfare maximizing outcome, and therefore widen the set of choices for regulators.

In games with continuum strategy sets, we model a player’s uncertainty about another player’s strategy, as an atomless probability distribution over the other player’s strategy set. We call a strategy profile (strictly) robust to strategic uncertainty if it is the limit, as uncertainty vanishes, of some sequence (all sequences) of strategy profiles in which every player’s strategy is optimal under his or her uncertainty about the others. General properties of this robustness criterion are derived and it is shown that it is a refinement of Nash equilibrium when payoff functions are continuous. We apply the criterion to a class of Bertrand competition games. These are discontinuous games that admit a continuum of Nash equilibria. Our robustness criterion selects a unique Nash equilibrium, and this selection agrees with recent experimental findings.

The apparent ubiquity of progressive taxation in advanced democracies has animated research by political economists in the past decade, but little progress has been made in modeling political equilibria over tax policy when labor supply is elastic with respect to taxation. Here, we postulate an economy with two worker types (wage capacities), in which the unskilled are more numerous than the skilled. Preferences are quasi-linear in income and leisure. One political party represents each worker type. A tax policy is any feasible incentive-compatible menu of pre- and post-tax incomes from which each worker must choose. This policy space is three-dimensional. Workers vote stochastically. The equilibrium concept for political competition is party-unanimity Nash equilibrium (PUNE)—thus, parties are both vote-seeking and representative. The set of political equilibria is characterized. We prove that, if the class of unskilled workers is not too large (but greater than one-half), then there always exist equilibria in which a regressive tax policy wins. If, however, that class is sufficiently numerous, or inequality is sufficiently great, then the victory of a progressive policy is guaranteed in all equilibria.

Several European countries have reformed their labor market institutions. Incentive effects of unemployment benefits have been an important aspect of these reforms. We analyse this issue in a principal-agent model, higher level of unemployment benefits improves the workers' position in wage bargaining, leading to stronger effort incentives and higher output. However, it also reduces incentives for labor market participation. Accordingly, there is a trade-off. We analyze how changes in the economic environment such as globalization and better educated workers affect this trade-off.

We formulate a dynamic game model of trade in an exhaustible resource with a quantity-setting cartel. We compute the feedback Nash equilibrium and two Stackelberg equilibria under two different leadership scenarios: leadership by the strategic importing country, and leadership by the exporting cartel. We numerically show that as compared to the Nash equilibrium, both players are better off if the importing country is the leader. The follower is worse off if the exporting cartel is the leader. Among the three game-theoretic outcomes, the world welfare is highest under the importing country's leadership and lowest under the exporting country's leadership.

We propose an equilibrium concept, the Robust Nash equilibrium (RNE), that combines the best-reply rationality and the first mover invariance condition. The single-stage 2x2 symmetric information game G is transformed into sequential two-stage games with two sub-trees: STA has the row player starting and STB has the column player starting. A profile in G is robust if it is the strict SPNE of the two branches; it is ephemeral if it is not the SPNE of any branch. We show that every strict dominant strategy equilibrium of G is robust but not every strict Nash equilibrium of G is. We show further that every robust profile of G is always a strict Nash equilibrium of G. A Robust Nash equilibrium (RNE) of G is any robust profile of G. The RNE of G is unique. We show in particular that the payoff dominant strict Nash equilibrium of a coordination game G is RNE while the strictly payoff-dominated Nash equilibrium of G is ephemeral. The original Harsanyi-Selten preference for payoff dominance over risk dominance is supported by robustness without invoking collective rationality.

This paper provides four axioms that uniquely characterize the sequential Raiffa solution proposed by Raiffa (1951, 1953) for two-person bargaining games. Three of these axioms are standard and are shared by several popular bargaining solutions. They suffice to characterize these solutions on TU-bargaining games where they coincide. The fourth axiom is a weakening of Kalai's (1977) axiom of step-by-step negotiating and turns out to be sort of a dual condition to a weaker version of Nash's IIA-axiom that together with the three standard axioms suffices to characterize the Nash bargaining solution due to Nash (1950). A conclusion of this axiomatization is that in contrast to all other known bargaining solutions the sequential Raiffa solution does not represent just another kind of fairness or equity condition in addition to the three standard axioms but rather is determined by indefinite repeated application of the three standard axioms.

Social networks, be it on the internet or in real life, facilitate information flows. We model this by giving agents incentives to link with others and receive information through those links. We consider networks where agents have an incentive to confirm the information they receive from others. Our paper analyzes the social networks that are formed. We first study the existence of Nash equilibria and then characterize the set of strict Nash networks. Next, we characterize the set of strictly efficient networks and discuss the relationship between strictly efficient networks and strict Nash networks. Finally, we check the robustness of our results by allowing for heterogeneity among agents, possibility of bilateral deviations of agents, and decay in the network.

We prove the existence of strategically stable sets of pure-strategy Nash equilibria (and hence the existence of pure-strategy trembling-hand perfect equilibria) in potential games that admit an upper semicontinuous potential, and we show that generic potential games possess pure-strategy strictly perfect and essential equilibria. In addition, we provide a link between upper semicontinuity of a potential and conditions defined directly on the payoff functions of a potential game. Finally, we show that stable sets and (strictly) perfect equilibria are related to the set of maximizers of a potential, which refines the set of Nash equilibria. Specifically, the set of maximizers of a potential contains a strategically stable set of pure-strategy Nash equilibria (and hence a pure-strategy trembling-hand perfect equilibrium) and, for generic games, any maximizer of a potential is a pure-strategy strictly perfect and essential equilibrium.

This paper characterizes analytically the optimal tariff of a large one-sector economy with monopolistic competition and firm heterogeneity in general equilibrium, thereby extending the small-country results of Demidova and Rodriguez-Clare (JIE, 2009) and the homogeneous firms framework of Gros (JIE, 1987). The optimal tariff internalizes a markup distortion and a terms of trade externality. It is larger the higher the dispersion of firm-level productivities, and the bigger the country's relative size or relative average productivity. Furthermore, in the two-country Nash equilibrium, tariffs turn out to be strategic substitutes. Small or poor economies set lower Nash tariffs than large or rich ones. Lower transportation costs or smaller fixed market entry costs induce higher equilibrium tariffs and larger welfare losses relative to the case of zero tariffs. Similarly, cross-country productivity or size convergence increases the global welfare loss due to non-cooperative tariff policies. These results suggest that post WWII trends have increased the relative merits of the WTO.

We investigate the relationship between the inner core and asymmetric Nash bargaining solutions for n-person bargaining games with complete information. We show that the set of asymmetric Nash bargaining solutions for different strictly positive vectors of weights coincides with the inner core if all points in the underlying bargaining set are strictly positive. Furthermore, we prove that every bargaining game is a market game. By using the results of Qin (1993) we conclude that for every possible vector of weights of the asymmetric Nash bargaining solution there exists an economy that has this asymmetric Nash bargaining solution as its unique competitive payoff vector. We relate the literature of Trockel (1996, 2005) with the ideas of Qin (1993). Our result can be seen as a market foundation for every asymmetric Nash bargaining solution in analogy to the results on non-cooperative foundations of cooperative games.

This paper yields sufficient conditions for Pareto inoptimality of controls forming Nash equilibria in differential games. In Appendix a result on existence of open loop Nash equilibria is added.

We provide approximation results for Nash equilibria in possibly discontinuous games when payoffs and strategy sets are perturbed, and compare these conditions to those considered in the related literature. We then prove existence results for a new finitistic infinite-game generalization of Selten's [17] notion of perfection, and study some of its properties. The existence results, which rely on the approximation theorems, relate existing notions of perfection to the new specification.

The paper shows that, in some important respects, the differences between the Nash equilibrium and competing concepts such as the quantalresponse equilibrium are smaller than they appear. I start from the observation that, in many experiments, parameter shifts that leave the Nash equilibrium unchanged affect behavior. I explain the direction of change with a heuristic structural approach, relying on properties such as strategic complementarities and increasing differences. I justify the approach using existing comparative statics results for the Nash equilibrium and new comparative statics results for the quantal response equilibrium. Further, I show that the experimental observations can also be rationalized by a model of adjustment to change that does not rely on any equilibrium concept. Finally, I relate the structural approach to equilibrium selection concepts.

Higher-dimensional symmetric games become of more and more importance for applied micro- and macroeconomic research. Standard approaches to uniqueness of equilibria have the drawback that they are restrictive or not easy to evaluate analytically. In this paper I provide some general but comparably simple tools to verify whether a symmetric game has a unique symmetric equilibrium or not. I distinguish between the possibility of multiple symmetric equilibria and asymmetric equilibria which may be economically interesting and is useful to gain further insights into the causes of asymmetric equilibria in symmetric games with higher-dimensional strategy spaces. Moreover, symmetric games may be used to derive some properties of the equilibrium set of certain asymmetric versions of the symmetric game. I further use my approach to discuss the relationship between stability and (in)existence of multiple symmetric equilibria. While there is an equivalence between stability, inexistence of multiple symmetric equilibria and the unimportance of strategic effects for the comparative statics, this relationship breaks down in higher dimensions. Stability under symmetric adjustments is a minimum requirement of a symmetric equilibrium for reasonable comparative statics of symmetric changes. Finally, I present an alternative condition for a symmetric equilibrium to be a local contraction which is more general than the conventional approach of diagonal dominance and yet simpler to evaluate than the eigenvalue condition of continuous adjustment processes.

Es werden verschiedene Verfahren zur Lösung verallgemeinerter Nash-Gleichgewichtsprobleme mit dem Schwerpunkt auf deren globaler Konvergenz entwickelt. Ein globalisiertes Newton-Verfahren zur Berechnung normalisierter Lösungen, ein nichtglattes Optimierungsverfahren basierend auf einer unrestringierten Umformulierung des spieltheoretischen Problems, und ein Minimierungsansatz sowei eine Innere-Punkte-Methode zur Lösung der gemeinsamen Karush-Kuhn-Tucker-Bedingungen der Spieler werden theoretisch untersucht und numerisch getestet. Insbesondere das Innere-Punkte Verfahren erweist sich als das zur Zeit wohl beste Verfahren zur Lösung verallgemeinerter Nash-Gleichgewichtsprobleme., In this thesis different algorithms for the solution of generalized Nash equilibrium problems with the focus on global convergence properties are developed. A globalized Newton method for the computation of normalized solutions, a nonsmooth algorithm based on an optimization reformulation of the game-theoretic problem, and a merit function approach and an interior point method for the solution of the concatenated Karush-Kuhn-Tucker-system are analyzed theoretically and numerically. The interior point method turns out to be one of the best existing methods for the solution of generalized Nash equilibrium problems.

This paper documents the short run and long run behavior of the search and matching model with staggered Nash wage bargaining. It turns out that there is a strong tradeoff inherent in assuming that previously bargained sticky wages apply to new hires. If sticky wages apply to new hires, then the staggered Nash bargaining model can generate realistic volatility in labor input, but it predicts a strong counterfactually negative long run relationship between inflation and unemployment. This finding is robust to including a microeconomically realistic degree of indexation of wages to inflation. The lack of a negative long run relationship between trend inflation and unemployment provides indirect evidence against the proposed mechanism that high inflation systematically makes new hiring more profitable by depressing the real wages of new hires.