Algorithmic Game Theory

by Edited by Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani

• ISBN13: 9780521872829
• ISBN10: 0521872820
• Format: Hardcover
• Copyright: 2007-09-24
• Publisher: Cambridge University Press

Summary

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.

Table of Contents

Introduction

Computing in Games

Basic solution concepts and computational issues

Algorithms for equilibria

Equilibrium computation for games in strategic and extensive form

Learning, regret minimization and correlated equilibria

Graphical games

Cryptography and game theory

Combinatorial algorithms for market equilibria Vijay V. Vazirani

Computation of market equilibria by convex programming

Algorithmic Mechanism Design

Introduction to mechanism design (for computer scientists)

Mechanism design without money

Combinatorial auctions

Computationally efficient approximation mechanisms

Profit maximization in mechanism design

Distributed algorithmic mechanism design

Cost sharing

On-line mechanisms

Quantifying the Inefficiency of Equilibria

Introduction to the inefficiency of equillibria

Routing games

Inefficiency of equilibria in network formation games

Selfish load-balancing

Efficiency loss and the design of scalable resource allocation mechanisms

Additional Topics

Incentives and pricing in communication networks

Incentives in peer-to-peer systems

Cascading behavior in networks: algorithmic and economic issues

Incentives and information security

Computational aspects of information markets

Manipulation-resistant reputation systems

Sponsored search auctions

Algorithmic issues in evolutionary game theory

Table of Contents provided by Publisher. All Rights Reserved.