Sensitivity analysis for convex separable optimization over integral polymatroids. (English) Zbl 1403.90571
Summary: 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 \(L_1\)-norm of the difference of the two solutions is at most two times the \(L_1\)-norm of the difference of the parameters. We apply these sensitivity results to a class of noncooperative games with a finite set of players where a strategy of a player is to choose a vector in a player-specific integral polymatroid base polytope defined on a common set of elements. The players’ private cost functions are regular, convex-separable, and the cost of each element is a nondecreasing function of the own usage of that element and the overall usage of the other players. Under these assumptions, we establish the existence of a pure Nash equilibrium. The existence is proven by an algorithm computing a pure Nash equilibrium that runs in polynomial time whenever the rank of the polymatroid base polytope is polynomially bounded. Both the existence result and the algorithm generalize and unify previous results appearing in the literature. We finally complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any nonpolymatroid 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 nonpolymatroid region and that does not admit a pure Nash equilibrium.
MSC:
| 90C27 | Combinatorial optimization |
| 91A10 | Noncooperative games |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 91A46 | Combinatorial games |
Keywords:
polymatroid; submodular function; sensitivity; reoptimization; integer optimization; noncooperative games; congestion games; pure Nash equilibriumReferences:
| [1] | H. Ackermann, H. Röglin, and B. Vöcking, Pure Nash equilibria in player-specific and weighted congestion games, Theoret. Comput. Sci., 410 (2009), pp. 1552–1563. · Zbl 1159.91328 |
| [2] | E. Anshelevich, A. Dasgupta, J. Kleinberg, Éva Tardos, T. Wexler, and T. Roughgarden, The price of stability for network design with fair cost allocation, SIAM J. Comput., 38 (2008), pp. 1602–1623. · Zbl 1173.91321 |
| [3] | R. Baldick, Refined proximity and sensitivity results in linearly constrained convex separable integer programming, Linear Algebra Appl., 226 (1995), pp. 389–407. · Zbl 0838.90083 |
| [4] | M. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics and Transportation, Yale University Press, New Haven, CT, 1956. |
| [5] | H.-L. Chen and T. Roughgarden, Network design with weighted players, Theory Comput. Syst., 45 (2009), pp. 302–324. · Zbl 1176.91003 |
| [6] | W. J. Cook, A. M. H. Gerards, A. Schrijver, and É. Tardos, Sensitivity theorems in integer linear programming, Math. Program., 34 (1986), pp. 251–264. · Zbl 0648.90055 |
| [7] | J. Dunkel and A. S. Schulz, On the complexity of pure-strategy Nash equilibria in congestion and local-effect games, Math. Oper. Res., 33 (2008), pp. 851–868. · Zbl 1231.91010 |
| [8] | A. Federgruen and H. Groenevelt, The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality, Oper. Res., 34 (1986), pp. 909–918. · Zbl 0619.90051 |
| [9] | D. Fotakis, S. Kontogiannis, and P. G. Spirakis, Selfish unsplittable flows, Theoret. Comput. Sci., 348 (2005), pp. 226–239. · Zbl 1152.90355 |
| [10] | S. Fujishige, Submodular Functions and Optimization, Elsevier, Amsterdam, 2005. · Zbl 1119.90044 |
| [11] | S. Fujishige, M. X. Goemans, T. Harks, B. Peis, and R. Zenklusen, Matroids are immune to Braess’ paradox, Math. Oper. Res., 42 (2017), pp. 745–761. · Zbl 1380.91034 |
| [12] | H. N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, J. Comput. Syst. Sci., 50 (1995), pp. 259–273. · Zbl 0827.68087 |
| [13] | Y. Gai, H. Liu, and B. Krishnamachari, A packet dropping mechanism for efficient operation of \(M/M/1\) queues with selfish users, in Proceedings of the 30th International Conference on Computer Communications, IEEE, New York, NY, 2011, pp. 2687–2695. |
| [14] | M. Gairing and M. Klimm, Congestion games with player-specific costs revisited, in Proceedings of the 6th International Symposium on Algorithmic Game Theory, B. Vöcking, ed., Lect. Notes Comput. Sci. 8146, Springer, Berlin, Heidelberg, 2013, pp. 98–109. · Zbl 1319.91015 |
| [15] | M. Gairing, B. Monien, and K. Tiemann, Routing (un-)splittable flow in games with player-specific linear latency functions, ACM Trans. Algorithms, 7 (2011), pp. 1–31. · Zbl 1295.91009 |
| [16] | M. X. Goemans, V. S. Mirrokni, and A. Vetta, Sink equilibria and convergence, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Ney York, NY, 2005, pp. 142–154. |
| [17] | H. Groenevelt, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, Eur. J. Oper. Res., 54 (1991), pp. 227–236. · Zbl 0745.90059 |
| [18] | T. Harks and M. Klimm, On the existence of pure Nash equilibria in weighted congestion games, Math. Oper. Res., 37 (2012), pp. 419–436. · Zbl 1297.91008 |
| [19] | T. Harks, M. Klimm, and B. Peis, Resource competition on integral polymatroids, in Proceedings of the 10th International Conference on Web and Internet Economics., T.-Y. Liu, Q. Qi, and Y. Ye, eds., Lect. Notes Comput. Sci. 8877, Springer, Heidelberg, Berlin, 2014, pp. 189–202. · Zbl 1406.91218 |
| [20] | S. He, J. Zhang, and S. Zhang, Polymatroid optimization, submodularity, and joint replenishment games, Oper. Res., 60 (2012), pp. 128–137. · Zbl 1245.90123 |
| [21] | D. S. Hochbaum and J. G. Shanthikumar, Convex separable optimization is not much harder than linear optimization, J. ACM, 37 (1990), pp. 843–862. · Zbl 0721.90060 |
| [22] | R. Johari and J. N. Tsitsiklis, A scalable network resource allocation mechanism with bounded efficiency loss., IEEE J. Sel. Areas Commun., 24 (2006), pp. 992–999. |
| [23] | F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, Rate control in communication networks: Shadow prices, proportional fairness, and stability, J. Oper. Res. Soc., 49 (1998), pp. 237–252. · Zbl 1111.90313 |
| [24] | Y. A. Korillis and A. A. Lazar, On the existence of equilibria in noncooperative optimal flow control, J. ACM, 42 (1995), pp. 584–613. · Zbl 0885.68015 |
| [25] | P. Krysta, P. Sanders, and B. Vöcking, Scheduling and traffic allocation for tasks with bounded splittability, in Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, B. Rovan and P. Vojtas, eds., Lect. Notes Comput. Sci. 2747, Springer, Heidelberg, Berlin, 2003, pp. 500–510. · Zbl 1124.68329 |
| [26] | C. Meyers, Network Flow Problems and Congestion Games: Complexity and Approximation Results, Ph.D. thesis, MIT, Cambridge, MA, 2006. |
| [27] | I. Milchtaich, Congestion games with player-specific payoff functions, Games Econom. Behav., 13 (1996), pp. 111–124. · Zbl 0848.90131 |
| [28] | I. Milchtaich, The equilibrium existence problem in finite network congestion games, in Proceedings of the 2nd International Workshop on Internet and Network Economics, M. Mavronicolas and S. Kontogiannis, eds., Lect. Notes Comput. Sci. 4286, Springer, Heidelberg, Berlin, 2006, pp. 87–98. |
| [29] | S. Moriguchi, A. Shioura, and N. Tsuchimura, M-convex function minimization by continuous relaxation approach: Proximity theorem and algorithm, SIAM J. Optim., 21 (2011), pp. 633–668. · Zbl 1236.90082 |
| [30] | K. Murota, Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications 10, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. · Zbl 1029.90055 |
| [31] | K. Murota and A. Tamura, Proximity theorems of discrete convex functions, Math. Program., 99 (2004), pp. 539–562. · Zbl 1084.90038 |
| [32] | R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, Internat. J. Game Theory, 2 (1973), pp. 65–67. · Zbl 0259.90059 |
| [33] | R. W. Rosenthal, The network equilibrium problem in integers, Networks, 3 (1973), pp. 53–59. · Zbl 0261.90017 |
| [34] | T. Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, Cambridge, MA, 2005. · Zbl 1318.68065 |
| [35] | R. Srikant, The Mathematics of Internet Congestion Control, Birkhäuser, Basel, 2003. · Zbl 1086.68018 |
| [36] | D. M. Topkis, Minimizing a submodular function on a lattice, Oper. Res., 26 (1978), pp. 305–321. · Zbl 0379.90089 |
| [37] | D. M. Topkis, Supermodularity and Complementarity, Princeton University Press, Princeton, NJ, 1998. |
| [38] | L. Tran-Thanh, M. Polukarov, A. Chapman, A. Rogers, and N. R. Jennings, On the existence of pure strategy Nash equilibria in integer-splittable weighted congestion games, in Proceedings of the 4th International Symposium on Algorithmic Game Theory, G. Persiano, ed., Lect. Notes Comput. Sci. 6982, Springer, Heidelberg, Berlin, 2011, pp. 236–253. · Zbl 1233.91072 |
| [39] | J. G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. Civil Engrs., 1 (1952), pp. 325–362. |
| [40] | D. D. Yao, Dynamic scheduling via polymatroid optimization, in Performance Evaluation of Complex Systems: Techniques and Tools, M. C. Calzarossa and S. Tucci, eds., Lect. Notes Comput. Sci. 2459, Springer, Heidelberg, Berlin, 2002, pp. 89–113. · Zbl 1017.68506 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
