Congestion games with mixed objectives

Matthias Feldotto; Lennart Leder; Alexander Skopalik

doi:10.1007/978-3-319-48749-6

Congestion games with mixed objectives

Matthias Feldotto
, Lennart Leder
, Alexander Skopalik

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

2 Downloads (Pure)

Abstract

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

Original language	English
Title of host publication	Combinatorial optimization and applications
Subtitle of host publication	10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016. Proceedings
Editors	T-H. Hubert Chan, Minming Li, Lusheng Wang
Place of Publication	Cham
Publisher	Springer
Pages	655-670
Number of pages	16
ISBN (Electronic)	978-3-319-48749-6
ISBN (Print)	978-3-319-48748-9
DOIs	https://doi.org/10.1007/978-3-319-48749-6
Publication status	Published - 20 Oct 2017
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10043
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Approximation
Bottleneck congestion games
Complexity
Congestion games
Convergence
Existence
Pure Nash equilibrium
n/a OA procedure

Access to Document

10.1007/978-3-319-48749-6

Congestion games with mixed objectives
Feldotto, M., Leder, L. & Skopalik, A., Nov 2018, In: Journal of combinatorial optimization. 36, 4, p. 1145-1167 23 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
2 Link opens in a new tab Citations (Scopus)

335 Downloads (Pure)

Cite this

Feldotto, M., Leder, L., & Skopalik, A. (2017). Congestion games with mixed objectives. In T.-H. H. Chan, M. Li, & L. Wang (Eds.), Combinatorial optimization and applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016. Proceedings (pp. 655-670). (Lecture Notes in Computer Science; Vol. 10043). Springer. https://doi.org/10.1007/978-3-319-48749-6

@inbook{67312ed69c084281913c1676ec76f382,

title = "Congestion games with mixed objectives",

abstract = "We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.",

keywords = "Approximation, Bottleneck congestion games, Complexity, Congestion games, Convergence, Existence, Pure Nash equilibrium, n/a OA procedure",

author = "Matthias Feldotto and Lennart Leder and Alexander Skopalik",

year = "2017",

month = oct,

day = "20",

doi = "10.1007/978-3-319-48749-6",

language = "English",

isbn = "978-3-319-48748-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "655--670",

editor = "Chan, \{T-H. Hubert\} and Li, \{Minming \} and Lusheng Wang",

booktitle = "Combinatorial optimization and applications",

address = "Germany",

}

Feldotto, M, Leder, L & Skopalik, A 2017, Congestion games with mixed objectives. in T-HH Chan, M Li & L Wang (eds), Combinatorial optimization and applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016. Proceedings. Lecture Notes in Computer Science, vol. 10043, Springer, Cham, pp. 655-670. https://doi.org/10.1007/978-3-319-48749-6

Congestion games with mixed objectives. / Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander.
Combinatorial optimization and applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016. Proceedings. ed. / T-H. Hubert Chan; Minming Li; Lusheng Wang. Cham: Springer, 2017. p. 655-670 (Lecture Notes in Computer Science; Vol. 10043).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Congestion games with mixed objectives

AU - Feldotto, Matthias

AU - Leder, Lennart

AU - Skopalik, Alexander

PY - 2017/10/20

Y1 - 2017/10/20

N2 - We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

AB - We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

KW - Approximation

KW - Bottleneck congestion games

KW - Complexity

KW - Congestion games

KW - Convergence

KW - Existence

KW - Pure Nash equilibrium

KW - n/a OA procedure

U2 - 10.1007/978-3-319-48749-6

DO - 10.1007/978-3-319-48749-6

M3 - Chapter

SN - 978-3-319-48748-9

T3 - Lecture Notes in Computer Science

SP - 655

EP - 670

BT - Combinatorial optimization and applications

A2 - Chan, T-H. Hubert

A2 - Li, Minming

A2 - Wang, Lusheng

PB - Springer

CY - Cham

ER -

Congestion games with mixed objectives

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Research output

Congestion games with mixed objectives

Cite this