Game Theory

Learning how to play Nash, potential games and alternating minimization method for structured nonconvex problems on Riemannian manifolds

  • J. X. da Cruz Neto
  • Paulo Roberto Oliveira
  • Antoine Soubeyran
  • Pedro A. Soares Jr.
    • Categories Applications - Science and Engineering, Game Theory, Nonsmooth Optimization

    In this paper we consider minimization problems with constraints. We show that if the set of constaints is a Riemannian manifold of non positive curvature and the objective function is lower semicontinuous and satisfi es the Kurdyka-Lojasiewicz property, then the alternating proximal algorithm in Euclidean space is naturally extended to solve that class of problems. We … Read more

    On Differentiability Properties of Player Convex Generalized Nash Equilibrium Problems

  • Nadja Harms
  • Oliver Stein
  • Christian Kanzow
    • Categories Constrained Nonlinear Optimization, Game Theory, Nonsmooth Optimization Tags , , , , ,

    This article studies differentiability properties for a reformulation of a player convex generalized Nash equilibrium problem as a constrained and possibly nonsmooth minimization problem. By using several results from parametric optimization we show that, apart from exceptional cases, all locally minimal points of the reformulation are differentiability points of the objective function. This justifies a … Read more

    A Primal-Dual Algorithm for Computing a Cost Allocation in the Core of Economic Lot-Sizing Games

  • Mohan Gopaladesikan
  • Nelson A. Uhan
  • Jikai Zou
    • Categories Combinatorial Optimization, Game Theory, Production and Logistics

    We consider the economic lot-sizing game with general concave ordering cost functions. It is well-known that the core of this game is nonempty when the inventory holding costs are linear. The main contribution of this work is a combinatorial, primal-dual algorithm that computes a cost allocation in the core of these games in polynomial time. … Read more

    A semi-discrete in time approximation for a model first order-finite horizon mean field game problem

  • F. Camilli
  • Francisco J. Silva
    • Categories Game Theory Tags ,

    In this article we consider a model first order mean field game problem, introduced by J.M. Lasry and P.L. Lions. Its solution $(v,m)$ can be obtained as the limit of the solutions of the second order mean field game problems, when the \textit{noise} parameter tends to zero. We propose a semi-discrete in time approximation of … Read more

    Welfare-Maximizing Correlated Equilibria using Kantorovich Polynomials with Sparsity

  • Fook Wai Kong
  • Berc Rustem
    • Categories Game Theory, Global Optimization, Semi-definite Programming Tags , , , , ,

    We propose an algorithm that computes the epsilon-correlated equilibria with global-optimal (i.e., maximum) expected social welfare for single stage polynomial games. We first derive an infinite-dimensional formulation of epsilon-correlated equilibria using Kantorovich polynomials and re-express it as a polynomial positivity constraint. In addition, we exploit polynomial sparsity to achieve a leaner problem formulation involving Sum-Of-Squares … Read more

    The Complexity of Egalitarian Mechanisms for Linear Programming Games

  • Nelson A. Uhan
    • Categories Combinatorial Optimization, Game Theory

    We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P = NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming … Read more

    A Bilevel Direct Search Method for Leader-Follower Optimization Problems and Applications

  • Gui-Hua Lin
  • Dali Zhang
    • Categories Game Theory, Other Topics, Stochastic Programming Tags , , , ,

    In the paper, we propose a bilevel direct search method for solving a type of leader-follower problems with each decision maker’s objective being a “black-box” function. First, we give a description for a leader-follower optimization problem. Then, we investigate a bilevel direct search method including two algorithms for combinatorially solving the upper and lower level … Read more

    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