Resource competition on integral polymatroids

DOI10.1007/978-3-319-13129-0_14zbMATH Open1406.91218arXiv1407.7650OpenAlexW16002891MaRDI QIDQ2936985FDOQ2936985

Authors: Tobias Harks, Max Klimm, Britta Peis 

Publication date: 7 January 2015

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

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.

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

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

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)

Cited In (8)

• A Unified Framework for Pricing in Nonconvex Resource Allocation Games
• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• Efficiency of equilibria in uniform matroid congestion games
• Sensitivity analysis for convex separable optimization over integral polymatroids
• Network-formation games with regular objectives
• Uniqueness of equilibria in atomic splittable polymatroid congestion games
• A logarithmic approximation for polymatroid congestion games
• On a Reduction for a Class of Resource Allocation Problems

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)