Game Theory

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    Cost-Sharing Mechanism Design for Ride-Sharing

  • Maged M. Dessouky
  • Nelson A. Uhan
  • Shichun Hu
  • Phebe Vayanos
    • Categories Game Theory, Transportation

    In this paper, we focus on the cost-sharing problem for ride-sharing that determines how to allocate the total ride cost between the driver and the passengers. We identify the properties that a desirable cost-sharing mechanism should have and develop a general framework which can be used to create specific cost-sharing mechanisms. We propose specific mechanisms … Read more

    The Price of Anarchy in Series-Parallel Network Congestion Games

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

    We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (2010) proved that the PoA is … Read more

    An equivalent mathematical program for games with random constraints

  • Monika Arora
  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming Tags , , ,

    This paper shows that there exists a Nash equilibrium of an n-player chance-constrained game for elliptically symmetric distributions. For a certain class of payoff functions, we suitably construct an equivalent mathematical program whose global maximizer is a Nash equilibrium. Article Download View An equivalent mathematical program for games with random constraints

    Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories Cutting Plane Approaches, Game Theory, Polyhedra Tags , ,

    Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more

    Complexity Aspects of Fundamental Questions in Polynomial Optimization

  • Jeffrey Zhang
    • Categories Game Theory, Global Optimization Theory, Nonlinear Optimization Tags , , , ,

    In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) testing local minimality of a candidate point, and (iii) deciding attainment of the optimal value. Our results characterize the complexity of these three questions for all degrees of the … Read more

    A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction

  • Veronika Grimm
  • Lars Schewe
  • Martin Schmidt
  • Daniel Nowak
  • Alexandra Schwartz
  • Gregor Zöttl
    • Categories Applications - OR and Management Sciences, Game Theory, Global Optimization Tags , , ,

    While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower … Read more

    No-regret Learning in Price Competitions under Consumer Reference Effects

  • Negin Golrezaei
  • Patrick Jaillet
  • Jason Cheuk Nam Liang
    • Categories Applications - OR and Management Sciences, Finance and Economics, Game Theory Tags , , ,

    We study long-run market stability for repeated price competitions between two firms, where consumer demand depends on firms’ posted prices and consumers’ price expectations called reference prices. Consumers’ reference prices vary over time according to a memory-based dynamic, which is a weighted average of all historical prices. We focus on the setting where firms are … Read more

    Characterization of an Anomalous Behavior of a Practical Smoothing Technique

  • Pedro Borges de Melo
    • Categories Game Theory, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    A practical smoothing method was analyzed and tested against state-of-the-art solvers for some non-smooth optimization problems in [BSS20a; BSS20b]. This method can be used to smooth the value functions and solution mappings of fully parameterized convex problems under mild conditions. In general, the smoothing of the value function lies from above the true value function … Read more

    Mixed Integer Bilevel Optimization with k-optimal Follower: A Hierarchy of Bounds

  • Xueyu Shi
  • Oleg A. Prokopyev
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags ,

    We consider mixed integer bilevel linear optimization problems in which the decision variables of the lower-level (follower’s) problem are all binary. We propose a general modeling and solution framework motivated by the practical reality that in a Stackelberg game, the follower does not always solve their optimization problem to optimality. They may instead implement a … Read more