Efficient Multi-Agent Delegated Search
Preprint
Abstract
Consider a principal who wants to search through a space of stochastic solutions for one maximizing their utility. If the principal cannot conduct this search on their own, they may instead delegate this problem to an agent with distinct and potentially misaligned utilities. This is called delegated search, and the principal in such problems faces a mechanism design problem in which they must incentivize the agent to find and propose a solution maximizing the principal's expected utility. Following prior work in this area, we consider mechanisms without payments and aim to achieve a multiplicative approximation of the principal's utility when they solve the problem without delegation. In this work, we investigate a natural and recently studied generalization of this model to multiple agents and find nearly tight bounds on the principal's approximation as the number of agents increases. As one might expect, this approximation approaches 1 with increasing numbers of agents, but, somewhat surprisingly, we show that this is largely not due to direct competition among agents.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Optimal contingent delegationJournal of Economic Theory, 2022
- An economic view of prophet inequalitiesACM SIGecom Exchanges, 2017
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution SchemesSIAM Journal on Computing, 2014
- A Model of Delegated Project ChoiceEconometrica, 2010
- Optimal DelegationReview of Economic Studies, 2008
- Semiamarts and finite valuesBulletin of the American Mathematical Society, 1977