Resource competition on integral polymatroids

DOI10.1007/978-3-319-13129-0_14MaRDI QIDQ2936985zbMATH OpenOpenAlexFDO

Authors Tobias Harks, Max Klimm, Britta Peis

Publication date 7 January 2015

Published in Web and Internet Economics (Search for Journal in Brave)

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

zbMATH Keywords

matroid congestion gamescompetitive resource allocationsingleton congestion games

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: We study competitive resource allocation problems in which players distribute their demands integrally on a set of resources subject to player-specific submodular capacity constraints. Each player has to pay for each unit of demand a cost that is a nondecreasing and convex function of the total allocation of that resource. This general model of resource allocation generalizes both singleton congestion games with integer-splittable demands and matroid congestion games with player-specific costs. As our main result, we show that in such general resource allocation problems a pure Nash equilibrium is guaranteed to exist by giving a pseudo-polynomial algorithm computing a pure Nash equilibrium.

Recommendations

• Equilibrium computation in resource allocation games
• Congestion games with capacitated resources
• Congestion games with capacitated resources
• Dynamic resource allocation games
• Dynamic resource allocation games

Cited in

(10)

• Efficiency of equilibria in uniform matroid congestion games
• Equilibrium computation in resource allocation games
• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• Competitive Resource Allocation Among Urban Congestion Areas in a Modern Big City
• Sensitivity analysis for convex separable optimization over integral polymatroids
• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• A Unified Framework for Pricing in Nonconvex Resource Allocation Games
• A logarithmic approximation for polymatroid congestion games
• On a Reduction for a Class of Resource Allocation Problems
• Network-formation games with regular objectives

This page was built for publication: Resource competition on integral polymatroids

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