Game Theory

A Criterion Space Search Feasibility Pump Heuristic for Solving Maximum Multiplicative Programs

  • Ashim Khanal
  • Hadi Charkhgard
    • Categories Game Theory, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    We study a class of nonlinear optimization problems with diverse practical applications, particularly in cooperative game theory. These problems are referred to as Maximum Multiplicative Programs (MMPs), and can be conceived as instances of “Optimization Over the Frontier” in multiobjective optimization. To solve MMPs, we introduce a feasibility pump-based heuristic that is specifically designed to … Read more

    A Tutorial on Solving Single-Leader-Multi-Follower Problems using SOS1 Reformulations

  • Didier Aussel
  • Cecile Egea
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Game Theory Tags , , ,

    In this tutorial we consider single-leader-multi-follower games in which the models of the lower-level players have polyhedral feasible sets and convex objective functions. This situation allows for classic KKT reformulations of the separate lower-level problems, which lead to challenging single-level reformulations of MPCC type. The main contribution of this tutorial is to present a ready-to-use … Read more

    Playing Stackelberg security games in perfect formulations

  • Victor Bucarey
  • Pamela Bustamante-Faúndez
  • Vladimir
  • Martine Labbé
  • Fernando Ordóñez
    • Categories Applications - OR and Management Sciences, Game Theory, Network Optimization

    Protecting critical infrastructure from intentional damage requires foreseeing the strategies of possible attackers. The problem faced by the defender of such infrastructure can be formulated as a Stackelberg security game. A defender must decide what specific targets to protect with limited resources, maximizing their expected utility (e.g., minimizing damage value) and considering that a second … Read more

    Algorithms for Cameras View-Frame Placement Problems in the Presence of an Adversary and Distributional Ambiguity

  • Seonghun Park
  • Manish Bansal
    • Categories Combinatorial Optimization, Game Theory, Stochastic Programming Tags , , ,

    In this paper, we introduce cameras view-frame placement problem (denoted by CFP) in the presence an adversary whose objective is to minimize the maximum coverage by p cameras in response to input provided by n autonomous agents in a remote location. We allow uncertainty in the success of attacks, incomplete information of the probability distribution … Read more

    Cooperative locker locations games

  • Fabio Mercurio
  • Loe Schlicher
  • S.U.K Rohmer
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Game Theory, Other Topics Tags , ,

    More and more people are ordering products online, having their parcels delivered to their homes. This leads to more congestion, which negatively impacts the environment as well as public health and safety. To reduce these negative impacts, carriers can use parcel lockers to consolidate and serve their customers. The implementation of a locker network can, … Read more

    A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport

  • Veronika Grimm
  • Michael Hintermueller
  • Olivier Huber
  • Lars Schewe
  • Martin Schmidt
  • Gregor Zöttl
    • Categories Game Theory, Infinite Dimensional Optimization, Systems governed by Differential Equations Optimization Tags , , , ,

    We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, … Read more

    Inefficiency of pure Nash equilibria in network congestion games: the impact of symmetry and graph structure

  • Bainian Hao
  • Carla Michini
    • Categories Combinatorial Optimization, Game Theory Tags , , , ,

    We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games. We first explore the impact of symmetry on the worst-case PoA of network congestion games. For polynomial delay functions with highest degree p, we construct a family of symmetric congestion games over arbitrary networks which achieves the same worst-case PoA of … Read more

    A branch-and-bound algorithm for non-convex Nash equilibrium problems

  • Peter Kirst
  • Stefan Schwarze
  • Oliver Stein
    • Categories Game Theory Tags , , , ,

    This paper introduces a spatial branch-and-bound method for the approximate computation of the set of all epsilon-Nash equilibria of continuous box-constrained non-convex Nash equilibrium problems. We explain appropriate discarding and fathoming techniques, provide a termination proof for a prescribed approximation tolerance, and report our computational experience. Article Download View A branch-and-bound algorithm for non-convex Nash … Read more

    A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Oliver Kolossoski
    • Categories Game Theory, Other Topics Tags , , , , ,

    A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system of nonlinear equations obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering that they … Read more

    Two-stage distributionally robust noncooperative games: Existence of Nash equilibrium and its application to Cournot-Nash competition

  • Atsushi Hori
  • Nobuo Yamashita
    • Categories Game Theory Tags , , ,

    Two-stage distributionally robust stochastic noncooperative games with continuous decision variables are studied. In such games, each player solves a two-stage distributionally robust optimization problem depending on the decisions of the other players. Existing studies in this area have been limited with strict assumptions, such as linear decision rules, and supposed that each player solves a … Read more