Game Theory

Smoothness Properties of a Regularized Gap Function for Quasi-Variational Inequalities

  • Nadja Harms
  • Oliver Stein
  • Christian Kanzow
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Game Theory Tags , , , , ,

    This article studies continuity and differentiability properties for a reformulation of a finite-dimensional quasi-variational inequality (QVI) problem using a regularized gap function approach. For a special class of QVIs, this gap function is continuously differentiable everywhere, in general, however, it has nondifferentiability points. We therefore take a closer look at these nondifferentiability points and show, … Read more

    Optimal Power Grid Protection through A Defender-Attacker-Defender Model

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

    Power grid vulnerability is a major concern of modern society, and its protection problem is often formulated as a tri-level defender-attacker-defender model. However, this tri-level problem is compu- tationally challenging. In this paper, we design and implement a Column-and-Constraint Generation algorithm to derive its optimal solutions. Numerical results on an IEEE system show that: (i) … Read more

    A New Error Bound Result for Generalized Nash Equilibrium Problems and its Algorithmic Application

  • Axel Dreves
  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Game Theory, Nonlinear Optimization Tags , , , , ,

    We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Newton method. We base our local convergence theory on an error bound and provide a new sufficient condition for it to hold that … Read more

    The Subset Sum Game

  • Andreas Darmann
  • Gaia Nicosia
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Combinatorial Optimization, Game Theory Tags , , ,

    In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in … Read more

    Equilibria on the Day-Ahead Electricity Market

  • Margarida Carvalho
  • João Pedro Pedroso
    • Categories Finance and Economics, Game Theory

    In the energy sector, there has been a transition from monopolistic to oligopolistic situations (pool markets); each time more companies’ optimization revenues depend on the strategies of their competitors. The market rules vary from country to country. In this work, we model the Iberian Day-Ahead Duopoly Market and find exactly which are the outcomes (Nash … Read more

    A Fair, Sequential Multiple Objective Optimization Algorithm

  • Can Kizilkale
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Game Theory Tags , ,

    In multi-objective optimization the objective is to reach a point which is Pareto ecient. However we usually encounter many such points and choosing a point amongst them possesses another problem. In many applications we are required to choose a point having a good spread over all objective functions which is a direct consequence of the … Read more

    Open versus closed loop capacity equilibria in electricity markets under perfect and oligopolistic competition

  • Julian Barquín
  • Daniel Ralph
  • E. Centeno
  • Benjamin Hobbs
  • S. Wogrin
    • Categories Applications - OR and Management Sciences, Game Theory

    We consider two game-theoretic models of the generation capacity expansion problem in liberalized electricity markets. The first is an open loop equilibrium model, where generation companies simultaneously choose capacities and quantities to maximize their individual profit. The second is a closed loop model, in which companies first choose capacities maximizing their profit anticipating the market … Read more

    On Traveling Salesman Games with Asymmetric Costs

  • Alejandro Toriello
  • Nelson A. Uhan
    • Categories Combinatorial Optimization, Game Theory, Integer Programming

    We consider cooperative traveling salesman games with non-negative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques … Read more

    Moneyless strategy-proof mechanism on single-sinked policy domain: characterization and applications

  • Donglei Du
  • Qiaoming Han
    • Categories Approximation Algorithms, Game Theory Tags , , , , , , , ,

    We completely characterize deterministic strategy-proof and group strategy-proof mechanisms on single-sinked public policy domain. The single-sinked domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents’ preferences have a single most loathful point (the sink) in the interval, and the preferences … Read more

    Simultaneous approximation of multi-criteria submodular function maximization

  • Donglei Du
  • Dachuan Xu
  • Naihua Xiu
  • Li Yu
    • Categories Approximation Algorithms, Game Theory, Multi-Criteria Optimization Tags , , ,

    Recently there has been intensive interest on approximation of the NP-hard submodular maximization problem due to their theoretical and practical significance. In this work, we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization. We address existence and nonexistence results for both deterministic and randomized approximation when the … Read more