Equal-Pay Contracts

This paper investigates multi-agent contract design under equal-pay constraints, providing tight polynomial-time approximation algorithms and hardness results for various reward functions while resolving open problems in unconstrained settings and quantifying the efficiency loss of fairness via a $\Theta(\log n / \log \log n)$ price of equality.

The Gist

Imagine you are the boss (the "Principal") of a massive construction project. You need a team of workers (the "Agents") to build a skyscraper. The building only gets finished if everyone does their part, but you can't see exactly what they are doing; you only see the finished building.

To get them to work hard, you have to promise them a share of the profit if the building is successful. This is a Contract.

The Problem: The "Fairness" Dilemma

In the old days of contract theory, the boss could be a bit of a tyrant or a genius negotiator. You could pay Worker A $100 because they are super strong, Worker B $5 because they are slow, and Worker C $0 because they are lazy. You tailor every payment perfectly to maximize your own profit.

But in the real world, this feels unfair. In schools, universities, and government jobs, there are strict rules: "Equal Pay for Equal Work." You can't just pay the star professor double what the new hire gets, even if the star brings in more grants. Everyone in the same role gets the same bonus.

This paper asks: If we force the boss to pay everyone the exact same amount (an "Equal-Pay Contract"), how much money does the boss lose? And can we still figure out the best way to do this without spending a lifetime on math?

The Core Findings (The "So What?")

The authors found three main things:

1. The "One-Size-Fits-All" Strategy is Harder, but Doable

If the project is simple (like just adding up bricks), you can easily calculate the perfect equal pay. But if the project is complex (where workers help or hinder each other in tricky ways), it gets much harder.

• The Good News: For a huge class of complex projects (called "Submodular" rewards), the authors found a fast algorithm. It's like having a GPS that doesn't find the absolute shortest path, but finds a path that is guaranteed to be within a few miles of the best one. You can compute this quickly.
• The Bad News: If the project is extremely complex (where workers have weird, non-linear interactions), it might be impossible to find a good solution quickly. It's like trying to solve a Sudoku puzzle that is so big it would take the universe's lifetime to finish.

2. The "Price of Equality" (The Cost of Being Fair)

This is the most fascinating part. The authors calculated exactly how much profit the boss loses by being forced to pay everyone the same.

• The Metaphor: Imagine you have a bucket of water (the total profit). If you can pour it however you want, you fill the bucket to the brim. If you have to pour it equally into 100 cups, some cups might overflow (waste) and some might be empty.
• The Result: The "Price of Equality" is surprisingly small, but not zero. It grows slowly as you add more workers.
  • If you have 10 workers, the loss is tiny.
  • If you have 1,000,000 workers, the loss is roughly 10 times larger than with 10 workers.
  • Mathematically, it's about $\frac{\log n}{\log \log n}$. In plain English: As the team gets huge, the boss loses a little bit more efficiency, but it's not a disaster. Fairness doesn't bankrupt the project; it just costs a manageable "tax."

3. The "Agent-Agnostic" Trap

The paper highlights a tricky technical problem. When you ask a computer to find the best group of workers to hire, the computer often looks at the tasks (e.g., "We need 5 people to lift beams") without caring who owns those tasks.

• The Analogy: Imagine you are hiring a band. You need a drummer, a guitarist, and a singer.
  • The Computer's View: "I need 3 people." It might pick 3 drummers because they are cheap and available.
  • The Reality: You need specific people. If the "drummer" is actually the same person as the "guitarist" (one person doing two jobs), the computer gets confused.
• The Insight: The authors realized that standard computer tools (Demand Queries) are "blind" to who owns the tasks. They had to invent new, clever ways to force the computer to look at the team structure, not just the tasks.

Why This Matters

This paper is a bridge between pure math and real-world policy.

1. For Policymakers: It proves that enforcing equal pay isn't a death sentence for efficiency. You can have a fair workplace without the boss losing their mind or the project failing. The "cost" of fairness is quantifiable and relatively low.
2. For Tech Companies: If you are building AI to manage teams or allocate resources, you can't just use the "unfair" optimal algorithms. You need these new "equal-pay" algorithms, or your AI will suggest paying the CEO 99% of the budget and the interns 1%.
3. For the Future: The authors also solved some old, unsolved math problems about how hard these contracts are to calculate, even without the fairness rules. They showed that for certain types of complex teamwork, finding the perfect solution is mathematically impossible to do quickly.

The Bottom Line

Fairness has a price, but it's a small one.

You don't have to choose between a fair workplace and a profitable one. While it makes the math harder and requires smarter algorithms, the authors showed that we can still run efficient, fair teams. The "Price of Equality" is just a small toll you pay to keep the peace, and thanks to this paper, we now know exactly how big that toll is.

Technical Summary

1. Problem Definition and Motivation

Context:
The paper addresses the problem of multi-agent contract design. A principal hires a team of $n$ agents to perform costly actions that jointly determine the success probability of a project. The project yields a reward of 1 upon success and 0 otherwise. The principal cannot observe individual actions (moral hazard) but observes the outcome.

The Constraint:
While prior work focuses on unconstrained contracts where the principal can tailor payments ($\alpha_i$) to each agent individually, real-world environments (public sector, academia, regulated industries) often impose fairness constraints. Specifically, the paper studies Equal-Pay Contracts, where all hired agents must receive the identical payment. A broader class, $\gamma$-equal-pay contracts, allows payments to differ by at most a constant factor $\gamma$.

Core Questions:

1. Algorithmic: Can we efficiently compute (near-)optimal equal-pay contracts for various classes of reward functions (Additive, Gross Substitutes, Submodular, XOS, Subadditive) under both binary and combinatorial action models?
2. Economic: What is the "Price of Equality" (PoE)? This is defined as the worst-case ratio between the principal's optimal utility under unconstrained contracts and the optimal utility under equal-pay contracts.

2. Methodology and Techniques

The authors employ a combination of algorithmic design, hardness reductions, and information-theoretic lower bounds.

Key Technical Challenges:

• Agent-Agnostic Demand Queries: A central difficulty is that standard demand oracles (which return a set of actions maximizing $f(S) - \sum p_j$) are "agent-agnostic." They treat actions as independent items and do not inherently respect the constraint that actions belong to specific agents. This makes it difficult to find action sets that are both high-reward and "agent-sparse" (involving few agents to minimize total payments).
• Combinatorial Actions: Unlike binary-action models (work/shirk), agents here can choose subsets of actions, creating complex interdependencies.

Key Techniques:

1. Constrained Demand Queries: For submodular rewards, the authors design a recursive "distorted greedy" procedure (Algorithm 1) that approximates demand queries subject to a cardinality constraint on the number of participating agents. This ensures the selected action set is both rewarding and involves a limited number of agents.
2. Bucketing and Scaling: For the Price of Equality analysis, they develop a bucketing procedure (Algorithm 3) that groups agents based on their payments in an optimal unconstrained contract. They use the Scaling-for-Existence Lemma to show that within these buckets, an equal-pay contract can induce an equilibrium with a constant fraction of the bucket's reward.
3. Hardness via Indistinguishability: To prove inapproximability for XOS rewards, they construct instances where the reward function depends on a hidden subset of "special" agents. They show that demand queries are unlikely to reveal this hidden structure (informative queries are exponentially rare), making it impossible for any polynomial-time algorithm to distinguish between instances where a high-reward solution exists and those where it does not.
4. Reduction from Coverage Problems: For Gross Substitutes (GS) hardness, they reduce from the Maximum Coverage problem, mapping the coverage structure over agents to a matroid structure over actions while preserving binary-like behavior.

3. Key Contributions and Results

The paper provides a comprehensive landscape of algorithmic tractability and hardness, summarized in the following categories:

A. Algorithmic Results (Positive)

• Submodular Rewards (Combinatorial Actions): The authors present a polynomial-time constant-factor approximation algorithm for equal-pay contracts. This is significant because the unconstrained version is known to be hard to approximate better than a constant factor, and no PTAS exists.
• XOS Rewards (Binary Actions): A polynomial-time constant-factor approximation algorithm is provided for equal-pay contracts.
• Additive Rewards: Optimal equal-pay contracts can be computed in polynomial time.

B. Hardness Results (Negative)

The paper resolves two major open problems in the unconstrained contract design literature, showing that the hardness persists even under the equal-pay restriction:

• No PTAS for Gross Substitutes (GS): Even for the strict subclass of Matroid Rank functions, there is no Polynomial-Time Approximation Scheme (PTAS) for the optimal contract problem (unless P=NP). This holds for both unconstrained and equal-pay contracts.
• No Constant-Factor Approximation for XOS (Combinatorial Actions): For XOS rewards with combinatorial actions, no algorithm using polynomially many value/demand queries can achieve a constant-factor approximation. This is the first separation between binary and combinatorial actions for unconstrained contracts regarding XOS rewards.

C. Price of Equality (PoE)

The authors quantify the loss incurred by fairness constraints:

• Tight Bound for XOS/Submodular: The PoE is $\Theta(\frac{\log n}{\log \log n})$.
  • Upper Bound: Holds even for XOS rewards with combinatorial actions.
  • Lower Bound: Holds even for additive rewards with binary actions.
• Subadditive Rewards: The PoE can be much larger, with a lower bound of $\Omega(\sqrt{n})$.

4. Significance and Impact

1. Resolution of Open Problems: The paper settles long-standing open questions regarding the tractability of optimal contracts in unconstrained settings. Specifically, it proves that XOS rewards with combinatorial actions are inapproximable (unlike the binary case) and that Gross Substitutes do not admit a PTAS.
2. Fairness vs. Efficiency: It provides a rigorous theoretical foundation for the "cost of fairness." The $\Theta(\frac{\log n}{\log \log n})$ bound suggests that while equal-pay contracts are not optimal, the loss is relatively mild (polylogarithmic) for standard reward classes, justifying their use in regulated environments.
3. Methodological Innovation: The development of constrained demand queries (optimizing over action sets with a limit on the number of agents) offers a new tool for algorithmic mechanism design that could be applicable to other problems involving agent-specific constraints.
4. Robustness: The results extend to "BEST" objectives (Beyond Standard, e.g., social welfare, reward maximization), not just profit maximization, particularly for Gross Substitutes.

Summary Table of Results

Reward Class	Action Model	Unconstrained (Known/New)	Equal-Pay (New)	Hardness/Approx
Additive	Binary/Combinatorial	P (FPTAS)	P	Optimal computable
Gross Substitutes	Combinatorial	O(1)-apx, No PTAS	O(1)-apx, No PTAS	No PTAS (Main Thm 2)
Submodular	Combinatorial	O(1)-apx, No PTAS	O(1)-apx	Constant-fact. approx (Main Thm 1)
XOS	Binary	O(1)-apx	O(1)-apx	Constant-fact. approx
XOS	Combinatorial	Open	No O(1)-apx	Inapproximable (Main Thm 3)
Subadditive	Any	No O(1)-apx	No O(1)-apx	Inapproximable

Price of Equality: $\Theta(\frac{\log n}{\log \log n})$ for XOS/Submodular; $\Omega(\sqrt{n})$ for Subadditive.

In conclusion, this paper establishes that while equal-pay constraints introduce computational challenges, efficient constant-factor approximations are possible for many natural reward classes. Furthermore, it demonstrates that the inherent hardness of contract design in unconstrained settings is often driven by the structure of the reward function itself, rather than the flexibility of payment schemes.