Fault tolerant mechanism design for general task allocation
File(s)
Accepted version
Author(s)
Zhao, D
Ramchurn, S
Jennings, N
Type
Conference Paper
Abstract
We study a general task allocation problem, involving multiple agents that collaboratively accomplish tasks and where agents may fail to successfully complete the tasks assigned to them (known as execution uncertainty). The goal is to choose an allocation that maximises social welfare while taking their execution uncertainty into account (i.e., fault tolerant). To achieve this, we show that the post-execution verification (PEV)-based mechanism presented by Porter et al. (2008) is applicable if and only if agents’ valuations are risk-neutral (i.e., the solution is almost universal). We then consider a more advanced setting where an agent’s execution uncertainty is not completely predictable by the agent alone but aggregated from all agents’ private opinions (known as trust). We show that PEV-based mechanism with trust is still applicable if and only if the trust aggregation is multilinear. Given this characterisation, we further demonstrate how this mechanism can be successfully applied in a real-world setting. Finally, we draw the parallels between our results and the literature of efficient mechanism design with general interdependent valuations.
Date Issued
2016-05
Date Acceptance
2016-01-01
Citation
2016
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Start Page
323
End Page
331
Copyright Statement
© 2016 by the International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). This paper is embargoed until published.
Source
The 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016)
Publication Status
Unpublished
Start Date
2016-05-09
Finish Date
2016-05-13
Coverage Spatial
Singapore