- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies dynamic contract design for a farsighted agent taking costly hidden actions in a finite-horizon MDP. The principal commits to a history-dependent policy specifying outcome-contingent payments and action recommendations. The paper shows that Markovian policies can be suboptimal and that approximating the best Markovian policy is NP-hard. It then uses promised continuation utility to represent history-dependent policies and develops a dynamic program over discretized promises. Finally, it adapts a payment-interpolation technique to convert an approximately incentive-compatible policy into an exactly incentive-compatible one with a bounded loss in the principal's utility. Together, these results yield a polynomial-time algorithm for computing an approximately optimal, incentive-compatible history-dependent policy.
Critical strengths
-
Thorough mathematical development. The paper provides a substantial theoretical treatment of dynamic hidden-action contracting, with detailed arguments covering policy representation, approximation, and incentive-compatibility restoration.
-
Complete theoretical result. The paper connects its structural results to a constructive approximation algorithm. In particular, the final guarantee combines a compact policy representation, polynomial-time computation, approximate optimality, and exact incentive compatibility.
Critical weaknesses
-
Limited conceptual and technical advance over existing approaches. My main concern is the limited additional understanding provided by the paper. The usefulness of history-dependent policies in dynamic principal-agent problems is already established in closely related work. In particular, Bernasconi et al. [1] demonstrate the limitations of Markovian policies and develop the promise-based representation and utility-discretization framework for farsighted persuasion. Against this background, extending the approach to dynamic contracting is a natural direction, and discretizing continuation utility to obtain a tractable dynamic program is a natural approximation strategy.
The approximate-to-exact IC conversion is potentially the most distinctive component, but it also uses the existing payment-interpolation technique of Dütting et al. [2]. Appendix E requires additional arguments to implement the transformation within a compact dynamic policy and to reconstruct honest promises; however, its central payoff comparison closely follows the existing one-shot argument. These extensions constitute mathematical work, but I find their technical increment limited. Overall, the paper does not make sufficiently clear what new insight into dynamic incentives, beyond the extension of an established framework to this setting, emerges from its results.
-
The presentation obscures the central ideas and the incremental contribution. Sections 4 and 5 introduce the full promise-form representation, several value functions, approximation-oracle requirements, and error parameters before providing a sufficiently accessible account of the underlying recursion. A reader must work through considerable notation to see how current payments and continuation promises define the dynamic program, why discretization relaxes IC, and which steps differ materially from prior work. An early recursive formulation or worked example, followed by an explicit comparison with the previous framework, would make both the method and its contribution easier to assess.
[1] Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, and Mirco Mutti. (2023). Persuading Farsighted Receivers in MDPs: The Power of Honesty. Advances in Neural Information Processing Systems, 36.
[2] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. (2021). The Complexity of Contracts. SIAM Journal on Computing, 50(1), 211–254.
Questions for authors
Which result do the authors consider the most surprising new insight of the paper, beyond extending existing promise-based and IC-repair techniques? In particular, what does it reveal about dynamic contracting that is not already suggested by the related literature? If the novelty of the result could be established, I would be more prone to accept.
We thank the Reviewer for the effort in evaluating our work.
The goal of our paper is to study the computational complexity of sequential contract design. Our main new insights concern the representation of an approximately optimal contract that can be computed in polynomial time.
The main additional challenge compared with the setting of Bernasconi et al. (2023) is that we cannot detect whether the agent deviated or not from the recommendations. Bernasconi et al. (2023) could naturally express IC as a "local" constraint, since their principal stops playing after a deviation; the agent's cumulative utility after a deviation Q^h(a,s) is thus independent from the principal's policy, and IC essentially reduces to ensuring that the utility following recommendations is larger than a fixed quantity. By contrast, in our setting Q^hπ(s,a,ι) depends on the principal's policy. This leads to more complex IC constraints, which in principle could prevent us from devising an FPTAS. The most novel result is that it is nonetheless possible to compute compact and approximately optimal policies in polynomial time.