Uniqueness of equilibria in atomic splittable polymatroid congestion games

DOI10.1007/978-3-319-45587-7_9zbMATH Open1432.91029arXiv1512.01375OpenAlexW2955411360MaRDI QIDQ2835665FDOQ2835665

Authors: Tobias Harks, Veerle Timmermans 

Publication date: 30 November 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1512.01375

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)