  


Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
Giampaolo Liuzzi(giampaolo.liuzziiasi.cnr.it) 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 NPhard 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 branchandbound approach where a predominant role is played by an optimalitybased domain reduction, based on the multiple solutions of LP problems at each node of the branchandbound 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; BranchandBound; BoundTightening 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  