The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism

WANG Gang; DAI Xia

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(3): 567-571

WANG Gang and DAI Xia, “The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 567-571, 2013,

Citation:

WANG Gang and DAI Xia, “The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 567-571, 2013,

WANG Gang and DAI Xia, “The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 567-571, 2013,

Citation:

WANG Gang and DAI Xia, “The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism,” Chinese Journal of Electronics, vol. 22, no. 3, pp. 567-571, 2013,

PDF( 254 KB)

The Price of Anarchy of Network Coding and Routing Based on an ACS Pricing Mechanism

WANG Gang,
DAI Xia

School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China

Funds: This work is supported by the National Natural Science Foundation of China (No.60972007, No.61271194), and the National Basic Research Program of China (973 Program) (No.2010CB731800).

Received Date: 2012-04-01
Rev Recd Date: 2012-08-01
Publish Date: 2013-06-15

Abstract

Abstract

To emphasize the decisions of all users, and the total number of users sharing the same technique, we propose a novel Average cost sharing (ACS) pricing mechanism to study the game between Network coding (NC) and routing flows sharing a single link when users are price anticipating. We characterize the worst-case efficiency bounds of the game compared with the optimal (i.e., the Price of anarchy (PoA)), which can be as low as 4/9 when the number of routing users becomes sufficiently large. NC cannot improve the PoA significantly under ACS. However, to achieve a more efficient use of limited resources, this approach indicates the sharing users have a greater tendency to choose NC. However, the users will follow the majority users' choice of data transmission technique.
- Average cost sharing (ACS),
- Congestion pricing,
- Network coding (NC),
- Price of anarchy (PoA)

FullText(HTML)

References(16)

References

Yingju Chen and Jiawei Zhang, “Design of price mechanisms for network resource allocation via price of anarchy”, Journal of Mathematical Programming, Series A and B, Vol.131, No.1-2, pp.333-364, 2012.

Yufang Xi and Edmund M. Yeh, “Pricing, competition, and routing in relay networks”, Allerton'09 Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, USA, pp.507-514, 2009.

Yufang Xi and Edmund M. Yeh, “Pricing, competition, and routing for selfish and strategic nodes in multi-hop relay networks”, in Proceedings of the IEEE Conference on Computer Communications (INFOCOM'08), Phoneix, Ariz, USA, pp.2137-2145, 2008.

F.P. Kelly, A.K. Maulloo and D.K.H .Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, Journal of the Operational Research Society, Vol.49, No.3, pp.237-252, 1998.

R. Ahlswede, N. Cai, S. Li and R. Yeung, “Network information flow”, IEEE Trans. on Information Theory, Vol.46, pp.12041216, 2000.

Xiao Song, Wang Hui, Wu Chengke, “A new network coding design for reliable video multicast”, Chinese Journal of Electronics, Vol.20, No.2, pp.361-364, 2011.

Guang Xuan, Fu Fangwei, “On random linear network coding for butterfly network”, Chinese Journal of Electronics, Vol.20, No.2, pp.283-286, 2011.

X. Liang, “Matrix games in the multicast networks: maximum information ?ows with network switching”, IEEE Trans. on Information Theory, Vol.52, pp.2433-2466, 2006.

Z. Li, “Cross-monotonic multicast”, Proc. of IEEE INFOCOM' 08, Phoenix, Ariz, USA, pp.1588-1596, 2008.

X. Zhang and B. Li, “Dice: a game theoretic framework for wireless multipath network coding”, Proc. of ACM MobiHoc, Hong Kong, China, pp.293-302, 2008.

A. Hamed Mohsenian-Rad, Jianwei Huang and Vincent W.S. Wong, “A game-theoretic analysis of inter-session network coding”, Proceedings of the 2009 IEEE International Conference on Communications, Dresden, Germany, pp.1690-1695, 2009.

Amir-Hamed Mohsenian-Rad, Jianwei Huang, Vincent W.S. Wong and Robert Schober, “Bargaining and price-of-anarchy in repeated inter-session network coding games”, Proceedings of IEEE INFOCOM'10, San Diego, CA, USA, pp.1927-1935, 2010.

Amir-Hamed Mohsenian-Rad, Jianwei Huang, Vincent W.S. Wong, “Inter-session network coding with strategic users: A game-theoretic analysis of network coding”, Submitted to IEEE Transactions on IT, 2009.

Tansu Alpcan, Tamer Basar, “A game theoretic framework for congestion control in general topology networks”, Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, Nevada USA, pp.1218-1224, 2002.

Ramesh Johari and John N. Tsitsiklis, “A scalable network resource allocation mechanism with bounded efficiency loss”, IEEE Journal on Selected Areas in Communications, Vol.24, No.5, pp.992-999, 2006.

Vasilis Ntranos, “Cost sharing network routing game”, wwwbcf. usc.edu/～shanghua/teaching/Fall2010/cost sharing.pdf.

Relative Articles

Supplements(0)

Cited By

Proportional views