Evangelos Markakis
ABSTRACT
In citepapa, Papadimitriou formalized the notion of routing stability in BGP as the following coalitional game theoretic problem: Given a network with a multicommodity flow satisfying node capacity and demand constraints, the payoff of a node is the total flow originated or terminated at it. A payoff allocation is in the core if and only if there is no subset of nodes that can increase their payoff by seceding from the network. We answer one of the open problems in citepapa by proving that for any network, the core is non-empty in both the transferable (where the nodes can compensate each other with side payments) and the non-transferable case. In the transferable case we show that such an allocation can be computed in polynomial time. We also generalize this result to the case where a strictly concave utility function is associated with each commodity.
- O. Bondareva. The core of an n person game. Vestnik Leningrad University, 13:141--142, 1962.Google Scholar
- W. C. Brainard and H. E. Scarf. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper, 1270, 2000.Google Scholar
- P. Chardaire. Facility Location Optimization and Cooperative Games. PhD Thesis, 1998.Google Scholar
- V. Conitzer and T. Sandholm. Complexity of determining non-emptiness of the core. Technical Report CS-02-137, CMU, 2002.Google Scholar
- X. Deng, T. Ibaraki, and H. Nagamochi. Algorithms and complexity in combinatorial optimization games. In Annual ACM-SIAM Symposium on Discrete Algorithms, pages 720--729, 1997. Google ScholarDigital Library
- X. Deng and C. Papadimitriou. On the complexity of cooperative game solution concepts. Mathematics of Operations Research, 19(2):257--266, 1994. Google ScholarDigital Library
- N. Devanur, A. Saberi, C. Papadimitriou, and V. V. Vazirani. Market equilibrium via a primal-dual-type algorithm. In Annual IEEE Symposium on the Foundations of Computer Science, pages 389--395, 2002. Google ScholarDigital Library
- U. Faigle, S. Fekete, W. Hochst$ddotmboxa$ttler, and W. Kern. On the complexity of testing membership in the core of min-cost spanning tree games. International Journal of Game Theory, 26:361--366, 1997. Google ScholarDigital Library
- J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker. A bgp-based mechanism for lowest-cost routing. In Symposium on Principles of Distributed Computing, pages 173--182, 2002. Google ScholarDigital Library
- J. Feigenbaum and S. Shenker. Distributed algorithmic mechanism design: Recent results and future directions. In International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 1--13. ACM Press, 2002. Google ScholarDigital Library
- N. Garg and N. Young. On-line end-to-end congestion control. In Annual IEEE Symposium on the Foundations of Computer Science, pages 303--312, 2002. Google ScholarDigital Library
- M. Goemans and M. Skutella. Cooperative facility location games. In Annual ACM-SIAM Symposium on Discrete Algorithms, pages 76--85, 2000. Google ScholarDigital Library
- D. Granot. A generalized linear production model: A unified model. Mathematical Programming, 34:212--222, 1986. Google ScholarDigital Library
- K. Jain and V. V. Vazirani. Application of approximation algorithms to cooperative games. In Annual Symposium on Theory of Computing, pages 364--372, 2001. Google ScholarDigital Library
- E. Kalai and E. Zemel. Generalized network problems yielding totally balanced games. Operations Research, 30:998--1008, 1982.Google ScholarDigital Library
- F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8:33--37, 1997.Google ScholarCross Ref
- F. P. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: Shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.Google ScholarCross Ref
- F. P. Kelly and V. V. Vazirani. Rate control as a market equilibrium. In preparation, 2003.Google Scholar
- S. Low and D. Lapsley. Optimization, flow control 1: Basic algorithm and convergence. IEEE Transactions on Networking, 7(6):861--874, 1999. Google ScholarDigital Library
- S. Low, F. Paganini, and J. Doyle. Internet congestion control. IEEE Control Systems Magazine, 22(1):28--43, Feb. 2002.Google ScholarCross Ref
- N. Nisan and A. Ronen. Algorithmic mechanism design. In Annual ACM Symposium on the Theory of Computing, pages 129--140, 1999. Google ScholarDigital Library
- M. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Massachusetts, 1994.Google Scholar
- G. Owen. On the core of linear production games. Mathematical Programming, 9:358--370, 1975.Google ScholarCross Ref
- C. H. Papadimitriou. Algorithms, games, and the internet. In Annual ACM Symposium on the Theory of Computing, pages 749--753, 2001. Google ScholarDigital Library
- H. Scarf. The core of an n person game. Econometrica, 35(1):50--69, 1967.Google ScholarCross Ref
- L. Shapley. On balanced sets and cores. Naval Research Logistics Quarterly, 14:453--460, 1967.Google ScholarCross Ref
- L. Shapley and M. Shubik. The assignment game 1: The core. International Journal of Game Theory, 1:111--130, 1972.Google ScholarCross Ref
- S. Shenker. Fundamental design issues for the future internet. IEEE Journal Selected Areas Communication, 13:1176--1188, 1995. Google ScholarDigital Library
- V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Google ScholarDigital Library
Index Terms
- On the core of the multicommodity flow game
Recommendations
On the core of the multicommodity flow game
Special issue: The fourth ACM conference on electronic commerceIn the work of Papadimitriou [C.H. Papadimitriou, Algorithms, games, and the internet. In Annual ACM Symposium on the Theory of Computing (2001) pp. 749-753], he proposed a game theoretic framework for analyzing incentive issues in Internet routing. In ...
The core of a cooperative game without side payments
For cooperative games without side payments, there are several types of conditions which guarantee nonemptiness of the core, for example balancedness and convexity. In the present paper, a general condition for nonempty core is introduced which includes ...
The non-emptiness of the core of a partition function form game
AbstractThe purpose of this paper is to provide a necessary and sufficient condition for the non-emptiness of the core for partition function form games. We generalize the Bondareva–Shapley condition to partition function form games and present the ...
Comments