Contract Design Under Approximate Best Responses

We believe there is misunderstanding on the main contributions of our paper and the challenges in obtaining efficient optimization algorithms.

• Computing robust equilibria is much harder than standard one. The Reviewer claims: “The principal knows the agent's deviation, which makes it way easier to tackle and not very far from analyzing a best response.” We disagree with this statement, as it contradicts known results for similar bilevel problems, such as Stackelberg games and Bayesian persuasion, where computing an equilibrium in the best-response case is computationally easy, but hard for worst-case robust approximate best-response.

• Main contribution of our paper. The Review seems mostly focused on the learning part, while it seems to ignore the more “surprising” computational results. As should be clear from our writing (see, e.g., the abstract), the learning part is not the main contribution but rather a valuable addition. While we agree with the Reviewer that the learning part alone is not enough for ICML, we hope the Reviewer would agree that it includes nice extensions and simplifications with respect to the approach by Zhu et al.

• On agent’s behavior. The Reviewer claims: “The paper assumes that the agent picks the principal's worst action within the set $A^\delta(p)$. This assumption does not make any sense from a rational agent's perspective, does not exist in the literature and seems to be there only to allow the proofs to work.” We respectfully, but strongly, disagree on this statement. First, the assumption is not intended to be predictive of the agent's behavior: rather, it is a worst-case perspective based on the fact that the agent's behavior is unpredictable within a small $\delta$ utility difference (e.g., due to noise in the model parameters or the agent's perception of their own utility). In such a scenario, the principal adopts a worst-case approach by computing a robust contract. In this way, the utility the principal secures, OPT($\delta$), is a lower bound on the actual utility the principal will obtain. Indeed, this robust equilibrium model is not our own invention, it has been previously proposed and studied in both Stackelberg and Bayesian persuasion settings (Gan et al., 2023; Yang & Zhang 2024).

Re: "I am concerned about Remark 2.."

The Reviewer’s observation is right, if the agent is allowed to break ties in any way when indifferent among multiple $\delta$-best response, then an optimal contract for the principal may not exist. However, Remark 2 is concerned with the learning part, where the goal is not to compute an optimal contract, but rather to attain no-regret against an optimal $\delta$-robust contract. Notice that such a contract always exists, given the correctness of Algorithm 1. Thus, non-existence is not an issue. Intuitively, the extension of Algorithm 2 informally described in Remark 2 has to deal with the fact that the feedback actually observed by the algorithm is not about the $\delta$-best response that minimizes principal’s utility, but about some other $\delta$-best response instead. This requires the adoption of an adversarial regret-minimization algorithm, but it intuitively does not detriment the regret against an optimal $\delta$-robust contract, since the observed $\delta$-best responses cannot be worse than the one played under a $\delta$-robust contract. Due to space constraints, we cannot provide a complete formal proof of this to the Reviewer, but we will certainly add it in the final version of the paper.

Re: "Comparison with Zhu et al. (2023)"

As we have already highlighted, the learning part is not our main contribution. However, our algorithm builds on Zhu et al. to deal with $\delta$-best responses of the agent. In doing so, it provides a simple algorithmic approach and analysis. While we agree that our approach is still far from practical applications, it should be acknowledged that a simpler approach and analysis are always beneficial.

Re: "Could you explain how it makes a difference to assume that the agent picks the worst action for the principal in as long as $\delta$ is known? I am not sure it makes it a harder problem as compared to a best-responsive agent."

Computing a robust contract when $\delta$ is known still poses several challenges. For instance, in Stackelberg games, computing a robust commitment is computationally intractable even when $\delta$ is known. This is because, unlike the non-robust case, the principal’s utility function is piecewise linear over an exponential number of regions (see, for instance, the hard instances in the reduction of Gan et al. (2023)). This contrasts with classical contract design, where the utility is piecewise linear over $n$ regions (one per action). It is only thanks to our analysis, which exploits the particular structure of contract design (not available in other bilevel problems), that we obtain a polynomial-time algorithm.

Re: "The online learning setting assumes the follower's action to be invisible, rendering the follower's response model a "black box" and thus an exponential dependency is unavoidable. My question is, If the follower consistently takes the worst -suboptimal action (from the leader's perspective), and the leader can observe the follower's taken action. Can the leader leverage this adversarial behavior to gain more information about the follower's cost structure? If so, could this lead to an improved regret bound compared to the standard setting?"

We thank the Reviewer for the question. Learning an optimal contract with observable actions in a polynomial number of queries (with respect to the parameters of the problem instance) remains an open problem, even in the non-robust case. Exponential lower bounds exist in Stackelberg games, but it is unclear whether they extend to contract design due to the particular structure of the utilities. However, we do not believe that the adversarial behavior of the follower would benefit the principal, since when $\delta$ is close to zero, the problem nearly reduces to the classical one (see Proposition 1).

Re:"Can the simple discretization apply to non-robust settings? "

Yes, the simple discretization can be employed in the non-robust version of the problem. Intuitively, it is sufficient to follow the same steps as in the proof of Theorem 2, with $\delta$ going to zero.

Re: "Can algorithm 2 take $\delta=0$?"

No, when $\delta=0$ the $\delta$-best responses are not well defined. (Please refer to the first equation in Section 2.2.)

Re: "Why does the regret definition $\mathcal{R}_T(\mathcal{C})$ coincide with Zhu et al's? …."

The Reviewer is right; we will fix this in the final version. Only the baseline (i.e., OPT) in that regret definition coincides with that considered by Zhu et al. (2023). However, when $\delta$ is approximately zero, the two regret definitions essentially coincide. Indeed, as $\delta$ tends to zero, the problem nearly reduces to the non-robust one (see Proposition 1). **

Re: "Can you elaborate more on which part of the results in section 5 can be applied to the non-robust setting?"

“As previously discussed, when $\delta$ is approximately zero, our problem essentially coincides with that of Zhu et al. (2023). Thus, our results can be extended to the non-robust problem. However, this requires addressing some technical details, since when $\delta = 0$, the agent's best response regions do not coincide with those in the non-robust case due to the strict inequality “>” in the definition of $A^\delta(p)$.

Re: "Challenges in Our Setting and Technical Novelty.”

We believe that the computational results presented in Section 4 are rather “surprising”. Indeed, such positive results are unexpected, as very similar problems are computationally intractable. In particular, computing an optimal $\delta$-robust commitment in Bayesian persuasion and Stackelberg game settings is known to be computationally intractable (see Gan et al. (2023), Yang & Zhang (2024)). Our case actually appears even more challenging because the strategy space, $\mathbb{R}_+^m$ is much less amenable compared with $\Dleta_m$ in Bayesian persuaison and Stackelberg games. And because of this, the quasi-polynomial-time approximation schemes (QPTAS) developed in the previous works do not apply to our setting. We initially conjectured that our setting was harder and attempted to prove that it was inapproximable.

It was only after a series of attemps and very careful analysis, we discovered that contract design scenarios are actually more structured and allow for efficient computation. Based on these unique structures, our method works entirely different from previous approaches to computing robust equilibria. It revolves around fixing the $\delta$-robust best response and the actual best response, then computing an optimal robust contract for such a scenario. By iterating this process for each pair of actions and solving an LP at each step, we prove that it is possible to recover an optimal robust contract. Our algorithm is guaranteed to work in contract design due to the particular structure of the principal’s and agent’s utilities. This approach is entirely new compared to existing ones, which, for example, require solving an exponential number of LPs. Indeed, notice that a similar approach cannot be employed in the settings studied in previous works.

We agree with the Reviewer that some of the techniques we adopted are common in algorithmic game theory, such as solving a set of LPs. However, the main contribution and most challenging step of our work is determining which LPs need to be solved to recover an optimal robust contract. (Indeed, a naive approach would require solving exponentially many LPs!) Hence, while the algorithmic approach may appear standard, this is in fact not the case for the analysis, which, as highlighted above, is entirely disjoint from previous works on the topic and requires non-trivial arguments.