Game Theory

Variational Convergence of Bifunctions: Motivating Applications

  • Alejandro Jofré
  • Roger J.B. Wets
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Game Theory Tags , , , , , , , , ,

    It’s shown that a number of variational problems can be cast as finding the maxinf-points (or minsup-points) of bivariate functions, coveniently abbreviated to bifunctions. These variational problems include: linear and nonlinear complementarity problems, fixed points, variational inequalities, inclusions, non-cooperative games, Walras and Nash equilibrium problems. One can then appeal to the theory of lopsided convergence … Read more

    On the Dynamic Stability of Electricity Markets

  • Mihai Anitescu
  • Victor M. Zavala
    • Categories Complementarity and Variational Inequalities, Dynamic Programming, Game Theory Tags , , , ,

    In this work, we present new insights into the dynamic stability of electricity markets. In particular, we discuss how short forecast horizons, incomplete gaming, and physical ramping constraints can give rise to stability issues. Using basic concepts of market efficiency, Lyapunov stability, and predictive control, we construct a new stabilizing market design. A numerical case … Read more

    Cost-sharing mechanisms for scheduling under general demand settings

  • Sindhura Balireddi
  • Nelson A. Uhan
    • Categories Game Theory, Scheduling

    We investigate cost-sharing mechanisms for scheduling cost-sharing games. We assume that the demand is general—that is, each player can be allocated one of several levels of service. We show how to design mechanisms for these games that are weakly group strategyproof, approximately budget-balanced, and approximately efficient, using approximation algorithms for the underlying scheduling problems. We … Read more

    Minimum cost subset selection with two competing agents

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

    We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item that may be … Read more

    A Game-Theoretical Dynamic Model for Electricity Markets

  • Aswin Kannan
  • Victor M. Zavala
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Game Theory Tags , , , , , , ,

    We present a game-theoretical dynamic model for competitive electricity markets.We demonstrate that the model can be used to systematically analyze the effects of ramp constraints, initial conditions, dynamic disturbances, forecast horizon, bidding frequency, and some other factors on the price signals.We illustrate the capabilities of the model using a numerical case study Article Download View … Read more

    Two stage stochastic equilibrium problems with equilibrium constraints: modeling and numerical schemes

  • Huifu Xu
  • Dali Zhang
    • Categories Complementarity and Variational Inequalities, Game Theory, Stochastic Programming Tags , , ,

    This paper presents a two stage stochastic equilibrium problem with equilibrium constraints(SEPEC) model. Some source problems which motivate the model are discussed. Monte Carlo sampling method is applied to solve the SEPEC. The convergence analysis on the statistical estimators of Nash equilibria and Nash stationary points are presented. Article Download View Two stage stochastic equilibrium … Read more

    Approximating the Least Core Value and Least Core of Cooperative Games with Supermodular Costs

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Approximation Algorithms, Game Theory, Graphs and Matroids

    We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time … Read more

    On the Equivalencey of Linear Programming Problems and Zero-Sum Games

  • Ilan Adler
    • Categories Game Theory, Linear Programming Tags , , , , ,

    In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more

    Fast population game dynamics for dominant sets and other quadratic optimization problems

  • Immanuel M. Bomze
  • Marcello Pelillo
  • Samuel Rota-Bulo
    • Categories Data-Mining, Game Theory, Quadratic Programming Tags ,

    We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more

    Flows and Decompositions of Games: Harmonic and Potential Games

  • Ozan Candogan
  • Ishai Menache
  • Asuman Ozdaglar
  • Pablo A. Parrilo
    • Categories Game Theory Tags , , ,

    In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this … Read more