没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
P1: SBT
FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6
Algorithmic Game Theory
Over the last few years, there has been explosive growth in the research done at the in-
terface of computer science, game theory, and economic theory, largely motivated by the
emergence of the Internet. Algorithmic Game Theory develops the central ideas and results
of this new and exciting area.
More than 40 of the top researchers in t his field have written chapters whose topics
range from the foundations to the state of the art. This book contains an extensive treatment
of algorithms for equilibria in games and markets, computational auctions and mechanism
design, and the “price of anarchy,” as well as applications in networks, peer-to-peer systems,
security, information markets, and more.
This book will be of interest to students, researchers, and practitioners in theoretical
computer science, economics, networking, artificial intelligence, operations research, and
discrete mathematics.
Noam Nisan is a Professor in the Department of Computer Science at The Hebrew Univer-
sity of Jerusalem. His other books include Communication Complexity.
Tim Roughgarden is an Assistant Professor in the Department of Computer Science at
Stanford University. His other books include Selfish Routing and the Price of Anarchy.
´
Eva Tardos is a Professor in the Department of Computer Science at Cornell University.
Her other books include Algorithm Design.
Vijay V. Vazirani is a Professor in the College of Computing at the Georgia Institute of
Technology. His other books include Approximation Algorithms.
i
P1: SBT
FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6
ii
P1: SBT
FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6
Algorithmic Game Theory
Edited by
Noam Nisan
Hebrew University of Jerusalem
Tim Roughgarden
Stanford University
´
Eva Tardos
Cornell University
Vijay V. Vazirani
Georgia Institute of Technology
iii
P1: SBT
FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6
cambridge university press
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S
˜
ao Paulo, Delhi
Cambridge University Press
32 Avenue of the Americas, New York, NY 10013-2473, USA
www.cambridge.org
Information on this title: www.cambridge.org/9780521872829
C
Noam Nisan, Tim Roughgarden,
´
Eva Tardos, Vijay V. Vazirani 2007
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without
the written permission of Cambridge University Press.
First published 2007
Printed in the United States of America
A catalog record for this book is available from the British Library.
Library of Congress Cataloging in Publication Data
Algorithmic game theory / edited by Noam Nisan ...[et al.]; foreword
by Christos Papadimitriou.
p. cm.
Includes index.
ISBN-13: 978-0-521-87282-9 (hardback)
ISBN-10: 0-521-87282-0 (hardback)
1. Game theory. 2. Algorithms. I. Nisan, Noam. II. Title.
QA269.A43 2007
519.3–dc22 2007014231
ISBN 978-0-521-87282-9 hardback
Cambridge University Press has no responsibility for
the persistence or accuracy of URLS for external or
third-party Internet Web sites referred to in this publication
and does not guarantee that any content on such
Web sites is, or will remain, accurate or appropriate.
i
P1: SBT
FM-main CUNY1061-Nisan 0 521 87282 0 August 3, 2007 12:6
Contents
Foreword page xiii
Preface xvii
Contributors xix
I Computing in Games
1 Basic Solution Concepts and Computational Issues 3
´
Eva Tardos and Vijay V. Vazirani
1.1 Games, Old and New
3
1.2 Games, Strategies, Costs, and Payoffs 9
1.3 Basic Solution Concepts 10
1.4 Finding Equilibria and Learning in Games 16
1.5 Refinement of Nash: Games with Turns and Subgame Perfect Equilibrium 18
1.6 Nash Equilibrium without Full Information: Bayesian Games 20
1.7 Cooperative Games 20
1.8 Markets and Their Algorithmic Issues 22
Acknowledgments 26
Bibliography 26
Exercises 26
2 The Complexity of Finding Nash Equilibria 29
Christos H. Papadimitriou
2.1 Introduction
29
2.2 Is the Nash Equilibrium Problem NP-Complete? 31
2.3 The Lemke–Howson Algorithm 33
2.4 The Class PPAD 36
2.5 Succinct Representations of Games 39
2.6 The Reduction 41
2.7 Correlated Equilibria 45
2.8 Concluding Remarks 49
Acknowledgment 50
Bibliography 50
v
剩余774页未读,继续阅读
资源评论
- lemonbirdy2014-09-28帮我同学下的,不错
cpcs
- 粉丝: 727
- 资源: 18
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功