Loading...
Please wait, while we are loading the content...
Similar Documents
Algorithmic Game Theory: The Price of Anarchy and the Design of Scalable Resource Allocation Mechanisms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Johari, Ramesh |
| Copyright Year | 2007 |
| Abstract | In this chapter, we study the allocation of a single infinitely divisible resource among multiple competing users. While we aim for efficient allocation of the resource, the task is complicated by the fact that users’ utility functions are typically unknown to the resource manager. We study the design of resource allocation mechanisms that are approximately efficient (i.e., have a low price of anarchy), with low communication requirements (i.e., the strategy spaces of users are low dimensional). Our main results concern the proportional allocation mechanism, for which a tight bound on the price of anarchy can be provided. We also show that in a wide range of market mechanisms that use a single market-clearing price, the proportional allocation mechanism minimizes the price of anarchy. Finally, we relax the assumption of a single market-clearing price, and show that by extending the class of Vickrey–Clarke–Groves mechanisms all Nash equilibria can be guaranteed to be fully efficient. |
| File Format | PDF HTM / HTML |
| DOI | 10.1017/CBO9780511800481.023 |
| Alternate Webpage(s) | http://ebook.nscpolteksby.ac.id/files/Ebook/Computer%20Engineering/Algorithmic%20Game%20Theory%20(2007)/22.%20Chapter%2021%20-%20The%20Price%20of%20Anarchy%20and%20the%20Design%20of%20Scalable%20Resource%20Allocation%20Mechanisms.pdf |
| Alternate Webpage(s) | https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithmic%20Game%20Theory%20(2007)/22.%20Chapter%2021%20-%20The%20Price%20of%20Anarchy%20and%20the%20Design%20of%20Scalable%20Resource%20Allocation%20Mechanisms.pdf |
| Alternate Webpage(s) | https://doi.org/10.1017/CBO9780511800481.023 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
