Computing all solutions of Nash equilibrium problems with discrete strategy sets
Dr. Simone Sagratella
Department of Computer, Control, and Management Engineering Antonio Ruberti, Sapienza - Università di Roma
DEIB - PT1 Room
February 2nd, 2016
5.15 pm
Contact:
Edoardo Amaldi
Research Line:
Operations research amd discrete optimization
Department of Computer, Control, and Management Engineering Antonio Ruberti, Sapienza - Università di Roma
DEIB - PT1 Room
February 2nd, 2016
5.15 pm
Contact:
Edoardo Amaldi
Research Line:
Operations research amd discrete optimization
Sommario
The Nash equilibrium problem (NEP) is a widely used tool to model non-cooperative games. Many solution methods have been proposed in the literature to compute solutions of NEPs with continuous strategy sets, but, besides some specific methods for some particular applications, there are no general algorithms to compute solutions of NEPs in which the strategy set of each player is assumed to be discrete.
We define a branching method to compute the whole solution set of NEPs with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree.
Furthermore for a particular application, i.e. the standard pricing game with indivisible quantities, we give existence results and we propose an extremely fast Jacobi-type method.
Our numerical results show that all proposed algorithms work very well in practice.
We define a branching method to compute the whole solution set of NEPs with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree.
Furthermore for a particular application, i.e. the standard pricing game with indivisible quantities, we give existence results and we propose an extremely fast Jacobi-type method.
Our numerical results show that all proposed algorithms work very well in practice.
Biografia
Simone Sagratella received his B.Sc. and his M.Sc. in management engineering respectively in 2005 and in 2008, all from Sapienza University of Rome, Italy. From 2009 to 2012 hefollowed a Ph.D. program in operations research at Department of Computer, Control, and Management Engineering Antonio Ruberti at Sapienza University of Rome, and received his Ph.D. degree in 2013 with a dissertation on quasi-variational inequalities. He is currently a research fellow at the same department. His research interests include optimization, Nash games, variational inequalities, bilevel programming and big data optimization.