Multi-Agent Non-Discriminatory Contracts

1 Introduction

As one of the pillars in microeconomic theory, contract theory utilizes the principal-agent model to achieve optimal outcomes amidst asymmetric information [Holmstr¨om, 1979; Holmstr¨om, 1982]. It focuses on designing the market for services, analogous to how mechanism design and auction theory structure the market for goods. The past few years have witnessed growing interest in contract theory in both the economics and computation, with the applications extending to real-world scenarios like crowdsourcing platforms [Ho et al., 2014], social media [Department, 2021], and government-run programs [Dai Li et al., 2021].

In the vanilla hidden-action principal-agent model [Holmstr¨om, 1979; Grossman and Hart, 1992], the principal delegates a single task to an agent who may take one of the costly actions and its outcome determines the reward. A contract, structured as a monetary transfer, incentivizes the agent to take the action maximizing his utility, which equals the transfer minus the cost. The principal cannot observe the action taken by the agent but only the outcome. Her goal is also to maximize her utility, which equals the reward obtained minus the payment transferred.

∗Ankang Sun is the corresponding author.

The basic model was later extended to the setting where the principal incentivizes a team of agents for a single project [Holmstr¨om, 1982; Babaioff et al., 2006]. In this framework, each of the agents faces a binary choice: to exert effort at a specific cost, or shirk without cost. This multiagent model involves strategic interactions among agents, ensuring that the resulting game induces a pure Nash equilibrium. For any subset of agents, the best way to incentivize them is to pay each agent his indifference payment between exerting effort and shirking, while paying zero to others. The scope of recent works focuses on computing the optimal contract [D¨utting et al., 2023; Ezra et al., 2023; D¨utting et al., 2025b].

In the multi-agent model, payments in the optimal contract may vary significantly across the agents. However, in practice, companies and organizations frequently implement standardized payment schemes. For example, chain stores such as McDonald's or Starbucks set standard hourly rates to treat every worker equally. A strengthened form of this egalitarianism is found in worker cooperatives, a concept dating back to the English labor movement. In organizations like the UK wholesaler Suma Wholefoods, equal pay is implemented to reflect the view that every worker is a co-owner and all contributions are essential to the business's success [Ethicalsuperstore, 2025].

Although equal pay brings high cohesion and equality, it is not universally viable. Not only because high-skill workers can command higher wages elsewhere, but also those high performers consider it unfair. A practical trade-off is to adopt the wage ratio, which refers to the gap between the top salaries and the bottom salaries in economy. For example, as a world leader in the co-operative movement, the Mondragon Corporation in Spain uses agreed-upon wage ratios [Institute, 2022]. The ratios range from 1:3 to 1:9 in its different cooperatives. The statutory minimum wage could also be viewed through a similar lens: by having the highest wage fixed, the minimum wage was guaranteed.

In this paper, we study contracts that give agents equitable payments, as considered in [Feng et al., 2024; Castiglioni et al., 2025b]. Motivated by wage ratios used in practice, we extend this by allowing agents' payments to differ by a multiplicative factor. Our goal is to offer a comprehensive understanding of how the degree of non-discrimination impacts the principal's optimal utility.

1.1 Contribution

We study multi-agent contracts, where a principal delegates a task to multiple agents. Each agent incurs a cost upon exerting effort, and the overall success probability across agents is monotone submodular. The principal incentivizes agents to contribute effort by offering contractual payments, aiming to maximize her utility. Our paper specifically centers on nondiscriminatory contracts, which ensure equitable payments to all agents, and we explore their impact on the principal's optimal utility. The results are summarized in Table 1.

Similar to [Feng et al., 2024], we consider the concept of price of non-discrimination (PoND), which is defined as the supremum ratio between the principal's optimal utility of unconstrained contracts and that of all non-discriminatory contracts. For any submodular reward function with n agents, we design a non-discriminatory contract that achieves Ω( 1 log n ) fraction of the optimal utility without constraints 1 , implying an O(logn) upper bound on PoND. We then prove that the bound cannot be improved by more than an O(log log n) factor, even if the success probability function is additive. Thus, the PoND is bounded between Ω( logn log log n ) and O(log n).

As n increases, the bound Θ(logn) becomes large, which means that optimality and non-discrimination are hardly compatible. We observe that if we are willing to relax the non-discrimination requirement, which is often acceptable in practice, the utility can be substantially increased. To more thoroughly and accurately examine this effect, for β ≥ 1, we extend the notion of non-discrimination to β-approximate non-discriminatory contracts (or β-non-discriminatory contracts), which permit the difference between the highest and lowest payments to be within a factor of β. When β = 1, all agents receive equal payments; as β approaches infinity, agents are paid according to the optimal unconstrained contract. Accordingly, the price of β-non-discrimination (PoND(β)) can be defined in the same manner.

We then provide a comprehensive parametric study on PoND(β), by setting β = nδ , where δ ≥ 0. When δ = 0, the problem degenerates to the non-relaxed version and in the following, we assume δ > 0. Our goal is to characterize the relationship between PoND(β) and δ.

Main Result 2: Letting β = nδ ,

• for 0 < δ < 1, max{2, 1 δ+o(1) } ≤ PoND(β) ≤ ⌈ 1δ ⌉+1;
• for δ = 1, 1.591 ≤ PoND(β) ≤ 2;
• for δ > 1, 1 ≤ PoND(β) ≤ 1+ o(1).

The above result offers an algorithmic framework that assists decision makers in selecting an appropriate level of non-discrimination, taking into account the potential loss in the principal's utility associated with non-discriminatory contracts. The bounds are asymptotically tight for both small and large values of δ. For example, if δ is set to 12 , then the ratio between the highest and lowest payments is within √n, and our contract ensures the principal's utility to be at least 13 of the optimal utility. If δ = 1 log n , the ratio of highest and lowest payments is within 2, and our contract ensures the principal's utility to be at least 1 logn+1 of the optimal utility. Besides, the bound is not tight for values of δ close to 1, which remains an open question for future research.

1 Throughout the paper, log denotes the base-2 logarithm.

In the previous two sets of results, we focused on the asymptotic bounds as n becomes large. To complement this analysis, we present a case study for two agents, where we derive the exact tight bound on PoND(β) using a more algebraic approach.

It is worth noting that non-discriminatory contracts in the same multi-agent model are studied in a simultaneous and independent work [Castiglioni et al., 2025b]. However, their main focus is on quantifying the difference between nondiscriminatory contracts and other forms of fair contracts, rather than examining how non-discrimination impacts the optimal utility of the principal.

1.2 RelatedWork

Algorithmic contract design. Following two aforementioned papers in microeconomics by [Holmstr¨om, 1979] and [Grossman and Hart, 1992], contract theory has been well explored from an algorithmic perspective. A core problem within is combinatorial contracts, which can be categorized into single-agent multi-action contracts and multi-contracts. [D¨utting et al., 2025a] studied the former one where an agent chooses any subset of possible actions, bringing dependencies among agent's actions. They showed an optimal contract can be computed efficiently if the success probability function is gross substitutes, while computing the optimal contract is NP-hard for submodular functions. As a consequence, a line of works by [Ezra et al., 2023; Dutting et al., 2024; Deo-Campo Vuong et al., 2024; Feldman and Yashin, 2025] also extended the model to a combinatorial setting, with the reward function ranging from gross substitutes and submodular to supermodular. They addressed problems in both tractability and hardness.

Multi-agent contracts. This paper is more closely related to the multi-agent setting pioneered by [Babaioff et al., 2006]. In their setting, a principal incentivizes a team of agents to jointly work on a single project. Each of the n agents chooses to exert effort or not, and optimizing the principal's utility was defined as the combinatorial agency problem. The landscape was significantly expanded by [D¨utting et al., 2023]. In their work, more complicated reward functions were considered, in which the payment to each agent in an incentivized set depends on their marginal contribution to the project. They gave constant-factor approximation algorithms for submodular and XOS reward functions, while there is an Ω(√n) impossibility for subadditive functions with n agents. The most recent work by [Ezra et al., 2023] and [D¨utting et al., 2025b] showed that no PTAS exists for Submodular functions, and no approximation better than Ω(n 16 ) exists.

Another multi-agent model was studied by [Castiglioni et al., 2023] and [Hann-Caruthers and Goel, 2024]. In their setting, each agent completes their own task with their payments conditioned on individual performance. Thus, it is natural that payments to each agent are linked to their own outcomes. Our work, however, is based on the first multi-agent model where a team of agents work on a single project. It is mainly because in practice, organizations like worker cooperatives make everyone work towards a common goal instead of finishing individual tasks. As there is no standard way of judging someone's outcome, equalizing the payments matters.

Fairness in contracts. [Feng et al., 2024] conducted the study of non-discriminatory contracts. The key difference is that they considered the second multi-agent model as previously mentioned, where agents complete individual tasks instead of a single task. While they have derived logarithmic price of non-discrimination across all their settings, our model introduces the concept of price of β-nondiscrimination to achieve constant-factor approximations. Fairness concerns were also investigated by [Castiglioni et al., 2025a], who considerd the trade-off between profitmaximizing and fairness when allocating a bunch of tasks to some agents. In a concurrent work with this paper, [Castiglioni et al., 2025b] explore fair contracts using a swapbased definition, whose objective is to bound the gap between non-discriminatory contracts and optimal fair contracts.

The price of non-discriminatory contracts is also studied in another concurrent and independent work [Feldman et al., 2026]. Their upper bound is stronger than ours: it closes the log log n factor gap, holds for XOS success functions, and applies under combinatorial actions. In contrast, in the current paper, we further provide a systematic study of the relaxed notion PoND(β), and give a near-tight bound on any β.

2 Preliminaries

Multi-agent hidden-action setting. For any k ∈ N+, let [k] = {1, . . . , k}. We study the model in which a principal interacts with a set of agents N = [n] = {1, . . . , n} to execute a project. Each agent chooses whether to exert effort or shirk. For each agent i, exerting effort incurs cost ci ∈ R>0, while shirking incurs zero cost. The outcome of the project is either "success" or "failure", and depends on the set of agents who choose to exert effort. The principal observes the outcome of the project but not the actions of agents. Let f : 2N → [0, 1] be the project's success probability function. When a set of agents S exert effort, the project succeeds with probability f(S). If the project succeeds, the principal derives reward normalized to r = 1. Thus, f is also referred to as the (expected) reward function. Otherwise if the project fails, the reward is zero. For any i ∈ N and S ⊆ N, define f(i | S) := f(S ∪ {i}) - f(S) as the marginal contribution of including i to S. In this paper, f is considered to be monotone and submodular, where monotonicity ensures that for any S ⊆ T, f(S) ≤ f(T), and submodularity ensures that for any S ⊆ T and any i /∈ T, f(i | T) ≤ f(i | S). For any S ⊆ N, |S| denotes its cardinality.

Optimal contract design. Since exerting effort is costly, agents by themselves have no interest in exerting effort, of which the benefit goes to the principal. To incentivize agents, the principal designs a contract that assigns payments to agents based on the outcome of the project. In this paper, we focus on the linear contract, an n-dimensional vector α = (α1, . . . , αn) with every αi ∈ [0, 1]. A contract α assigns payment αi to agent i when the project succeeds, regardless of whether agent i exerts effort or not.

When analyzing contracts, we consider the pure Nash equilibria of the induced game among the agents and adopt the tie-breaking rule where agents exert effort when indifferent. For a contract α, suppose that it incentivizes agents S to exert effort, i.e.,

Note that each agent i ∈ S has expected utility αif(S) - ci, while each i /∈ S has expected utility αif(S). Then for contract α and the equilibrium where agents in S exert effort, the principal's utility is

The principal pursues the contract that maximizes her utility. Then for a fixed set of agents S, the contract α that maximizes the principal's utility among all contracts in which the set of agents exerting effort is exactly S, is

For any S ⊆ N, define

the principal's optimal utility for the contracts where the set of agents exerting effort is S. Therefore, the problem of finding the contract with the maximum utility of the principal is equivalent to maxS⊆2N g(S), which, however, is known to be NP-hard [D¨utting et al., 2023].

Approximately non-discriminatory contracts. We now introduce non-discriminatory (linear) contracts. Informally, a contract is non-discriminatory (ND) if the payments assigned to agents who exert effort are identical. The ND requirement does not apply to the agents who choose to shirk. For a fixed set of agents S, the ND contract α that incentivizes S and maximizes the principal's utility satisfies

For any S ⊆ N, define

The contract that pays αS to each agent in S and zero to all other agents incentivizes exactly the agents in S and attains the minimum total payment among all contracts that induce effort by S. We also define

The interpretation of gND(S) is the principal's optimal utility under the ND contract that induces effort by S. Therefore, in this context, the principal faces the optimization problem of maxS⊆2N gND(S). Throughout the paper, we refer to contracts without the ND constraint as unconstrained contracts. When incentivizing the same set of agents S, the payments for agents under the optimal ND contract are weakly higher than those under the unconstrained contract. Hence, the nondiscrimination requirement reduces the principal's utility.

In addition to the exact non-discrimination, we are also concerned with approximately non-discriminatory contracts, in which payments assigned to agents who exert effort do not differ substantially. To measure the disparity among agents' payments, we use a multiplicative factor β with β ≥ 1, standing for the wage ratio. For a β-non-discriminatory (β-ND) contract α, if it incentives S to exert effort, then for any i, j ∈ S with αi ≤ αj, αj β ≤ αi ≤ αj holds. For a fixed set of agents S, the β-ND contract α that incentivizes S and maximizes the principal's utility satisfies

For any S ⊆ N and β ≥ 1, define gND(β, S) as

which stands for the principal's utility under the optimal βND contract in which the set of agents exerting effort is S. Note that gND(1, S) = gND(S). For β-ND contracts, the optimization problem for principal is maxS⊆2N gND(β, S).

The price of non-discrimination. We quantify the optimal utility loss due to the requirement of non-discrimination through the framework of the price of β-non-discrimination, a function with respect to β. Informally, it is the supremum ratio between the principal's optimal utility of all contracts and the principal's optimal utility of all β-ND contracts. Denote by I the set of problem instances. For any instance I ∈ I, let OPT(I) be the principal's optimal utility of all contracts and let OPTND(β, I) be the principal's optimal utility of all β-ND contracts.

Definition 1. For any β ≥ 1, the price of β-nondiscrimination is

When I and β are clear from the context, we use OPT and OPTND to refer to OPT(I) and OPTND(β, I), respectively. Also, PoND denotes PoND(1) for simplicity.

3 Logarithmic PoND

In this section, we study the price of (exact) nondiscrimination. We show that there always exists a nondiscriminatory contract achieving at least 1 logn of the unconstrained optimum, and this is almost tight, as there exist instances where the ratio is at most O( log log n logn ).

Theorem 1. For n agents with submodular reward function f, the price of 1-non-discrimination is at least Ω( logn log log n ) and at most O(log n).

The difficulty for deriving the O(log n) upper bound lies in identifying the set of agents to be incentivized by the contract. A natural greedy approach that adds agents sequentially, for example in decreasing order of "price to performance ratio 2 ", is unlikely to work. The rationale is that including an agent with huge payment gap can dramatically reduce the principal's utility, since under non-discrimination all incentivized agents are equally paid. Skipping that high-reward agent does not necessarily resolve the issue, because the current set of incentivized agents may already be at a threshold where adding any additional agent pushes the total payment above 1.

Instead, we design the contract based on a particular configuration of agents. Begin with the optimal unconstrained contract in which the agents in S∗ are incentivized to exert effort. We partition S∗ into several groups G1, . . . , Gm, such that (1) the total payment to each group under ND contracts does not exceed the total payment to S∗ in the optimal unconstrained contract, and (2) the sum of the principal's reward over the groups under ND contract is at least the reward under the optimal unconstrained contract.

2 For an agent, his price-performance ratio is the ratio between his marginal contribution and his payment in the optimal contract.

Lemma 2. Suppose S∗ is the set of agents exerting effort in the optimal unconstrained contract. When f is submodular, there exists a subset of agents S ⊆ S∗ such that

Proof. Since |S∗ | ≤ n, it suffices to show gND(S) ≥ 1 ⌈log |S∗ |⌉ g(S∗ ). Assume without loss of generality that the optimal unconstrained contract incentivizes all n agents, i.e. S∗ = N. For each i ∈ N, define αi,N = ci f(i |N\{i}) . Reindex the agents according to a descending order of αi,N, such that α1,N ≥ ... ≥ αn,N .

We now partition N into m = ⌈log n⌉ groups G1, . . . , Gm as follows: for each k ∈ [m- 1], group Gk contains 2k-1 consecutive agents 2k-1 , 2k-1 +1, . . . , 2k -1; the remaining agents form group Gm. Informally, group Gm contains the half of N with smaller αi,N, and group Gm-1 contains the half of N \ Gm with smaller αi,N, and so on. We illustrate this partition in Figure 1.

Consider incentivizing all agents in a single group Gk under ND contracts. The optimal ND contract that incentivizes exactly Gk pays each i ∈ Gk the amount αGk = maxj∈Gk cj f(j |Gk\{j}) and pays zero to agents in N \ Gk. The total payment to agents in Gk equals

where (a) holds due to Gk ⊆ N and the submodularity of f and (b) is due to that αi,N's are sorted in descending order and |G1| + |G2| + · · · + |Gk-1| ≥ |Gk| - 1.

Inequality (1) implies that for each group Gk, the principal's maximum utility when incentivizing Gk is

Summing over k ∈ [m] yields

where the second inequality transition is due to the submodularity of f. The above inequality implies that the maximum of gND(Gk) among all k ∈ [m] is at least 1m OPT = 1 ⌈log n⌉ OPT.

Lemma 2 indicates PoND ≤ O(logn). For the lower bound, we construct an additive instance with about logn groups of agents, homogeneous within each group. Incentivizing any group yields the same reward. As shown in this example, the optimal unconstrained contract incentivizes all groups, while any ND contract that yields positive utility for the principal can incentivize at most O( log log n logn ) groups.

Lemma 3. There exists an instance with additive f such that the principal's utility under any ND contract is no greater than a O( log log n logn ) fraction of that under the optimal unconstrained contract.

Proof. Let n = 2m -1 where m is an integer. In the instance, the n agents are classified into m groups G1,G2, . . . ,Gm, where for any k ∈ [m], group Gk contains 2k-1 agents. Agents within a group share the same cost function and reward function. In particular, for any Gk and any i ∈ Gk, f({i}) = 1 m2k-1 and ci = 1 Tm2 4k-1 , where T ≥ 2 is a constant number. Thus, to incentivize agent i ∈ Gk, the principal must pay at least 1 Tm2k-1 .

We claim that the optimal utility of the principal under the unconstrained contract is achieved by incentivizing all n agents. If A is a strict subset of N, then there exists an agent j ∈ N with j /∈ A. Define A′ := A ∪ {j}. One can verify that the difference between the utilities at A′ and A equals

Observe for any i ∈ N, αi = f({i}) T . Since ∑i∈A αi ≤ 1 T and f(A) ≤ 1, the difference is at least f({j}) T-1 T - αj = f ({j}) T -2 T > 0. Therefore, g(S) is maximized at S = N with value 1 - 1 T .

Next, we turn to ND contracts and suppose that the optimal ND contract incentivizes only a set S ⊆ N. Then in this ND contract, each agent in N \ S receives zero payment. Define L := min{k : Gk ∩ S ̸= ∅}. Since each agent in S receives the same payment 1 Tm2L-1 under the optimal ND contract, and agents in the group with a lower index have higher marginal contributions to f, the principal must prioritize agents from lower-index groups. Hence, if S contains some agent(s) in Gk for k ≥ L + 1, then all agents from GL to Gk-1 must belong to S.

Assume without loss of generality that f(S) = λ ≤ 1, since f(N) = 1. Because every group contributes 1m to the total reward, S must contain at least t = ⌊λm⌋ entire groups, that is, GL ∪ GL+1 ∪ · · · ∪ GL+t-1 ⊆ S. Then the number of agents in S satisfies

Since each agent in S receives payment 1 Tm2L-1 , the principal's optimal utility gND(S) is at most

Since an ND contract that incentivizes a single group yields positive utility for the principal, the upper bound on gND(S) must be positive. Then 2⌊λm⌋ - 1 ≤ Tm holds, and thus, λ ≤ log(Tm+1) m . Therefore, it holds that

implying that PoND = Ω( logn log log n ) as n = 2m - 1.

Theorem 1 directly follows from Lemmas 2 and 3.

4 Constant-Factor PoND(β)

In the previous bad example, a non-discriminatory contract yields about O( 1 logn ) of the optimal utility, driven by large disparities in unconstrained payments across agents. A natural question raised is how much the price of nondiscrimination improves if the ratio of the maximum to minimum payment among incentivized agents is bounded by a factor β.

In this section, we show that when β = nδ for some constant δ ∈ (0, 1] , PoND(β) is bounded by a constant. The case when δ > 1 follows from the remark below:

Remark 1. For δ > 1, one can achieve exact-approximation with sufficiently large n: For agents N incentivized under the optimal contract, the total payment with and without ND differs by at most (n-1)αi n → 0, where αi is the maximum payment value among N. Thus, we restrict our attention to δ ∈ (0, 1].

Theorem 4. Suppose f is submodular. For any δ ∈ (0, 1] and sufficiently large n, the price of nδ -non-discrimination is at most ⌈ 1δ ⌉ + 1 and at least max{2, 1 δ+O( log log n logn ) } when δ ∈ (0, 1) and at least 1.591 when δ = 1.

The lemma below establishes the upper bound on the price of nδ -non-discrimination.

Lemma 5. Suppose that f is submodular and S∗ is the set of agents exerting effort in the optimal unconstrained contract. For any δ ∈ (0, 1] and sufficiently large n, there exists an ND contract in which agents S ⊆ S∗ exert effort and

Proof. As our objective is to design an ND contract that incentivizes a subset of agents in S∗ , assume without loss of generality that the optimal unconstrained contract incentivizes all n agents as we did in Lemma 2, i.e. S∗ = N. For any i ∈ N, define αi,N := ci f(i |N\{i}) . By the optimality of g(S∗ ), we have αi,N < 1 for all i. We now group agents by their αi,N values.

Let t = ⌈ 1δ ⌉ and we partition agents into t + 1 groups G1,G2, . . . ,Gt+1, defined as follows:

and for any j = 3, . . . , t + 1,

Note that group G2 is well defined because (t - 1)δ < 1. Starting from the right boundary of G2, repeatedly extend to the right by a factor of 1δ to obtain groups G3, . . . ,Gt+1.

We then consider β-ND contracts that incentivize each group Gk separately and show that the sum of the principal's utilities from these contracts is at least the optimal utility under the unconstrained contract. For any agent i, suppose that i ∈ Gk. Define

the minimum payment to i under the nδ -ND contract that induces effort by exactly Gk.

First, consider group Gk with k ≥ 2. Since f is submodular, then ∑i∈Gk ˆαi is at most

which equals ∑i∈Gk αi,N as αi,N ≥ 1 nδ maxj∈Gk αj,N.

have

For group G1, since ˆαi ≤ αi,N < 1n for all i ∈ G1, we

Since |G1| ≤ n and n is sufficiently large, the above inequality implies ∑i∈G1 ˆαi < ∑i∈G1 αi,N + o(1). Note that setting payment ˆαi to every i ∈ Gk and zero to others yields the optimal nδ -ND contract that induces effort exactly by Gk. Under this contract, the principal has utility

We design such a contract for each group Gk. Then the principal's total utility from t + 1 separate contracts is at least

where the first inequality transition is due to Gk ⊆ N for all k and the second inequality uses submodularity of f. By the above inequality, there exists a group Gk∗ such that the nδ -ND contract with payment ˆαi to every i ∈ Gk∗ (and 0 to all other agents) yields utility for the principal of at least 1 t+1 OPT = 1 ⌈ 1 δ ⌉+1 OPT.

We complement the upper bound with a counter example, in which the optimal nδ -ND contract achieves at most δ+o(1) fraction of the unconstrained optimum.

Lemma 6. For any δ ∈ (0, 1), there exists an instance where the principal's optimal utility under any nδ -ND contract is at most a (δ + O( log log n logn )) fraction of the optimal utility under unconstrained contracts.

We outline the proof of Lemma 6 and the proof could be found in the full version of this paper [Ding et al., 2026]. To sketch, we consider the very same instance as that in Lemma 3, where the agents belonging to lower-indexed groups have higher success probability and payment threshold, and vice versa. Based on our definition of β-ND, we partition all agents into A and B according to a "pivot" group k0, as illustrated in Figure 2. Agents in groups with index smaller than or equal to k0 are paid the original amount as in the optimal unconstrained contract, while agents in groups with higher index are paid a uniform amount. We upper-bound OPTND by incentivizing as many agents from A, plus some consecutive groups fromB.

We also derive another lower bound that improves the bound in Lemma 6 in some cases, e.g., when δ ≥ 12 .

Lemma 7. For any δ ∈ (0, 1) and arbitrarily small ϵ > 0, there exists an instance where the principal's optimal utility under nδ -ND contracts is at most a ( 12 + ϵ) fraction of that under unconstrained contracts.

The details of the construction are given in our full version [Ding et al., 2026]. The idea is as follows: the upper bound shown in Lemma 5 requires payment disparities. We exploit such disparities by creating an agent with high contribution and payment (A) and a group of "free labor" with very low contribution and payment (B). In order to incentivize the powerful agent in A, the principal is forced to exclude all the agents in B.

To conclude, we provide an lower bound for δ = 1.

Lemma 8. There exists an instance where the principal's optimal utility under n-ND contracts is no greater than 0.629 fraction of that under unconstrained contracts.

Basically, the construction is analogous to that of Lemma 7, while we can additionally incentivize a portion of agents in B. The discussion could be found in the full version [Ding et al., 2026].

5 Tight Results for Two Agents

Our results in the previous section are grounded in large n. In this section, we shift our focus to the case of two agents, in which we are able to identify the optimal β-ND contract, and establish tight PoND(β) for all β ≥ 1.

Theorem 9. For any β ≥ 1, when there are two agents and the reward function f is submodular, the PoND(β) equals (1+ 1 √β+1 ), and this bound is tight.

The whole proof of this theorem is given in the full version [Ding et al., 2026]. The PoND(β) is characterized by enumerating all different ways to incentivize agent(s).

6 Conclusion

This paper investigates how varying degrees of nondiscrimination influence the optimal revenue in multi-agent contracts. We provide asymptotic bounds on the price of βnon-discrimination, characterizing the tradeoff between nondiscrimination and revenue. Our bounds are nearly tight for both the strict and relaxed cases when β is either small or large. However, determining the exact bound when β approaches n remains an open question for future research.

Our results uncover several promising directions for further study. For example, it would be valuable to extend our framework to other classes of reward functions, such as fractionally subadditive (XOS) and subadditive functions. It is also interesting to investigate alternative objectives, such as social welfare, social surplus, and various fairness criteria.

Acknowledgments

We thank Yiding Feng and Yingkai Li for valuable discussions, and the anonymous reviewers for their helpful comments. Bo Li is supported in part by the Hong Kong SAR Research Grants Council (Grant No. PolyU 15224823) and Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515011524).