Article

Algorithms, games, and the internet

Author:

Christos PapadimitriouAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 749 - 753

https://doi.org/10.1145/380752.380883

Published: 06 July 2001 Publication History

Abstract

If the Internet is the next great subject for Theoretical Computer Science to model and illuminate mathematically, then Game Theory, and Mathematical Economics more generally, are likely to prove useful tools. In this talk I survey some opportunities and challenges in this important frontier.

References

[1]

Chandra, Kozen, Stockmeyer, "Alternation," JACM, 28, 1, 1981.

Digital Library

[2]

Cottle The Linear Complementarity Problem, 1992.

[3]

Deng, Papadimitriou, "On the complexity of cooperative game solution concepts," Math. Oper. Res., 19, 1994.

Digital Library

[4]

Deng, Papadimitriou, in preparation.

[5]

de Vries, Vohra, "Combinatorial Auctions: A Survey." http://www.kellogg.nwu.edu/research/math/Downpapers.htm

[6]

Faloutsos, Faloutsos, Faloutsos, "On power-law relationships of the Internet topology," Proc. 1999 SIGCOMM.

Digital Library

[7]

Feigenbaum, Papadimitriou, Shenker "Sharing the cost of multicast transmissions," Proc. 2000 STOC.

Digital Library

[8]

Friedman, Shenker "Learning and implementation on the Internet," 1998.

[9]

Fudenberg Learning in Games, M.I.T. Press, 1998.

[10]

Kelly "Mathematical modelling of the Internet," in Mathematics Unlimited - 2001 and Beyond (Editors B. Engquist and W. Schmid), Springer-Verlag, 2001.

[11]

www.google.com/technology/index.html

[12]

Karp, Koutsoupias, Papadimitriou, Shenker, "Optimization problems in congestion control," Proceedings of the 41st FOCS, 2000.

Digital Library

[13]

Kleinberg "Authoritative sources in a hyperlinked environment," Proc. 1999 SODA.

Digital Library

[14]

Kleinberg, Papadimitriou, Raghavan "On the value of private information," Proc. 2001 Conf. on Theoretical Aspects of Reasoning about Knowledge, Sienna, July 2001.

Digital Library

[15]

Kleinberg, Papadimitriou, Raghavan "Segmentation problems," Proc. 1998 STOC.

Digital Library

[16]

Koutsoupias, Papadimitriou "Worst-case equilibria," Proc. 1998 STACS.

Digital Library

[17]

Kumar, Raghavan, Rajagopalan, Sivakumar, Tomkins, Upfal, "Random graph models for the Web graph," Proc. 2000 FOCS.

Digital Library

[18]

Mas-Collel, Winston, Green Microeconomic Theory, Oxford University Press 1995.

[19]

Mavronikolas, Spirakis, "The price of selfish routing," this conference.

Digital Library

[20]

Maynard-Smith, Evolution and the Theory of Games Cambridge University Press, 1982.

[21]

Nisan "Algorithms for selfish agents - Mechanism design for distributed computation," Proc. 1999 STACS.

Digital Library

[22]

Nisan, Ronen "Algorithmic Mechanism Design," Proc. STOC 1999.

Digital Library

[23]

Osborne and Rubinstein, A Course in Game Theory, MIT Press, 1994.

[24]

Papadimitriou "On the complexity of the parity argument and other inefficient proofs of existence, J.CSS, 48, 3, 1994.

Digital Library

[25]

Papadimitriou, Yannakakis "Complexity as bounded rationality," Proc. 1994 STOC.

Digital Library

[26]

Raghavan, "Probabilistic construction of deterministic algorithms: approximate packing integer programs," J.CSS, 37, 1988.

Digital Library

[27]

Rekhter, Li "RFC 1771, BGP-4," www.cis.ohio-state.edu/cgi-bin/rfc/rfc1771.html.

[28]

Roughgarden, Tardos, "How Bad is Selfish Routing? (Extended Abstract)," Proc. FOCS 2000.

Digital Library

[29]

Singh, Kearns, Mansour, "Nash Convergence of Gradient Dynamics in General-Sum Games," Proc. UAI 2000.

Digital Library

[30]

Yao "Probabilistic computations: Toward a unified measure of complexity (extended abstract)," Proc. 1977 FOCS.

Cited By

Kupferman OShenwald N(2024)The Complexity of LTL Rational SynthesisACM Transactions on Computational Logic10.1145/364847325:2(1-31)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3648473
Gorbaneva OOugolnitsky G(2024)Game-Theoretic Analysis of the Interaction of Economic Agents in the Cournot Oligopoly with Consideration of the Linear Structure, the Green Effect, and Fairness ConcernAutomation and Remote Control10.1134/S000511792402005X85:2(174-199)Online publication date: 26-Jul-2024
https://doi.org/10.1134/S000511792402005X
Del Santo O’Neill TRossberg AThorpe R(2024) An efficient tool to find multispecies MSY for interacting fish stocks Fish and Fisheries10.1111/faf.1281725:3(441-454)Online publication date: 20-Mar-2024
https://doi.org/10.1111/faf.12817
Show More Cited By

Recommendations

Internet-of-things-enabled serious games: A comprehensive survey
Abstract
Internet of things has been one of the predominant research areas for the past two decades. Many application domains have embraced it to solve challenges that have long been considered hurdles. A recent trend in information ...
Highlights
- To survey state-of-the-art methods in Internet-of-things-enabled serious games.
Topologies for combining the internet of things and serious games
Multimedia in technology enhanced learning

Serious Games have been established over recent years as a means of utilising gaming for applications other than entertainment. With the emergence of the Internet of Things (IoT) paradigm, a new direction for serious games arises, where data gathered from ...
Games, algorithms, and the Internet
WWW '11: Proceedings of the 20th international conference on World wide web

The advent of the Internet brought parallel paradigm shifts to both Economics and Computer Science. Computer scientists realized that large-scale performing systems can emerge from the interaction of selfish agents and that incentives are a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

755
Total Citations
View Citations
478
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)14

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kupferman OShenwald N(2024)The Complexity of LTL Rational SynthesisACM Transactions on Computational Logic10.1145/364847325:2(1-31)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3648473
Gorbaneva OOugolnitsky G(2024)Game-Theoretic Analysis of the Interaction of Economic Agents in the Cournot Oligopoly with Consideration of the Linear Structure, the Green Effect, and Fairness ConcernAutomation and Remote Control10.1134/S000511792402005X85:2(174-199)Online publication date: 26-Jul-2024
https://doi.org/10.1134/S000511792402005X
Del Santo O’Neill TRossberg AThorpe R(2024) An efficient tool to find multispecies MSY for interacting fish stocks Fish and Fisheries10.1111/faf.1281725:3(441-454)Online publication date: 20-Mar-2024
https://doi.org/10.1111/faf.12817
Mao WMa QLiao GChen X(2024)Game Analysis and Incentive Mechanism Design for Differentially Private Cross-Silo Federated LearningIEEE Transactions on Mobile Computing10.1109/TMC.2024.336437223:10(9337-9351)Online publication date: Oct-2024
https://doi.org/10.1109/TMC.2024.3364372
Chremos IMalikopoulos A(2024)Mechanism Design Theory in Control Engineering: A Tutorial and Overview of Applications in Communication, Power Grid, Transportation, and Security SystemsIEEE Control Systems10.1109/MCS.2023.332991944:1(20-45)Online publication date: Feb-2024
https://doi.org/10.1109/MCS.2023.3329919
Bandiera CConnors RViti F(2024)Mobility service providers’ interacting strategies under multi-modal equilibriumTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104766(104766)Online publication date: Jul-2024
https://doi.org/10.1016/j.trc.2024.104766
Mancuso VBadia LCastagno PSereno MAjmone Marsan M(2024)Effectiveness of distributed stateless network server selection under strict latency constraintsComputer Networks10.1016/j.comnet.2024.110558251(110558)Online publication date: Sep-2024
https://doi.org/10.1016/j.comnet.2024.110558
Cominetti RDose VScarsini M(2024)The price of anarchy in routing games as a function of the demandMathematical Programming: Series A and B10.1007/s10107-021-01701-7203:1-2(531-558)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10107-021-01701-7
Korolev AKotova MUgolnitsky G(2023)Comparison of Methods of Organization and Management Efficiency in Dynamic Models of Cournot OligopolyИзвестия Российской академии наук. Теория и системы управления10.31857/S0002338823010043(82-105)Online publication date: 1-Jan-2023
https://doi.org/10.31857/S0002338823010043
Seaton JHounsinou SBloom GBrown P(2023)Competitive Information Provision Among Internet Routing Nodes2023 American Control Conference (ACC)10.23919/ACC55779.2023.10156591(1074-1079)Online publication date: 31-May-2023
https://doi.org/10.23919/ACC55779.2023.10156591
Show More Cited By

View Options

Get Access

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