Multi-Unit Auctions for Allocating Chance-Constrained Resources

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.

Authors

• Anna Gautier University of Oxford Oxford Robotics Institute
• Bruno Lacerda Stateful Robotics
• Nick Hawes University of Oxford
• Michael Wooldridge University of Oxford

Keywords

• GTEP: Auctions and Market-Based Systems
• MAS: Multiagent Planning
• MAS: Multiagent Systems under Uncertainty
• PRS: Planning under Uncertainty
• PRS: Planning with Markov Models (MDPs, POMDPs)