Papers
Topics
Authors
Recent
Search
2000 character limit reached

A priori data-driven robustness guarantees on strategic deviations from generalised Nash equilibria

Published 11 Apr 2023 in math.OC | (2304.05308v2)

Abstract: In this paper we focus on noncooperative games with uncertain constraints coupling the agents' decisions. We consider a setting where bounded deviations of agents' decisions from the equilibrium are possible, and uncertain constraints are inferred from data. Building upon recent advances in the so called scenario approach, we propose a randomised algorithm that returns a nominal equilibrium such that a pre-specified bound on the probability of violation for yet unseen constraints is satisfied for an entire region of admissible deviations surrounding it, thus supporting neighbourhoods of equilibria with probabilistic feasibility certificates. For the case in which the game admits a potential function, whose minimum coincides with the social welfare optimum of the population, the proposed algorithmic scheme opens the road to achieve a trade-off between the guaranteed feasibility levels of the region surrounding the nominal equilibrium, and its system-level efficiency. Detailed numerical simulations corroborate our theoretical results.

Definition Search Book Streamline Icon: https://streamlinehq.com
References (49)
  1. D. Acemoglu and M. K. Jensen. Aggregate comparative statics. Games and Economic Behavior, 81:27 – 49, 2013.
  2. D. Acemoglu and A. Ozdaglar. Opinion dynamics and learning in social networks. Dynamic Games and Applications, 1(1):3–49, 2011.
  3. M. Aghassi and D. Bertsimas. Robust game theory. Math. Program., 107(1-2):231–273, 2006.
  4. Safe approximations of chance constrained sets by probabilistic scaling. 2019 18th European Control Conference (ECC), pages 1380–1385, 2019.
  5. Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems. IEEE Transactions on Automatic Control, 54(11):2545–2559, 2009.
  6. Studies in the economics of transportation. Yale University Press, 1956.
  7. Randomized sampling for large zero-sum games. Automatica, 49(5):1184–1194, 2013.
  8. G. C. Calafiore. Random convex programs. SIAM Journal on Optimization, 20(6):3427–3464, 2010.
  9. The scenario approach to robust control design. IEEE Transactions on Automatic Control, 51(5):742–753, 2006.
  10. C. F. Camerer. Behavioral Game Theory: Experiments in Strategic Interaction. Princeton University Press, 2003.
  11. M. C. Campi and S. Garatti. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3):1211–1230, 2008.
  12. M. C. Campi and S. Garatti. Wait-and-judge scenario optimization. Mathematical Programming, 167(1):155–189, Jan 2018.
  13. The scenario approach for systems and control design. Annual Reviews in Control, 33(2):149–157, 2009.
  14. A general scenario theory for nonconvex optimization and decision making. IEEE Transactions on Automatic Control, 63(12):4067 – 4078, 2018.
  15. Gaming strategy for electric power with random demand. IEEE Transactions on Power Systems, 20(3):1283–1292, 2005.
  16. The linear programming approach to approximate dynamic programming. Operations Research, 51:850–865, 2003.
  17. On the robustness of equilibria in generalized aggregative games. 2020 59th IEEE Conference on Decision and Control (CDC), pages 3725–3730, 2020.
  18. Probabilistic feasibility guarantees for solution sets to uncertain variational inequalities. Automatica, 137:110120, 2022.
  19. F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. Annals of Operations Research, 175(1):177–211, 2010.
  20. F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer-Verlag New York, 2003.
  21. Decomposition algorithms for generalized potential games. Computational Optimization and Applications, 50(2):237–262, 2011.
  22. F. Fele and K. Margellos. Probabilistic sensitivity of Nash equilibria in multi-agent games: a wait-and-judge approach. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5026–5031, Dec 2019.
  23. F. Fele and K. Margellos. Probably approximately correct Nash equilibrium learning. IEEE Transactions on Automatic Control, 66(9):4238–4245, 2021.
  24. Decentralized convergence to Nash equilibria in constrained deterministic mean field control. IEEE Transactions on Automatic Control, 61(11):3315–3329, 2016.
  25. A scenario approach for non-convex control design. IEEE Transactions on Automatic Control, 61(2):334–345, 2016.
  26. P. T. Harker. Generalized Nash games and quasi-variational inequalities. European Journal of Operational Research, 54(1):81–94, 1991.
  27. Robust Nash equilibria and second-order cone complementarity problems. Journal of Nonlinear and Convex Analysis, 6, 2005.
  28. M. K. Jensen. Aggregative games and best-reply potentials. Economic Theory, 43(1):45–66, 2010.
  29. D. Kahneman and A. Tversky. Prospect theory: An analysis of decision under risk. Econometrica, 47(2):263–291, 1979.
  30. N. S. Kukushkin. Best response dynamics in finite games with additive aggregation. Games and Economic Behavior, 48(1):94–110, 2004.
  31. On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica, 48(1):45–55, 2012.
  32. Systems & control for the future of humanity, research agenda: Current and future roles, impact and grand challenges. Annual Reviews in Control, 43:1–64, 2017.
  33. Chance-constrained sets approximation: A probabilistic scaling approach. Automatica, 137:110–108, 2022.
  34. On the connection between compression learning and scenario based single-stage and cascading optimization problems. IEEE Transactions on Automatic Control, 60(10):2716–2721, 2015.
  35. J. F. Nash. Equilibrium points in N𝑁Nitalic_N-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(48-49), 1950.
  36. Robust nash equilibria in n-person non-cooperative games: Uniqueness and reformulation. Pacific Journal of Optimization, 5(2):237–259, 05 2009.
  37. D. Paccagnan and M. C. Campi. The scenario approach meets uncertain game theory and variational inequalities. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 6124–6129, 2019.
  38. Nash and Wardrop equilibria in aggregative games with coupling constraints. IEEE Transactions on Automatic Control, 64(4):1373–1388, April 2019.
  39. A posteriori probabilistic feasibility guarantees for Nash equilibria in uncertain multi-agent games. IFAC-PapersOnLine, 53(2):3403–3408, 2020. 21st IFAC World Congress.
  40. On the probabilistic feasibility of solutions in multi-agent optimization problems under uncertainty. European Journal of Control, 63:186–195, 2022.
  41. C. R. Plott and V. L. Smith, editors. Handbook of Experimental Economics Results, volume 1. Elsevier, 2008.
  42. A. Rubinstein. Modeling Bounded Rationality. MIT Press, 1998.
  43. W. Rudin. Principles of mathematical analysis. McGraw-Hill, Inc., 3rd edition, 1976.
  44. Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications. IEEE Signal Processing Magazine, 29(5):86–105, 2012.
  45. Randomized solutions to convex programs with multiple chance constraints. SIAM Journal on Optimization, 23, May 2012.
  46. Real and complex monotone communication games. IEEE Transactions on Information Theory, 60(7):4197–4231, July 2014.
  47. Existence of Nash equilibrium for chance-constrained games. Operations Research Letters, 44(5):640 – 644, 2016.
  48. Load shifting in the smart grid: To participate or not? IEEE Transactions on Smart Grid, 7(6):2604–2614, 2016.
  49. D. L. Zhu and P. Marcotte. Co-coercivity and its role in the convergence of iterative schemes for solving variational inequalities. SIAM Journal on Optimization, 6(3):714–726, 1996.
Citations (3)
View on Semantic Scholar

Summary

No one has generated a summary of this paper yet.

Sign Up to Summarize

Paper to Video (Beta)

No one has generated a video about this paper yet.

Sign Up to Generate All Videos Subscribe on YouTube

Whiteboard

No one has generated a whiteboard explanation for this paper yet.

Sign Up to Generate

Open Problems

We haven't generated a list of open problems mentioned in this paper yet.

Generate Now

Continue Learning

We haven't generated follow-up questions for this paper yet.

Generate Now

Collections

Sign up for free to add this paper to one or more collections.

Sign Up