Article

Stability vs optimality tradeoff in game theoretic mechanisms for QoS provision

Authors:

Andrew Lomonosov,

Meera Sitharam,

Kihong ParkAuthors Info & Claims

SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

Pages 28 - 32

https://doi.org/10.1145/952532.952541

Published: 09 March 2003 Publication History

Get Access

Abstract

We study noncooperative games whose players are selfish, distributed users of a network and the game's objective is to optimize Quality of Service (QoS). Our classes of games are based on generally accepted realistic microeconomic market models of QoS provision, and unlike most other games that have been recently studied in this context, stability is not guaranteed for our class of games. Stability here refers to whether the game reaches a Nash equilibrium. Optimality is a measure of how close a Nash equilibrium is to optimizing a given objective function defined on game configuration. The overall goal is to determine a minimal set of static game rules based on pricing that result in stable and optimal QoS provision. The combination of stability and optimality opens an interesting direction of investigation. We give a new and general technique to establish stability and demonstrate a close trade-off between stability and optimality for our game classes. Additionally, these results directly give a simple, computationally efficient, self-organizing mechamism for stable and optimal QoS provision in natural cases.

References

[1]

Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, and Scott Shenker, Approximation and collusion in multicast, cost sharing. In Proceedings of the 3rd Conference on Electronic Commerce, ACM Press, New York, pages 253--255, 2001.

Digital Library

Google Scholar

[2]

Yannis A. Korilis and Aurel A. Lazar. Why is flow control hard: Optimality etc. In CTR Technical Report CU/CTR/TR 332-93-11, Center for Telecommunications Research, Columbia University, 1992. Presented in part in the Second ORSA Telecommunications Conference, Boca Raton, FL March 1992, 1992.

Google Scholar

[3]

Yannis A. Korilis and Aurel A. Lazar. On the existence of equilibria in noncooperative optimal flow control. Journal of the ACM, 42(3):584--613, 1995.

Digital Library

Google Scholar

[4]

Yannis A. Korilis, Aurel A. Lazar, and Ariel Orda. Architecting noncooperative networks. IEEE Journal of Selected Areas in Communications, 13(7):1241--1251, 1995.

Digital Library

Google Scholar

[5]

Lavy Libman and Ariel Orda. Atomic resource sharing in noncooperative networks. In INFOCOM (3), pages 1006--1013, 1997.

Digital Library

Google Scholar

[6]

Noam Nisan. Algorithms for selfish agents. In Symposium on Theoretical Aspects of Computer Science, pages 1--15, 1999.

Digital Library

Google Scholar

[7]

Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proc. 31st ACM Symp. on Theory of Computing, pages 129--140, 1999.

Digital Library

Google Scholar

[8]

Ariel Orda, Raphael Rom, and Nahum Shimkin. Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking, 1(5) 510--521, 1993.

Digital Library

Google Scholar

[9]

C. Papadimitriou. Computational aspects of organization theory. In Proceedings of the 1996 European Symposium on Algorithms. Springer LNCS, 1996., 1996.

Digital Library

Google Scholar

[10]

K. Park, M. Sitharam, and S. Chen. Quality of service provision in noncooperative networks: Heterogenous preferences. In Proceedings of the First Int. Conf. on Information and Computation Economics ICE'98, Charleston, SC, USA, October, 1998., 1998.

Digital Library

Google Scholar

[11]

Tim Roughgarden and Eva Tardos. How bad is selfish routing? In IEEE Symposium on Foundations of Computer Science, pages 93--102, 2000.

Digital Library

Google Scholar

[12]

Scott Shenker. Making greed work in networks: A game-theoretic analysis of switch service disciplines. IEEE/ACM Transactions on Networking, 3, 1995.

Digital Library

Google Scholar

[13]

Scott Shenker. Mechanism design and the internet. In Presented in DIMACS Workshop on Computational Issues in Game Theory and Mechanism Design, October 31 - November 2, 2OO1 DIMACS Center, Rutgers University, 2001.

Google Scholar

Cited By

View all

Gollapudi SSivakumar DAidong Zhang (2005)Exploiting anarchy in networks: a game-theoretic approach to combining fairness and throughputProceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.10.1109/INFCOM.2005.1498490(2147-2158)Online publication date: 2005
https://doi.org/10.1109/INFCOM.2005.1498490

Recommendations

Game-theoretic auction design for bandwidth sharing in helper-assisted P2P streaming

Video traffic offloading through the helper peers can significantly alleviate the server workload and enhance users' quality of experience. In this paper, the complex interactions of a number of helpers seeking to trade their bandwidth surplus in a peer-...
Zero-Sum Game Techniques for Approximate Nash Equilibria
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

We apply existing, and develop new, zero-sum game techniques for designing polynomial-time algorithms to compute additive approximate Nash equilibria in bimatrix games. In particular, we give a polynomial-time algorithm that given an arbitrary bimatrix ...
Vickrey vs. eBay: Why Second-Price Sealed-Bid Auctions Lead to More Realistic Price-Demand Functions

Knowledge of consumers' willingness-to-pay (WTP) is critical for marketing managers when designing optimal pricing policies. The large-scale applicability, reliability, and validity of Vickrey auctions as an incentive-compatible method for eliciting WTP ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SAC '03: Proceedings of the 2003 ACM symposium on Applied computing

March 2003

1268 pages

ISBN:1581136242

DOI:10.1145/952532

Conference Chair:
Gary B. Lamont
Air Force Institute of Technology
,
Program Chairs:
Hisham Haddad
Kennesaw State University
,
George A. Papadopoulos
University of Cyprus, Cyprus
,
Publications Chair:
Brajendra Panda
University of Arkansas

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 March 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC03

Sponsor:

SIGAPP

SAC03: ACM Symposium on Applied Computing

March 9 - 12, 2003

Florida, Melbourne

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gollapudi SSivakumar DAidong Zhang (2005)Exploiting anarchy in networks: a game-theoretic approach to combining fairness and throughputProceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.10.1109/INFCOM.2005.1498490(2147-2158)Online publication date: 2005
https://doi.org/10.1109/INFCOM.2005.1498490

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Game-theoretic auction design for bandwidth sharing in helper-assisted P2P streaming

Zero-Sum Game Techniques for Approximate Nash Equilibria

Vickrey vs. eBay: Why Second-Price Sealed-Bid Auctions Lead to More Realistic Price-Demand Functions