The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs
Optimizing decision quality in large scale, distributed, resource allocation problems requires selecting the appropriate decision network architecture. Such resource allocation problems occur in distributed sensor networks, military air campaign planning, logistics networks, energy grids, etc. Optim...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Scitepress
2021
|
| Online Access: | https://hdl.handle.net/1721.1/128947 |
| _version_ | 1826216183390535680 |
|---|---|
| author | Guo, Jinhong Karlovitz, Alexander Jaillet, Patrick Hofmann, Martin |
| 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 Guo, Jinhong Karlovitz, Alexander Jaillet, Patrick Hofmann, Martin |
| author_sort | Guo, Jinhong |
| collection | MIT |
| description | Optimizing decision quality in large scale, distributed, resource allocation problems requires selecting the appropriate decision network architecture. Such resource allocation problems occur in distributed sensor networks, military air campaign planning, logistics networks, energy grids, etc. Optimal solutions require that demand, resource status, and allocation decisions are shared via messaging between geographically distributed, independent decision nodes. Jamming of wireless links, cyber attacks against the network, or infrastructure damage from natural disasters interfere with messaging and, thus, the quality of the allocation decisions. Our contribution described in the paper is a decentralized resource allocation architecture and algorithm that is robust to significant message loss and to uncertain demand arrival, and provides fine-grained, many-to-many combinatorial task allocation. Most importantly, it enables a conscious choice of the best level of decentralization under the expected degree of communications denial and quantifies the benefits of approximating status of peer nodes using proxy agents during temporary communications loss. |
| first_indexed | 2024-09-23T16:43:36Z |
| format | Article |
| id | mit-1721.1/128947 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:43:36Z |
| publishDate | 2021 |
| publisher | Scitepress |
| record_format | dspace |
| spelling | mit-1721.1/1289472022-10-03T07:52:23Z The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs Guo, Jinhong Karlovitz, Alexander Jaillet, Patrick Hofmann, Martin Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Optimizing decision quality in large scale, distributed, resource allocation problems requires selecting the appropriate decision network architecture. Such resource allocation problems occur in distributed sensor networks, military air campaign planning, logistics networks, energy grids, etc. Optimal solutions require that demand, resource status, and allocation decisions are shared via messaging between geographically distributed, independent decision nodes. Jamming of wireless links, cyber attacks against the network, or infrastructure damage from natural disasters interfere with messaging and, thus, the quality of the allocation decisions. Our contribution described in the paper is a decentralized resource allocation architecture and algorithm that is robust to significant message loss and to uncertain demand arrival, and provides fine-grained, many-to-many combinatorial task allocation. Most importantly, it enables a conscious choice of the best level of decentralization under the expected degree of communications denial and quantifies the benefits of approximating status of peer nodes using proxy agents during temporary communications loss. ONR (Contract N00014-12-C-0162) 2021-01-04T21:07:16Z 2021-01-04T21:07:16Z 2019-02 2020-12-21T18:25:44Z Article http://purl.org/eprint/type/ConferencePaper 9789897583506 https://hdl.handle.net/1721.1/128947 Guo, Jinhong et al. "The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs." Proceedings of the 11th International Conference on Agents and Artificial Intelligence, February 2019, Prague, Czech Republic, Scitepress, 2019. © 2019 Scitepress en http://dx.doi.org/10.5220/0007345701460153 Proceedings of the 11th International Conference on Agents and Artificial Intelligence Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Scitepress SciTePress |
| spellingShingle | Guo, Jinhong Karlovitz, Alexander Jaillet, Patrick Hofmann, Martin The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title | The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title_full | The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title_fullStr | The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title_full_unstemmed | The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title_short | The Price of Anarchy: Centralized versus Distributed Resource Allocation Trade-offs |
| title_sort | price of anarchy centralized versus distributed resource allocation trade offs |
| url | https://hdl.handle.net/1721.1/128947 |
| work_keys_str_mv | AT guojinhong thepriceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT karlovitzalexander thepriceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT jailletpatrick thepriceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT hofmannmartin thepriceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT guojinhong priceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT karlovitzalexander priceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT jailletpatrick priceofanarchycentralizedversusdistributedresourceallocationtradeoffs AT hofmannmartin priceofanarchycentralizedversusdistributedresourceallocationtradeoffs |