Nash equilibrium problems with congestion costs and shared constraints

Huibing Yin; Uday V. Shanbhag; Prashant G. Mehta

doi:10.1109/CDC.2009.5400502

Nash equilibrium problems with congestion costs and shared constraints

Huibing Yin, Uday V. Shanbhag, Prashant G. Mehta

Marcus Department of Industrial and Manufacturing Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

Abstract

Generalized Nash equilibria (GNE) represent extensions of the Nash solution concept when agents have shared strategy sets. This generalization is particularly relevant when agents compete in a networked setting. In this paper, we consider such a setting and focus on a congestion game in which agents contend with shared network constraints. We make two sets of contributions: (1) Under two types of congestion cost functions, we prove the existence of the primal generalized Nash equilibrium. The results are provided without a compactness assumption on the constraint set and are shown to hold when the mappings associated with the resulting variational inequality are non-monotone. Under further assumptions, the local and global uniqueness of the primal and primal-dual generalized Nash equilibrium is also provided. (2) We provide two distributed schemes for obtaining such equilibria: a dual and a primal-dual algorithm. Convergence of both algorithms is analyzed and preliminary numerical evidence is presented with the aid of an example.

Original language	English (US)
Title of host publication	Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4649-4654
Number of pages	6
ISBN (Print)	9781424438716
DOIs	https://doi.org/10.1109/CDC.2009.5400502
State	Published - 2009
Event	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 - Shanghai, China Duration: Dec 15 2009 → Dec 18 2009

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Other

Other	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Country/Territory	China
City	Shanghai
Period	12/15/09 → 12/18/09

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.2009.5400502

Cite this

Yin, H., Shanbhag, U. V., & Mehta, P. G. (2009). Nash equilibrium problems with congestion costs and shared constraints. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 (pp. 4649-4654). Article 5400502 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2009.5400502

Yin, Huibing ; Shanbhag, Uday V. ; Mehta, Prashant G. / Nash equilibrium problems with congestion costs and shared constraints. Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc., 2009. pp. 4649-4654 (Proceedings of the IEEE Conference on Decision and Control).

@inproceedings{f0e912a8fc9546f49e0848603ae649f4,

title = "Nash equilibrium problems with congestion costs and shared constraints",

abstract = "Generalized Nash equilibria (GNE) represent extensions of the Nash solution concept when agents have shared strategy sets. This generalization is particularly relevant when agents compete in a networked setting. In this paper, we consider such a setting and focus on a congestion game in which agents contend with shared network constraints. We make two sets of contributions: (1) Under two types of congestion cost functions, we prove the existence of the primal generalized Nash equilibrium. The results are provided without a compactness assumption on the constraint set and are shown to hold when the mappings associated with the resulting variational inequality are non-monotone. Under further assumptions, the local and global uniqueness of the primal and primal-dual generalized Nash equilibrium is also provided. (2) We provide two distributed schemes for obtaining such equilibria: a dual and a primal-dual algorithm. Convergence of both algorithms is analyzed and preliminary numerical evidence is presented with the aid of an example.",

author = "Huibing Yin and Shanbhag, {Uday V.} and Mehta, {Prashant G.}",

year = "2009",

doi = "10.1109/CDC.2009.5400502",

language = "English (US)",

isbn = "9781424438716",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4649--4654",

booktitle = "Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009",

address = "United States",

note = "48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 ; Conference date: 15-12-2009 Through 18-12-2009",

}

Yin, H, Shanbhag, UV & Mehta, PG 2009, Nash equilibrium problems with congestion costs and shared constraints. in Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009., 5400502, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 4649-4654, 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009, Shanghai, China, 12/15/09. https://doi.org/10.1109/CDC.2009.5400502

Nash equilibrium problems with congestion costs and shared constraints. / Yin, Huibing; Shanbhag, Uday V.; Mehta, Prashant G.
Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc., 2009. p. 4649-4654 5400502 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Nash equilibrium problems with congestion costs and shared constraints

AU - Yin, Huibing

AU - Shanbhag, Uday V.

AU - Mehta, Prashant G.

PY - 2009

Y1 - 2009

N2 - Generalized Nash equilibria (GNE) represent extensions of the Nash solution concept when agents have shared strategy sets. This generalization is particularly relevant when agents compete in a networked setting. In this paper, we consider such a setting and focus on a congestion game in which agents contend with shared network constraints. We make two sets of contributions: (1) Under two types of congestion cost functions, we prove the existence of the primal generalized Nash equilibrium. The results are provided without a compactness assumption on the constraint set and are shown to hold when the mappings associated with the resulting variational inequality are non-monotone. Under further assumptions, the local and global uniqueness of the primal and primal-dual generalized Nash equilibrium is also provided. (2) We provide two distributed schemes for obtaining such equilibria: a dual and a primal-dual algorithm. Convergence of both algorithms is analyzed and preliminary numerical evidence is presented with the aid of an example.

AB - Generalized Nash equilibria (GNE) represent extensions of the Nash solution concept when agents have shared strategy sets. This generalization is particularly relevant when agents compete in a networked setting. In this paper, we consider such a setting and focus on a congestion game in which agents contend with shared network constraints. We make two sets of contributions: (1) Under two types of congestion cost functions, we prove the existence of the primal generalized Nash equilibrium. The results are provided without a compactness assumption on the constraint set and are shown to hold when the mappings associated with the resulting variational inequality are non-monotone. Under further assumptions, the local and global uniqueness of the primal and primal-dual generalized Nash equilibrium is also provided. (2) We provide two distributed schemes for obtaining such equilibria: a dual and a primal-dual algorithm. Convergence of both algorithms is analyzed and preliminary numerical evidence is presented with the aid of an example.

UR - http://www.scopus.com/inward/record.url?scp=77950811663&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950811663&partnerID=8YFLogxK

U2 - 10.1109/CDC.2009.5400502

DO - 10.1109/CDC.2009.5400502

M3 - Conference contribution

AN - SCOPUS:77950811663

SN - 9781424438716

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4649

EP - 4654

BT - Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

Y2 - 15 December 2009 through 18 December 2009

ER -

Yin H, Shanbhag UV, Mehta PG. Nash equilibrium problems with congestion costs and shared constraints. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc. 2009. p. 4649-4654. 5400502. (Proceedings of the IEEE Conference on Decision and Control). doi: 10.1109/CDC.2009.5400502

Nash equilibrium problems with congestion costs and shared constraints

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this