We study the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the cost of each element and the polytope. Under convexity and a regularity assumption on the functional dependency of the cost function with respect to the parameters, we show that reoptimization after a change in parameters can be done by elementary local operations. Applying this result, we derive that starting from any optimal solution there is a new optimal solution to new parameters such that the L1-norm of the difference of the two solutions is at most two times the L1 norm of the difference of the parameters. We apply these sensitivity results to a class of non-cooperative polymatroid games and derive the existence of pure Nash equilibria. We complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any non-polymatroid region, there is a corresponding optimization problem for which the sensitivity results do not hold. In addition, there is a game where the players strategies are isomorphic to the non-polymatroid region and that does not admit a pure Nash equilibrium.
Parts of the results of this paper have been presented by the authors in less general and preliminary form in the Proceedings of the 10th Conference on Web and Internet Economics @cite_35 .
@cite_35
16002891
We study competitive resource allocation problems in which players distribute their demands integrally over 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 non-decreasing 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.