Budget-restricted utility games with ordered strategic decisions

Maximilian Drees; Sören Riechers; Alexander Skopalik

doi:10.1007/978-3-662-44803-8_10

Budget-restricted utility games with ordered strategic decisions

Maximilian Drees^*, Sören Riechers, Alexander Skopalik

^*Corresponding author for this work

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

6 Citations (Scopus)

16 Downloads (Pure)

Abstract

We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

Original language	English
Title of host publication	Algorithmic Game Theory
Subtitle of host publication	7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings
Editors	Ron Lavi
Pages	110-121
Number of pages	12
ISBN (Electronic)	978-3-662-44803-8
DOIs	https://doi.org/10.1007/978-3-662-44803-8_10
Publication status	Published - 1 Jan 2014
Externally published	Yes
Event	7th International Symposium on Algorithmic Game Theory, SAGT 2014 - Haifa, Israel Duration: 30 Sept 2014 → 2 Oct 2014 Conference number: 7 http://sagt-2014.iew.technion.ac.il/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	8768
ISSN (Print)	0302-9743

Conference

Conference	7th International Symposium on Algorithmic Game Theory, SAGT 2014
Abbreviated title	SAGT 2014
Country/Territory	Israel
City	Haifa
Period	30/09/14 → 2/10/14
Internet address	http://sagt-2014.iew.technion.ac.il/

Access to Document

10.1007/978-3-662-44803-8_10

budgetAccepted author version, 451 KB

Cite this

Drees, M., Riechers, S., & Skopalik, A. (2014). Budget-restricted utility games with ordered strategic decisions. In R. Lavi (Ed.), Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings (pp. 110-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8768). https://doi.org/10.1007/978-3-662-44803-8_10

Drees, Maximilian ; Riechers, Sören ; Skopalik, Alexander. / Budget-restricted utility games with ordered strategic decisions. Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. editor / Ron Lavi. 2014. pp. 110-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{96a677b23b3e4e538dfe0e1ff4a96cb9,

title = "Budget-restricted utility games with ordered strategic decisions",

abstract = "We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.",

author = "Maximilian Drees and S{\"o}ren Riechers and Alexander Skopalik",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-662-44803-8_10",

language = "English",

isbn = "978-3-662-44802-1",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "110--121",

editor = "Ron Lavi",

booktitle = "Algorithmic Game Theory",

note = "7th International Symposium on Algorithmic Game Theory, SAGT 2014, SAGT 2014 ; Conference date: 30-09-2014 Through 02-10-2014",

url = "http://sagt-2014.iew.technion.ac.il/",

}

Drees, M, Riechers, S & Skopalik, A 2014, Budget-restricted utility games with ordered strategic decisions. in R Lavi (ed.), Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8768, pp. 110-121, 7th International Symposium on Algorithmic Game Theory, SAGT 2014, Haifa, Israel, 30/09/14. https://doi.org/10.1007/978-3-662-44803-8_10

Budget-restricted utility games with ordered strategic decisions. / Drees, Maximilian; Riechers, Sören; Skopalik, Alexander.
Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. ed. / Ron Lavi. 2014. p. 110-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8768).

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

TY - GEN

T1 - Budget-restricted utility games with ordered strategic decisions

AU - Drees, Maximilian

AU - Riechers, Sören

AU - Skopalik, Alexander

N1 - Conference code: 7

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

AB - We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

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

U2 - 10.1007/978-3-662-44803-8_10

DO - 10.1007/978-3-662-44803-8_10

M3 - Conference contribution

AN - SCOPUS:84922192198

SN - 978-3-662-44802-1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 110

EP - 121

BT - Algorithmic Game Theory

A2 - Lavi, Ron

T2 - 7th International Symposium on Algorithmic Game Theory, SAGT 2014

Y2 - 30 September 2014 through 2 October 2014

ER -

Drees M, Riechers S, Skopalik A. Budget-restricted utility games with ordered strategic decisions. In Lavi R, editor, Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. 2014. p. 110-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-44803-8_10

Budget-restricted utility games with ordered strategic decisions

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this