Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function

Kenjiro Takazawa ()
Additional contact information
Kenjiro Takazawa: Hosei University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 4, 1043-1065

Abstract: Abstract Congestion games provide a model of human’s behavior of choosing an optimal strategy while avoiding congestion. In the past decade, matroid congestion games have been actively studied and their good properties have been revealed. In most of the previous work, the cost functions are assumed to be univariate or bivariate. In this paper, we discuss generalizations of matroid congestion games in which the cost functions are n-variate, where n is the number of players. First, motivated from polymatroid congestion games with $$\mathrm {M}^\natural $$ M ♮ -convex cost functions, we conduct sensitivity analysis for separable $$\mathrm {M}^\natural $$ M ♮ -convex optimization, which extends that for separable convex optimization over base polyhedra by Harks et al. (SIAM J Optim 28:2222–2245, 2018. https://doi.org/10.1137/16M1107450 ). Second, we prove the existence of pure Nash equilibria in matroid congestion games with monotone cost functions, which extends that for weighted matroid congestion games by Ackermann et al. (Theor Comput Sci 410(17):1552–1563, 2009. https://doi.org/10.1016/j.tcs.2008.12.035 ). Finally, we prove the existence of pure Nash equilibria in matroid resource buying games with submodular cost functions, which extends that for matroid resource buying games with marginally nonincreasing cost functions by Harks and Peis (Algorithmica 70(3):493–512, 2014. https://doi.org/10.1007/s00453-014-9876-6 ).

Keywords: Matroid congestion game; Resource buying game; Pure Nash equilibrium; Monotone set function; Submodular function; $${\mathrm {M}}^\natural $$ M ♮ -convex function (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00435-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00435-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00435-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().