Multi-Unit Auctions for Allocating Chance-Constrained Resources
Anna Gautier, Bruno Lacerda, Nick Hawes, Michael Wooldridge
Abstract
Sharing scarce resources is a key challenge in multi-agent interaction, especially when individual agents are uncertain about their future consumption. We present a new auction mechanism for preallocating multi-unit resources among agents, while limiting the chance of resource violations. By planning for a chance constraint, we strike a balance between worst-case approaches, which under-utilise resources, and expected-case approaches, which lack formal guarantees. We also present an algorithm that allows agents to generate bids via multi-objective reasoning, which are then submitted to the auction. We then discuss how the auction can be extended to non-cooperative scenarios. Finally, we demonstrate empirically that our auction outperforms state-of-the-art techniques for chance-constrained multi-agent resource allocation in complex settings with up to hundreds of agents.
BibTeX
@article{Gautier_Lacerda_Hawes_Wooldridge_2023, title={Multi-Unit Auctions for Allocating Chance-Constrained Resources}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26366}, DOI={10.1609/aaai.v37i10.26366}, abstractNote={Sharing scarce resources is a key challenge in multi-agent interaction, especially when individual agents are uncertain about their future consumption. We present a new auction mechanism for preallocating multi-unit resources among agents, while limiting the chance of resource violations. By planning for a chance constraint, we strike a balance between worst-case approaches, which under-utilise resources, and expected-case approaches, which lack formal guarantees. We also present an algorithm that allows agents to generate bids via multi-objective reasoning, which are then submitted to the auction. We then discuss how the auction can be extended to non-cooperative scenarios. Finally, we demonstrate empirically that our auction outperforms state-of-the-art techniques for chance-constrained multi-agent resource allocation in complex settings with up to hundreds of agents.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Gautier, Anna and Lacerda, Bruno and Hawes, Nick and Wooldridge, Michael}, year={2023}, month={Jun.}, pages={11560-11568} }