Uniqueness of equilibria in atomic splittable polymatroid congestion games

DOI10.1007/978-3-319-45587-7_9MaRDI QIDQ2835665zbMATH OpenOpenAlexFDO

Authors Tobias Harks, Veerle Timmermans

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.01375, http://link.springer.com/10.1007/s10878-017-0166-5

Mathematics Subject Classification ID

Applications of graph theory (05C90) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Noncooperative games (91A10) Combinatorial aspects of matroids and geometric lattices (05B35) Games involving graphs (91A43)

Abstract: We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on polymatroid theory: when the strategy space of every player is a bidirectional flow polymatroid, then equilibria are unique. Bidirectional flow polymatroids are introduced as a subclass of polymatroids possessing certain exchange properties. We show that important cases such as base orderable matroids can be recovered as a special case of bidirectional flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and nonmatroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.

Recommendations

• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• On the uniqueness of equilibrium in atomic splittable routing games
• scientific article; zbMATH DE number 7051244
• The uniqueness property for networks with several origin-destination pairs
• Efficiency of equilibria in uniform matroid congestion games

Cites work

• A polynomial cycle canceling algorithm for submodular flows
• Collusion in atomic splittable routing games
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Comments on bases in dependence structures
• Competitive routing in networks with polynomial costs
• Discrete Convex Analysis
• Equilibrium computation in atomic splittable singleton congestion games
• Exchange systems, matchings, and transversals
• Local smoothness and the price of anarchy in splittable congestion games
• On the impact of combinatorial structure on congestion games
• On the relationship between Nash—Cournot and Wardrop equilibria
• Pure Nash equilibria in player-specific and weighted congestion games
• Resource buying games
• Resource competition on integral polymatroids
• Stackelberg strategies and collusion in network games with splittable flow
• Submodular functions and independence structures
• The impact of oligopolistic competition in networks
• The uniqueness property for networks with several origin-destination pairs
• Topological Conditions for Uniqueness of Equilibrium in Networks
• Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users

Cited in

(5)

• The uniqueness property for networks with several origin-destination pairs
• Equilibrium and inefficiency in multi-product Cournot games
• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• scientific article; zbMATH DE number 7051244 (Why is no real title available?)
• On the uniqueness of equilibrium in atomic splittable routing games

This page was built for publication: Uniqueness of equilibria in atomic splittable polymatroid congestion games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835665)