1 Introduction↩︎

The creator economy constitutes one of the workhorses of the burgeoning digital ecosystem, with its value projected to exceed half a trillion dollars within the next few years [1]. Platforms such as YouTube and Spotify derive much of their value from content created by independent artists, and therefore invest considerable resources to encourage the production of high-quality and diverse content, thereby stimulating user engagement and attracting new users. The same design problem arises in many other digital domains, where platforms may seek to incentivize users or firms to share valuable datasets, contribute computational resources, or participate in federated learning protocols (2.4).

Taken together, these applications bring to the fore a central incentive-design problem: how should a budget be distributed so as to encourage valuable participation by external contributors? In each of these highly decentralized settings, the system designer derives value from the collective set of contributions, but participation cannot be mandated [2], [3]. The challenge is to design payments that induce voluntary participation by a subset of contributors that optimizes system utility, subject to the budget constraint. Moreover, contributors invest considerable time, capital, and other resources when they decide to participate, thereby incurring a private cost. Since the platform cannot force participation, each contributor independently decides whether to opt in or out. In particular, a contributor will be inclined to participate only if the compensation offered by the platform outweighs the private cost of opting in.

At the same time, mechanisms that rely on complex elicitation of private information or computationally intractable primitives—such as VCG-type schemes—are often impractical at scale, while highly discriminatory payment rules may lead to perceptions of unfairness and discourage participation. There is, therefore, an imperative to design payment rules that are anonymous—equal contributors are treated equally—and cost oblivious, in the sense that payments are determined solely by observable measures of utility rather than reported costs.

A natural assumption in this setting is that system utility exhibits diminishing marginal returns: the addition of a new contributor can bring considerable value to a nascent platform, but provides less marginal benefit to a platform already saturated with similar content or data. As a result, the platform’s objective is naturally modeled as a monotone submodular function. If the platform had full knowledge of contributors’ private costs, the problem would reduce to a standard algorithmic problem—namely, submodular maximization subject to a budget constraint. In practice, however, these costs are private and participation decisions are decentralized. The platform must therefore design payment rules that steer the resulting strategic system toward near-optimal equilibria.

1.1 Compensation design: our basic model↩︎

We introduce compensation design: the problem of designing computable payment rules that induce high-value decentralized participation under a fixed budget and private participation costs. We begin by describing the key aspects of our basic model, and then highlight the differences between our framework and other related models in game theory (1.1.1).

The central object in the paper is the following game. There is a set \(N\) of agents, a budget \(B\), and a normalized value function \(v:2^N\to\mathbb{R}_{\geq0}\) for the principal. Each agent \(i\) has a private cost \(c_i\) and chooses whether to opt in or opt out. Denote \(S \subseteq N\) the set of agents that opt in. A payment rule assigns nonnegative payments \(p_i(S)\) to the agents who opt in, subject to the budget constraint \(\sum_{i\in S}p_i(S)\le B\) for every realized set \(S\). Crucially, this payment depends only on the binary signals the principal receives from the agents, as well as the public value function. The payment rule induces a game among agents in which the utility of each agent \(i\) is \(p_i(S)-c_i\) if \(i\in S\), and zero if \(i\notin S\). The goal is to design a budget-feasible payment rule that is cost oblivious (i.e., it cannot depend on the private cost vector³) and maximizes the principal’s value. The benchmark is the full-information budgeted optimum \(\operatorname{OPT}:=\max_{S \subseteq N}\{v(S): \sum_{i \in S} c_i \le B\}\), which is the maximum value of any set whose total cost does not exceed the budget \(B\). Performance is measured through the price of anarchy (PoA) with respect to the equilibrium concept under consideration, mainly pure Nash equilibria and coarse correlated equilibria (2). A key parameter is the large-market ratio \(\lambda=\max_{i\in N} c_i/B\), which measures the highest individual cost as a fraction of the total budget [4], [5]. In the sequel, we also consider compensation design without the large-market assumption and the combinatorial setting where agents choose from a set of actions (1.2.3).

1.1.1 Comparison with existing models↩︎

Compensation design is closely related to several existing models. In what follows, we highlight the similarities and the key differences with those models, with a summary given in 1. A more detailed comparison with each of these lines of work is deferred to 2.

6pt

• Budget-feasible mechanism design [6] is a classic framework for optimizing allocation under private costs: a principal designs a procurement auction such that the agents first report their private costs, and the mechanism then determines an allocation (i.e., which agents are selected) and payments (i.e., how to pay the agents). The key difference is that mechanism design rests on bidding and centralized allocation, whereas compensation design promotes voluntary decentralized participation without bidding or centralized allocation.

• Compensation design is closely related to the problem of multi-agent contract design [7], where a principal aims to incentivize efforts from agents with voluntary participation. Contract design assumes that the principal knows agents’ costs but does not observe their actions. In contrast, compensation design assumes that the principal observes agents’ actions but must design cost-oblivious payment rules that perform well for any unknown cost vector. Compensation design is more natural in content platforms where agents’ actions (e.g., creating content) are publicly known, yet the costs (e.g., the time and monetary costs of creation) are private and not available to the platform.

• Compensation design can be understood through the general framework of utility design: agents control actions that determine the social welfare; the principal designs a welfare-sharing mechanism that assigns a utility function to each agent, with the goal of ensuring that agents’ local optimization behavior (i.e., the resulting pure Nash equilibria) leads to near-optimal global social welfare. There is a long line of work on utility design across various settings, including profit sharing [8]–[10], distributed welfare games [2], and distributed resource allocation [3]. However, the setting with private costs and a budget constraint has not been studied.

Taken together, there are fundamental differences between our setting and prior work in budgeted mechanism design, contract design, and utility design in the context of profit sharing. Our paper revolves around the following set of questions.

1. First, can one design efficient, anonymous, budget-feasible, and cost-oblivious payment rules that guarantee equilibrium existence and near-optimal price of anarchy bounds?

2. Second, how robust are such guarantees to weaker equilibrium concepts such as coarse correlated equilibria and to broader valuation classes beyond monotone submodular?

3. Third, what changes when each agent has a combinatorial action space rather than a single, binary participation decision?

1.2 Our results↩︎

The high-level quantitative picture painted by our results is summarized in ¿tbl:tab:valuation-action-bounds?. The remainder of this section describes our main results and the key ideas behind them.

1.2.1 Binary participation under monotone submodular valuations↩︎

Perhaps the most natural payment rule is based on the Shapley value [11], a cornerstone of cooperative game theory that is ubiquitous in practice and theory alike. In particular, let \(\phi_i(S)\) denote the Shapley value of agent \(i\) in the cooperative game obtained by restricting \(v\) to \(S\); that is, \[\label{eq:Shapleyval-intro} \phi_i(S) = \sum_{T\subseteq S\setminus\{i\}} \frac{|T|!(|S|-|T|-1)!}{|S|!} \bigl(v(T\cup\{i\})-v(T)\bigr).\tag{1}\] The Shapley payment rule is defined as \[\label{eq:intro-Shapley} p^{\textrm{Sh}}_i(S)= \begin{cases} B\dfrac{\phi_i(S)}{v(S)} & \text{if } i\in S\text{ and }v(S)>0,\\[1.5ex] 0 & \text{otherwise.} \end{cases}\tag{2}\] This payment rule is budget feasible, cost oblivious, and anonymous ([lem:shapley-efficiency-covering]). Surprisingly, we show that the induced game may admit no pure Nash equilibria.

6pt

This is unexpected because in many related utility design problems, the Shapley value always guarantees the existence of pure Nash equilibria [2], [3], [9], [12], [13]. This shows that our setting is fundamentally different. The argument revolves around quadratic submodular functions, in which case Shapley values 1 admit a more tractable characterization (2).

1.2.1.1 Marginal contribution rule.

We then consider a simpler payment rule, whereby the compensation to agent \(i\) under a realized set \(S\) is proportional to its marginal contribution: \[\label{eq:mc} p^{\textrm{mc}}_i(S) \mathrel{\vcenter{:}}= \begin{cases} B \frac{v(S) - v(S \setminus \{i\})}{v(S)} & \text{if } v(S) > 0,\\ 0 & \text{otherwise}. \end{cases}\tag{3}\] If \(v\) is monotone and submodular, marginals are nonnegative and their sum is at most \(v(S)\), so the rule is nonnegative and budget feasible (1). It is also cost oblivious and anonymous: it uses only the realized set and the value oracle, and treats agents with the same contribution symmetrically. Unlike the payment rule based on Shapley values, we show that this simple payment rule always guarantees the existence of a pure Nash equilibrium.

In fact, we establish a stronger property: the induced game is an ordinal potential game, so every sequence of strict better responses terminates (1). The argument establishes that the function \(\Phi(S) = v(S)\prod_{i\in S}(1-c_i/B)\) serves as a potential. An opt-in deviation is profitable exactly when the gain in value is large enough to offset the multiplicative penalty from the entrant’s cost; conversely, an opt-out deviation is profitable exactly when removing the agent increases the same potential.

1.2.1.2 Price of anarchy.

We then examine the price of anarchy (PoA)⁴ with respect to pure Nash equilibria of the game induced by the marginal contribution rule.

This result shows that the principal can guarantee a constant fraction of the optimal value without knowing anything about the agents’ costs. Moreover, this guarantee is tight, even for additive value functions ([thm:poa-pne,prop:tight]). We also remark that in the special case of additive value, the same PoA bound has been established for a non-truthful first-price procurement auction [14]. In comparison, we show that a simple marginal-contribution payment rule achieves the same guarantee in the more general monotone submodular value setting.

The proof of 3 is based on a relatively standard argument: if an agent \(i\) is absent from equilibrium, then its decision not to enter upper bounds the relative marginal gain \((v(S\cup\{i\})-v(S))/v(S)\) by \((c_i/B)/(1-c_i/B)\). Submodularity then allows summing these inequalities over agents present in an optimal set.

1.2.1.3 Optimality among cost-oblivious rules.

It turns out that the factor two is not merely an artifact of the marginal-contribution rule. We prove that no nonnegative, budget-feasible, and cost-oblivious rule can guarantee PoA with respect to pure Nash equilibria below \(2\), even for additive values, and even as \(\lambda \to 0\). The rule here may depend arbitrarily on agent identities and on the value function; the only information it cannot use is the private cost vector (6), for otherwise the problem becomes trivial from an information-theoretic standpoint.

The obstacle is information-theoretic: by cost obliviousness, if one alters only the cost vector, the induced payment rule must remain the same. We identify an instance where one cost vector forces the rule to admit a certain equilibrium while the other cost vector makes that same equilibrium far from optimal.

1.2.1.4 Beyond the large-market assumption.

So far, our results focus on the large-market assumption, i.e., \(c_i < B\). We also investigate the case in which an agent’s cost may be as large as or larger than the budget. We first show two negative results on deterministic payment rules: (1) there exists an instance where the PoA of any deterministic rule is \(+\infty\) (5); this lower bound is immediate: one agent with cost \(c_i = B\) may be indifferent between opting in and opting out, and opting out can lead to unbounded PoA. (2) Taking a step further, even under principal-favoring tie-breaking—whereby an indifferent agent chooses the action that maximizes the principal’s value—there exists an instance where any deterministic rule suffers a PoA of \(\Omega(\sqrt{n})\) (7). Both lower bounds hold even with additive values.

We then demonstrate the power of randomized payment rules, circumventing the aforementioned lower bounds for deterministic rules. Specifically, we show that a randomized rule that chooses between the marginal-contribution rule and a singleton-selection rule achieves constant PoA for monotone submodular values without the large-market assumption (8).

This randomization bypasses the deterministic lower bound in a way reminiscent of how the smart greedy algorithm achieves a constant-factor approximation for maximizing a submodular function subject to a budget constraint [15]. In fact, in the monotone submodular setting, the \(3\)-approximation obtained in 5 is better than the state-of-the-art (either randomized or deterministic) truthful budget-feasible mechanism that achieves a \(3.798\)-approximation [16].

1.2.1.5 Computation of equilibria.

The existence of pure Nash equilibria notwithstanding (2), we show that strict better-response dynamics can take exponentially many steps, even under an arbitrarily strong large-market condition. What is more, computing a pure Nash equilibrium of the marginal-contribution game is -complete [17] for monotone submodular value functions ([theorem:exp-br-lower,thm:pls-complete]). The reduction is from the usual local version of MaxCut: we encode the cut objective into a monotone submodular valuation so that unilateral participation changes simulate FLIP improvements. On the positive side, for additive valuations with integral values, better-response paths have pseudo-polynomial length \(O(W^2)\), where \(W\) is an upper bound on the total value of all agents (2).

1.2.1.6 Coarse correlated equilibria.

Motivated by the hardness of computing pure Nash equilibria and their non-existence under the Shapley payment rule, we examine the efficiency of coarse correlated equilibria (CCE) (2). CCE is a relaxed notion of Nash equilibrium that always exists and can be approached efficiently by no-regret learning algorithms [18], [19]. Without knowledge of the platform’s value function and other participants’ private costs, it is often impossible for an agent to compute and play a pure Nash equilibrium. However, the agents could employ simple, efficient learning algorithms that require only their own utilities, and the whole system would then converge to the set of CCE. It is thus important to understand the efficiency of outcomes produced by learning dynamics.

For monotone submodular values, we prove that every CCE of the marginal-contribution game attains an asymptotically tight large-market guarantee: the PoA of CCE is at most \(2/(1-2\lambda)\), and hence at most \(2+o_{\lambda}(1)\) when \(\lambda<1/2\) (10); the PoA of CCE is at most \(2 + 1/(1-\lambda)\) when \(\lambda < 1\) (9). These results in fact hold even for the game induced by the Shapley value (3), where pure Nash equilibria may not exist.

Notably, our argument does not go through the usual smoothness framework [20], which has been the main engine behind many PoA bounds for CCEs [21], [22].

1.2.1.7 Price of stability of CCEs.

A price of anarchy analysis revolves around worst-case equilibria. Another natural question concerns the best-case equilibrium, which is captured by the so-called price of stability [23]. This can be motivated when a platform can somehow steer agents toward more desirable equilibria.

In this context, we point out that CCEs exhibit an interesting phenomenon that has no analogue for pure equilibria: there can exist a CCE whose expected value is higher than the full-information budget-feasible optimum! In other words, the price of stability with respect to CCEs can be strictly smaller than one. In particular, we find an example where the price of stability is approaching \(1/2\), and this is in fact tight within the class of additive valuations (5.5).

Attaining a price of stability strictly below one may seem at first glance impossible because \(\operatorname{OPT}\) is the benchmark that an omniscient principal could achieve subject to the budget constraint. The explanation is that a CCE is a distribution over participation profiles, whereas budget feasibility constrains payments in each realized profile rather than the private cost of the selected agents. This means that a CCE may assign positive probability to coalitions whose realized cost exceeds \(B\); the CCE condition only forces cost feasibility in expectation. For additive values, this turns the comparison with \(\operatorname{OPT}\) into the standard fractional relaxation of knapsack, whose value can exceed the integral optimum by at most a factor of two.

Taken together, these results give a sharp interpretation of the marginal-contribution rule in the binary, monotone-submodular model. It is simple, anonymous, cost oblivious, budget feasible, admits pure Nash equilibria, and achieves the best possible PoA among cost-oblivious rules.

1.2.2 Beyond monotone submodular valuations↩︎

We next extend our scope beyond monotone submodular functions. For monotone XOS valuations, we prove an oracle lower bound: no payment designer using only polynomially many value queries can guarantee \(O(n^{1/2-\epsilon})\) price of anarchy with respect to CCEs for every XOS valuation, even with known unit costs and \(\lambda=1/\sqrt n\) (14). The construction is based on the standard information-theoretic lower bound for XOS maximization [24]. In particular, a polynomial-query payment designer cannot distinguish a base valuation, on which all approximate CCEs have low value by budget feasibility, from a planted valuation whose optimum is significantly higher. This shows that constant PoA guarantees for CCEs are impossible for oracle-efficient payment design over XOS valuations (14).

For non-monotone submodular objectives, the obstruction is different. First, if costs are allowed to be zero, then no nonnegative budget-feasible rule can guarantee finite PoA (8); this is driven by the fact that certain harmful agents will be inclined to participate to the detriment of the efficiency of the system. Moreover, even when each cost is strictly positive, we show that a broad class of payment rules inevitably incurs unbounded pure price of anarchy (15).

1.2.3 Combinatorial compensation design↩︎

Finally, we move beyond binary participation. This is motivated by many applications in which a single agent controls many possible actions. For example, a creator may produce any subset of videos, a data provider may contribute any subset of datasets, and a compute provider may allocate any subset of jobs. The resulting combinatorial compensation design problem is much harder than the binary-action case, since the payment rule now must incentivize high-quality contributions from an agent without knowing their private costs.

1.2.3.1 Single-agent combinatorial compensation design.

The combinatorial compensation design problem is already non-trivial in the single-agent setting. In this setting, there is one agent with \(m\) actions \(A\), where each action \(e \in A\) has cost \(c_e\). The challenge is that the principal needs to entice high effort with a carefully designed payment rule, while in the binary-action setting the principal could just pay the whole budget to the agent.

We establish that, even for additive value functions, any deterministic rule has price of anarchy at least \(\Omega(m)\) (16), and any randomized payment rule has price of anarchy at least \(\Omega(\log m)\) (19). The intuition for the randomized lower bound is that, given a value function, the payment rule must be fixed for any cost vector. Under uniform costs, the payment induces a demand curve for the number of actions the agent chooses. If the cost is \(t\), the offline optimum grows as \(1/t\), then it can be shown that any single rule is bound to miss some scale by a logarithmic factor.

On the positive side, we show that it is possible to achieve a matching PoA upper bound of \(O(\log m)\) using a simple randomized payment rule, even for subadditive value functions (17).

The key observation is that if the principal knew the optimal value \(\operatorname{OPT}\), there is a straightforward payment rule: pay the whole budget to the agent if the value is at least \(\operatorname{OPT}\). In view of this, we propose a simple randomized threshold-prize rule that samples a target value on a geometric scale. We show that it attains a PoA of \(O(\log m)\) even for monotone subadditive values—under the mild assumption that every action is individually feasible (17).⁵

1.2.3.2 Multi-agent combinatorial compensation design.

We then extend the model to multiple agents, which is the most general problem addressed in our paper. Here, there are \(n\) agents and each agent controls a block of actions. We denote by \(m\) the total number of actions. The principal has budget \(B > 0\) and aims to maximize a monotone value function over the union of chosen actions. When the value function is XOS, we have a lower bound of \(\Omega(n^{1/2-\epsilon})\) already in the multi-agent binary-action setting. Thus, we focus on the case of monotone submodular functions.

Since the multi-agent setting generalizes the single-agent setting, we know that it is impossible to beat \(\Omega(\log m)\). Whether it is possible to achieve a PoA of \(O(\log m)\) is not straightforward. The multi-agent setting is harder because the payment rule must not only incentivize high-quality actions within each agent’s action set, but also manage competition among multiple agents, all without knowing the private costs. Nevertheless, we show that it is still possible to achieve \(O(\log m)\) (20).

The randomized rule combines ideas from both the single-agent combinatorial and multi-agent binary-action settings. We first sample a target value on a geometric scale intended to approximate \(\operatorname{OPT}\). Given such a target value \(R\), the mechanism then uses the marginal contribution payment based on the capped payment potential \(F_R(S):= B \min \{\frac{v(S)}{R},1\}\). Here, the cap \(R\) incentivizes agents to contribute value at least \(R\), while the marginal contribution structure ensures sufficient competition among agents. We show that when \(R\) is a constant-factor lower estimate of \(\operatorname{OPT}\), this branch achieves constant PoA. Randomization over the geometric scale thus gives a PoA of \(O(\log m)\).

2 Further related work↩︎

This section elaborates on related lines of work.

2.1 Contract design↩︎

There is a burgeoning line of work on algorithmic contract theory [7], [25]–[33]. We refer to the excellent surveys of [34] and [35] for further pointers to that line of work.

In the multi-agent binary-action setting, compensation design is closest in spirit to the multi-agent contract problem [7], in which the principal seeks to incentivize a group of agents to exert effort. More specifically, there is a set of agents \(N\) with binary actions (exert effort or not exert effort) and each agent \(i\) incurs cost \(c_i\) for exerting effort and cost \(0\) otherwise. The principal has a monotone utility function \(f: 2^N \rightarrow [0,1]\) that maps the set of agents \(S \subseteq N\) who exert effort to a reward.⁶ The principal does not observe the agents’ actions but knows the costs \(c\) and incentivizes effort using a linear contract \(\boldsymbol{\alpha} \in \mathbb{R}^{N}_{\ge 0}\).⁷ If \(S\) is the set of agents that exert effort, then agent \(i\)’s expected payment is \(\alpha_i f(S)\). This induces a game among agents, where agent \(i\)’s utility is \(\alpha_i f(S) - c_i\) if \(i \in S\) and \(\alpha_i f(S)\) otherwise. Given \((N, f, c)\), the goal of the principal is to design a linear contract that, under a pure Nash equilibrium \(S\), maximizes her expected profit \((1 - \sum_{i=1}^n \alpha_i) f(S)\). The multi-agent contract model has also been studied in the budget-feasible setting with more general objectives such as social welfare and principal’s value [44], [45], under coarse correlated equilibria [46], and in the combinatorial-action setting [47].

The key differences between the multi-agent contract model and compensation design are:

• In the multi-agent contract model, the agents’ costs are provided as part of the input, and the principal can design a contract based on them. In compensation design, we assume that costs are private and that the payment rule is cost-oblivious.

• In the multi-agent contract model, it is assumed the principal cannot observe agents’ actions, whereas compensation design assumes the principal can. In content platforms such as YouTube and TikTok, we can observe whether each provider creates content.

Compensation design is natural for settings such as content platforms, where each provider’s action (e.g., creating content) is publicly observable, but the costs (e.g., the time and monetary costs of creation) are often private and not available to the platform.

2.2 Budget-feasible mechanism design and procurement auctions↩︎

Budget-feasible mechanism design and procurement auctions were first proposed by [6]. Here, a buyer with a budget aims to buy from multiple sellers whose items have private costs. Most existing mechanisms work as sealed-bid procurement auctions that first let sellers report their costs and then, based on the reports, decide an allocation and payment. Budget-feasible mechanism design has been extensively studied, focusing on approximation to the full-information optimal value [48]–[55] and competitive ratios of sequential posted-price mechanisms [56], [57]. This line of work also includes budget-feasible mechanisms for non-monotone submodular objectives [58]. There are also budget-feasible mechanisms based on clock auctions [16], [59]–[63] that have many appealing properties. With value oracle access, a randomized mechanism achieves a tight \(2\) approximation for additive values [52]; a recent work by [16] gives a deterministic clock auction with a \(3.798\) approximation for monotone submodular values, a randomized auction with \(9.742\) for non-monotone submodular values; both of these guarantees are state-of-the-art among all possibly randomized truthful budget-feasible mechanisms. In comparison, one of our contributions is to provide a simple alternative framework that achieves PoA of \(2+o_\lambda(1)\) or \(3\) (without the large-market assumption) in the monotone submodular value setting.

The underlying full-information problem of maximizing a monotone submodular function subject to a budget constraint is -hard, but its approximability is well understood: the best polynomial-time approximation factor is \(1-1/e\) [64]–[66].

More closely related to our work, [14] recently studied budget-feasible first-price (non-truthful) procurement auctions in the additive value setting and established equilibrium existence and constant PoA bounds for a greedy allocation rule under the large-market assumption. It is perhaps surprising that, using only payments, we show that compensation design achieves guarantees similar to those of a first-price procurement auction, even in the more general monotone submodular value setting and without the large-market assumption. A more recent work by [67] initiates the study of multidimensional budget-feasible mechanism design, similar to the combinatorial-action extension . They show that constant approximation to the full-information benchmark is impossible; they then consider a weaker benchmark and develop constant-approximation mechanisms. It is an interesting future direction to identify meaningful weaker benchmarks that enable constant approximation in the combinatorial compensation design setting.

In principle, one can employ a procurement auction mechanism in our setting with the buyer being the principal and the sellers being the agents. The key difference is that mechanism design assumes the power of centralized allocation to enforce the allocation rule, while compensation design promotes voluntary decentralized participation without a bidding or allocation process. In particular, procurement auctions are not suitable for the applications that motivate our work. First, platforms cannot simply procure contributions on demand: participation is voluntary and decentralized, taking the form of an opt-in or opt-out decision rather than a bidding process. Moreover, the sheer scale of modern digital ecosystems makes repeated auction-based elicitation impractical. For example, running a fresh procurement auction for each use of content among millions of AI agents is clearly out of reach. These considerations make it clear that modern platforms need to design simple payment rules that can be applied on a continuous basis at scale, without requiring constant elicitation of private costs.

2.3 Utility design and welfare-sharing games↩︎

Compensation design is also connected to the utility design literature, where a designer aims to design utilities so that agents’ decentralized optimization leads to high welfare. A central reference point is the class of valid utility games of [8], which gives PoA guarantees for marginal-contribution-type utility sharing in submodular welfare settings. Subsequent work studies related welfare-sharing and profit-sharing models [9], [10], distributed welfare games [2], distributed resource allocation [3], and collaborative environments with Shapley-based incentives [13]. The main distinction is that those models typically treat utilities as shares of welfare chosen by the designer, without a budget constraint and without private participation costs. In our setting, the payment rule must be budget feasible for every realized set and cost oblivious across all possible private costs. Equilibrium behavior in our setting is fundamentally different. For example, the standard sharing rule based on the Shapley value may admit no pure Nash equilibria (1).

2.4 Further applications↩︎

An additional real-world example related to compensation design is Parallel—a startup building a search engine for AI agents—which recently launched Index [68], [69]. Index aims to compensate publishers, data providers, and independent creators when AI agents utilize their work, determining compensation by estimating each source’s Shapley value to reflect its marginal contribution. Further applications are discussed below.

2.4.0.1 Incentivizing data sharing in federated learning.

Incentivizing participation is also a central theme in federated learning [70], [71]. A growing literature is examining incentive issues in such settings, where clients may withhold data due to privacy concerns, free-ride on others’ contributions, or require compensation for participation [72]–[77]. This line of work is motivated by a similar participation friction: valuable contributions are supplied by decentralized clients with private participation costs or privacy costs. The focus, however, is typically on incentives within a learning protocol, data valuation, or privacy-aware participation. Our model abstracts away the learning protocol itself and shifts the focus to the design of payment rules for general submodular objectives.

2.4.0.2 Value-sharing in emerging AI platforms.

[78] propose a framework based on the Shapley value for compensating copyright owners whose data contributes to generative-AI outputs. More recently, [79] study in-context credit assignment using the least core to reduce coalition-level undercompensation among creators whose intellectual property appears in a model’s context window. These works focus on attribution and value division for realized AI-generated outputs or contexts. Our focus is complementary: we study payment rules as an ex ante incentive device in decentralized systems, where agents decide whether to participate before the realized set of contributions is known.

2.4.0.3 Revenue sharing in music streaming.

Finally, our framework is also related to recent work on revenue sharing in music streaming platforms such as Spotify. A central question in this literature is how subscription revenue should be divided among artists. The two main rules are pro-rata payments, where each artist is paid according to their share of total streams on the platform, and user-centric payments, where each subscriber’s payment is divided only among the artists that subscriber listens to. [80] compare these two rules and show that the pro-rata rule can have advantages that are not captured by the usual criticism that it cross-subsidizes heavy users. In particular, they identify conditions under which pro-rata sharing can be Pareto-superior to user-centric sharing. From a cooperative game-theoretic perspective, [81] give axiomatic foundations for these streaming payment rules, including characterizations of the pro-rata and user-centric rules. These works divide realized subscription revenue among artists, whereas our model studies incentives for voluntary participation under a fixed budget and private costs.

3 The basic model↩︎

We now define our basic model in more detail. 1 contains an illustration. [sec:single-agent-combinatorial,sec:multi-agent-combinatorial] extend the scope of compensation design beyond the binary-action setting.

3.1 Compensation design with binary participation↩︎

We let \(N=\{1,\ldots,n\}\) be the set of agents (for example, content creators or data providers). The principal (for example, the platform) has a budget \(B>0\). The principal’s goal is to maximize the value \(v(S)\) of the participating set \(S\). We use value-oracle access as the baseline oracle model: given a subset \(S\subseteq N\), the oracle returns \(v(S)\). This value can be interpreted as the aggregate utility generated by the participating agents, for example over a sequence of user queries. (Stronger oracle models, such as demand oracles, are discussed as a direction for future work in 8.)

Our blanket assumptions concerning the value function are gathered below; more general value functions are considered in 6 and 7.

In the basic version of our model, we assume that each agent \(i \in [n]\) has a private cost \(c_i \geq 0\), and has two possible actions, which we denote by \(\mathsf{in}\) and \(\mathsf{out}\); we denote by \(\mathcal{A}_i \mathrel{\vcenter{:}}=\{\mathsf{in}, \mathsf{out}\}\) \(i\)’s action set. These modeling assumptions, which are in line with the targeted applications, are reversed relative to the contract design literature, where the cost is typically assumed to be known but the action unobserved. We generally operate in the large-market regime [4], [5], wherein \[\lambda \mathrel{\vcenter{:}}=\max_{i\in N}\frac{c_i}{B} \ll 1.\]

A joint action profile \((a_1, \dots, a_n)\) is in one-to-one correspondence with a set \(S \mathrel{\vcenter{:}}=\{ i \in N : a_i = \mathsf{in}\}\). The principal designs a payment rule \(p : 2^N \to \mathbb{R}_{\geq 0}^n\). This enforces limited liability: the payment attached to each agent is nonnegative. The payment rule should be budget feasible such that \(\sum_i p_i(S) \le B\) for all \(S \subseteq N\). We typically assume that if \(i \notin S\), it receives no payment, so its utility is zero. On the other hand, if \(i \in S\), its utility is \(p_i(S) - c_i\). Under a joint action \((a_1, \dots, a_n)\) associated with \(S \subseteq N\), we denote by \(u_i(S)\) the utility of agent \(i\). Namely, \[u_i(S) \mathrel{\vcenter{:}}= \begin{cases} 0 & \text{if } i \notin S,\\ p_i(S) - c_i & \text{otherwise}. \end{cases}\] In what follows, it will sometimes be convenient to identify a joint action profile by the associated subset \(S\).

3.1.0.1 Equilibrium concepts.

Perhaps the most natural solution concept in this model is the pure Nash equilibrium, formally defined below.

In general games, pure Nash equilibria may or may not exist (e.g., [82]). Nevertheless, we shall show that the game induced by a suitable payment rule always admits a pure Nash equilibrium through a potential argument.

A more permissive solution concept is the coarse correlated equilibrium [83], which is in turn a relaxation of correlated equilibria [84].

Above, we used the standard notation \(\boldsymbol{a}_{-i} \mathrel{\vcenter{:}}=(a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n)\). If \(\mu\) in 2 is a product distribution, one obtains the usual notion of a mixed Nash equilibrium [85].

3.1.0.2 Price of anarchy.

The goal of the principal is to maximize the value function subject to the budget constraint: \[\operatorname{OPT}= \max\left\{v(S): S \subseteq N,\;\sum_{i \in S} c_i \le B\right\}. \label{eq:opt}\tag{4}\] For a game \(\Gamma\), we let \(\mathsf{Eq}(\Gamma) \neq \emptyset\) denote a set of solutions according to some equilibrium concept. The price of anarchy with respect to the solution concept \(\mathsf{Eq}\) is defined as \[\label{eq:PoA} \operatorname{PoA}_{\mathsf{Eq}}(\mathcal{G}) = \sup_{\Gamma \in \mathcal{G}} \frac{\operatorname{OPT}(\Gamma)}{\inf \{ \mathbb{E}_{S \sim \mu}[v(S)] : \mu \in \mathsf{Eq}(\Gamma) \}},\tag{5}\] where \(\mathcal{G}\) is a set of instances. If \(\operatorname{OPT}> 0\) and the denominator is zero, the ratio is to be interpreted as \(+\infty\). We will write \(\operatorname{PoA}_{\mathsf{PNE}}\) to denote the price of anarchy with respect to pure Nash equilibria (assuming existence of such equilibria) and \(\operatorname{PoA}_{\mathsf{CCE}}\) for the price of anarchy with respect to coarse correlated equilibria.

3.2 Budget-share payment rules↩︎

The payment rules we consider can be described as shares of the total budget.

The case \(\gamma=1\) will be especially relevant, capturing the scenario where each selected agent’s budget share covers their normalized marginal contribution.

3.2.1 Shapley payments↩︎

Perhaps the most natural payment rule is the one induced by the Shapley value [11]. We recall that for a nonempty coalition \(S\) and an agent \(i\in S\), \(\phi_i(S)\) denotes the Shapley value of agent \(i\) in the cooperative game obtained by restricting \(v\) to \(S\): \[\label{eq:Shapley} \phi_i(S)= \sum_{T\subseteq S\setminus\{i\}} \frac{|T|!(|S|-|T|-1)!}{|S|!} \bigl(v(T\cup\{i\})-v(T)\bigr).\tag{6}\] The Shapley value has many important applications, including profit sharing between internet service providers [86], measuring the influence of nodes in social networks [87], identifying salient genes for biological functions [88], feature attribution in machine learning [89], and responsibility or importance measures in database queries and temporal logics [90], [91].

In the context of compensation design, we define the Shapley payment rule as \[\label{eq:shapley-payment} p^{\textrm{Sh}}_i(S)= \begin{cases} B\dfrac{\phi_i(S)}{v(S)} & \text{if } i\in S\text{ and }v(S)>0,\\[1.5ex] 0 & \text{otherwise.} \end{cases}\tag{7}\] This payment rule is indeed budget feasible—in fact, it fully exhausts the budget—and satisfies the marginal-covering condition per 4.

For completeness, we provide the proof in 9.

3.2.2 Marginal contribution payments↩︎

We also consider the marginal contribution payment rule. For a subset \(S \subseteq N\) and an agent \(i \in S\), we let \[\Delta_i(S) \mathrel{\vcenter{:}}= v(S)-v(S\setminus\{i\}).\] The marginal contribution payment rule is defined as \[p^{\textrm{mc}}_i(S)= \begin{cases} B\dfrac{\Delta_i(S)}{v(S)} & \text{if } i\in S\text{ and }v(S)>0,\\[1.5ex] 0 & \text{otherwise.} \end{cases} \label{eq:mc-rule}\tag{8}\] By monotonicity (1), this guarantees limited liability. Just like 7 , this payment rule is anonymous (or non-discriminatory) in the sense that it uses the same formula for every agent without taking into account provider identities. It is also clearly cost oblivious, as it only depends on the set of agents that decided to opt in together with each agent’s marginal contribution. We denote by \(\Gamma^{\textrm{mc}}\) the binary-action \(n\)-player game induced by the marginal contribution payment rule defined in 8 .

We now show that this payment rule is indeed budget feasible. We begin by establishing a simple upper bound on the sum of the marginal contributions, which is a direct consequence of submodularity.

This lemma readily implies budget feasibility.

This shows that the marginal-contribution rule is a legitimate budget-share rule. Moreover, by definition, it is \(1\)-marginal-covering in the sense of 4.

We conclude this section by pointing out that any pure Nash equilibrium \(S\) under a budget-feasible payment rule is cost feasible. Indeed, if \(i \in S\), then \(p_i(S)\ge c_i\), for otherwise agent \(i\) would prefer to opt out; summing over participating agents and using budget feasibility gives \(\sum_{i\in S} c_i \le \sum_{i\in S} p_i(S)\le B\). Interestingly, this is not the case under weaker notions, such as coarse correlated equilibrium, as discussed further in 5.5.

4 Pure Nash equilibrium↩︎

The first natural question in our model is whether a pure Nash equilibrium exists. This section answers this in the affirmative for the game induced by the marginal contribution rule. In contrast, we show that the answer is negative for the game induced by the Shapley payment rule. Beyond existence, we go on to examine the complexity of computing a pure Nash equilibrium.

4.1 Existence in the marginal contribution game↩︎

We first show that pure Nash equilibria exist under the marginal contribution payment rule.

4.2 Nonexistence under Shapley payments↩︎

In stark contrast, we show that a pure Nash equilibrium need not exist under the normalized Shapley payment rule \(p^{\textrm{Sh}}\) defined in 7 . This nonexistence persists even though \(p^{\textrm{Sh}}\) is a \(1\)-marginal-covering budget-share rule ([lem:shapley-efficiency-covering]), and even in the large-market regime.

4.2.1 A quadratic submodular family↩︎

In our construction, it is convenient to use value functions of the form \[\label{eq:sc-quadratic-value} v(S)=\sum_{i\in S}a_i- \sum_{\{i,i' \}\subseteq S}b_{i i' },\tag{9}\] where \(b_{i i' }=b_{i' i} \geq 0\).

Our goal is to prove the following theorem.

In the proof, we will make use of the following simple lemma.

4.3 Complexity of pure Nash equilibria↩︎

We next examine the complexity of computing pure Nash equilibria in \(\Gamma^{\textrm{mc}}\).

4.3.1 Exponential better-response paths↩︎

1 shows that every sequence of strict better responses terminates at a pure Nash equilibrium. Here, we show that the number of steps required for convergence is exponential in the number of agents.

The proof reduces from the standard FLIP dynamics—whereby exactly one node changes side—for weighted MaxCut. Specifically, here we are given a weighted graph \(G=(V,E,w)\) with nonnegative integer edge weights. We let \[\label{eq:cutvalue} \operatorname{Cut}(X)=\sum_{\{i,j\}\in E}w_{ij}\mathbb{1}\{|\{i,j\}\cap X|=1\}\tag{18}\] be the total weight of a cut \((X, V \setminus X)\), where \(X \subseteq V\). A FLIP step flips one vertex if doing so strictly increases the cut weight. We will use the fact that weighted MaxCut admits instances and initial cuts with exponentially long FLIP improvement paths [93], [94].

Our reduction proceeds as follows. For every vertex \(u \in V\), we let \(d_u = \sum_{v: \{u, v\} \in E} w_{u v}\), and choose \(L \geq \max_{u \in V} d_u\). We create one agent for each vertex in \(V\) and one additional agent \(a\). For every \(S \subseteq \{a \} \cup V\), the value function is defined as \[\label{eq:valuefun} v(S) = \frac{L}{\gamma}\mathbb{1}\{a\in S\} + L|S\cap V|+\operatorname{Cut}(S\cap V),\tag{19}\] where \(\gamma \in (0, 1)\). In terms of the costs, we set \(c_a = 0\) and \(c_i = \gamma\) for all \(i \in V\). We first formalize that the value function defined in 19 is indeed monotone and submodular. (Of course, \(v(\emptyset) = 0\).)

We are now ready to establish the existence of exponential better-response paths.

In fact, this result holds even when \(\lambda = \max_{i \in N} c_i/B \ll 1\), so the large-market assumption does not preclude this lower bound.

4.3.2 -completeness↩︎

Taking a step further, we show that computing a pure Nash equilibrium in \(\Gamma^{\textrm{mc}}\) is -complete. , which stands for polynomial local search, was introduced by [17].

4.3.3 Pseudo-polynomial bound for additive valuation functions↩︎

We complement the foregoing hardness results by establishing a positive result when the value function is additive, meaning that \(v(S)=\sum_{i\in S} v_i\), where \(v_i \ge 0\). In this case, assuming \(v(S)>0\), the marginal contribution payment rule becomes \[p^{\textrm{mc}}_i(S) = B \frac{v_i}{v(S)}.\] In what follows, it will be convenient to define \[\theta_i=\frac{Bv_i}{c_i}-v_i = v_i\frac{B-c_i}{c_i}>0,\] where we can assume that \(c_i \in (0, B)\). If \(i \notin S\), then \(i\) strictly prefers to opt in if and only if \[B \frac{v_i}{v(S)+v_i} > c_i \iff v(S) < \theta_i.\] Conversely, if \(i\in S\), then \(i\) strictly prefers to opt out if and only if \[B\frac{v_i}{v(S)} < c_i \iff v(S) - v_i > \theta_i.\] Therefore, the pure Nash equilibria are exactly the sets \(S\) satisfying \[v(S)\ge \theta_i \quad \forall i\notin S \text{ and } v(S)-v_i\le \theta_i \quad \forall i\in S.\] For the case of additive valuations, we can derive the following potential function.

Now, let us assume that each value \(v_i\) is integral and \(W \mathrel{\vcenter{:}}=\sum_{i \in N} v_i\). We claim that 2 implies the following pseudo-polynomial upper bound on the length of any strict better-response path.

As a result, while general monotone submodular valuation functions can admit exponentially long better-response paths, additivity with polynomially bounded values yields a polynomial bound. A key aspect of 2 is that the bound on the length of the better-response path does not depend on the costs.

The case where \(c_i = 0\) is not interesting: if \(v_i > 0\), then agent \(i\) has a strict dominant strategy to opt in, whereas if \(v_i = 0\) that agent is strategically irrelevant.

5 Price of anarchy bounds↩︎

In this section, we derive price of anarchy bounds for both pure Nash equilibria and coarse correlated equilibria, primarily under the large-market condition \(\lambda = \max_{i \in N} c_i / B \ll 1\).

5.1 Pure Nash equilibria↩︎

To begin with, we focus on pure Nash equilibria. Our bound will depend on the following cost concentration term: \[\kappa(\lambda)= \max\left\{ \sum_{i \in S } \frac{x_i }{1 - x_i}: 0 \le x_i \le \lambda \text{ and } \sum_i x_i \le 1 \text{ for a finite } S \right\}. \label{eq:costcon-def}\tag{20}\] An immediate upper bound is \(\kappa(\lambda) \leq \frac{1}{1 - \lambda}\). More precisely, we can determine \(\kappa(\lambda)\) exactly as follows. For \(\lambda\in(0,1)\), let \[q = \left\lfloor\frac{1}{\lambda}\right\rfloor \text{ and } r=1-q\lambda\in[0,\lambda).\] It is easy to see that \(\kappa(\lambda)\) can be expressed in the following form.

Indeed, the function \(x\mapsto x/(1-x)\) is increasing and convex on \([0,1)\), so the maximum in 20 is attained by filling as many coordinates as possible (namely, \(q\)) at the upper bound \(\lambda\), plus one remainder coordinate when \(q < \frac{1}{\lambda}\). We formalize this in 9.

As a result, under a monotone and submodular valuation function, the marginal contribution payment rule guarantees a PoA of \(1 + \kappa(\lambda) \leq \frac{2 - \lambda}{1 - \lambda}\), thereby approaching \(2\) when \(\lambda \to 0\).

5.1.1 Tightness of the analysis↩︎

We now show that 5 is tight even when the value function is additive: for any \(\lambda \in (0, 1)\), there exists an instance where \(\operatorname{PoA}_{\mathsf{PNE}}\geq 1 + \kappa(\lambda)\).

In the construction above outside agents are indifferent between opting in and opting out. One can make this lower bound agnostic to how ties are handled by making the value \(x/(1 - x) - \eta\) for some arbitrarily small \(\eta > 0\), where \(x \in \{\lambda, r \}\).

5.2 Lower bounds↩︎

We complement our positive results with several lower bounds. First, we show that any cost-oblivious payment rule must incur a PoA of at least \(2\) even when \(\lambda \to 0\).

5.2.1 Anonymous and cost-oblivious rules↩︎

As a warm-up, we first treat the case where the payment rule is anonymous. We then extend the lower bound even when the payment rule is not anonymous (6).

5.2.2 Cost-oblivious rules without anonymity↩︎

The preceding lower bound makes crucial use of anonymity. We now show that the barrier of \(2\) also applies without anonymity.

This result implies the following dichotomy. For every deterministic payment rule that is nonnegative, budget feasible, and cost oblivious, either it does not always guarantee existence of a pure Nash equilibrium, or there exists an instance with a pure Nash equilibrium whose welfare ratio is at least \(2\).

5.2.3 Beyond the large-market assumption↩︎

We now turn our attention to settings beyond the large-market condition. 5 provides a PoA bound that diverges when \(\lambda \uparrow 1\). We observe that this is, in some sense, fundamental:

This lower bound hinges on a high-value agent being indifferent between opting in and opting out. We next show that even if ties are broken in favor of the principal (all else being equal, the agent selects the action maximizing the principal’s value), the price of anarchy of any deterministic payment rule is \(\Omega(\sqrt{n})\).

5.2.3.1 An \(\Omega(\sqrt{n})\) lower bound for principal-favoring tie breaking.

Unlike 5, the lower bound below does not rely on adversarial tie breaking.

5.3 Constant PoA beyond the large-market assumption via randomization↩︎

In this subsection, we assume platform-favoring tie-breaking but work without any large-market assumption: agents may have costs as large as or larger than the budget. Despite the \(\Omega(\sqrt{n})\) lower bound for deterministic payment rules (7), we show that one can recover a constant PoA using a randomized payment rule. A randomized rule is a distribution over deterministic payment rules, and a deterministic payment rule is sampled and announced before the agents choose whether to opt in. The performance guarantee is with respect to the expectation over randomization and the worst principal-favoring pure Nash equilibrium in each realized branch.

We consider a randomized rule over two deterministic branches. The first branch is a singleton-prize rule. For every nonempty \(S\subseteq N\), let \(w(S)\in\operatorname*{arg\,max}_{i\in S} v(\{i\})\) be selected according to a fixed public priority order. We define \[p^{\mathrm{sing}}_i(S) = \begin{cases} B & \text{if }S\neq\emptyset\text{ and }i=w(S),\\ 0 & \text{otherwise.} \end{cases}\] The second branch is the marginal-contribution rule \(p^{\textrm{mc}}\) from 8 . Both branches are budget feasible; the budget feasibility of \(p^{\textrm{mc}}\) is exactly 1.

We first show that pure Nash equilibria exist in both branches. We note that the potential function argument in 1 requires \(c_i < B\) for every agent and does not directly generalize. Nevertheless, we use a refined argument to show the existence of a pure Nash equilibrium.

We then analyze the performance of the pure Nash equilibrium under the two deterministic rules. Define the best affordable singleton value \(M \mathrel{\vcenter{:}}=\max\{v(\{i\}): c_i\leq B\}\) with the convention that \(M=0\) if no agent is individually affordable.

The randomized rule mixes the two branches as follows: \[\begin{array}{ccl} \text{singleton-prize branch} & \text{with probability} & 1/3,\\[1mm] \text{marginal-contribution branch} & \text{with probability} & 2/3. \end{array}\]

5.4 Coarse correlated equilibria↩︎

In light of the intractability of pure Nash equilibria (4), an important question is whether coarse correlated equilibria also attain a constant fraction of the optimal value. We first give a simple constant-factor argument and then sharpen it to the asymptotically tight large-market bound.

In what follows, for \(i \notin S\), it will be convenient to introduce the notation \[x_i(S)= \begin{cases} \dfrac{v(S\cup\{i\})-v(S)}{v(S\cup\{i\})} & \text{if } v(S\cup\{i\})>0,\\ 0 & \text{if } v(S\cup\{i\})=0. \end{cases}\] In particular, if an agent \(i\) opts in and the selected set is \(S\), its payment under our marginal contribution rule will be \(B x_i(S)\). We are now ready to obtain a PoA bound for CCEs.

5.4.0.1 A sharp large-market bound.

We next sharpen the argument by using a fixed marginal decomposition of the optimal set rather than bounding every optimal singleton. The result applies to the marginal-contribution rule, and more generally to any \(1\)-marginal-covering budget-share rule in the sense of 4.

5.4.1 Additive valuation functions↩︎

Finally, for the special case of additive valuation functions, we can recover the exact bound established for pure Nash equilibria.

This bound is tight under the marginal contribution payment rule in view of the tight pure Nash equilibrium instance constructed in 3 (pure Nash equilibria are, of course, coarse correlated equilibria).

5.5 On the price of stability of CCEs↩︎

We conclude this section by making a counter-intuitive observation: the price of stability—defined similarly to the price of anarchy but with respect to the best equilibrium—of CCEs can be strictly smaller than 1. This means the best CCE can have better performance than the full-information benchmark. In particular, we provide a tight characterization for additive value functions. The reason why this happens is that CCEs may place positive probability on a coalition \(S\) that violates the constraint \(\sum_{i \in S} c_i \leq B\), even though the payment is budget feasible. Thus, a CCE can approximately implement a fractional solution of the budget-constraint optimization problem and beats the full-information integral solution benchmark.

We begin with an explicit construction showing that the price of stability with respect to CCEs can be arbitrarily close to \(1/2\)!

In fact, we shall now show that the construction in 12 is tight for additive valuations. To begin with, we prove the following auxiliary lemma, pointing out that CCEs satisfy cost feasibility in expectation.

We next point out that individually infeasible agents can never be in the support of a CCE.

The key idea in the price of stability lower bound is that cost feasibility in expectation corresponds to a fractional relaxation of knapsack, which can only be larger by a factor of \(2\). For completeness, we include the simple proof below.

We are now ready to show that 12 is tight.

6 Beyond monotone submodular↩︎

A natural question arising from our positive results so far is whether they can be extended to more general valuation functions beyond monotone submodular. Here, we consider XOS and subadditive value functions, both of which are general and include the submodular case as a special case.

We recall the relationship between value functions in the complement-free hierarchy [95]: \[\mathrm{Additive}\; \subseteq \; \mathrm{Submodular}\; \subseteq \; \mathrm{XOS} \; \subseteq \; \mathrm{Subadditive}.\]

6.1 PoA lower bounds for XOS valuations↩︎

This subsection presents an information-theoretic obstruction for fractionally subadditive value functions (equivalently, XOS): even under a large-market condition, no payment rule that uses only polynomially many value queries can guarantee an \(O(n^{1/2-\epsilon})\) price of anarchy with respect to CCEs.

As before, we assume a set \(N\) comprising \(n\) agents. The value function \(v\) can be accessed through a value oracle. In what follows, for our lower bound construction, we take all costs to be equal to one; that is, \(c_i = 1\) for any \(i \in N\). Moreover, the budget is \(B = \sqrt{n}\). For convenience, we assume that \(n\) is a perfect square. This instance satisfies the large-market assumption. We can write the (offline) optimum as \[\operatorname{OPT}(v) = \max\{v(S): |S|\le B \}.\] (Here we write \(\operatorname{OPT}(v)\) to make explicit the dependence on \(v\), as this will be relevant in our construction.) A payment rule \(p\) assigns nonnegative payments \(p_i(S)\) to agents within \(S\) and zero to agents outside it. It is budget feasible if \(\sum_{i\in S} p_i (S)\le B\) for any \(S \subseteq N\). In this context, since each cost is taken to be one, the utility of agent \(i\) can be expressed as \[u_i(S)= \begin{cases} p_i(S)-1 & \text{if } i \in S,\\ 0 & \text{if } i\notin S. \end{cases}\]

Our lower bound concerns payment rules that are oracle efficient, in the sense of making only \(\poly(n)\) value queries.

In fact, our lower bound applies even if the rule is allowed to depend on the private costs (all costs in the lower-bound instance are equal to \(1\)).

We say that \(\mathcal{A}\) guarantees \(\operatorname{PoA}_{\mathsf{CCE}}\leq \rho(n)\) if any \(\eta\)-CCE \(\mu\) of the induced game satisfies \[\mathbb{E}_{S\sim\mu}[v(S)]\ge \frac{1}{\rho(n)} \operatorname{OPT}\] for any small enough \(\eta = \poly(1/n)\).

6.1.1 The hard XOS instance↩︎

We rely on the lower bound of [24] concerning XOS valuations in the value-query model. For a small enough \(\delta > 0\), we let \[h = \left\lfloor (1+\delta)n^{2\delta}\right\rfloor \text{ and } \beta=(1+\delta)n^{-1/2+\delta}.\] The base value function is defined as \[v_0 (S) \mathrel{\vcenter{:}}= \max\left\{ \max_{S' : |S'| \le h} |S \cap S'|,\;\beta |S| \right\} = \max\{\min\{|S|,h\},\;\beta |S|\}.\] Next, for a hidden set \(T\subset N\)—which will be drawn uniformly at random among all sets of size \(B\)—we define the value function \[v_T(S) \mathrel{\vcenter{:}}=\max\{v_0(S), |S \cap T| \}.\]

It is clear that both \(v_0\) and \(v_T\) are XOS (5). The optimal solution (subject to the budget constraint) differs substantially depending on whether the underlying value function is \(v_0\) or \(v_T\).

6.1.2 Indistinguishability by value queries↩︎

The next lemma establishes the key hardness statement in the oracle setting. A query distinguishes \(v_T\) from \(v_0\) only if it has an unusually large intersection with the random hidden set \(T\).

6.1.3 Implications for approximate CCE↩︎

We next prove an auxiliary lemma concerning the expected cost in an approximate CCE. It is independent of the hard distribution; it only uses budget feasibility and the deviation in which an agent always opts out.

This lemma allows us to upper bound the value of approximate CCEs on the base instance.

6.1.4 Putting everything together↩︎

We are now ready to prove our main theorem. The proof is based on a reduction: a sufficiently strong PoA guarantee for CCEs would enable a payment designer to distinguish between \(v_0\) and \(v_T\) with polynomially many queries.

6.2 Non-monotone value functions↩︎

We next consider what happens when we relax monotonicity. Our previous analysis made crucial use of monotonicity. First, it guarantees that the marginal contribution rule is nonnegative, guaranteeing limited liability. Moreover, monotonicity implies that if a payment rule ensures that an equilibrium \(S\) contains a target set \(T\), then \(v(S) \geq v(T)\); this can fail in the non-monotone setting, which means that a payment rule here must do more than attract a good set of agents—it must also exclude harmful ones.

We begin by pointing out a simple example showing that marginal payments can be negative without monotonicity.

A natural way to repair this issue is to pay only the positive part of the marginal contribution. Namely, if \(\Delta_i(S) \mathrel{\vcenter{:}}= v(S) - v(S \setminus \{i \})\), \[p_i^+(S) \mathrel{\vcenter{:}}= \begin{cases} B\dfrac{[\Delta_i(S)]_+}{\sum_{i' \in S}[\Delta_{i'}(S)]_+} &\text{if }i\in S\text{ and }\sum_{i' \in S}[\Delta_{i'}(S)]_+>0,\\ 0 &\text{otherwise.} \end{cases} \label{eq:positive-part-rule}\tag{47}\] This rule is nonnegative and budget feasible (because of submodularity). However, it does not guarantee bounded PoA.

6.2.1 Impossibility for a broader class↩︎

The previous lower bound concerns a very specific payment rule. We next show that the obstruction is broader. In particular, we consider deterministic cost-oblivious payment rules that satisfy the following natural conditions. (We recall that \(\Delta_i(S) = v(S) - v(S \setminus \{i \})\).)

1. Equal treatment of equal marginal contributions: for every value function \(v\), subset \(S\subseteq N\), and agents \(i, i' \in S\), \[\Delta_i(S)=\Delta_{i'}(S) \quad\Longrightarrow\quad p_i(S)=p_{i'}(S).\]

2. Positive compensation on uniformly productive coalitions: for every nonempty \(S\subseteq N\), if there is a \(q>0\) such that \(\Delta_i(S) = q\) for every \(i\in S\), then \[\sum_{i\in S} p_i(S)>0.\]

The last condition only rules out paying a total of zero to a coalition whose members all have the same strictly positive marginal contribution.

For an integer \(m\ge2\), we consider \(m\) agents \(L=\{\ell_1,\ldots,\ell_m\}\) and one high-value agent \(h\), so \(N=L\cup\{h\}\). For every \(S \subseteq L\), we define \[v(S)=\frac{|S|}{m^2} \text{ and } v(S\cup\{h\})=1-\frac{|S|}{m}. \label{eq:nm-equal-marginal-value}\tag{48}\]

In the following proof, two coalitions will be important. First, \[v(L)=\frac{1}{m} \text{ and } \Delta_\ell(L) = v(L)-v(L\setminus\{\ell\}) = \frac{1}{m^2} \text{ for all } \ell\in L. \label{eq:nm-equal-marginal-at-L}\tag{49}\] Second, at the full coalition \(N\), \[v(N)=0 \text{ and } v(N\setminus\{h\})=v(L)=\frac{1}{m},\] and, for every \(\ell\in L\), \[v(N\setminus\{\ell\}) = v((L\setminus\{\ell\})\cup\{h\}) = \frac{1}{m}.\] As a result, \[\Delta_i(N)=-\frac{1}{m} \text{ for every }i\in N. \label{eq:nm-equal-marginal-at-N}\tag{50}\]

6.2.2 A broader impossibility with zero-cost harmful agents↩︎

The preceding lower bounds still impose structure on the payment rule. We next point out that harmful zero-cost agents can always make the price of anarchy arbitrarily large. In other words, the principal needs a way to exclude harmful agents in order to guarantee a finite price of anarchy.

For completeness, 11 contains a complementary positive result beyond cost-oblivious payment rules, based on what we refer to as targeted implementation.

7 Combinatorial compensation design↩︎

The key premise so far is that each agent has binary actions: they can either opt in or opt out. In many cases, however, the agent’s action set is more complex. For example, a YouTube content creator could create multiple videos, and each video has a private cost. In this section, we introduce the combinatorial compensation design problem, in which each agent chooses a subset from multiple actions. In contrast to the binary-action setting, we show that the combinatorial compensation design problem is non-trivial even in the single-agent setting in 7.1. We further study the even more general problem of multi-agent combinatorial compensation design in 7.2.

7.1 Single-agent↩︎

We first consider the setting where there is a single agent with a finite set of actions \(A=\{1,\ldots,m\}\). The agent chooses an arbitrary subset \(S\subseteq A\). Each action \(e\in A\) has a private cost \(c_e>0\), and costs are additive: \(c(S)=\sum_{e\in S}c_e.\) The principal has a budget \(B > 0\) and a normalized monotone value function \(v:2^A\to \mathbb{R}_{\geq 0}\) with \(v(\emptyset)=0\). The principal designs a compensation rule \(p: 2^{A} \rightarrow \mathbb{R}_{\ge 0}\) that pays \(p(S)\) to the agent if they choose \(S \subseteq A\). We require the compensation rule to be budget feasible, meaning that \[0\leq p(S)\leq B \qquad \forall S\subseteq A.\] Given the compensation rule \(p\) and the cost vector \(c\), the agent chooses a subset \(S_p(c)\) satisfying \[S_p(c)\in\operatorname*{arg\,max}_{S \subseteq A}\{p(S)-c(S)\}.\]

The principal aims to design a compensation rule that maximizes its value. The full-information benchmark is \[\operatorname{OPT}\mathrel{\vcenter{:}}=\max\{v(T): T\subseteq A,\;c(T)\leq B\}.\]

We assume platform-favoring tie-breaking: among all subsets maximizing the agent’s payoff \(p(S)-c(S)\), the agent chooses one with maximum principal utility \(v(S)\). This assumption matters only at indifference points, for example, when a feasible set has payoff exactly zero.

7.1.1 Deterministic rules↩︎

Unlike the binary-action setting, where a deterministic compensation rule achieves a constant PoA even in the multi-agent setting with a submodular value function, any deterministic rule incurs \(\Omega(m)\) PoA even in single-agent combinatorial compensation design, and even for additive values. The lower bound holds even when \(c_e \le B\) for all actions \(e \in A\). This lower bound is tight: under the same assumption, one can achieve a PoA of \(m\) even for subadditive values by paying the agent \(B\) only when they choose an action \(e^* \in \operatorname*{arg\,max}_{e \in A} v(\{e\})\), which guarantees \(v(\{e^*\})\ge v(A)/m \ge \operatorname{OPT}/m\).

7.1.2 Randomized threshold-prize rule↩︎

Given the lower-bound results for deterministic rules, even in the additive-value setting, it is then interesting to investigate whether randomized compensation rules would have improved PoA bounds. We consider randomized compensation rules that are distributions over deterministic compensation rules. The random seed is drawn and publicly announced before the agent chooses a subset. The performance of such a rule is the expected principal’s value over this public randomization and the induced platform-favoring best-response of the agent. Our main result shows that there is a randomized compensation rule with PoA of \(O(\log m)\) even for subadditive values.

Throughout this section, we assume the value function \(v\) is normalized, monotone, and subadditive: \(v(S \cup S') \leq v(S)+v(S'), \forall S, S' \subseteq A\). We let \(U \mathrel{\vcenter{:}}= v(A)\) and recall that \(\operatorname{OPT}\) is the full-information benchmark. If \(\operatorname{OPT}=0\), the problem is trivial. So we can assume that \(U \ge \operatorname{OPT}>0\). We set the parameter \[L \mathrel{\vcenter{:}}=\lceil \log_2 m\rceil.\] We propose the following randomized threshold-prize rule. It first samples an index \(r\in\{0,1,\ldots,L\}\) uniformly at random and publicly announces it. It then sets a threshold \[\tau_r \mathrel{\vcenter{:}}=\frac{U}{2^r}\] and selects the deterministic payment rule \[p_r(S) \mathrel{\vcenter{:}}= \begin{cases} B & \text{if } v(S) \geq \tau_r,\\ 0 & \text{if } v(S)<\tau_r. \end{cases}\] This rule is clearly cost oblivious and budget feasible. The idea is that since \(\operatorname{OPT}\in [U/m, U]\), we can use a geometric scaled grid of size \(O(\log m)\) to guess the range of \(\operatorname{OPT}\) and get a value of \(O(\operatorname{OPT})\) with probability at least \(\Omega(1/\log m)\).

We will now provide an improvement to 17 under a large-market condition. Namely, we assume that the principal knows an upper bound \[c_e \leq \lambda B\qquad \forall e\in A\] for some \(\lambda\in(0,1]\). We set \[k \mathrel{\vcenter{:}}=\min\left\{m,\left\lfloor \frac{1}{\lambda}\right\rfloor\right\} \text{ and } q \mathrel{\vcenter{:}}=\left\lceil\frac{m}{k}\right\rceil.\] By the cost bound, every set comprising at most \(k\) actions is budget feasible. We will use a similar threshold-prize rule, but now set \[L_\lambda \mathrel{\vcenter{:}}=\lceil \log_2 q\rceil \text{ and } \tau_r=\frac{U}{2^r}.\] where \(r \in \{0, 1, \dots, L_\lambda \}\) is again sampled uniformly at random.

7.1.3 A matching lower bound for additive values↩︎

We now show that the logarithmic dependence obtained in 17 is unavoidable for cost-oblivious rules, even when \(v\) is additive.

In what follows, we normalize \(B=1\). We will consider the additive value function \[v(S)=|S|.\] For a scalar \(t > 0\), consider the uniform cost vector \[c_e=t \quad \forall e\in A.\] The optimum subject to the budget constraint reads \[\operatorname{OPT}(t) = \max\{|S|: t|S| \leq 1\} = \min\left\{m,\left\lfloor\frac{1}{t}\right\rfloor\right\}.\]

Now, we consider a cost-oblivious payment rule \(p:2^A\to[0,1]\). We define \[p_k=\max\{p(S): |S|=k\},\qquad k=0,1,\ldots,m,\] where by convention \(p_0 = p(\emptyset)\). At a cost level \(t\), the agent will choose a cardinality \[D_p(t) \in \operatorname*{arg\,max}_{k \in \{0,\ldots,m\}} \{p_k-t k\},\] where ties are broken in favor of the largest \(k\), which is the platform-favoring choice for \(v(S)=|S|\). The proof of our lower bound will make use of the following bound on the demand integral.

An analogous argument gives the matching dependence under the large-market parameter of 18.

7.2 Multiple agents↩︎

We finally consider the multi-agent version of the combinatorial-action model. Here there is a finite ground set \(A\) of atomic actions, partitioned across \(n\) agents: \(A=A_1\sqcup A_2 \sqcup \cdots \sqcup A_n\), where \(A_i\) is the set of actions controlled by agent \(i\). Let \(m=|A|\). Agent \(i\) chooses an arbitrary subset \(S_i\subseteq A_i\), and the realized action set is \(S=\bigcup_{i=1}^n S_i\). Each atomic action \(e\in A\) has a private cost \(c_e \ge 0\). As before, it is assumed that costs are additive, so agent \(i\)’s cost from choosing \(S_i\) is \(c(S_i) = \sum_{e\in S_i}c_e\). The principal has a normalized, monotone, submodular value function \(v:2^A\to \mathbb{R}_{\geq 0}\). A payment rule assigns a nonnegative payment \(p_i(S_1,\ldots,S_n)\) to each agent. It is budget feasible if \[\sum_{i=1}^n p_i(S_1,\ldots,S_n)\le B \qquad\text{for every profile }(S_1,\ldots,S_n).\] The utility of agent \(i\) is \(p_i(S_1,\ldots,S_n)-c(S_i)\). The full-information benchmark is \[\operatorname{OPT} = \max\left\{v(S): S \subseteq A,\;\sum_{e \in S} c_e \le B \right\}.\]

As in the single-agent model, we use principal-favoring tie-breaking: whenever an agent has multiple payoff-maximizing choices against the other agents’ choices, it chooses one that maximizes the principal’s value. This assumption is only used in the singleton-prize branch below, and only at exact indifference when an action costs exactly \(B\).

Since the multi-agent setting generalizes the single-agent setting, we know that it is impossible to beat \(\Omega(\log m)\) (19). However, whether it is possible to achieve a PoA of \(O(\log m)\) in the multi-agent setting is not straightforward. The multi-agent setting is harder because the payment rule must not only incentivize high-quality actions within each agent’s action set, but also manage competition among multiple agents, all without knowing the private costs. As the main result in this section, we show in 20 that it is still possible to achieve \(O(\log m)\).

7.2.1 A randomized payment rule↩︎

The randomized rule combines ideas from both the single-agent combinatorial and multi-agent binary-action settings. It has two types of branches. The singleton prize branch is similar to that in 8 to guarantee a lower bound of value. The second type of branch is a capped marginal-contribution branch, which incentivizes high-quality contributions from the agents. Specifically, we first sample a target value on a geometric scale intended to approximate \(\operatorname{OPT}\). Given such a target value \(R\), the mechanism then uses the marginal contribution payment based on the capped payment potential \(F_R(S):= B \min \{\frac{v(S)}{R},1\}\). Here, the cap \(R\) incentivizes agents to contribute value at least \(R\), while the marginal contribution structure ensures sufficient competition among agents. We show that when \(R\) is a constant-factor lower estimate of \(\operatorname{OPT}\), this branch achieves constant PoA. Randomization over the geometric scale thus gives a PoA of \(O(\log m)\). We provide a detailed proof below.

7.2.1.1 The singleton-prize branch.

First, we let \[M=\max_{e\in A}v(\{e\}) \text{ and } e^*\in\operatorname*{arg\,max}_{e\in A}v(\{e\}).\] Let \(i(e^*)\) denote the owner of \(e^*\). In the singleton-prize branch, the principal pays \[p_i^{\mathrm{sing}}(S_1,\ldots,S_n) = \begin{cases} B & \text{if } i=i(e^*) \text{ and }e^*\in S_i,\\ 0 & \text{otherwise.} \end{cases}\] This branch is clearly budget feasible. The following lemma follows directly.

7.2.1.2 The capped marginal-potential branches.

Next, for a scale parameter \(R>0\), we define the capped payment potential \[F_R(S)=B\min\left\{\frac{v(S)}{R},1\right\}.\] The branch with scale \(R\) pays each agent its final marginal contribution to \(F_R\); namely \[p_i^R(S_1,\ldots,S_n)=F_R(S)-F_R(S_{-i}),\] where \(S=\bigcup_{j=1}^n S_j\) and \(S_{-i}=\bigcup_{i' \ne i} S_{i'}\). In what follows, we show that the capped marginal-potential compensation rule is budget feasible and that the induced game among agents always admits a pure Nash equilibrium. We first show that the capped potential \(F_R\) is submodular.

The capped potential then satisfies budget feasibility.

We are now ready to justify the use of capped potentials: if one identifies a suitable scale \(R\), then every pure Nash equilibrium of the capped branch has a high value unless the optimum is essentially captured by a large singleton.

This lemma implies that identifying a good scale \(R\) suffices to upper bound the price of anarchy, as we point out below.

7.2.2 Unknown scale and the logarithmic approximation↩︎

The challenge, of course, is that the principal does not know \(\operatorname{OPT}\) since costs are assumed to be private. We now show that one can obtain a logarithmic approximation by randomly guessing the value scale. This mirrors the algorithm behind 17 concerning the single-agent (combinatorial) setting.

First, if every \(c_e \le B\) for all \(e\in A\), then every singleton is feasible and, by monotonicity and subadditivity of \(v\), \[\frac{v(A)}{m}\le \operatorname{OPT}\le v(A).\] More broadly, if the principal is given a large-market parameter \(\lambda\in(0,1]\) such that \(c_e \le \lambda B\) for all \(e \in A\), we can define \[\label{eq:q} k = \min\left\{m,\left\lfloor \frac{1}{\lambda}\right\rfloor\right\} \text{ and } q = \left\lceil \frac{m}{k}\right\rceil.\tag{54}\] We can then partition \(A\) arbitrarily into \(q\) blocks, each of size at most \(k\). Every block has total cost at most \(B\). Moreover, since \(v\) is subadditive, \[v(A)\le \sum_{\ell=1}^{q}v(A_\ell).\] This means that some feasible block has value at least \(v(A)/q\), so \[\frac{v(A)}{q} \le \operatorname{OPT}\le v(A).\] In what follows, in the general case where a large-market parameter is not given, we can set \(q = m\). We can then tune the upper bound as \[\label{eq:L} L = \left\lceil \log_{3/2}\left(\frac{4q}{3}\right)\right\rceil,\tag{55}\] so that the scales are given by \[\label{eq:scales} R_r=\frac{v(A)}{(3/2)^r}, \quad r=0,1,\ldots,L.\tag{56}\] In this context, we consider a randomized payment rule that chooses uniformly from the following \(L+2\) branches: \[\text{singleton-prize branch}, R_0\text{-branch},R_1\text{-branch},\ldots,R_L\text{-branch}.\] The scales constructed in 56 have the following property.

We are now ready to state our main guarantee.

As we saw earlier, this logarithmic dependence is unavoidable even in the single-agent model (19).

8 Conclusions and future research↩︎

We introduced compensation design, a framework for incentivizing high-quality contributions in decentralized systems. Unlike budget-feasible mechanism design, compensation design does not hinge on centralized allocation. Instead, in the spirit of utility design, participation is shaped through a (cost-oblivious) payment rule. Our results paint a comprehensive picture of what is possible in this model. Most notably, we established that a simple marginal contribution payment rule attains a sharp constant-factor price of anarchy for monotone submodular value functions under the large-market assumption, and this is so even with respect to coarse correlated equilibria. Moreover, there are obstacles to extending these positive results beyond monotone submodular objectives. Finally, logarithmic price of anarchy guarantees are possible when agents have combinatorial action sets.

Several directions remain open for future research. Our oracle lower bound for XOS valuations applies to value-query access; it would be interesting to understand what is possible in compensation design with stronger oracle access, such as demand oracles. Moreover, our model treats the budget as a fixed, exogenous parameter. In some cases, the budget can be adjusted dynamically based on participation and the quality of the contributions generated [96]. Extending compensation design to such settings is an important direction.

Acknowledgments↩︎

For some of the proofs, the authors used Gemini 3.1 Pro and ChatGPT 5.5 Pro to generate candidate ideas or formalize proof sketches, which the authors then verified and edited.

9 Omitted proofs↩︎

This section contains the proofs omitted from the main body.

10 Other cost-oblivious and anonymous payment rules↩︎

This section examines other cost-oblivious and anonymous payment rules beyond the marginal contribution rule defined in 3.2.2.

10.1 Marginal covering suffices for bounded PoA↩︎

We first extend 5 under the marginal-covering condition introduced in 4.

10.2 Equal splitting can have unbounded PoA↩︎

Finally, for completeness, we point out that the simple equal-split rule—whereby \(p_i(S) = B/|S|\) for any \(i \in S\)—can have unbounded price of anarchy.

11 Targeted implementation↩︎

The main challenge in compensation design is that the agents’ costs are private. Otherwise, there is a simple approach based on what we refer to as targeted implementation, which in fact succeeds even under non-monotone (submodular) objectives. The idea here is that one can implement a target set by excluding agents outside of it. This section spells out this approach.

Specifically, let \(T\subseteq N\) be a target set; one can think of \(T\) as the output of an approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint. Suppose further there are strict bonuses \(b_i > 0\) such that \[\sum_{i\in T}(c_i+b_i)\le B; \label{eq:target-budget}\tag{57}\] we will further justify this assumption in 11.1. One can then define the payment rule \[p_i(S) = \begin{cases} c_i+b_i & \text{if } i\in S\cap T,\\ 0 & \text{otherwise.} \end{cases} \label{eq:targeted-rule}\tag{58}\] This rule is budget feasible by 57 .

In particular, if the target set \(T\) has a certain approximation ratio relative to the optimum, the payment rule introduced above inherits that.

11.1 Large market slack for strict bonuses↩︎

To account for strict bonuses when identifying the target set, an obvious approach is to work with a reduced budget. The following lemma bounds the loss from reducing the budget even without monotonicity.

The corollary can be paired with any available approximation algorithm for non-monotone submodular maximization under a knapsack constraint; the resulting approximation factor enters through the parameter \(\alpha\).

References↩︎

---

1. Corresponding authors: ianagnos@cmu.edu and weiqiang.zheng@yale.edu. Work performed while at Google Research.↩︎

2. Authors are ordered alphabetically.↩︎

3. Otherwise, the problem reduces to pure algorithmic optimization, namely submodular maximization subject to a budget constraint, as we explain in 11.↩︎

4. It is common to define the price of anarchy in terms of the social welfare \(\sum_{i=1}^n u_i\), but here we define it with respect to the underlying value function \(v\).↩︎

5. In fact, logarithmic PoA continues to hold without the assumption that every action is individually feasible or the assumption that the value function is subadditive (we only need it to be monotone). Using the same idea, we can still guarantee a PoA of \(O(\log V)\), where \(V:= v(A)/\min_e v(\{e\})\) is the largest ratio between the upper and lower bounds on \(\operatorname{OPT}\).↩︎

6. Strictly speaking, the multi-agent contract model assumes a normalized reward \(1\) for success, and \(f\) denotes the probability of success. So \(f\) denotes the expected reward for the principal.↩︎

7. There are other models for contract design where agents have hidden types and their realized costs may be private [36]–[43]. These models generally make assumptions that are incomparable to our model of compensation design. We refer to [35, Sec. 6] for a detailed survey.↩︎

8. This hinges on standard complexity assumptions concerning the representation of the value function, which we do not spell out here.↩︎

9. As we point out in 10.1, this PoA bound can be extended to the class of \(\gamma\)-marginal-covering rules (4); however, a pure Nash equilibrium is not guaranteed to exist for that broader class of payment rules (cf. 2).↩︎

10. This does not presuppose the existence of a pure Nash equilibrium. If no pure Nash equilibrium exists, the theorem becomes vacuous.↩︎