Interfaces between Optimization and Game Theory

WD-03: Interfaces between Optimization and Game Theory
Stream: Variational inequalities, Nash games, game theory, multilevel and dynamic optimization
Room: Nash
Chair(s): Laura Rosa Maria Scrimali

Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
Veronica Piccialli, Giampaolo Liuzzi, Marco Locatelli, Stefan Rass
In this work, 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 that minimize a linear payoff functional. In this paper an additional quadratic term is added to the minimization problem representing switching costs, i.e., the costs for the defender of switching from a given strategy to another one. The resulting problem is a nonconvex QP problem with linear constraints, that is NP-hard. We propose an effective branch and bound for solving it.

Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
Pavel Dvurechensky
We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distributedly stored over a network. We assume there is a network of agents/machines/computers, and each agent holds a private continuous probability measure and seeks to compute the barycenter of all the measures in the network by getting samples from its local measure and exchanging information with its neighbors. Motivated by this problem, we develop, and analyze, a novel accelerated primal-dual stochastic gradient method

Solving non-monotone equilibrium problems via a DIRECT-type approach
Mauro Passacantando, Stefano Lucidi, Francesco Rinaldi
A global optimization approach for solving non-monotone equilibrium problems (EPs) is proposed. The class of (regularized) gap functions is used to reformulate any EP as a constrained global optimization program and some bounds on the Lipschitz constant of such functions are provided. The proposed approach is a combination of an improved version of the DIRECT algorithm with local minimizations. Unlike most existing solution methods for EPs, no monotonicity-type condition is assumed in this paper. Preliminary numerical results on several classes of EPs show the effectiveness of the approach.

Theme: Overlay by Kaira