Optimization Online


Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems

Giampaolo Liuzzi(giampaolo.liuzzi***at***iasi.cnr.it)
Marco Locatelli(marco.locatelli***at***unipr.it)
Veronica Piccialli(veronica.piccialli***at***uniroma2.it)
Stefan Rass(Stefan.Rass***at***aau.at)

Abstract: In this paper we address a game theory problem arising in the context of network security. In traditional game theory problems, given a defender and an attacker, one searches for mixed strategies which minimize a linear payoff functional. In the problem addressed in this paper an additional quadratic term is added to the minimization problem. Such term represents switching costs, i.e., the costs for the defender of switching from a given strategy to another one at successive rounds of the game. The resulting problem is a nonconvex QP problem with linear constraints. We prove that, though simple when one of the two terms in the objective function is missing, the problem is, in general, a NP-hard one. The proof is based on a reduction from the decision version of the clique problem. Next, we discuss different reformulations and bounds for such problem. Finally, we show, through an extensive set of computational experiments, that the most promising approach to tackle this problem appears to be a branch-and-bound approach where a predominant role is played by an optimality-based domain reduction, based on the multiple solutions of LP problems at each node of the branch-and-bound tree. The computational cost per node is, thus, high but this is largely compensated by the rather small size of the corresponding tree.

Keywords: Game Theory; Nonconvex Quadratic Programming Problems; Branch-and-Bound; Bound-Tightening

Category 1: Global Optimization (Applications )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Other Topics (Game Theory )

Citation: arXiv:2002.12599 [math.OC]

Download: [PDF]

Entry Submitted: 03/02/2020
Entry Accepted: 03/02/2020
Entry Last Modified: 03/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society