More Web Proxy on the site http://driver.im/

research-article

The price of anarchy in bertrand games

Authors:

Feng NiuAuthors Info & Claims

EC '09: Proceedings of the 10th ACM conference on Electronic commerce

Pages 305 - 314

https://doi.org/10.1145/1566374.1566418

Published: 06 July 2009 Publication History

Abstract

The Internet is composed of multiple economically-independent service providers that sell bandwidth in their networks so as to maximize their own revenue. Users, on the other hand, route their traffic selfishly to maximize their own utility. How does this selfishness impact the efficiency of operation of the network? To answer this question we consider a two-stage network pricing game where service providers first select prices to charge on their links, and users pick paths to route their traffic. We give tight bounds on the price of anarchy of the game with respect to social value--the total value obtained by all the traffic routed. Unlike recent work on network pricing, in our pricing game users do not face congestion costs; instead service providers must ensure that capacity constraints on their links are satisfied. Our model extends the classic Bertrand game in economics to network settings.

References

[1]

D. Acemoglu and A. Ozdaglar. Competition and efficiency in congested markets. Mathematics of Operations Research, 32(1):1--31, 2007.

Digital Library

[2]

D. Acemoglu and A. Ozdaglar. Competition in parallel-serial networks. IEEE Journal on Selected Areas in Communications, special issue on Non-cooperative Behavior in Networking, 25(6):1180--1192, 2007.

Digital Library

[3]

E. Anshelevich, A. Dasgupta, J. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In Proc. 45th IEEE Symp. Foundations of Computer Science, pages 295--304, 2004.

Digital Library

[4]

E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler. Near-optimal network design with selfish agents. In Proc. ACM Symp. Theory of Computing, pages 511--520, 2003.

Digital Library

[5]

Mark Bagnoli and Ted Bergstrom. Log-concave probability and its applications. Economic Theory, 26(2):445--469, 08 2005.

[6]

Michael R. Baye and John Morgan. A folk theorem for one-shot bertrand games. Economics Letters, 65(1):59--65, 1999.

[7]

Shuchi Chawla and Tim Roughgarden. Bertrand competition in networks. In Symposium on Algorithmic Game Theory, pages 70--82, 2008.

Digital Library

[8]

R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous selfish users. In Proc. 34th ACM Symp. Theory of Computing, 2003.

Digital Library

[9]

A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and S. Shenker. On a network creation game. In Proc. ACM Symp. Principles of Distributed Computing, pages 247--251, 2003.

Digital Library

[10]

L. Fleischer, K. Jain, and M. Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Proc. 45th IEEE Symp. Foundations of Computer Science, pages 277--285, 2004.

Digital Library

[11]

Joseph Jr. Harrington. A re-evaluation of perfect competition as the solution to the bertrand price game. Mathematical Social Sciences, 17(3):315--328, 1989.

[12]

Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In WWW '08: Proceeding of the 17th international conference on World Wide Web, pages 189--198, 2008.

Digital Library

[13]

A. Hayrapetyan, É. Tardos, and T. Wexler. A network pricing game for selfish traffic. In Proc. Symp. Principles of distributed Computing, pages 284--291, 2005.

Digital Library

[14]

A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford, 1995.

[15]

J. Musacchio and S. Wu. The price of anarchy in a network pricing game. In 45th Annual Allerton Conference on Communication and Control, 2007.

[16]

A. Ozdaglar and R. Srikant. Incentives and pricing in communication networks. In Algorithmic Game Theory. Cambridge Press, 2007.

[17]

T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005.

Digital Library

[18]

T. Roughgarden and É. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236--259, 2002.

Digital Library

Cited By

Deng XLi NLi WQi Q(2023)Equilibrium Analysis of Customer Attraction GamesWeb and Internet Economics10.1007/978-3-031-48974-7_14(242-255)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_14
Correa JGuzmán CLianeas TNikolova ESchröder M(2022)Network Pricing: How to Induce Optimal Flows Under Strategic Link OperatorsOperations Research10.1287/opre.2020.206770:1(472-489)Online publication date: Jan-2022
https://doi.org/10.1287/opre.2020.2067
Fedele ARoner C(2021)Dangerous games: A literature review on cybersecurity investmentsJournal of Economic Surveys10.1111/joes.1245636:1(157-187)Online publication date: 26-Jul-2021
https://doi.org/10.1111/joes.12456
Show More Cited By

Index Terms

The price of anarchy in bertrand games
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Bertrand competition in networks

We briefly summarize our recent work characterizing the efficiency of equilibria in pricing games in two-sided combinatorial markets.
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions

We study the price of anarchy (PoA) of simultaneous first-price auctions (FPAs) for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian price of anarchy (BPoA) of these auctions are e/(e − 1) [Syrgkanis and ...
Bertrand equilibria and efficiency in markets for congestible network services

This paper is motivated by study of the economics of Quality of Service (QoS) of congestible services. We introduce a queueing game framework to study such problems. We consider multiple competing providers, each offering a queued service. Users are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '09: Proceedings of the 10th ACM conference on Electronic commerce

July 2009

376 pages

ISBN:9781605584584

DOI:10.1145/1566374

General Chair:
John Chuang
University of California at Berkeley, USA
,
Program Chairs:
Lance Fortnow
Northwestern University, USA
,
Pearl Pu
Ecole Polytechnique Fédérale de Lausanne, Switzerland

Copyright © 2009 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '09

Sponsor:

EC '09: ACM Conference on Electronic Commerce

July 6 - 10, 2009

California, Stanford, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
226
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deng XLi NLi WQi Q(2023)Equilibrium Analysis of Customer Attraction GamesWeb and Internet Economics10.1007/978-3-031-48974-7_14(242-255)Online publication date: 31-Dec-2023
https://doi.org/10.1007/978-3-031-48974-7_14
Correa JGuzmán CLianeas TNikolova ESchröder M(2022)Network Pricing: How to Induce Optimal Flows Under Strategic Link OperatorsOperations Research10.1287/opre.2020.206770:1(472-489)Online publication date: Jan-2022
https://doi.org/10.1287/opre.2020.2067
Fedele ARoner C(2021)Dangerous games: A literature review on cybersecurity investmentsJournal of Economic Surveys10.1111/joes.1245636:1(157-187)Online publication date: 26-Jul-2021
https://doi.org/10.1111/joes.12456
Correa JGuzmán CLianeas TNikolova ESchröder MTardos EElkind EVohra R(2018)Network PricingProceedings of the 2018 ACM Conference on Economics and Computation10.1145/3219166.3219190(375-392)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3219166.3219190
Chen LMislove AWilson CBourdeau JHendler JNkambou RHorrocks IZhao B(2016)An Empirical Analysis of Algorithmic Pricing on Amazon MarketplaceProceedings of the 25th International Conference on World Wide Web10.1145/2872427.2883089(1339-1349)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2872427.2883089
Babaioff MNisan NPaes Leme RChung CBroder AShim KSuel T(2014)Price competition in online combinatorial marketsProceedings of the 23rd international conference on World wide web10.1145/2566486.2568016(711-722)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2566486.2568016
Esquivel HMuthukrishnan CAkella AChawla S(2012)Better Internet routing through intrinsic support for selfishness2012 Fourth International Conference on Communication Systems and Networks (COMSNETS 2012)10.1109/COMSNETS.2012.6151317(1-10)Online publication date: Jan-2012
https://doi.org/10.1109/COMSNETS.2012.6151317
Anshelevich EHate AKar K(2011)Strategic pricing in next-hop routing with elastic demandsProceedings of the 4th international conference on Algorithmic game theory10.5555/2050805.2050838(278-289)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.5555/2050805.2050838
Akella AChawla SEsquivel HMuthukrishnan C(2011)De-ossifying internet routing through intrinsic support for end-network and ISP selfishnessACM SIGMETRICS Performance Evaluation Review10.1145/2007116.200716539:1(337-338)Online publication date: 7-Jun-2011
https://dl.acm.org/doi/10.1145/2007116.2007165
Akella AChawla SEsquivel HMuthukrishnan CMerchant AKeeton KRubenstein D(2011)De-ossifying internet routing through intrinsic support for end-network and ISP selfishnessProceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems10.1145/1993744.1993798(145-146)Online publication date: 7-Jun-2011
https://dl.acm.org/doi/10.1145/1993744.1993798
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents