A game-theoretic analysis of bandwidth allocation under a user-grouping constraint. (English) Zbl 1266.91012

Hsu, Shun-Pin; Hsu, Shun-Liang; Tsai, Alan Shenghan

J. Appl. Math. 2013, Article ID 480962, 9 p. (2013).

Summary: A new bandwidth allocation model is studied in this paper. In this model, a system, such as a communication network, is composed of a finite number of users, and they compete for limited bandwidth resources. Each user adopts the decision that maximizes his or her own benefit characterized by the utility function. The decision space of each user is subject to constraints. In addition, some users form a group, and their joint decision space is also subject to constraints. Under the assumption that each user’s utility function satisfies some continuity and concavity conditions, the existence, uniqueness, and fairness, in some appropriate sense, of the Nash equilibrium point in the allocation game are proved. An algorithm yielding a sequence converging to the equilibrium point is proposed. Finally, a numerical example with detailed analysis is provided to illustrate the effectiveness of our work.

MSC:

91A12	Cooperative games
91B32	Resource and cost allocation (including fair division, apportionment, etc.)
90B18	Communication networks in operations research

References:

[1]	J. Anselmi, U. Ayesta, and A. Wierman, “Competition yields efficiency in load balancing games,” Evaluation, vol. 68, no. 11, pp. 986-1001, 2011. · Zbl 06016252
[2]	U. Ayesta, O. Brun, and B. J. Prabhu, “Price of anarchy in non-cooperative load balancing games,” Performance Evaluation, vol. 68, no. 12, pp. 1312-1332, 2011. · Zbl 06016273
[3]	R. J. La and V. Anantharam, “Optimal routing control: repeated game approach,” IEEE Transactions on Automatic Control, vol. 47, no. 3, pp. 437-450, 2002. · Zbl 1364.91028
[4]	O. Richman and N. Shimkin, “Topological uniqueness of the nash equilibrium for selfish routing with atomic users,” Mathematics of Operations Research, vol. 32, no. 1, pp. 215-232, 2007. · Zbl 1276.91038
[5]	T. Boulogne, E. Altman, H. Kameda, and O. Pourtallier, “Mixed equilibrium (ME) for multiclass routing games,” IEEE Transactions on Automatic Control, vol. 47, no. 6, pp. 903-916, 2002. · Zbl 1364.91013
[6]	Y. A. Korilis, A. A. Lazar, and A. Orda, “Architecting noncooperative networks,” IEEE Journal on Selected Areas in Communications, vol. 13, no. 7, pp. 1241-1251, 1995.
[7]	Y. A. Korilis, A. A. Lazar, and A. Orda, “Achieving network optima using Stackelberg routing strategies,” IEEE/ACM Transactions on Networking, vol. 5, no. 1, pp. 161-173, 1997.
[8]	Y. A. Korilis, A. A. Lazar, and A. Orda, “Capacity allocation under noncooperative routing,” IEEE Transactions on Automatic Control, vol. 42, no. 3, pp. 309-325, 1997. · Zbl 0872.90035
[9]	D. Niyato and E. Hossain, “QoS-aware bandwidth allocation and admission control in IEEE 802.16 broadband wireless access networks: a non-cooperative game theoretic approach,” Computer Networks, vol. 51, no. 11, pp. 3305-3321, 2007. · Zbl 1120.68366
[10]	A. Ganesh, K. Laevens, and R. Steinberg, “Congestion pricing and noncooperative games in communication networks,” Operations Research, vol. 55, no. 3, pp. 430-438, 2007. · Zbl 1167.90420
[11]	H. Yaïche, R. R. Mazumdar, and C. Rosenberg, “A game theoretic framework for bandwidth allocation and pricing in broadband networks,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 667-678, 2000.
[12]	E. Altman, T. Boulogne, R. El-Azouzi, T. Jiménez, and L. Wynter, “A survey on networking games in telecommunications,” Computers & Operations Research, vol. 33, no. 2, pp. 286-311, 2006. · Zbl 1116.91310
[13]	F. Bonomi and K. W. Fendick, “Rate -based flow control framework for the available bit rate ATM service,” IEEE Network, vol. 9, no. 2, pp. 25-39, 1995.
[14]	D. Niyato and E. Hossain, “Queue-aware uplink bandwidth allocation and rate control for polling service in IEEE 802.16 broadband wireless networks,” IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 668-679, 2006. · Zbl 05110311
[15]	A. A. Lazar, A. Orda, and D. E. Pendarakis, “Virtual path bandwidth allocation in multiuser networks,” IEEE/ACM Transactions on Networking, vol. 5, no. 6, pp. 861-871, 1997.
[16]	J. W. Evans and C. Filsfils, Deploying IP and MPLS QoS for Multiservice Networks: Theory & Practice, Morgan Kaufmann, Boston, Mass, USA, 1st edition, 2007.
[17]	S. H. Rhee and T. Konstantopoulos, “Decentralized optimal flow control with constrained source rates,” IEEE Communications Letters, vol. 3, no. 6, pp. 188-190, 1999.
[18]	S. H. Rhee, Optimal flow control and bandwidth allocation in multiservice networks: decentralized approaches [Ph.D. thesis], The University of Texas at Austin, 1999.
[19]	C. M. Assi, Y. Ye, S. Dixit, and M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over ethernet PONs,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 9, pp. 1467-1477, 2003.
[20]	J. Xie, S. Jiang, and Y. Jiang, “A dynamic bandwidth allocation scheme for differentiated services in EPONs,” IEEE Communications Magazine, vol. 42, no. 8, pp. 32-39, 2004.
[21]	S. I. Choi and J. D. Huh, “Dynamic bandwidth allocation algorithm for multimedia services over ethernet PONs,” ETRI Journal, vol. 24, no. 6, pp. 465-468, 2002.
[22]	J. B. Rosen, “Existence and uniqueness of equilibrium points for concave n-person games,” Econometrica, vol. 33, pp. 520-534, 1965. · Zbl 0142.17603
[23]	J. F. Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences of the United States of America, vol. 36, pp. 48-49, 1950. · Zbl 0036.01104
[24]	J. Nash, “Non-cooperative games,” Annals of Mathematics, Second Series, vol. 54, pp. 286-295, 1951. · Zbl 0045.08202
[25]	E. K. P. Chong and S. H. Zak, An Introduction to Optimization, Wiley-Interscience, Hoboken, NJ, USA, 3rd edition, 2008. · Zbl 1140.90041
[26]	A. Bovopoulos and A. Lazar, “Decentralized algorithms for optimal flow control,” in Proceedings of the 25th Allerton Conference on Communication, Control, and Computing, pp. 979-988, 1987.