Online Multi-Agent Contracts
TL;DR
An online variant of the multi-agent contract model that reveals a surprising separation between submodular and XOS rewards: unlike related settings such as offline contract design and prophet inequalities, where constant-factor guarantees for submodular rewards extend to XOS rewards, the online contract setting separates the two classes.
Abstract
We introduce and study an online variant of the multi-agent contract model. In our model, agents arrive one-by-one and are active with a certain probability. Upon arrival of agent $i$, the principal offers a linear contract $\alpha_i$, specifying the fraction of the principal's reward transferred to agent $i$. Agents can either exert effort or not, incurring a cost if they do. The set of agents that exert effort determines the principal's expected reward through a reward function $f$. After all agents have arrived, the agents form a (pure) Nash equilibrium. As our main result we design an $O(1)$-competitive policy for submodular rewards, compared to the offline optimum. We also show that this result is tight in two ways. First, if we require that agents make decisions on the spot, then for submodular rewards any policy is $\Omega((\log n)/(\log \log n)^2)$-competitive. Second, for the broader class of XOS (a.k.a., fractionally subadditive) rewards, any online policy is $\Omega((\log \log n)/(\log \log \log n))$-competitive. The latter result reveals a surprising separation between submodular and XOS rewards: unlike related settings such as offline contract design and prophet inequalities, where constant-factor guarantees for submodular rewards extend to XOS rewards, the online contract setting separates the two classes.