Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature
 
conference paper

Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature

Sessa, Pier Giuseppe
•
Kamgarpour, Maryam  
•
Krause, Andreas
April 11, 2019
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics
The 22nd International Conference on Artificial Intelligence and Statistics

Games with continuous strategy sets arise in several machine learning problems (e.g. adversarial learning). For such games, simple no-regret learning algorithms exist in several cases and ensure convergence to coarse correlated equilibria (CCE). The efficiency of such equilibria with respect to a social function, however, is not well understood. In this paper, we define the class of valid utility games with continuous strategies and provide efficiency bounds for their CCEs. Our bounds rely on the social function being a monotone DR-submodular function. We further refine our bounds based on the curvature of the social function. Furthermore, we extend our efficiency bounds to a class of non-submodular functions that satisfy approximate submodularity properties. Finally, we show that valid utility games with continuous strategies can be designed to maximize monotone DR-submodular functions subject to disjoint constraints with approximation guarantees. The approximation guarantees we derive are based on the efficiency of the equilibria of such games and can improve the existing ones in the literature. We illustrate and validate our results on a budget allocation game and a sensor coverage problem.

  • Details
  • Metrics
Type
conference paper
Author(s)
Sessa, Pier Giuseppe
Kamgarpour, Maryam  
Krause, Andreas
Date Issued

2019-04-11

Publisher

PMLR

Published in
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics
Start page

2017

End page

2027

URL
https://proceedings.mlr.press/v89/sessa19a.html
Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
SYCAMORE  
Event nameEvent date
The 22nd International Conference on Artificial Intelligence and Statistics

2019-04-11

Available on Infoscience
December 1, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/183312
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés