Algorithmic Game Theory

In the last few years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on incentives and pricing, cost sharing, information markets and cryptography and security. Students, researchers and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application. With Contributions From Major Researchers In The Field, 'algorithmic Game Theory' Presents A Comprehensive Treatment Of This Important Practical Application. Basic Solution Concepts And Computational Issues / Éva Tardos, Vijay V. Vazirani -- The Complexity Of Finding Nash Equilibria / Christos H. Papadimitriou -- Equilibrium Computation For Two-player Games In Strategic And Extensive Form / Bernhard Von Stengel -- Learning, Regret Minimization, Equilibria / Avrim Blum, Yishay Mansour -- Combinatorial Algorithms For Market Equilibria / Vijay V. Vazirani -- Computation Of Market Equilibria By Convex Programming / Bruno Codenotti, Kasturi Varadarajan -- Graphical Games / Michael Kearns -- Cryptography And Game Theory / Yevgeniy Dodis, Tal Rabin -- Introduction To Mechanism Design (for Computer Scientists) / Noam Nisan -- Mechanism Design Without Money / James Schummer, Rakesh V. Vohra -- Combinatorial Auctions / Liad Blumrosen, Noam Nisan -- Computationally Efficient Approximation Mechanisms / Ron Lavi -- Profit Maximization In Mechanism Design / Jason D. Hartline, Anna R. Karlin --^ Distributed Algorithmic Mechanism Design / Joan Feigenbaum, Michael Schapira, Scott Shenker -- Cost Sharing / Kamal Jain, Mohammad Mahdian -- Online Mechanisms / David C. Parkes -- Introduction To The Inefficiency Of Equilibria / Tim Roughgarden, Éva Tardos -- Routing Games / Tim Roughgarden -- Network Formation Games And The Potential Function Method / Éva Tardos, Tom Wexler -- Selfish Load Balancing / Berthold Vöcking -- The Price Of Anarchy And The Design Of The Scalable Resource Allocation Mechanisms / Ramesh Johari -- Incentives And Pricing In Communications Networks / Asuman Ozdaglar, R. Srikant -- Incentives In Peer-to-peer Systems / Moshe Babaioff, John Chuang, Michal Feldman -- Cascading Behavior In Networks: Algorithmic And Economic Issues / Jon Kleinberg -- Incentives And Information Security / Ross Anderson [and Others] -- Computational Aspects Of Prediction Markets / David M. Pennock, Rahul Sami --^ Manipulation-resistant Reputation Systems / Eric Friedman, Paul Resnick, Rahul Sami -- Sponsored Search Auctions / Sébastien Lahaie [and Others] -- Computational Evolutionary Game Theory / Siddharth Suri. Edited By Noam Nisan ... [et Al.]. Includes Bibliographical References And Index. 00 9780521872829 01.0_pp_i_iv_Frontmatter 02.0_pp_v_xii_Contents 03.0_pp_xiii_xvi_Foreword 04.0_pp_xvii_xviii_Preface 05.0_pp_xix_xxi_Contributors 06.0_pp_1_2_Computing_in_Games 06.1_pp_3_28_Basic_Solution_Concepts_and_Computational_Issues 06.2_pp_29_52_The_Complexity_of_Finding_Nash_Equilibria 06.3_pp_53_78_Equilibrium_Computation_for_Two-Player_Games_in_Strategic_and_Extensive_Form 06.4_pp_79_102_Learning_Regret_Minimization_and_Equilibria 06.5_pp_103_134_Combinatorial_Algorithms_for_Market_Equilibria 06.6_pp_135_158_Computation_of_Market_Equilibria_by_Convex_Programming 06.7_pp_159_180_Graphical_Games 06.8_pp_181_206_Cryptography_and_Game_Theory 07.0_pp_207_208_Algorithmic_Mechanism_Design 07.1_pp_209_242_Introduction_to_Mechanism_Design_for_Computer_Scientists 07.2_pp_243_266_Mechanism_Design_without_Money 07.3_pp_267_300_Combinatorial_Auctions 07.4_pp_301_330_Computationally_Efficient_Approximation_Mechanisms 07.5_pp_331_362_Profit_Maximization_in_Mechanism_Design 07.6_pp_363_384_Distributed_Algorithmic_Mechanism_Design 07.7_pp_385_410_Cost_Sharing 07.8_pp_411_440_Online_Mechanisms 08.0_pp_441_442_Quantifying_the_Inefficiency_of_Equilibria 08.1_pp_443_460_Introduction_to_the_Inefficiency_of_Equilibria 08.2_pp_461_486_Routing_Games 08.3_pp_487_516_Network_Formation_Games_and_the_Potential_Function_Method 08.4_pp_517_542_Selfish_Load_Balancing 08.5_pp_543_568_The_Price_of_Anarchy_and_the_Design_of_Scalable_Resource_Allocation_Mechanisms 09.0_pp_569_570_Additional_Topics 09.1_pp_571_592_Incentives_and_Pricing_in_Communications_Networks 09.2_pp_593_612_Incentives_in_Peer-to-Peer_Systems 09.3_pp_613_632_Cascading_Behavior_in_Networks_Algorithmic_and_Economic_Issues 09.4_pp_633_650_Incentives_and_Information_Security 09.5_pp_651_676_Computational_Aspects_of_Prediction_Markets 09.6_pp_677_698_Manipulation-Resistant_Reputation_Systems 09.7_pp_699_716_Sponsored_Search_Auctions 09.8_pp_717_736_Computational_Evolutionary_Game_Theory 10.0_pp_737_754_Index In recent years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. Algorithmic Game Theory, first published in 2007, develops the central ideas and results of this exciting area in a clear and succinct manner. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on important game theory applications such as incentives and pricing, cost sharing, information markets and cryptography and security. This definitive work will set the tone of research for the next few years and beyond. Students, researchers, and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application.