Game Theory

Stackelberg Games with k-Submodular Function under Distributional Risk-Receptiveness and Robustness

  • Seonghun Park
  • Manish Bansal
    • Categories Game Theory, Robust Optimization, Stochastic Programming

    \(\) We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection using data susceptible to uncertainties and attacks. We focus on Stackelberg games between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender’s objective of maximizing a k-submodular function. We allow uncertainties arising … Read more

    Scheduling Bodyguards

  • Loe Schlicher
    • Categories Game Theory Tags , ,

    Security agencies throughout the world use bodyguards to protect government officials and public figures. In this paper, we consider a two-person zero-sum game between a defender who allocates such bodyguards to protect several targets and an attacker who chooses one target to attack. Because the number of feasible bodyguard allocations grows quickly as either the … Read more

    Freight consolidation through carrier collaboration – A cooperative game

  • Fabio Mercurio
  • Loe Schlicher
  • S.U.K Rohmer
  • Tom Van Woensel
    • Categories Applications - OR and Management Sciences, Game Theory, Transportation Tags , , , ,

    Reducing inefficient truck movements, this research investigates the potential of freight consolidation through carrier collaboration. Considering the financial benefits of consolidation and the additional cost arising from collaboration, we propose a cooperative game to explore under which circumstances carriers can collaborate. We show that stable cost allocations are not always possible, affecting stability and thus … Read more

    Fast convergence of the primal-dual dynamical system and algorithms for a nonsmooth bilinearly coupled saddle point problem

  • Kewei Ding
  • Jörg Fliege
  • Phan Vuong
    • Categories Game Theory, Nonsmooth Optimization Tags , , , ,

    \(\) This paper is devoted to study the convergence rates of a second-order dynamical system and its corresponding discretizations associated with a nonsmooth bilinearly coupled convex-concave saddle point problem. We derive the convergence rate of the primal-dual gap for the second-order dynamical system with asymptotically vanishing damping term. Based on the implicit discretization, we propose … Read more

    A Jacobi-type Newton method for Nash equilibrium problems with descent guarantees

  • Oliver Kolossoski
  • Luís Felipe Bueno
  • Gabriel Haeser
    • Categories Game Theory, Nonlinear Optimization, Other Topics Tags , , , ,

    A common strategy for solving an unconstrained two-player Nash equilibrium problem with continuous variables is applying Newton’s method to the system obtained by the corresponding first-order necessary optimality conditions. However, when taking into account the game dynamics, it is not clear what is the goal of each player when considering they are taking their current … Read more

    Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased

  • Eva Ley
  • Maximilian Merkert
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Game Theory Tags , , ,

    Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include a given set of elements in the solution of their combinatorial problem. If the set of required elements defines a complete follower solution, the inverse combinatorial problem is solvable in polynomial time as soon as … Read more

    Addressing Hierarchical Jointly-Convex Generalized Nash Equilibrium Problems with Nonsmooth Payoffs

  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Game Theory, Other Topics Tags , , , , ,

    We consider a Generalized Nash Equilibrium Problem whose joint feasible region is implicitly defined as the solution set of another Nash game. This structure arises e.g. in multi-portfolio selection contexts, whenever agents interact at different hierarchical levels. We consider nonsmooth terms in all players’ objectives, to promote, for example, sparsity in the solution. Under standard … Read more

    Price of Anarchy in Paving Matroid Congestion Games

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

    Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, … Read more

    Strategy Investments in Matrix Games

  • Raul Garcia
  • Seyedmohammadhossein Hosseinian
  • Mallesh Pai
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags , ,

    We propose an extension of matrix games where the row player may select rows and remove columns, subject to a budget constraint. We present an exact mixed-integer linear programming (MILP) formulation for the problem, provide analytical results concerning its solution, and discuss applications in the security domain. Our computational experiments show heuristic approaches on average … Read more

    Solving Multi-Follower Games

  • Oliver Stein
  • Lorenzo Lampariello
  • Simone Sagratella
  • Valerio Giuseppe Sasso
    • Categories Game Theory Tags , , , ,

    We consider bilevel programs where a single leader interacts with multiple followers who are coupled by a Nash equilibrium problem at the lower level. We generalize the value function reformulation to include multiple followers. This allows us to propose a convergent method based on the sequential convex approximation paradigm, and study the (exact or inexact) … Read more