ESSENTIALS OF GAME THEORY
Synthesis Lectures on Artificial Intelligence and Machine Learning
Editors
Ronald J. Brachman, Yahoo Research
Tom Dietterich, Oregon State University
Intelligent Autonomous Robotics
Peter Stone
2007
A Concise Introduction to Multiagent Systems and Distributed Artificial Intelligence
Nikos Vlassis
2007
Essentials of Game Theory: A Concise, Multidisciplinary Introduction
Kevin Leyton-Brown and Yoav Shoham
2008
Copyright 2008 by Morgan & Claypool
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any meanselectronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews, without the prior permission of the publisher.
Essentials of Game Theory
Kevin Leyton-Brown and Yoav Shoham
www.morganclaypool.com
ISBN: 9781598295931 paper
ISBN: 9781598295948 ebook
DOI: 10.2200/S00108ED1V01Y200802AIM003
A Publication in the Morgan & Claypool Publishers series
SYNTHESIS LECTURES ON ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING #3
Lecture #3
Series Editor: Ronald J. Brachman, Yahoo! Research and Tom Dietterich, Oregon State University
Library of Congress Cataloging-in-Publication Data
Series ISSN: 1939-4608 print
Series ISSN: 1939-4616 electronic
ESSENTIALS OF GAME THEORY
A Concise, Multidisciplinary Introduction
Kevin Leyton-Brown
University of British Columbia, Vancouver, BC, Canada
http://cs.ubc.ca/~kevinlb
Yoav Shoham
Stanford University, Palo Alto, CA, USA
http://cs.stanford.edu/~shoham
ABSTRACT
Game theory is the mathematical study of interaction among independent, self-interested agents. The audience for game theory has grown dramatically in recent years, and now spans disciplines as diverse as political science, biology, psychology, economics, linguistics, sociology and computer scienceamong others. What has been missing is a relatively short introduction to the field covering the common basis that anyone with a professional interest in game theory is likely to require. Such a text would minimize notation, ruthlessly focus on essentials, and yet not sacrifice rigor. This Synthesis Lecture aims to fill this gap by providing a concise and accessible introduction to the field. It covers the main classes of games, their representations, and the main concepts used to analyze them.
This introduction is just what a growing multidisciplinary audience needs: it is concise, authoritative, up to date, and clear on the important conceptual issues.
Robert Stalnaker, MIT, Linguistics and Philosophy
I wish Id had a comprehensive, clear and rigorous introduction to the essentials of game theory in under one hundred pages when I was starting out.
David Parkes, Harvard University, Computer Science
Beside being concise and rigorous, Essentials of Game Theory is also quite comprehensive. It includes the formulations used in most applications in engineering and the social sciences, and illustrates the concepts with relevant examples.
Robert Wilson, Stanford University, Graduate School of Business
Best short introduction to game theory I have seen! I wish it was available when I started being interested in the field!
Silvio Micali, MIT, Computer Science
Although written by computer scientists, this book serves as a sophisticated introduction to the main concepts and results of game theory from which other scientists, including social scientists, can greatly benefit. In eighty pages, Essentials of Game Theory formally defines key concepts, illustrated with apt examples, in both cooperative and noncooperative game theory.
Steven Brams, New York University, Political Science
This book will appeal to readers who do not necessarily hail from economics, and who want a quick grasp of the fascinating field of game theory. The main categories of games are introduced in a lucid way and the relevant concepts are clearly defined, with the underlying intuitions always provided.
Krzysztof Apt, University of Amsterdam, Institute for Logic, Language and Computation
To a large extent, modern behavioral ecology and behavioral economics are studied in the framework of game theory. Students and faculty alike will find this concise, rigorous and clear introduction to the main ideas in game theory immensely valuable.
Marcus Feldman, Stanford University, Biology
This unique book is today the best short technical introduction to game theory. Accessible to a broad audience, it will prove invaluable in artificial intelligence, more generally in computer science, and indeed beyond.
Moshe Tennenholtz, Technion, Industrial Engineering and Management
Excerpted from a much-anticipated, cross-disciplinary book on multiagent systems, this terse, incisive and transparent book is the ideal introduction to the key concepts and methods of game theory for researchers in several fields, including artificial intelligence, networking, and algorithms.
Vijay Vazirani, Georgia Institute of Technology, Computer Science
The authors admirably achieve their aim of providing a scientist or engineer with the essentials of game theory in a text that is rigorous, readable and concise.
Frank Kelly, University of Cambridge, Statistical Laboratory
KEYWORDS
Game theory, multiagent systems, competition, coordination, Prisoners Dilemma: zero-sum games, Nash equilibrium, extensive form, repeated games, stochastic games, Bayesian games, coalitional games
To my parents Anne and David Leyton-Brown KLB
To my parents Leila and Havis Stein YS
with much love and thanks for all that you have taught us
Contents
Credits and Acknowledgments
We thank the many colleagues, including past and present graduate students, who made substantial contributions. Sam Ieong deserves special mention: (coalitional games) is based entirely on writing by him, and he was also closely involved in the editing of this chapter. Other colleagues either supplied material or provided useful council. These include Felix Brandt, Vince Conitzer, Yossi Feinberg, Jeff Fletcher, Nando de Freitas, Ben Galin, Geoff Gordon, Teg Grenager, Albert Xin Jiang, David Poole, Peter Stone, David Thompson, Bob Wilson, and Erik Zawadzki. We also thank David Thompson for his assistance with the production of this book, particularly with the index and bibliography.
Of course, none of our colleagues are to be held accountable for any errors or other shortcomings. We claim sole credit for those.
We thank Morgan & Claypool, and particularly our editor Mike Morgan, for publishing Essentials of Game Theory, and indeed for suggesting the project in the first place. This booklet weaves together excerpts from our much longer book, Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations, published by Cambridge University Press. We thank CUP, and particularly our editor Lauren Cowles, for not only agreeing to but indeed supporting the publication of this booklet. We are fortunate to be working with such stellar, forward-looking editors and publishers.
A great many additional colleagues contributed to the full Multiagent Systems book, and we thank them there. Since the project has been in the works in one way or another since 2001, it is possibleindeed, likelythat we have failed to thank some people. We apologize deeply in advance.
Next page