Algorithms, games, and the internet

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms, games, and the internet

Full text

Pdf (151 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents

Hersonissos, Greece

Pages: 749 - 753

Year of Publication: 2001

ISBN:1-58113-349-9

Author

Christos Papadimitriou

University of California, Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 190, Citation Count: 141

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/380752.380883 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	2	Cottle The Linear Complementarity Problem, 1992.
	3	Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
	4	Deng, Papadimitriou, in preparation.
	5	de Vries, Vohra, "Combinatorial Auctions: A Survey." http://www.kellogg.nwu.edu/research/math/Downpapers.htm
	6	Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	7	Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
	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	R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
	13	Kleinberg "Authoritative sources in a hyperlinked environment," Proc. 1999 SODA.
	14	Jon Kleinberg , Christos H. Papadimitriou , Prabhakar Raghavan, On the value of private information, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	15	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
	16	Koutsoupias, Papadimitriou "Worst-case equilibria," Proc. 1998 STACS.
	17	R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
	18	Mas-Collel, Winston, Green Microeconomic Theory, Oxford University Press 1995.
	19	Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
	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.
	22	Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
	23	Osborne and Rubinstein, A Course in Game Theory, MIT Press, 1994.
	24	Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
	25	Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
	26	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	27	Rekhter, Li "RFC 1771, BGP-4," www.cis.ohio-state.edu/cgi-bin/rfc/rfc1771.html.
	28	T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
	29	Satinder P. Singh , Michael J. Kearns , Yishay Mansour, Nash Convergence of Gradient Dynamics in General-Sum Games, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.541-548, June 30-July 03, 2000
	30	Yao "Probabilistic computations: Toward a unified measure of complexity (extended abstract)," Proc. 1977 FOCS.

CITED BY 141

	Sudipta Rakshit , Ratan K. Guha, Fair Bandwidth Sharing in Distributed Systems: A Game-Theoretic Approach, IEEE Transactions on Computers, v.54 n.11, p.1384-1393, November 2005
	Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
	Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA
	Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Proceedings of the 4th ACM conference on Electronic commerce, p.93-97, June 09-12, 2003, San Diego, CA, USA
	Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002
	Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan
	Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
	Faron Moller , Scott A. Smolka, On the computational complexity of bisimulation, redux, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.55-59, June 08-08, 2003, San Diego, California, USA
	Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Proceedings of the 4th ACM conference on Electronic commerce, p.98-107, June 09-12, 2003, San Diego, CA, USA
	Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Michael L. Littman , Peter Stone, A polynomial-time nash equilibrium algorithm for repeated games, Proceedings of the 4th ACM conference on Electronic commerce, p.48-54, June 09-12, 2003, San Diego, CA, USA
	Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of price equilibria, Journal of Computer and System Sciences, v.67 n.2, p.311-324, September 2003
	Martin Gairing , Burkhard Monien , Karsten Tiemann, Selfish routing with incomplete information, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Chrysanthos Dellarocas, The Digitization of Word of Mouth: Promise and Challenges of Online Feedback Mechanisms, Management Science, v.49 n.10, p.1407-1424, October 2003
	Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003
	Michael J. Fischer , Michael Merritt, Appraising two decades of distributed computing theory research, Distributed Computing, v.16 n.2-3, p.239-247, September 2003
	Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Vincent Conitzer , Tuomas Sandholm, Communication complexity as a lower bound for learning in games, Proceedings of the twenty-first international conference on Machine learning, p.24, July 04-08, 2004, Banff, Alberta, Canada
	Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Pino Persiano, How to route and tax selfish unsplittable traffic, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Kate Larson , Tuomas Sandholm, Miscomputing ratio: social cost of selfish computing, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Bruno Codenotti , Daniel Štefankovič, On the computational complexity of Nash equilibria for (0, 1) bimatrix games, Information Processing Letters, v.94 n.3, p.145-150, 16 May 2005
	Mike Afergan , John Wroclawski, On the benefits and feasibility of incentive based routing infrastructure, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA
	Kate Larson , Tuomas Sandholm, Strategic deliberation and truthful revelation: an impossibility result, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Navin A. R. Bhat , Kevin Leyton-Brown, Computing Nash equilibria of action-graph games, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.35-42, July 07-11, 2004, Banff, Canada
	Nikhil R. Devanur, The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien, Computing Nash equilibria for scheduling on restricted parallel links, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Marek Chrobak , Elias Koutsoupias, Coordination mechanisms for congestion games, ACM SIGACT News, v.35 n.4, December 2004
	Moni Naor, Cryptography and mechanism design, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Andrew Lomonosov , Meera Sitharam , Kihong Park, Network QoS games: stability vs optimality tradeoff, Journal of Computer and System Sciences, v.69 n.2, p.281-302, September 2004
	Michael L. Littman , Peter Stone, A polynomial-time Nash equilibrium algorithm for repeated games, Decision Support Systems, v.39 n.1, p.55-66, March 2005
	Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Edith Elkind , Amit Sahai , Ken Steiglitz, Frugality in path auctions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Andrew V. Goldberg , Jason D. Hartline, Competitiveness via consensus, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Éva Tardos, Network games, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.341-342, June 13-16, 2004, Chicago, IL, USA
	Jacomo Corbo , David Parkes, The price of selfish behavior in bilateral network formation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Vincent Conitzer , Tuomas Sandholm, Complexity of (iterated) dominance, Proceedings of the 6th ACM conference on Electronic commerce, p.88-97, June 05-08, 2005, Vancouver, BC, Canada
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Decision Support Systems, v.39 n.1, p.3-10, March 2005
	Ahuva Mu'alem, On decentralized incentive compatible mechanisms, Proceedings of the 6th ACM conference on Electronic commerce, p.240-248, June 05-08, 2005, Vancouver, BC, Canada
	George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Michal Feldman , Kevin Lai , Li Zhang, A price-anticipating resource allocation mechanism for distributed shared clusters, Proceedings of the 6th ACM conference on Electronic commerce, p.127-136, June 05-08, 2005, Vancouver, BC, Canada
	Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Bruno Codenotti , Sriram Pemmaraju , Kasturi Varadarajan, The computation of market equilibria, ACM SIGACT News, v.35 n.4, December 2004
	Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	George Kouroupas , Elias Koutsoupias , Christos H. Papadimitriou , Martha Sideri, An economic model of the worldwide web, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Sheng Zhong , Li (Erran) Li , Yanbin Grace Liu , Yang (Richard) Yang, On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany
	Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Dov Monderer , Moshe Tennenholtz, k-Implementation, Proceedings of the 4th ACM conference on Electronic commerce, p.19-28, June 09-12, 2003, San Diego, CA, USA
	Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
	Nicolas Christin , Jens Grossklags , John Chuang, Near rationality and competitive equilibria in networked systems, Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems, September 03-03, 2004, Portland, Oregon, USA
	Xiaotie Deng , Li-Sha Huang, On the complexity of market equilibria with maximum social welfare, Information Processing Letters, v.97 n.1, p.4-11, 16 January 2006
	Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Vincent Conitzer , Tuomas Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Artificial Intelligence, v.170 n.6, p.607-619, May 2006
	Luis López , Gemma del Rey Almansa , Stéphane Paquelet , Antonio Fernández, A mathematical model for the TCP tragedy of the commons, Theoretical Computer Science, v.343 n.1-2, p.4-26, 10 October 2005
	Christoph Ambühl , Andrea E. F. Clementi , Paolo Penna , Gianluca Rossi , Riccardo Silvestri, On the approximability of the range assignment problem on radio networks in presence of selfish agents, Theoretical Computer Science, v.343 n.1-2, p.27-41, 10 October 2005
	M. Gairing , T. Lücking , M. Mavronicolas , B. Monien , P. Spirakis, Structure and complexity of extreme Nash equilibria, Theoretical Computer Science, v.343 n.1-2, p.133-157, 10 October 2005
	Richard Cole , Yevgeniy Dodis , Tim Roughgarden, How much can taxes help selfish routing?, Journal of Computer and System Sciences, v.72 n.3, p.444-467, May 2006
	A.C. Kaporis , P.G. Spirakis, The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Milena Mihail , Christos Papadimitriou , Amin Saberi, On certain connectivity properties of the internet topology, Journal of Computer and System Sciences, v.72 n.2, p.239-251, March 2006
	Narayanan Sadagopan , Mitali Singh , Bhaskar Krishnamachari, Decentralized utility-based sensor network design, Mobile Networks and Applications, v.11 n.3, p.341-350, June 2006
	Tim Roughgarden, On the severity of Braess's paradox: designing networks for selfish users is hard, Journal of Computer and System Sciences, v.72 n.5, p.922-953, August 2006
	Matt Lepinski , David Liben-Nowell , Seth Gilbert , April Rasala Lehman, Playing games in many possible worlds, Proceedings of the 7th ACM conference on Electronic commerce, p.150-159, June 11-15, 2006, Ann Arbor, Michigan, USA
	Selwyn Yuen , Baochun Li, Strategyproof mechanisms towards dynamic topology formation in autonomous networks, Mobile Networks and Applications, v.10 n.6, p.961-970, December 2005
	Henrik Björklund , Sergei Vorobyov, Combinatorial structure and randomized subexponential algorithms for infinite games, Theoretical Computer Science, v.349 n.3, p.347-360, 16 December 2005
	Baruch Awerbuch , Yossi Azar , Yossi Richter , Dekel Tsur, Tradeoffs in worst-case equilibria, Theoretical Computer Science, v.361 n.2, p.200-209, 1 September 2006
	Chandra Chekuri , Julia Chuzhoy , Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Non-cooperative multicast and facility location games, Proceedings of the 7th ACM conference on Electronic commerce, p.72-81, June 11-15, 2006, Ann Arbor, Michigan, USA
	Moshe Babaioff , Michal Feldman , Noam Nisan, Combinatorial agency, Proceedings of the 7th ACM conference on Electronic commerce, p.18-28, June 11-15, 2006, Ann Arbor, Michigan, USA
	Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Narender Hanchate , Nagarajan Ranganathan, A game-theoretic framework for multimetric optimization of interconnect delay, power, and crosstalk noise during wire sizing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.711-739, July 2006
	Jon Kleinberg, Distributed social systems, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.5-6, July 23-26, 2006, Denver, Colorado, USA
	Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Ho-Lin Chen , Tim Roughgarden, Network design with weighted players, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA
	Jon Kleinberg, Social networks, incentives, and search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, p.210-211, August 06-11, 2006, Seattle, Washington, USA
	Tao Wu , David Starobinski, On the price of anarchy in unbounded delay networks, Proceeding from the 2006 workshop on Game theory for communications and networks, October 14-14, 2006, Pisa, Italy
	Petteri Nurmi, Modeling energy constrained routing in selfish ad hoc networks, Proceeding from the 2006 workshop on Game theory for communications and networks, October 14-14, 2006, Pisa, Italy
	Jochen Mundinger , Jean-Yves Le Boudec, Reputation in self-organized communication systems and beyond, Proceedings from the 2006 workshop on Interdisciplinary systems approach in performance evaluation and design of computer & communications sytems, October 14-14, 2006, Pisa, Italy
	V. Bilò , M. Flammini , G. Melideo , L. Moscardelli , A. Navarra, Sharing the cost of multicast transmissions in wireless networks, Theoretical Computer Science, v.369 n.1, p.269-284, 15 December 2006
	Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien, The price of anarchy for polynomial social cost, Theoretical Computer Science, v.369 n.1, p.116-135, 15 December 2006
	Luis López , Antonio Fernández , Vicent Cholvi, A game theoretic comparison of TCP and digital fountain based protocols, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.12, p.3413-3426, August, 2007
	Vincent Conitzer , Tuomas Sandholm, AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, Machine Learning, v.67 n.1-2, p.23-43, May 2007
	Yu-Kwong Kwok , Kai Hwang , ShanShan Song, Selfish Grids: Game-Theoretic Modeling and NAS/PSA Benchmark Evaluation, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.621-636, May 2007
	Eyal Even-Dar , Alex Kesselman , Yishay Mansour, Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms (TALG), v.3 n.3, p.32-es, August 2007
	Vincent Conitzer , Tuomas Sandholm, A technique for reducing normal-form games to compute a Nash equilibrium, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Sheng Zhong , Li Erran Li , Yanbin Grace Liu , Yang Richard Yang, On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretic and cryptographic techniques, Wireless Networks, v.13 n.6, p.799-816, December 2007
	Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos , Evi Papaioannou, Scheduling to maximize participation, Theoretical Computer Science, v.402 n.2-3, p.142-155, August, 2008
	Frank Guerin, Applying game theory mechanisms in open agent systems with complete information, Autonomous Agents and Multi-Agent Systems, v.15 n.2, p.109-146, October 2007
	Christian Borgs , Jennifer Chayes , Constantinos Daskalakis , Sebastien Roch, First to market is not everything: an analysis of preferential attachment with fitness, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Amir Epstein , Michal Feldman , Yishay Mansour, Strong equilibrium in cost sharing connection games, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Fang Wu , Li Zhang, Proportional response dynamics leads to market equilibrium, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Dinesh Garg , Kamal Jain , Kunal Talwar , Vijay V. Vazirani, A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property, Theoretical Computer Science, v.378 n.2, p.143-152, June, 2007
	Patrick Briest , Piotr Krysta, Buying cheap is expensive: hardness of non-parametric multi-product pricing, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.716-725, January 07-09, 2007, New Orleans, Louisiana
	Narender Hanchate , Nagarajan Ranganathan, Post-Layout Gate Sizing for Interconnect Delay and Crosstalk Noise Optimization, Proceedings of the 7th International Symposium on Quality Electronic Design, p.92-97, March 27-29, 2006
	Frank Guerin , Emmanuel M. Tadjouddine, Realising Common Knowledge Assumptions in Agent Auctions, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.579-586, December 18-22, 2006
	Shantanu Biswas , Y. Narahari, Iterative Dutch combinatorial auctions, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.185-205, July 2005
	Eugene Nudelman , Jennifer Wortman , Yoav Shoham , Kevin Leyton-Brown, Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.880-887, July 19-23, 2004, New York, New York
	Ning Chen , Anna R. Karlin, Cheap labor can be expensive, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.707-715, January 07-09, 2007, New Orleans, Louisiana
	Kimaya Mittal , Elizabeth M. Belding , Subhash Suri, A game-theoretic analysis of wireless access point selection by mobile users, Computer Communications, v.31 n.10, p.2049-2062, June, 2008
	Juncheng Jia , Qian Zhang, Competitions and dynamics of duopoly wireless service providers in dynamic spectrum market, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	A. C. Kaporis , P. G. Spirakis, The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions, Theoretical Computer Science, v.410 n.8-10, p.745-755, March, 2009
	Stefano Leonardi , Piotr Sankowski, Network formation games with local coalitions, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Cuihong Li , Bin Yu , Katia Sycara, An incentive mechanism for message relaying in unstructured peer-to-peer systems, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Ravi Kannan , Thorsten Theobald, Games of fixed rank: a hierarchy of bimatrix games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1124-1132, January 07-09, 2007, New Orleans, Louisiana
	Jun Xiao , Naixue Xiong , Laurence T. Yang , Y. He, A joint selfish routing and channel assignment game in wireless mesh networks, Computer Communications, v.31 n.7, p.1447-1459, May, 2008
	Erik D. Demaine , MohammadTaghi Hajiaghayi , Hamid Mahini , Morteza Zadimoghaddam, The price of anarchy in network creation games, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
	Sheng Zhong , Fan Wu, On designing collusion-resistant routing schemes for non-cooperative wireless ad hoc networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada
	Alessandro Ferrante , Mimmo Parente, Mixed Nash equilibria in selfish routing problems with dynamic constraints, Theoretical Computer Science, v.393 n.1-3, p.37-53, March, 2008
	Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Maximum-lifetime routing: system optimization & game-theoretic perspectives, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada
	David Ilcinkas , Andrzej Pelc, Impact of Asynchrony on the Behavior of Rational Selfish Agents, Fundamenta Informaticae, v.82 n.1-2, p.113-125, January 2008
	Panos Parpas , Berç Rustem, A Pricing Mechanism for Resource Management in Grid Computing, Computational Economics, v.31 n.4, p.381-395, May 2008
	Tomas Klos , Gerrit Jan van Ahee, Evolutionary dynamics for designing multi-period auctions, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Nikolaos Laoutaris , Laura J. Poplawski , Rajmohan Rajaraman , Ravi Sundaram , Shang-Hua Teng, Bounded budget connection (BBC) games or how to make friends and influence people, on a budget, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Stephan Schosser , Klemens Böhm , Bodo Vogt, Do humans identify efficient strategies in structured peer-to-peer systems?, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Costas Busch , Rajgopal Kannan , Athanasios V. Vasilakos, Quality of routing congestion games in wireless sensor networks, Proceedings of the 4th Annual International Conference on Wireless Internet, November 17-19, 2008, Maui, Hawaii
	Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien , Manuel Rode, Nash equilibria in discrete routing games with convex latency functions, Journal of Computer and System Sciences, v.74 n.7, p.1199-1225, November, 2008
	George F. Georgakopoulos, Buffered cross-bar switches, revisited: design steps, proofs and simulations towards optimal rate and minimum buffer memory, IEEE/ACM Transactions on Networking (TON), v.16 n.6, p.1340-1351, December 2008
	Ioannis Caragiannis, Efficient coordination mechanisms for unrelated machine scheduling, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.815-824, January 04-06, 2009, New York, New York
	Zhenjie Zhang , Laks V. S. Lakshmanan , Anthony K. H. Tung, On domination game analysis for microeconomic data mining, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-27, January 2009
	Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Giuseppe Persiano, The power of verification for one-parameter agents, Journal of Computer and System Sciences, v.75 n.3, p.190-211, May, 2009
	Vincent Conitzer , Tuomas Sandholm, A generalized strategy eliminability criterion and computational methods for applying it, Proceedings of the 20th national conference on Artificial intelligence, p.483-488, July 09-13, 2005, Pittsburgh, Pennsylvania
	Samuel Ieong , Robert McGrew , Eugene Nudelman , Yoav Shoham , Qixiang Sun, Fast and compact: a simple class of congestion games, Proceedings of the 20th national conference on Artificial intelligence, p.489-494, July 09-13, 2005, Pittsburgh, Pennsylvania
	Thomas Sandholm , Andrew Gilpin , Vincent Conitzer, Mixed-integer programming methods for finding Nash equilibria, Proceedings of the 20th national conference on Artificial intelligence, p.495-501, July 09-13, 2005, Pittsburgh, Pennsylvania
	Paolo Penna , Guido Proietti , Peter Widmayer, Strongly polynomial-time truthful mechanisms in one shot, Theoretical Computer Science, v.410 n.17, p.1607-1615, April, 2009
	Ryan Porter , Eugene Nudelman , Yoav Shoham, Simple search methods for finding a Nash equilibrium, Proceedings of the 19th national conference on Artifical intelligence, p.664-669, July 25-29, 2004, San Jose, California
	Xi Chen , Xiaotie Deng , Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria, Journal of the ACM (JACM), v.56 n.3, p.1-57, May 2009
	Thomas Sandholm , Kevin Lai, MapReduce optimization using regulated dynamic prioritization, Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, June 15-19, 2009, Seattle, WA, USA
	George Christodoulou , Elias Koutsoupias , Akash Nanavati, Coordination mechanisms, Theoretical Computer Science, v.410 n.36, p.3327-3336, August, 2009
	Dov Monderer , Moshe Tennenholtz, K-implementation, Journal of Artificial Intelligence Research, v.21 n.1, p.37-62, January 2004
	Itai Ashlagi , Dov Monderer , Moshe Tennenholtz, On the value of correlation, Journal of Artificial Intelligence Research, v.33 n.1, p.575-613, September 2008
	Enrico Malizia , Luigi Palopoli , Francesco Scarcello, Infeasibility certificates and the complexity of the core in coalitional games, Proceedings of the 20th international joint conference on Artifical intelligence, p.1402-1407, January 06-12, 2007, Hyderabad, India
	Ola Rozenfeld , Moshe Tennenholtz, Routing mediators, Proceedings of the 20th international joint conference on Artifical intelligence, p.1488-1493, January 06-12, 2007, Hyderabad, India
	Costas Busch , Malik Magdon-Ismail, Atomic routing games on maximum congestion, Theoretical Computer Science, v.410 n.36, p.3337-3347, August, 2009
	Vincent Conitzer , Tüomas Sandholm, Complexity results about Nash equilibria, Proceedings of the 18th international joint conference on Artificial intelligence, p.765-771, August 09-15, 2003, Acapulco, Mexico