Efficiency of scalar-parameterized mechanisms
We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to mechanisms that satisfy certain scalability constraints motivated by large scale communi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences
2010
|
| Online Access: | http://hdl.handle.net/1721.1/51697 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1811086390428958720 |
|---|---|
| author | Johari, Ramesh Tsitsiklis, John N. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Johari, Ramesh Tsitsiklis, John N. |
| author_sort | Johari, Ramesh |
| collection | MIT |
| description | We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple
competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to
mechanisms that satisfy certain scalability constraints motivated by large scale communication networks;
in particular, we restrict attention to mechanisms where users are restricted to one-dimensional strategy
spaces. We first study the efficiency guarantees possible when the mechanism is not allowed to price differen-
tiate. We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the
maximum possible utility), and show that the proportional allocation mechanism of Kelly (1997) minimizes
the efficiency loss when users are price anticipating. We then turn our attention to mechanisms where price
differentiation is permitted; using an adaptation of the Vickrey-Clarke-Groves class of mechanisms, we con-
struct a class of mechanisms with one-dimensional strategy spaces where Nash equilibria are fully efficient.
These mechanisms are shown to be fully efficient even in general convex environments, under reasonable
assumptions. Our results highlight a fundamental insight in mechanism design: when the pricing flexibility
available to the mechanism designer is limited, restricting the strategic flexibility of bidders may actually
improve the efficiency guarantee. |
| first_indexed | 2024-09-23T13:25:14Z |
| format | Article |
| id | mit-1721.1/51697 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:25:14Z |
| publishDate | 2010 |
| publisher | Institute for Operations Research and the Management Sciences |
| record_format | dspace |
| spelling | mit-1721.1/516972022-10-01T15:10:19Z Efficiency of scalar-parameterized mechanisms Johari, Ramesh Tsitsiklis, John N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Tsitsiklis, John N. Tsitsiklis, John N. We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to mechanisms that satisfy certain scalability constraints motivated by large scale communication networks; in particular, we restrict attention to mechanisms where users are restricted to one-dimensional strategy spaces. We first study the efficiency guarantees possible when the mechanism is not allowed to price differen- tiate. We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the maximum possible utility), and show that the proportional allocation mechanism of Kelly (1997) minimizes the efficiency loss when users are price anticipating. We then turn our attention to mechanisms where price differentiation is permitted; using an adaptation of the Vickrey-Clarke-Groves class of mechanisms, we con- struct a class of mechanisms with one-dimensional strategy spaces where Nash equilibria are fully efficient. These mechanisms are shown to be fully efficient even in general convex environments, under reasonable assumptions. Our results highlight a fundamental insight in mechanism design: when the pricing flexibility available to the mechanism designer is limited, restricting the strategic flexibility of bidders may actually improve the efficiency guarantee. National Science Foundation Army Research Office DARPA - Next Generation Internet Initiative National Science Foundation Graduate Research Fellowship 2010-02-11T14:05:11Z 2010-02-11T14:05:11Z 2008-07 2008-06 Article http://purl.org/eprint/type/SubmittedJournalArticle 0030-364X 1526-5463 http://hdl.handle.net/1721.1/51697 Johari, Ramesh, and John N. Tsitsiklis. “Efficiency of Scalar-Parameterized Mechanisms.” Operations Research 57.4 (2009): 823-839. https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1287/opre.1080.0638 Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences John Tsitsiklis |
| spellingShingle | Johari, Ramesh Tsitsiklis, John N. Efficiency of scalar-parameterized mechanisms |
| title | Efficiency of scalar-parameterized mechanisms |
| title_full | Efficiency of scalar-parameterized mechanisms |
| title_fullStr | Efficiency of scalar-parameterized mechanisms |
| title_full_unstemmed | Efficiency of scalar-parameterized mechanisms |
| title_short | Efficiency of scalar-parameterized mechanisms |
| title_sort | efficiency of scalar parameterized mechanisms |
| url | http://hdl.handle.net/1721.1/51697 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT johariramesh efficiencyofscalarparameterizedmechanisms AT tsitsiklisjohnn efficiencyofscalarparameterizedmechanisms |