Theorem 1 — under independence, over the prefixes of the stand-alone order
OpenMultitaskContracts.Supplement.theorem_1contract-theorymultitask-contractsp2o-gran-per-chapterp2o-plan-paperp2o-v1principal-agent
Let be an instance of the multitask model with independent tasks on a finite nonempty task set . The stand-alone payment of task is (Definition 4), the incentive price of a strategy is (Definition 3), and (eq. (10)).
Let be the tasks in ascending order of stand-alone payment, with ties broken arbitrarily, and let . Then
The identity holds for every such order.
Only the prefixes of one sorted order need to be examined instead of all deviations. This gives the algorithm for optimal Min-Pay contracts with heterogeneous independent tasks (Corollary 2).
Formalization Note The order is any bijection along which the stand-alone payment is non-decreasing, and , so ; ranges over .
Differences from the source:
- encoding: the tasks in ascending order of stand-alone payment, with ties broken arbitrarily → every bijection e : Fin |K| ≃ K with standAlone ∘ e monotone, S_ℓ = e({i : i < ℓ}), ℓ : Fin |K|; reason: an ordering of a finite set is a bijection with an initial segment of ℕ; quantifying over every monotone e is "ties broken arbitrarily"
- encoding: §4.1 standing assumptions (independent tasks; t⋆ over the deviations of K) → hypothesis I.IsIndependent and [Nonempty K]; reason: the section title "Independent Tasks" and the proof's "By independence" make independence a standing assumption; t⋆ = max over S ⊊ K needs a deviation, so K is nonempty
Preamble
import Mathlib import Definitions.Def_MultitaskContracts_Instance import Definitions.Def_MultitaskContracts_Instance_IsIndependent import Definitions.Def_MultitaskContracts_Instance_incentivePrice import Definitions.Def_MultitaskContracts_Instance_tStar import Definitions.Def_MultitaskContracts_Instance_standAlone set_option autoImplicit false open scoped ENNReal
Formal statement
namespace MultitaskContracts.Supplement
/-- **Theorem 1** (§4.1.2, p.14, PDF 16). Let `k(1), …, k(|K|)` be the tasks in ascending order
of stand-alone payment (Definition 4), with ties broken arbitrarily. Then
`t⋆ = max_{0≤ℓ<|K|} θ(S_ℓ)`, where `S_ℓ := {k(1), …, k(ℓ)}`.
E. Saig, I. Talgam-Cohen, Y. Tolkowsky, *Multitask Contracts: Realizing the Value of Bundling*,
STOC 2027 submission (held version, sha256 e991a51a…), Theorem 1, p.14.
**Formalization Note.** §4.1 assumes independent tasks (`hI`), and `t⋆` (published
`Instance.tStar`, eq. (10)) needs `K` nonempty. The order is any bijection
`e : Fin |K| ≃ K` along which the stand-alone payment (published `Instance.standAlone`) is
monotone; quantifying over every such `e` is "ties broken arbitrarily". `ℓ` ranges over
`Fin |K|`, i.e. `0 ≤ ℓ < |K|`, and `S_ℓ` is the image under `e` of `{i : i < ℓ}`
(`S_0 = ∅`). `θ` is the published `Instance.incentivePrice`. -/
theorem theorem_1 {K : Type*} [Fintype K] [DecidableEq K] [Nonempty K] (I : Instance K)
(hI : I.IsIndependent) (e : Fin (Fintype.card K) ≃ K) (he : Monotone (I.standAlone ∘ e)) :
I.tStar = (Finset.univ : Finset (Fin (Fintype.card K))).sup'
(Finset.univ_nonempty_iff.2 ⟨⟨0, Fintype.card_pos⟩⟩)
(fun ℓ => I.incentivePrice
(((Finset.univ : Finset (Fin (Fintype.card K))).filter (fun i => i.val < ℓ.val)).map
e.toEmbedding)) := 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 1, p.14 (PDF p.16)