acceptodds
Under review as a conference paper at ICLR 2027

Linear Contract Design with Predictions

Abstract

We study the problem of contract design with predictions, where a principal delegates decision-making to an agent and aims to induce the agent to take actions that lead to outcomes in favor of the principal. The principal designs a contract that ties compensation to these outcomes. Faced with the contract, the agent chooses an action to maximizes his utility. While it is common that only the agent knows his action’s cost and the outcome distribution induced by his action, we consider a special case where the principal has access to prediction of this information. The principal's challenge in contract design is to pursue both consistency, i.e., achieving near-optimal performance if the prediction is highly accurate, and robustness, i.e., maintaining performance under inaccurate prediction. Our main contribution is the development of two algorithms that satisfy both consistency and robustness, along with the technical methodologies employed.

Primary area:
learning theory
Keywords:
Mechanism Design with Predictions, Contract Theory, Algorithmic Game Theory

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_YfRcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the linear contract design problem in the principal-agent framework augmented with machine learning predictions. The authors formulate a consistency-robustness tradeoff for prediction-aided contracting, propose two intuitive algorithmic solutions (discrete search and pessimistic breakpoint search), and provide complete theoretical guarantees including worst-case lower bounds, polynomial-time complexity, and consistency/robustness proofs. The paper is well-structured, the problem statement is clear, and all theoretical claims are rigorously proven.

Critical strengths
  1. Clear problem formulation and rigorous theory The paper clearly defines the prediction-augmented linear contract design problem and formalizes the critical tradeoff between consistency (optimality under accurate predictions) and robustness (worst-case performance under noisy predictions). All theorems, lemmas, and lower-bound analyses are solid and easy to follow.

  2. Complete theoretical guarantees The work provides full theoretical characterization for both proposed algorithms, including pseudo-polynomial guarantees for the first method and polynomial-time optimality for the second practical algorithm. The impossibility lower bound is a clean and valid theoretical contribution.

Critical weaknesses
  1. Limited technical novelty in algorithm design The core algorithms proposed in this work are overly straightforward and heuristic-driven. The discrete search and pessimistic breakpoint buffering strategies are standard robust optimization techniques and require minimal innovative design. There are no novel structural insights or algorithmic innovations tailored specifically to strategic principal-agent contracting. The algorithmic pipeline is intuitive rather than non-trivial or creative.

  2. Oversimplified problem setup with limited realism

  • The model relies on extremely restrictive assumptions that significantly limit its practical applicability: It only considers pure linear revenue-sharing contracts without fixed wages or hybrid compensation structures, which dominate real-world industrial contracting.
  • The agent’s action space and prediction error model are highly simplified and do not reflect real strategic behaviors, market volatility, or asymmetric information complexity in practical principal-agent scenarios.

Such oversimplification makes the theoretical results difficult to generalize to real contract design tasks.

Questions for authors

Q1. Your current model assumes pure linear sharing contracts and a multiplicative prediction‑error metric, while real‑world principal‑agent applications usually adopt hybrid contracts (fixed payment plus linear share) and exhibit complex, non‑multiplicative prediction noise. Could you explicitly explain which key theoretical guarantees (consistency, robustness bounds) would break, and what new technical obstacles would emerge, if you extend your framework toward these more practical real‑world contract settings?

Q2. Both of your algorithms build upon well‑known robust‑optimization heuristics: discretized parameter search and buffered breakpoint‑based filtering. Beyond applying existing prediction‑augmented algorithm templates to linear‑contract setting, what unique structural insight specific to strategic principal‑agent incentives enables your guarantees, which cannot be directly derived from prior general algorithms‑with‑predictions literature?

1 comment

We thank the reviewer for the valuable comments.

Q1: Hybrid contracts.

Under our current model, allowing an optional nonnegative fixed payment does not improve the optimal contract or affect our consistency and robustness guarantees. For a hybrid contract of the form t(r)=w+αrt(r)=w+\alpha r, with w≥0w\geq0,

=\arg\max_i\{\alpha R_i-c_i\}.$$ Thus, the fixed payment $w$ leaves the agent's best response unchanged while reducing the principal's profit. Consequently, $w=0$ is optimal, and both the full-information benchmark and our theoretical guarantees remain unchanged. We will clarify this observation in the revision. **Prediction error.** In our work, prediction error is a metric for quantifying prediction quality, rather than an assumption about how noise is generated. Our multiplicative error does not require multiplicatively generated noise, and we impose no independence or distributional assumptions. Within our model's input constraints, additive, correlated, and adversarial perturbations can also be evaluated using this metric. Moreover, multiplicative error is commonly adopted in prediction-augmented algorithmic settings (e.g., [1] ), and different error metrics can usually be related through suitable transformations. For instance, if the additive error satisfies $|\widehat R_i-R_i|\leq\epsilon_R\leq\epsilon$ and $|\widehat c_i-c_i|\leq\epsilon_c\leq\epsilon$, and the corresponding true quantities are bounded away from zero, these additive bounds can be translated into multiplicative error bounds. Therefore, we believe that the key insights underlying our algorithms can also be extended to other error metrics, such as additive error, with appropriate adjustments to the analysis. **Q2**: We thank the reviewer for raising this important question. Our key insight is that *contract design introduces a strategic-response layer that is absent from conventional prediction-augmented optimization*. In conventional settings such as ski rental and scheduling, predictions typically concern external or environmental parameters, and the algorithm directly determines its own actions based on these predictions. For example, in ski rental, the predicted skiing duration guides the algorithm's decision between renting and buying. In contrast, in our setting, predictions concern the agent's private rewards and costs. The principal cannot directly determine the agent's action; instead, she selects a contract parameter $\alpha$, and the agent subsequently chooses an action by maximizing its utility under the true parameters. Consequently, prediction errors affect not only the principal's contract decisions but also the agent's induced actions, potentially leading to substantial changes in the principal's realized profit. The sensitivity of the agent's best response to prediction errors therefore introduces distinctive challenges in contract design, which we summarize as follows: *Best-response uncertainty:* Prediction errors can change the agent's utility ordering, making the predicted best response different from the true one. *Breakpoint sensitivity:* Small prediction errors can substantially shift breakpoint locations and even change the number and order of critical breakpoints. (See section 3) *Profit guarantees:* Even without accurately recovering the true critical-breakpoint structure, which can vary across many possible scenarios, we need to ensure that the selected contract achieves near-optimal profit under the agent's true best response. These distinctive challenges motivate our algorithmic design. Algorithm 1 constructs an $\eta$-best-response set to account for uncertainty in the agent's action selection and evaluates candidates pessimistically. Algorithm 2 further exploits the structure of linear contracts: reward gaps determine both the sensitivity of pairwise breakpoints and the profit differences between actions. Based on this insight, it combines reward-separation filtering, tolerant breakpoints, and pessimistic evaluation to construct a polynomial-size candidate set. Importantly, our analysis establishes near-optimality even when the true optimal critical action pair is excluded from the candidate set. These contract-specific insights enable Algorithm 2 to achieve polynomial-time complexity without recovering the entire true critical-breakpoint structure. Thus, our contribution goes beyond simply applying existing prediction-augmented optimization techniques to linear contracts. We exploit the specific structure of linear contracts to develop algorithms and theoretical guarantees that explicitly account for prediction-induced changes in the agent's strategic best response and their impact on the principal's realized profit. [1]Xu, Chenyang, and Pinyan Lu. "Mechanism design with predictions." arXiv preprint arXiv:2205.11313 (2022).
Reviewer_zrBKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the contract design problem, in which a principal offers payments to incentivize an agent to take actions that maximize the principal's expected profit. The authors consider the learning-augmented setting, where the principal has access to predictions of the costs and expected rewards of the agent's actions. Their goal is to achieve both consistency, i.e., near-optimal profit when predictions are accurate, and robustness, i.e., a bounded approximation ratio even when predictions are inaccurate.

The authors show that directly optimizing a linear contract based on predictions can be unreliable, as small prediction errors may significantly affect the agent's best response.

They propose two algorithms. The first discretizes the space of linear contract parameters and pessimistically estimates the principal's profit using approximate best-response sets. Since this algorithm has pseudo-polynomial running time, they introduce a second polynomial-time algorithm that instead relies on selected predicted breakpoints.

Critical strengths
  • To the best of my knowledge, this is the first work to study consistency and robustness for linear contract design with predictions of action costs and expected rewards.
  • The paper is clearly written and easy to follow. Its overall structure is well organized, and the main ideas are presented intuitively.
  • The proposed algorithms are interesting and technically nontrivial. In particular, the breakpoint-based approach provides an interesting way to handle the sensitivity of the agent's best response to prediction errors.
Critical weaknesses
  • Unless I am missing something, Theorems 1 and 4 are incorrect as stated. For some parameter values allowed by their assumptions, the claimed upper bounds on the approximation ratio become negative, which is impossible. One can obtain this case with γ=1,R=2,M=3\gamma = 1, R = 2, M = 3 and η=1\eta = 1. This seems to arise from missing positivity conditions in the proofs. For instance, the step from (14) to (15) in Appendix B.2 requires 1/γ2−2η/(xγ)≥01/\gamma^2 - 2\eta/(x\gamma) \geq 0, which is not guaranteed by the assumptions. Similar issues appear in Theorem 4.
  • The lower bound in Theorem 2 appears to apply only to deterministic algorithms, since its proof constructs an adversarial instance based on the parameter chosen by the algorithm. This restriction should be made explicit in the theorem statement.
Questions for authors

My questions mainly concern the issues raised above.

  • Could you clarify how Theorems 1 and 4 can be corrected? In particular, which additional assumptions on the parameters are needed, and do the consistency guarantees still hold under these restrictions?
  • Regarding Theorem 2, does the lower bound extend to randomized algorithms? If not, do you have an idea what consistency and robustness guarantees might be achievable through randomization?

Minor comments:

  • The notation in the statement of Theorem 1 is ambiguous: it is unclear whether 1/AB means 1/(AB) or (1/A)B. Since the former is intended, I suggest using explicit parentheses to avoid confusion.
  • Some parentheses are too small relative to the expressions they enclose, particularly in the statements of Theorem 1 and Lemma 3. Using appropriately sized delimiters (e.g., \left and \right in LaTeX) would improve readability.
2 comments

We thank the reviewer for the careful reading and valuable comments.

Q1: Thanks for point these out. We agree that the original statements allow parameters for which the displayed approximation expressions are invalid. For the expression in Theorem 1, the required positivity condition is

\qquad\text{equivalently}\qquad \eta<\frac{1}{2M\gamma},$$ in addition to $M>R$. For Theorem 4, we require $\sigma,\delta>1$ and $$\eta<\min\\{ \frac{\sigma-1}{\sigma+1}, \frac{\delta-1}{2\gamma\delta} \\}.$$ These make both denominator factors strictly positive. The error-coverage condition $2R(\gamma-\gamma^{-1})\leq\eta$ is retained. We will state the admissible parameter regimes explicitly and revise them accordingly. *These added restrictions do not obstruct consistency.* For fixed $R$, take $$\eta=t^2,\qquad M=\lceil t^{-1}\rceil,\qquad \sigma=\delta=1+t.$$ For sufficiently small $t>0$, all the above positivity conditions hold and both displayed approximation expressions approach $1$ as $t\to0$. Thus, the consistency guarantee remains valid, and the unconditional $R$-robustness guarantee is unaffected. **Q2**: The current proof establishes a lower bound for deterministic algorithms. We will explicitly state this restriction in the revision. Deterministic algorithms are commonly considered as a starting point in classical contract design (e.g.,[1]). Randomization constitutes a substantive extension, and its benefits have been studied independently in prior work. For randomized extensions, we can establish the tight randomized robustness bound $$r_{\rm rand}=\frac{R\ln R}{R-1}<R,\qquad R>1.$$ A two-action instance distribution combined with Yao's minimax principle yields the lower bound, while the prediction-independent randomized sampler $$U\sim\operatorname{Unif}[0,1],\qquad \alpha_{\rm rand}=1-R^{-U}$$ achieves the matching upper bound. We further consider the following randomized contract. For $0<\varepsilon\leq1$, we choose $\alpha=\alpha_{\rm det}$ (the coefficient selected by the deterministic algorithm) with probability $1/(1+\varepsilon)$, and $\alpha=\alpha_{\rm rand}$ with probability $\varepsilon/(1+\varepsilon)$. Let $r(\gamma)$ denote the deterministic approximation guarantee under prediction error $\gamma$, and let $R$ denote its unconditional robustness bound. By linearity of expectation, $$r_{\rm mix}\leq \frac{1+\varepsilon}{1/R+\varepsilon/r_{\rm rand}} <R, \qquad r_{\rm mix}=O(\log R/\varepsilon),$$ and $$r_{\rm mix}(\gamma)\leq \frac{1+\varepsilon}{1/r(\gamma)+\varepsilon/r_{\rm rand}} \leq(1+\varepsilon)r(\gamma).$$ When the deterministic guarantee approaches $1$, the mixture achieves asymptotically at most *$(1+\varepsilon)$-consistency and $O(\log R/\varepsilon)$-robustness* for $R\geq2$. Smaller $\varepsilon$ prioritizes consistency, whereas larger $\varepsilon$ improves worst-case protection. We will incorporate these results into the revision. **Minor Comment:** We will use explicit fraction bars to eliminate the ambiguity in Theorem 1 and appropriately sized delimiters in Theorem 1 and Lemma 3. [1] Dütting, Paul, Tim Roughgarden, and Inbal Talgam-Cohen. "Simple versus optimal contracts." Proceedings of the 2019 ACM Conference on Economics and Computation. 2019.

I thank the authors for their response and clarifications. I will maintain the positive score.

Reviewer_eKxxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper defines specific mathematical structures for outcomes, agent actions, action costs, expected rewards, and linear contracts where the principal transfers a fraction of the reward to the agent. It also introduces breakpoints (where the agent is indifferent between actions) and critical breakpoints (where the agent's best-response action changes).

Sensitivity Challenge (Section 3): Visual analyses demonstrate that even small prediction errors can drastically alter the agent's best-response behavior, shift calculated breakpoints, and misidentify the order and number of critical breakpoints.

We design an algorithm using Discrete Search, and another Pessimistic Breakpoint Search algorithm. We also proved mathematically that reward upper and lower bounds are strictly necessary; without them, no algorithm can guarantee robustness or positive profit under arbitrary prediction errors.

Critical strengths

This paper is the first to integrate machine learning predictions into contract theory. It successfully introduces two original algorithms that achieve both consistency (near-optimal performance with accurate predictions) and robustness (guaranteed worst-case performance under arbitrary prediction errors). The main algorithm bridges a critical efficiency gap by achieving these dual guarantees in polynomial time while matching tight mathematical lower bounds.

Critical weaknesses

Restricted Scope: The framework is confined to single-agent linear contracts, which follows classical contract theory traditions (e.g., Carroll 2015) rather than multi-agent or non-linear settings.

Theoretical Constraints: The reliance on strict reward bounds is a known structural necessity in learning-augmented mechanism design; the paper's appendices formally prove that without these bounds, robustness is mathematically impossible.

Absence of Empirical Testing: As is standard for theoretical algorithmic game theory papers, the work is entirely analytical and omits real-world simulations or dataset evaluations.

Questions for authors

Algorithmic Complexity: Are the proposed algorithms polynomial-time? Does the program size scale polynomially with the outcome space? ○ Reasoning: This determines practical applicability.

1 comment

We thank the reviewer for the constructive feedback.

Q1: Algorithm 1 is pseudo-polynomial, whereas Algorithm 2 is polynomial-time.

Algorithm 1 uses O(MN)\mathcal O(MN) arithmetic operations, evaluating MM grid points in O(N)\mathcal O(N) time each. Its consistency analysis requires a resolution depending on the numerical reward bound RR, resulting in pseudo-polynomial dependence on RR.

Algorithm 2 uses O(N3)\mathcal O(N^3) arithmetic operations: it examines O(N2)\mathcal O(N^2) action pairs, each generating two candidates. For each candidate, the maximum predicted utility is computed once, and a further scan constructs the approximate-best-response set and its pessimistic value, all in O(N)\mathcal O(N) time.

Both algorithms take predicted expected rewards and costs as input, so contract selection has no additional dependence on the number of outcomes. If predictions are supplied as explicit distributions over OO outcomes, expected-reward computation adds O(NO)\mathcal O(NO) preprocessing, giving O(MN+NO)\mathcal O(MN+NO) for Algorithm 1 and O(NO+N3)\mathcal O(NO+N^3) for Algorithm 2.

W1: Single-agent linear contracts provide a natural starting point for incorporating predictions into contract design. They also align with our information model, as expected payments depend on expected rewards without requiring predictions of full outcome distributions. Even in this relatively simple setting, small prediction errors can shift breakpoints and alter the structure of critical transitions. Extending our framework to multi-agent settings and nonlinear contracts remains an important direction for future work.

W2: Although we assume bounded rewards, we also establish impossibility results showing that robustness cannot be guaranteed without these bounds. Moreover, upper and lower reward bounds are commonly adopted in prediction-augmented algorithmic settings (e.g., [1] ).

W3: Since our work primarily focuses on theoretical analysis, we did not include empirical experiments in the original submission.

Nevertheless, following the reviewer's suggestion, we have conducted two complementary synthetic experiments: 200 random instances with N=32N=32 actions and 200 two-action breakpoint stress instances. The stress instances have

\theta\sim\operatorname{Unif}[0.1,0.7],$$ with exact reward predictions and $\widehat c_2=c_2/\gamma$. Random instances use ordered random rewards/costs. We compare with Zero ($\alpha=0$) and Plug-in, which optimizes the predicted model directly. The metric is true profit divided by the full-information optimal linear-contract profit. | Instance group | Zero | Plug-in | Algorithm 1 | Algorithm 2 | |:---|---:|---:|---:|---:| | Random (small error) | 24.27 | 69.67 | 99.07 | 99.79 | | Random (medium error) | 24.27 | 69.32 | 97.20 | 89.06 | | Random (large error) | 24.27 | 69.20 | 71.79 | 70.29 | | Breakpoint stress (small error) | 18.74 | 10.00 | 99.13 | 95.23 | | Breakpoint stress (medium error) | 18.74 | 10.01 | 96.07 | 95.31 | | Breakpoint stress (large error) | 18.74 | 10.79 | 10.71 | 45.09 | Mean normalized profit (%). Regarding the empirical results, even small prediction errors can cause simple baselines to perform poorly due to the sensitivity of strategic responses in contract design. This effect is particularly pronounced in the breakpoint stress test. In contrast, both of our algorithms substantially outperform these two simple baselines in the small- and medium-error regimes. [1] Xu, Chenyang, and Pinyan Lu. "Mechanism design with predictions." arXiv preprint arXiv:2205.11313 (2022).
Reviewer_HyFmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies linear contracts in the setting where the Principal can access some information about the action cost and outcome distribution of the Agent. The paper discusses how the quality of information influences the contract offered, recognizing that the Agent’s best-response is sensitive to the contract offered. The paper makes consistency (i.e. if predictions are accurate and close to the true values, the contract should result in close to optimal utility for the Principal if they had full information) and robustness guarantees (the Principal is not harmed too much by inaccurate predictions).

Critical strengths

The paper has a number of strengths.

  • First, it is clearly written, and I generally found it easy to follow. It also seems to be technically sound.

  • The model was well-motivated, and it follows the general interest in exploring linear contracts that is growing in the literature.

  • To the best of my knowledge, this is the first paper that explicitly combines contracts with predictions so there is a certain element of novelty.

Critical weaknesses

While I generally thought the paper was interesting, I did have questions about the significance of the results.

  1. One of the claims of the paper is that a key technical contribution is robustness guarantees. But if I understand the findings in Theorems 3 and 5, robustness almost comes for free. In particular, we have that given how the algorithms are designed for any α∈[0,1−1/R]\alpha\in[0,1-1/R] one has a guarantee of RR. So even α=0\alpha=0 (which is like no contract) is RR robust.

  2. There are some lines of work (not cited in this paper) that I think are relevant.

Bacchiocchi et al, Learning optimal contract: How to exploit small action spaces, ICLR 2024: They look at robust contracts (and how they can be learned) if the agent is limited in their best-responses. The exact problem is a little different but there are clear parallels and complements between the papers and their focus on robustness and analysis of the Agent's best-response

There is also a relationship between contracting and Stackelberg games (e.g. Gan et al (2025), Robust Stackelberg Equilibria (https://arxiv.org/abs/2304.14990v3) ) Are there insights as to how to structure studied in Gan et al can be ported over to the contracting space when thinking about robustness?

Questions for authors

I would appreciate it if the authors could discuss the robustness results in more detail. In particular, I want to make sure I have not misunderstood anything. I would also like the authors to engage with the related research so as to better understand how their contributions differ and advance our understanding of contracting further.

1 comment

We thank the reviewer for the positive assessment and constructive suggestions.

W1: The reviewer is correct that, regarding robustness, α=0\alpha=0 is also RR-robust. However, robustness alone does not guarantee consistency. Consider two actions (R1,c1)=(1,0)(R_1,c_1)=(1,0) and (R2,c2)=(R,θ(R−1))(R_2,c_2)=(R,\theta(R-1)), where 0<θ<1−1/R0<\theta<1-1/R. The zero contract earns only 11, whereas the optimal contract earns R(1−θ)R(1-\theta), even with perfect predictions. Thus, our main contribution is not merely achieving robustness, but exploiting accurate predictions despite strategic-response sensitivity while retaining this worst-case guarantee.

W2: We thank the reviewer for pointing out these relevant works, which we will incorporate into the revised related-work section.

Comparison with Bacchiocchi et al. (ICLR 2024). A key difference lies in how the two approaches obtain and utilize information. The difference in information sources fundamentally changes how uncertainty can be addressed.

Bacchiocchi et al. learn through repeated interactions: the principal proposes different contracts, observes outcomes, and uses additional samples to refine estimates and learn approximate best-response regions. Their challenge is to learn a near-optimal contract with limited interaction.

In contrast, we study one-shot contract selection based on externally supplied predictions, without an exploratory phase to validate or refine them. Consequently, prediction errors must be accommodated directly rather than reduced through further sampling. Our algorithm must handle potentially incorrect predicted breakpoint structures while achieving consistency under accurate predictions and robustness under unreliable predictions. This motivates constructing candidate contracts directly from predictions and analyzing their realized profits, rather than first learning a representation of the best-response regions.

Comparison with Gan et al (2025). Gan et al study general Stackelberg games, primarily maximizing worst-case utility over approximate follower responses. We instead select a linear contract from predictions and measure consistency and robustness against the true full-information optimal linear contract.

Regarding algorithms, their polynomial-time construction in Corollary 1 requires an inducibility gap Δ>δ\Delta>\delta. Their general exact algorithm and gap-independent approximation scheme have exponential and quasi-polynomial running times, respectively. Under our model, no additional uniform positive inducibility-gap assumption is required. Algorithm 1 is pseudo-polynomial, whereas Algorithm 2 can be implemented using O(N3)\mathcal{O}(N^3) arithmetic operations by exploiting the specific structure of linear contracts.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.