Game Theory

Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Frank Navarro Rojas
    • Categories Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    Generalized Nash Equilibrium Problems (GNEPs) are a generalization of the classic Nash Equilibrium Problems (NEPs), where each player’s strategy set depends on the choices of the other players. In this work we study constraint qualifications and optimality conditions tailored for GNEPs and we discuss their relations and implications for global convergence of algorithms. Surprisingly, differently … Read more

    Variational inequality formulation for the games with random payoffs

  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming

    We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case … Read more

    Meta-Modeling to Assess the Possible Future of Paris Agreement

  • Frédéric Babonneau
  • A Bernard
  • Alain Haurie
  • Alain Vielle
    • Categories Game Theory Tags , , , , , ,

    In the meta-modeling approach one builds a numerically tractable dynamic optimization or game model in which the parameters are identified through statistical emulation of a detailed large scale numerical simulation model. In this paper we show how this approach can be used to assess the economic impacts of possible climate policies compatible with the Paris … Read more

    Numerically tractable optimistic bilevel problems

  • Lorenzo Lampariello
  • Simone Sagratella
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Game Theory Tags , ,

    We consider fully convex lower level standard optimistic bilevel problems. We show that this class of mathematical programs is sufficiently broad to encompass significant real-world applications. We establish that the critical points of a relaxation of the original problem correspond to the equilibria of a suitably defined generalized Nash equilibrium problem. The latter game is … Read more

    Payment Mechanisms for Electricity Markets with Uncertain Supply

  • Ryan Cory-Wright
  • Andrew B. Philpott
  • Golbon Zakeri
    • Categories Finance and Economics, Game Theory, Stochastic Programming Tags , , ,

    This paper provides a framework for deriving payment mechanisms for intermittent, flexible and inflexible electricity generators who are dispatched according to the optimal solution of a stochastic program that minimizes the expected cost of generation plus deviation. The first stage corresponds to a pre-commitment decision, and the second stage corresponds to real-time generation that adapts … Read more

    Semidefinite Programming and Nash Equilibria in Bimatrix Games

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Game Theory, Semi-definite Programming Tags , ,

    We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … Read more

    Airport Capacity Extension, Fleet Investment, and Optimal Aircraft Scheduling in a Multi-Level Market Model: On the Effects of Market Regulations

  • Mathias Sirvent
  • Martin Weibelzahl
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Transportation Tags , , , ,

    In this paper we present a four-level market model that accounts for airport capacity extension, fleet investment, aircraft scheduling, and ticket trade in a liberalized aviation market with independent decision makers. In particular, budget-constrained airports decide on the first level on their optimal runway capacity extension and on a corresponding airport charge. Airports anticipate optimal … Read more

    Second-order cone programming formulation for two player zero-sum game with chance constraints

  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming Tags , , , ,

    We consider a two player finite strategic zero-sum game where each player has stochastic linear constraints. We formulate the stochastic constraints of each player as chance constraints. We show the existence of a saddle point equilibrium if the row vectors of the random matrices, defining the stochastic constraints of each player, are elliptically symmetric distributed … Read more

    Moulin Mechanism Design for Freight Consolidation

  • Maged M. Dessouky
  • Alejandro Toriello
  • Nelson A. Uhan
  • Wentao Zhang
    • Categories Game Theory, Supply Chain Management, Transportation

    In freight consolidation, a “fair” cost allocation scheme is critical for forming and sustaining horizontal cooperation that leads to reduced transportation cost. We study a cost-sharing problem in a freight consolidation system with one consolidation center and a common destination. In particular, we design a mechanism that collects bids from a set of suppliers, and … Read more

    The complexity of simple models – a study of worst and typical hard cases for the Standard Quadratic Optimization Problem

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Game Theory, Global Optimization Theory, Quadratic Programming

    In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. … Read more