%% Theory of Computing
%% File: v004a004.bib
%% Publication date: August 4, 2008
%% Authors: Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler

%
%
@string{ACMTransAlgorithms="ACM Trans. Algorithms"}
%
@string{Econometrica="Econometrica"}
%
@string{InternatJGameTheory="Internat. J. Game Theory"}
%
@string{JACM="J. ACM"}
%
@string{JComputSystemSci="J. Comput. System Sci."}
%
@string{SIAMJApplDynSyst="SIAM J. Appl. Dyn. Syst."}
%
@string{SIAMJApplMath="SIAM J. Appl. Math."}
%
@string{SIAMJComput="SIAM J. Comput."}
%
@string{SIAMJControlOptim="SIAM J. Control Optim."}
%
@string{SIAMJDiscreteMath="SIAM J. Discrete Math."}
%
@string{SIAMJMathAnal="SIAM J. Math. Anal."}
%
@string{SIAMJMatrixAnalAppl="SIAM J. Matrix Anal. Appl."}
%
@string{SIAMJNumerAnal="SIAM J. Numer. Anal."}
%
@string{SIAMJOptim="SIAM J. Optim."}
%
@string{SIAMJSciComput="SIAM J. Sci. Comput."}
%
@string{SIAMMonogrDiscreteMathAppl="SIAM Monogr. Discrete Math. Appl."}
%
@string{SIAMRev="SIAM Rev."}

@article{AKR95,
	Address = {Philadelphia, PA, USA},
	Author = {Ajit Agrawal and Philip Klein and R. Ravi},
	Issn = {0097-5397},
	Journal = SIAMJComput,
	Number = {3},
	Pages = {440--456},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {When Trees Collide: An Approximation Algorithm for the Generalized {Steiner} Problem on Networks},
	Volume = {24},
	Year = {1995},
	eprint="sicomp:10.1137/S0097539792236237"}

@article{AKPSS02,
	Address = {New York, NY, USA},
	Author = {Aditya Akella and Srinivasan Seshan and Richard Karp and Scott Shenker and Christos Papadimitriou},
	Issn = {0146-4833},
	Journal = {SIGCOMM Comput. Commun. Rev.},
	Number = {4},
	Pages = {117--130},
	Publisher = {ACM},
	Title = {Selfish behavior and stability of the {I}nternet: {A} game-theoretic analysis of {TCP}},
	Volume = {32},
	Year = {2002},
	eprint="acm:964725.633037"}

@inproceedings{AEEM06,
	Address = {New York, NY, USA},
	Author = {Susanne Albers and Stefan Eilts and Eyal Even-Dar and Yishay Mansour and Liam Roditty},
	Booktitle = {Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA'06)},
	Isbn = {0-89871-605-5},
	Location = {Miami, Florida},
	Pages = {89--98},
	Publisher = {ACM},
	Title = {On {Nash} equilibria for a network creation game},
	Year = {2006},
	eprint="soda:1109557.1109568"}

@inproceedings{ADKTWR04,
	Address = {Washington, DC, USA},
	Author = {Elliot Anshelevich and Anirban Dasgupta and Jon Kleinberg and \'Eva Tardos and Tom Wexler and Tim Roughgarden},
	Booktitle = {Proc. 45th FOCS},
	Isbn = {0-7695-2228-9},
	Pages = {295--304},
	Publisher = {IEEE Computer Society},
	Title = {The Price of Stability for Network Design with Fair Cost Allocation},
	Year = {2004},
	eprint="focs:10.1109/FOCS.2004.68"}

@inproceedings{ADTW03,
	Address = {New York, NY, USA},
	Author = {Elliot Anshelevich and Anirban Dasgupta and \'Eva Tardos and Tom Wexler},
	Booktitle = {Proc. 35th STOC},
	Isbn = {1-58113-674-9},
	Location = {San Diego, CA, USA},
	Pages = {511--520},
	Publisher = {ACM},
	Title = {Near-optimal network design with selfish agents},
	Year = {2003},
	eprint="stoc:780542.780617"}

@inproceedings{AAE05,
	Address = {New York, NY, USA},
	Author = {Baruch Awerbuch and Yossi Azar and Amir Epstein},
	Booktitle = {Proc. 37th STOC},
	Isbn = {1-58113-960-8},
	Location = {Baltimore, MD, USA},
	Pages = {57--66},
	Publisher = {ACM},
	Title = {The price of routing unsplittable flow},
	Year = {2005},
	eprint="stoc:1060590.1060599"}

@article{BG00,
	Author = {Venkatesh Bala and Sanjeev Goyal},
	Journal = Econometrica,
	Month = {September},
	Number = {5},
	Pages = {1181-1230},
	Title = {A Noncooperative Model of Network Formation},
	Url = {http://ideas.repec.org/a/ecm/emetrp/v68y2000i5p1181-1230.html},
	Volume = {68},
	Year = 2000}

@inproceedings{CCCDGGL98,
	Address = {Philadelphia, PA, USA},
	Author = {Moses Charikar and Chandra Chekuri and To-yat Cheung and Zuo Dai and Ashish Goel and Sudipto Guha and Ming Li},
	Booktitle = {Proc. 9th ACM-SIAM Symp. on Discrete Algorithms (SODA'98)},
	Isbn = {0-89871-410-9},
	Location = {San Francisco, California, United States},
	Pages = {192--200},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {Approximation algorithms for directed {Steiner} problems},
	Year = {1998},
	eprint="soda:314613.314700"}

@inproceedings{CCLNO06,
	Address = {New York, NY, USA},
	Author = {Chandra Chekuri and Julia Chuzhoy and Liane Lewin-Eytan and Joseph (Seffi) Naor and Ariel Orda},
	Booktitle = {Proc. 7th ACM Conference on Electronic Commerce (EC'06)},
	Isbn = {1-59593-236-4},
	Location = {Ann Arbor, Michigan, USA},
	Pages = {72--81},
	Publisher = {ACM},
	Title = {Non-cooperative multicast and facility location games},
	Year = {2006},
	eprint="acm:1134707.1134716"}

@inproceedings{CR06,
	Address = {New York, NY, USA},
	Author = {Ho-Lin Chen and Tim Roughgarden},
	Booktitle = {Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA'06)},
	Isbn = {1-59593-452-9},
	Location = {Cambridge, Massachusetts, USA},
	Pages = {29--38},
	Publisher = {ACM},
	Title = {Network design with weighted players},
	Year = {2006},
	eprint="acm:1148109.1148114"}

@inproceedings{CK05,
	Address = {New York, NY, USA},
	Author = {George Christodoulou and Elias Koutsoupias},
	Booktitle = {Proc. 37th STOC},
	Isbn = {1-58113-960-8},
	Location = {Baltimore, MD, USA},
	Pages = {67--73},
	Publisher = {ACM},
	Title = {The price of anarchy of finite congestion games},
	Year = {2005},
	eprint="stoc:1060590.1060600"}

@inproceedings{CKV02,
 author = {Artur Czumaj and Piotr Krysta and Berthold V\"{o}cking},
 title = {Selfish traffic allocation for server farms},
 booktitle = {Proc. STOC},
 year = {2002},
 isbn = {1-58113-495-9},
 pages = {287--296},
 location = {Montreal, Quebec, Canada},
 publisher = {ACM},
 address = {New York, NY, USA},
eprint="stoc:509907.509952"}

@article{CV07,
	Address = {New York, NY, USA},
	Author = {Artur Czumaj and Berthold V\"{o}cking},
	Issn = {1549-6325},
	Journal = ACMTransAlgorithms,
	Number = {1},
	Pages = {4},
	Publisher = {ACM},
	Title = {Tight bounds for worst-case equilibria},
	Volume = {3},
	Year = {2007},
	eprint={acm:1186810.1186814,acm:545436}}

@article{DGH02,
	Address = {New York, NY, USA},
	Author = {Debojyoti Dutta and Ashish Goel and John Heidemann},
	Date-Modified = {2008-06-16 16:02:25 -0400},
	Issn = {0146-4833},
	Journal = {SIGCOMM Comput. Commun. Rev.},
	Number = {3},
	Pages = {20--20},
	Publisher = {ACM},
	Title = {Oblivious {AQM} and {Nash} equilibria},
	Volume = {32},
	Year = {2002},
	eprint="acm:571697.571709"}

@inproceedings{EFM07,
	Address = {New York, NY, USA},
	Author = {Amir Epstein and Michal Feldman and Yishay Mansour},
	Booktitle = {Proc. 8th ACM Conference on Electronic Commerce (EC'07)},
	Isbn = {978-1-59593-653-0},
	Location = {San Diego, California, USA},
	Pages = {84--92},
	Publisher = {ACM},
	Title = {Strong equilibrium in cost sharing connection games},
	Year = {2007},
	eprint="acm:1250910.1250924"}

@inproceedings{FLMPS03,
	Address = {New York, NY, USA},
	Author = {Alex Fabrikant and Ankur Luthra and Elitza Maneva and Christos H. Papadimitriou and Scott Shenker},
	Booktitle = {Proc. 22nd Symp. on Principles of Distributed Computing (PODC'03)},
	Isbn = {1-58113-708-7},
	Location = {Boston, Massachusetts},
	Pages = {347--351},
	Publisher = {ACM},
	Title = {On a network creation game},
	Year = {2003},
	eprint="acm:872035.872088"}

@article{F98,
	Address = {New York, NY, USA},
	Author = {Uriel Feige},
	Issn = {0004-5411},
	Journal = JACM,
	Number = {4},
	Pages = {634--652},
	Publisher = {ACM},
	Title = {A threshold of {$\ln n$} for approximating set cover},
	Volume = {45},
	Year = {1998},
	eprint="jacm:285055.285059"}

@article{FPS01,
	Address = {Orlando, FL, USA},
	Author = {Joan Feigenbaum and Christos H. Papadimitriou and Scott Shenker},
	Issn = {0022-0000},
	Journal = JComputSystemSci,
	Number = {1},
	Pages = {21--41},
	Publisher = {Academic Press, Inc.},
	Title = {Sharing the cost of multicast transmissions},
	Volume = {63},
	Year = {2001},
	eprint="jcss:10.1006/jcss.2001.1754"}

@inproceedings{FKLOS06,
	Author = {Amos Fiat and Haim Kaplan and Meital Levy and Svetlana Olonetsky and Ronen Shabo},
	Booktitle = {Proc. 33rd International Colloq. on Automata, Languages, and Programming (ICALP'06)},
	Date = {2006-07-03},
	Isbn = {3-540-35904-4},
	Pages = {608-618},
	Publisher = {Springer},
	Series = {Lecture Notes in Computer Science},
	Title = {On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations.},
	Url = {http://dblp.uni-trier.de/db/conf/icalp/icalp2006-1.html#FiatKLOS06},
	Volume = {4051},
	Year = {2006},
	eprint="icalp:w045t0318v5116xl"}

@article{GW95,
	Address = {Philadelphia, PA, USA},
	Author = {Michel X. Goemans and David P. Williamson},
	Issn = {0097-5397},
	Journal = SIAMJComput,
	Number = {2},
	Pages = {296--317},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {A General Approximation Technique for Constrained Forest Problems},
	Volume = {24},
	Year = {1995},
	eprint="sicomp:10.1137/S0097539793242618"}

@techreport{HS01,
	Author = {H. Heller and S. Sarangi},
	Institution = {Virginia Tech},
	Number = {E-2001-1},
	Title = {{Nash} Networks with Heterogeneous Agents},
	Type = {Working Paper},
	Year = 2001,
	url="http://www.bus.lsu.edu/economics/papers/pap03_06.pdf"}

@inproceedings{H06,
	Author = {Martin Hoefer},
	Bibsource = {DBLP, http://dblp.uni-trier.de},
	Booktitle = {Proc. 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS'06)},
	Pages = {517-527},
	Title = {Non-cooperative Tree Creation},
	Year = {2006},
	eprint="mfcs:uu60q8258u47802v"}

@inproceedings{H06b,
	Author = {Martin Hoefer},
	Bibsource = {DBLP, http://dblp.uni-trier.de},
	Booktitle = {Proc. 17th Int. Symp. on Algorithms and Computation (ISAAC'06)},
	Pages = {369-378},
	Title = {Non-cooperative Facility Location and Covering Games},
	Year = {2006},
	eprint="isaac:rwk3528257852rh1"}

@inproceedings{HK05,
	Author = {Martin Hoefer and                Piotr Krysta},
	Bibsource = {DBLP, http://dblp.uni-trier.de},
	Booktitle = {Proc. 11th Int. Conf. on Computing and Combinatorics (COCOON'05)},
	Pages = {167-178},
	Title = {Geometric Network Design with Selfish Agents},
	Year = {2005},
	eprint="springer:2fbchhr9y2x08k8l"}

@inproceedings{JV01,
	Address = {New York, NY, USA},
	Author = {Kamal Jain and Vijay Vazirani},
	Booktitle = {Proc. 33rd STOC},
	Isbn = {1-58113-349-9},
	Location = {Hersonissos, Greece},
	Pages = {364--372},
	Publisher = {ACM},
	Title = {Applications of approximation algorithms to cooperative games},
	Year = {2001},
	eprint="stoc:380752.380825"}

@inproceedings{KP99,
	Address = {Trier, Germany},
	Author = {E. Koutsoupias and C. Papadimitriou},
	Booktitle = {Proc. 16th Symp. on Theoretical Aspects of Computer Science (STACS'99)},
	Month = mar,
	Pages = {404--413},
	Title = {Worst-case equilibria},
	Year = 1999,
	eprint="stacs:y37e5ne8bbafjb5r"}

@inproceedings{MS01,
 author = {Marios Mavronicolas and Paul Spirakis},
 title = {The price of selfish routing},
 booktitle = {Proc. STOC},
 year = {2001},
 isbn = {1-58113-349-9},
 pages = {510--519},
 location = {Hersonissos, Greece},
 publisher = {ACM},
 address = {New York, NY, USA},
eprint="stoc:380752.380846"}

@article{MS96,
  author={Dov Monderer and Lloyd S. Shapley},
  title={Potential Games},
  journal={Games and Economic Behavior},
  year=1996,
  volume={14},
  number={1},
  pages={124--143},
  month={May},
  url={http://ideas.repec.org/a/eee/gamebe/v14y1996i1p124-143.html}
}

@inproceedings{P01,
	Address = {New York, NY, USA},
	Author = {Christos Papadimitriou},
	Booktitle = {Proc. 33rd STOC},
	Isbn = {1-58113-349-9},
	Location = {Hersonissos, Greece},
	Pages = {749--753},
	Publisher = {ACM},
	Title = {Algorithms, games, and the internet},
	Year = {2001},
	eprint="stoc:380752.380883"}

@inproceedings{RZ00,
	Address = {Philadelphia, PA, USA},
	Author = {Gabriel Robins and Alexander Zelikovsky},
	Booktitle = {Proc. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA'00)},
	Isbn = {0-89871-453-2},
	Location = {San Francisco, California, United States},
	Pages = {770--779},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {Improved {Steiner} tree approximation in graphs},
	Year = {2000},
	eprint="soda:338219.338638"}

@article{R73,
	Author = {R.W. Rosenthal},
	Journal = InternatJGameTheory,
	Pages = {65--67},
	Title = {A Class of Games Possessing Pure-Strategy {Nash} Equilibria},
	Volume = {2},
	Year = {1973}}

@inproceedings{R02,
	Address = {New York, NY, USA},
	Author = {Tim Roughgarden},
	Booktitle = {Proc. 34th STOC},
	Isbn = {1-58113-495-9},
	Location = {Montreal, Quebec, Canada},
	Pages = {428--437},
	Publisher = {ACM},
	Title = {The price of anarchy is independent of the network topology},
	Year = {2002},
	eprint="stoc:509907.509971"}

@inproceedings{R01,
	Address = {New York, NY, USA},
	Author = {Tim Roughgarden},
	Booktitle = {Proc. 33rd STOC},
	Isbn = {1-58113-349-9},
	Location = {Hersonissos, Greece},
	Pages = {104--113},
	Publisher = {ACM},
	Title = {{Stackelberg} scheduling strategies},
	Year = {2001},
	eprint="stoc:380752.380783"}

@article{RT02,
	Address = {New York, NY, USA},
	Author = {Tim Roughgarden and \'{E}va Tardos},
	Issn = {0004-5411},
	Journal = JACM,
	Number = {2},
	Pages = {236--259},
	Publisher = {ACM},
	Title = {How bad is selfish routing?},
	Volume = {49},
	Year = {2002},
	eprint="jacm:506147.506153"}

@inproceedings{SS03,
	Address = {Philadelphia, PA, USA},
	Author = {Andreas S. Schulz and Nicol\'{a}s Stier Moses},
	Booktitle = {Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA'03)},
	Isbn = {0-89871-538-5},
	Location = {Baltimore, Maryland},
	Pages = {86--87},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {On the performance of user equilibria in traffic networks},
	Year = {2003},
	eprint="soda:644108.644121"}

@article{S90,
	Address = {New York, NY, USA},
	Author = {Scott Shenker},
	Issn = {0163-5999},
	Journal = {SIGMETRICS Perform. Eval. Rev.},
	Number = {1},
	Pages = {241--242},
	Publisher = {ACM},
	Title = {Making greed work in networks: a game-theoretic analysis of gateway service disciplines},
	Volume = {18},
	Year = {1990},
	eprint="acm:98460.98764"}

@inproceedings{V02,
	Address = {Washington, DC, USA},
	Author = {Adrian Vetta},
	Booktitle = {Proc. 43rd FOCS},
	Isbn = {0-7695-1822-2},
	Pages = {416},
	Publisher = {IEEE Computer Society},
	Title = {{Nash} Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions},
	Year = {2002},
	eprint="focs:10.1109/SFCS.2002.1181966"}

--Apple-Mail-4--1003346821
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed
Content-Transfer-Encoding: 7bit



--Apple-Mail-4--1003346821--


