Selfish Routing and the Price of Anarchy (Hardcover)
暫譯: 自私路由與無政府狀態的代價 (精裝版)

Tim Roughgarden

Selfish Routing and the Price of Anarchy (Hardcover)
  • 出版商: MIT
  • 出版日期: 2005-05-01
  • 售價: $1,800
  • 貴賓價: 9.5 折 $1,710
  • 語言: 英文
  • 頁數: 240
  • 裝訂: Hardcover
  • ISBN: 0262182432
  • ISBN-13: 9780262182430

    • 海外代購書籍(需單獨結帳)

買這商品的人也買了...

商品描述

Description:

Most of us prefer to commute by the shortest route available, without taking into account the traffic congestion that we cause for others. Many networks, including computer networks, suffer from some type of this "selfish routing." In Selfish Routing and the Price of Anarchy, Tim Roughgarden studies the loss of social welfare caused by selfish, uncoordinated behavior in networks. He quantifies the price of anarchy -- the worst-possible loss of social welfare from selfish routing -- and also discusses several methods for improving the price of anarchy with centralized control.

Roughgarden begins with a relatively nontechnical introduction to selfish routing, describing two important examples that motivate the problems that follow. The first, Pigou's Example, demonstrates that selfish behavior need not generate a socially optimal outcome. The second, the counterintiuitve Braess's Paradox, shows that network improvements can degrade network performance. He then develops techniques for quantifying the price of anarchy (with Pigou's Example playing a central role). Next, he analyzes Braess's Paradox and the computational complexity of detecting it algorithmically, and he describes Stackelberg routing, which improves the price of anarchy using a modest degree of central control. Finally, he defines several open problems that may inspire further research. Roughgarden's work will be of interest not only to researchers and graduate students in theoretical computer science and optimization but also to other computer scientists, as well as to economists, electrical engineers, and mathematicians.

Tim Roughgarden is a postdoctoral researcher at the University of California, Berkeley and will be Assistant Professor in the Computer Science Department at Stanford University beginning in September 2004.

 

 

 

Table of Contents:

Preface vii
I INTRODUCTION AND PRELIMINARIES 1
1 Introduction 3
2 Preliminaries 17
II BOUNDING THE PRICE OF ANARCHY 49
3 How Bad Is Selfish Routing? 51
4 Extensions 85
III COPING WITH SELFISHNESS 119
5 Bounding and Detecting Braess's Paradox 121
6 Stackelberg Routing 151
References 169
Index 191

商品描述(中文翻譯)

**描述：**
大多數人都喜歡選擇最短的通勤路線，而不考慮我們對他人造成的交通擁堵。許多網路，包括計算機網路，都遭受某種形式的「自私路由」問題。在《Selfish Routing and the Price of Anarchy》中，Tim Roughgarden 研究了自私且未協調的行為對網路社會福利造成的損失。他量化了無政府狀態的代價——自私路由所造成的最糟糕社會福利損失，並討論了幾種通過集中控制來改善無政府狀態代價的方法。

Roughgarden 以相對非技術性的方式介紹自私路由，描述了兩個重要的例子，這些例子激發了後續的問題。第一個是 Pigou 的例子，展示了自私行為不一定會產生社會最優結果。第二個是反直覺的 Braess 悖論，顯示網路改善可能會降低網路性能。接著，他發展了量化無政府狀態代價的技術（Pigou 的例子在其中扮演了核心角色）。然後，他分析了 Braess 悖論及其算法檢測的計算複雜性，並描述了 Stackelberg 路由，這種方法利用適度的中央控制來改善無政府狀態的代價。最後，他定義了幾個可能激發進一步研究的開放問題。Roughgarden 的研究不僅對理論計算機科學和優化領域的研究人員和研究生感興趣，對其他計算機科學家、經濟學家、電機工程師和數學家也同樣重要。

Tim Roughgarden 是加州大學伯克利分校的博士後研究員，並將於 2004 年 9 月開始擔任史丹佛大學計算機科學系的助理教授。

**目錄：**
- 前言 vii
- I 引言與初步知識 1
- 1 引言 3
- 2 初步知識 17
- II 界定無政府狀態的代價 49
- 3 自私路由有多糟？ 51
- 4 擴展 85
- III 應對自私行為 119
- 5 界定與檢測 Braess 悖論 121
- 6 Stackelberg 路由 151
- 參考文獻 169
- 索引 191

類似商品