Theorem 6 — for independent tasks the explicit clipped contract implements full effort with budget
OpenMultitaskContracts.Supplement.theorem_6contract-theorymultitask-contractsp2o-gran-per-chapterp2o-plan-paperp2o-v1principal-agent
Let be an instance of the multitask model with independent tasks. There is a contract that implements full effort with budget at most , and it can be computed and evaluated efficiently. Namely, the clipped contract of eq. (23),
with , , as in its definition, satisfies:
- for every performance (it is a bundle contract);
- implements full effort, i.e. is a best response of the agent to ;
- for every performance .
Theorem 5 shows that the exact Min-Budget optimum is NP-hard to compute; this theorem gives a constant-factor approximation in one pass over the tasks.
Formalization Note The budget bound is stated in as for every , with the published optimum over bundle contracts. "Computed and evaluated efficiently" is encoded by the explicit closed form: , , and are single sums over the tasks.
Differences from the source:
- encoding: there exists a contract … and it can be computed and evaluated efficiently → the explicit contract clippedContract I of eq. (23) (closed form from single sums over the tasks) has the three properties; reason: the explicit witness of the paper's proof implies the existence claim, and its closed form is what the proof's "Running time" paragraph calls efficient
- encoding: budget at most 10·OPT^Bun_MinBudget → ∀ Y, ENNReal.ofReal (ˆt Y) ≤ 10 * I.optMinBudget (bundle K); reason: the budget is max_Y ˆt(Y); optima live in ℝ≥0∞
Preamble
import Mathlib import Definitions.Def_MultitaskContracts_Instance import Definitions.Def_MultitaskContracts_bundle import Definitions.Def_MultitaskContracts_Instance_IsIndependent import Definitions.Def_MultitaskContracts_Supplement_clippedContract set_option autoImplicit false open scoped ENNReal
Formal statement
namespace MultitaskContracts.Supplement
/-- **Theorem 6** (§5.2, p.36, PDF 38). For independent tasks, there exists a contract that
implements full effort with budget at most `10·OPT^Bun_MinBudget`, and it can be computed and
evaluated efficiently: the explicit contract `ˆt` of Eq. (23) is a bundle contract (nonnegative),
implements full effort, and pays at most `10·OPT^Bun_MinBudget` on every performance.
E. Saig, I. Talgam-Cohen, Y. Tolkowsky, *Multitask Contracts: Realizing the Value of Bundling*,
STOC 2027 submission (held version, sha256 e991a51a…), Theorem 6, p.36, and eq. (23), p.37.
**Formalization Note.** The witness is `clippedContract I`, the closed form (23) built from
single sums over the tasks (`µ`, `σ`, `L`, `t_Sep`); this is how "computed and evaluated
efficiently" is encoded. The budget bound is `ofReal (ˆt(Y)) ≤ 10·OPT^Bun_MinBudget` for every
`Y` in `ℝ≥0∞` (published `Instance.optMinBudget` over `bundle K`). -/
theorem theorem_6 {K : Type*} [Fintype K] [DecidableEq K] (I : Instance K)
(hI : I.IsIndependent) :
clippedContract I ∈ bundle K ∧ I.Implements (clippedContract I) Finset.univ ∧
∀ Y : Finset K, ENNReal.ofReal (clippedContract I Y) ≤ 10 * I.optMinBudget (bundle K) := by sorry
end MultitaskContracts.Supplement
Source
Saig, Talgam-Cohen, Tolkowsky, Multitask Contracts: Realizing the Value of Bundling, STOC 2027 submission (held version, sha256 e991a51a…), Theorem 6, p.36 (PDF p.38); the contract is eq. (23), p.37 (PDF p.39)