Game Theory

An exact solution method for binary equilibrium problems with compensation and the power market uplift problem

  • Daniel Huppmann
  • Sauleh Siddiqui
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Game Theory Tags , , , , , ,

    We propose a novel method to fi nd Nash equilibria in games with binary decision variables by including compensation payments and incentive-compatibility constraints from non-cooperative game theory directly into an optimization framework in lieu of using first order conditions of a linearization, or relaxation of integrality conditions. The reformulation off ers a new approach to obtain and … Read more

    The cone condition and nonsmoothness in linear generalized Nash games

  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories Game Theory, Nonsmooth Optimization

    We consider linear generalized Nash games and introduce the so-called cone condition which characterizes the smoothness of the Nikaido-Isoda function under weak assumptions. The latter mapping arises from a reformulation of the generalized Nash equilibrium problem as a possibly nonsmooth optimization problem. Other regularity conditions like LICQ or SMFC(Q) are only sufficient for smoothness, but … Read more

    Achieving Cost-Effective Power Grid Hardening through Transmission Network Topology Control

  • Wei Yuan
  • Bo Zeng
    • Categories Applications - Science and Engineering, Game Theory Tags , , ,

    Vulnerability of power grid is a critical issue in power industry. In order to understand and reduce power grid vulnerability under threats, existing research often employs defender-attacker-defender (DAD) models to derive effective protection plans and evaluate grid performances under various contingencies. Transmission line switching (also known as topology control) is an effective operation to mitigate … Read more

    A close look at auxiliary problem principles for equilibria

  • Giancarlo Bigi
  • Mauro Passacantando
    • Categories Complementarity and Variational Inequalities, Game Theory

    The auxiliary problem principle allows solving a given equilibrium problem (EP) through an equivalent auxiliary problem with better properties. The paper investigates two families of auxiliary EPs: the classical auxiliary problems, in which a regularizing term is added to the equilibrium bifunction, and the regularized Minty EPs. The conditions that ensure the equivalence of a … Read more

    Justification of Constrained Game Equilibrium Models

  • Igor V. Konnov
    • Categories Basic Sciences Applications, Complementarity and Variational Inequalities, Game Theory

    We consider an extension of a noncooperative game where players have joint binding constraints. In this model, the constrained equilibrium can not be implemented within the same noncooperative framework and requires some other additional regulation procedures. We consider several approaches to resolution of this problem. In particular, a share allocation method is presented and substantiated. … Read more

    On the shortest path game

  • Andreas Darmann
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Game Theory, Graphs and Matroids Tags , , ,

    In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (agents/players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in … Read more

    Scheduling the Tasks of Two Agents with a Central Selection Mechanism

  • Gaia Nicosia
  • Ulrich Pferschy
  • Andrea Pacifici
    • Categories Combinatorial Optimization, Game Theory, Scheduling Tags , ,

    We address a class of deterministic scheduling problems in which two agents compete for the usage of a single machine. The agents have their own objective functions and submit in each round an arbitrary, unprocessed task from their buffer for possible selection. In each round the smaller of the two submitted tasks is chosen and … Read more

    Computation of Stochastic Nash Equilibrium via Variable Sample Distributed Methods

  • Ming Dong
  • Lizhi Wang
  • Dali Zhang
    • Categories Game Theory, Stochastic Programming Tags

    In this paper, we propose a variable sample distributed algorithm for the computation of stochastic Nash equilibrium in which the objective functions are replaced, at each iteration, by sample average approximations. We investigate the contraction mapping properties of the variable sample distributed algorithm and show that the accuracy of estimators yielded in the algorithms to … Read more

    Dynamic Cost Allocation for Economic Lot Sizing Games

  • Alejandro Toriello
  • Nelson A. Uhan
    • Categories Game Theory, Production and Logistics Tags , ,

    We consider a cooperative game defined by an economic lot sizing problem with concave ordering costs over a finite time horizon, in which each player faces demand for a single product in each period and coalitions can pool orders. We show how to compute a dynamic cost allocation in the strong sequential core of this … Read more

    Dynamic Linear Programming Games with Risk-Averse Players

  • Alejandro Toriello
  • Nelson A. Uhan
    • Categories Applications - OR and Management Sciences, Game Theory, Stochastic Programming Tags , ,

    Motivated by situations in which independent agents, or players, wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk … Read more