FB-03: Game theory, multilevel and dynamic optimization II
Stream: Variational inequalities, Nash games, game theory, multilevel and dynamic optimization
Chair(s): Giancarlo Bigi
Near-Optimal Robust Bilevel Optimization
Miguel F. Anjos, Mathieu Besançon, Luce Brotcorne
We introduce near-optimal robustness for bilevel optimization problems to protect the upper-level decision-maker from bounded rationality at the lower level. We show that it is a restriction of the corresponding pessimistic bilevel problem. Essential properties are derived in generic and specific settings. This model has an intuitive interpretation in various situations cast as bilevel optimization problems. We develop a duality-based solution method for cases where the lower level is convex. The models obtained are successfully tested numerically using different solvers and formulations.
A Bilevel Optimization Model for Poison Attacks on Regression Learning
Zeynep Suvak, Miguel F. Anjos, Luce Brotcorne, Diego Cattaruzza
Poisoning attack is one of the attack types commonly studied in the field of adversarial machine learning. The adversary generating poison attacks is assumed to have access to the training process of a machine learning algorithm and aims to prevent the algorithm from functioning properly by injecting manipulative data while the algorithm is being trained. In this work, our focus is on poisoning attacks against linear regression models which target to weaken the prediction power of the attacked regression model. This problem is formulated as a bilevel optimization problem where the adversary who generates poison attack samples is the leader and the regression learner is the follower. The details of the model, the solution approach and the computational results will be presented.
Best response approaches for optimization problems with equilibrium constraints
Maria Carmela Ceparano, Francesco Caruso, Jacqueline Morgan
We consider a one-leader two-follower Stackelberg game where the leader’s payoff depends on the followers’ actions but the followers’ payoffs do not depend on the leader’s actions. We first present a theoretical method exploiting affine relaxations of the classical best response algorithm which globally converges to an equilibrium for a class of Stackelberg games where the uniqueness of the Nash equilibrium of the game played by the followers is ensured. Then, the convergence of a derivative-free numerical method will be shown, together with error bounds.
An explicit Tikhonov algorithm for nested variational inequalities
Lorenzo Lampariello, Christoph Neumann, Jacopo Maria Ricci, Simone Sagratella, Oliver Stein
We consider nested variational inequalities consisting in a (upper-level) variational inequality whose feasible set is given by the solution set of another (lower-level) variational inequality. Purely hierarchical convex bilevel optimization problems and certain multi-follower games are particular instances of nested variational inequalities. We present an explicit and ready-to-implement Tikhonov-type solution method for such problems. We give conditions that guarantee global strong convergence of the proposed method and we provide a convergence rate analysis.