Game Theory

Addressing Hierarchical Jointly-Convex Generalized Nash Equilibrium Problems with Nonsmooth Payoffs

  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Game Theory, Other Topics Tags , , , , ,

    We consider a Generalized Nash Equilibrium Problem whose joint feasible region is implicitly defined as the solution set of another Nash game. This structure arises e.g. in multi-portfolio selection contexts, whenever agents interact at different hierarchical levels. We consider nonsmooth terms in all players’ objectives, to promote, for example, sparsity in the solution. Under standard … Read more

    Price of Anarchy in Paving Matroid Congestion Games

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

    Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, … Read more

    Strategy Investments in Matrix Games

  • Raul Garcia
  • Seyedmohammadhossein Hosseinian
  • Mallesh Pai
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags , ,

    We propose an extension of matrix games where the row player may select rows and remove columns, subject to a budget constraint. We present an exact mixed-integer linear programming (MILP) formulation for the problem, provide analytical results concerning its solution, and discuss applications in the security domain. Our computational experiments show heuristic approaches on average … Read more

    Solving Multi-Follower Games

  • Oliver Stein
  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Game Theory Tags , , , ,

    We consider bilevel programs where a single leader interacts with multiple followers who are coupled by a Nash equilibrium problem at the lower level. We generalize the value function reformulation to include multiple followers. This allows us to propose a convergent method based on the sequential convex approximation paradigm, and study the (exact or inexact) … Read more

    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

    Fighting Terrorism: How to position Rapid Response Teams?

  • Lotte van Aken
  • Geert-Jan van Houtum
    • Categories Applications - OR and Management Sciences, Game Theory Tags , ,

    In light of recent terrorist attacks, we introduce and study a Stackelberg game between a government and a terrorist. In this game, the government positions a number of heavily-armed rapid response teams on a line segment (e.g., a long boulevard or shopping avenue) and then the terrorist attacks a location with the highest damage. This … Read more

    Cooperative locker locations games

  • Fabio Mercurio
  • 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