Algorithms, games, and the internet

By Christos H. Papadimitriou. Symposium on the Theory of Computing, 2001

1,256 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/2434a75d334b10f2eadddb80bb6cbe7af9f19bae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Truthful approximation mechanisms for restricted combinatorial auctions (2008, background): “(Rosenschein & Zlotkin 1994) for an early treatment, and (Nisan 1999; Papadimitriou 2001) for more recent surveys.”
Playing large games using simple strategies (2003, neutral): “Playing Large Games using Simple Strategies * Richard J. Lipton Evangelos Markakis Aranyak Mehta rjl@cc.gatech.edu vangelis@cc.gatech.edu aranyak@cc.gatech.edu Georgia Tech Georgia Tech Georgia Tech College of Computing College of Computing College of Computing Atlanta, GA 30332 Atlanta, GA 30332…”
The Price of Fairness (2011, background): “See Johari and Tsitsiklis (2004), Koutsoupias and Papadimitriou (1999), Papadimitriou (2001), Perakis (2007), Roughgarden and Tardos (2002) for more details.”
Game Theory for Wireless Engineers (2006, background): “How much information is enough for effective distributed decision making? The performance difference between following selfish, local goals and acting in a communal, network-wide mode of operation is called the price of anarchy in [53].”
Prediction, learning, and games (2006, methodology): “We refer the interested reader to Papadimitriou [230, 231], Kearns and Mansour [179], Papadimitriou and Roughgarden [232].”
Computing correlated equilibria in multi-player games (2005, background): “In this latter regard, the existence of a polynomial algorithm for computing a mixed Nash equilibrium in a two-person game is famously, and quite astonishingly, open [22, 28].”
Computing the optimal strategy to commit to (2006, background): “This polynomial-time solvability of the problem of computing an optimal mixed strategy to commit to in two-player normal-form games contrasts with the unknown complexity of computing a Nash equilibrium in such games [21], as well as with the NP-hardness of finding a Nash equilibrium with maximum uti”
The price of anarchy is independent of the network topology (2002, background): “Roughgarden and Tardos [20] showed that this ratio (dubbed “the price of anarchy” by Papadimitriou [ 14 ]) can be arbitrarily large unless additional structure is imposed on the classes of allowable edge latency functions and/or allowable network topologies.”
AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents (2003, background): “…& Veloso, 2002), we also assume that the agents can compute a Nash equilibrium.6 (It is still unknown whether a Nash equilibrium can be found in worst-case polynomial time (Papadimitriou, 2001), but it is known that certain related questions are hard in the worst case (Conitzer & Sandholm, 2003).)”
Nash equilibria in random games (2005, background): “The complexity of finding a Nash equilibrium in a player game is perhaps the outstanding open problem in algorithmic game theory [ 28 ].”
Efficiency loss in a network resource allocation game: the case of elastic supply (2004, background): “Recent research efforts have focused on quantifying this loss for specific game environments; the resulting degree of efficiency loss is known as the “price of anarchy” [ 11 ].”
CONGA: distributed congestion-aware load balancing for datacenters (2015, methodology): “We then revisit the design decisions shown in Figure 1 in more detail from the top down.”
Cognitive networks: adaptation and learning to achieve end-to-end performance objectives (2006, background): “The performance difference between cognitive elements following selfish, local goals and acting in an altruistic, network-wide mode of operation is called the price of anarchy in [ 12 ].”
A polynomial-time nash equilibrium algorithm for repeated games (2003, background): “This result stands in contrast to the problem of computing a Nash equilibrium in a one-shot game, the complexity of which remains an important and long-standing open problem (Papadimitriou 2001).”
Issues in Multiagent Resource Allocation (2006, background): “For further introductions to computational complexity theory we refer the reader to the textbook by Papadimitriou [69].”