Optimal Utility Design in Convex Distributed Welfare Games
| Autor: | Jason R. Marden, Emily Jensen |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Linear programming Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Shapley value symbols.namesake 020901 industrial engineering & automation 010201 computation theory & mathematics Nash equilibrium Price of anarchy symbols Resource allocation Resource management Relaxation (approximation) Price of stability |
| Zdroj: | ACC |
| DOI: | 10.23919/acc.2018.8431131 |
| Popis: | This paper focuses on the design of local agent objective functions for resource allocation problems with separable, convex, and increasing system level objective functions. We employ two well-known measures to characterize the quality of local utility functions: Price of Anarchy (PoA) and Price of Stability (PoS), which provide a measure the best and worst Nash equilibrium, respectively. Our main results characterize the tradeoff between optimizing the PoA and optimizing the PoS; we show that if optimal PoA (resp. PoS) is achieved, there is a limitation on the achievable PoS (resp. PoA). Further, we show that the Shapley value objective function is the unique rule which optimizes PoA followed by PoS, and the marginal contribution rule is the unique rule which optimizes PoS followed by PoA. Lastly, we show that relaxation in the objective of optimizing PoA impacts the attainable PoS guarantees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|