Theorem 3, p. 8 — OSP CMON: a tree admits OSP payments iff no OSP-graph has a negative-weight cycle
ProvedOSPMech.SqrtLB.theorem_3Let be an implementation tree for agents with finite type domains , outcomes in a set , and costs for an agent of type and outcome . For each agent , let be the OSP-graph: its nodes are the profiles of , and there is an edge from to whenever both are compatible with a vertex labelled at which they diverge, with weight .
Then there is a payment function making obviously strategyproof if and only if, for every agent ,
This is the extension of Rochet's cycle monotonicity from direct mechanisms to extensive-form mechanisms ("OSP CMON"). Its "only if" direction applied to cycles of length two gives the monotonicity constraints used in the lower bound of Theorem 12.
Formalization Note. "Is an OSP mechanism for " is read as "some payment function makes it OSP", as in the proof (p. 24). The edge weight is that of the proof (p. 24) and of Observation 1; Definition 2 prints the opponents' profiles swapped. A cycle is a closed walk along edges.
import Mathlib import Definitions.Def_OSPMech_SqrtLB_Model
namespace OSPMech.SqrtLB
theorem theorem_3 {n : ℕ} {X : Type} (D : Fin n → Finset ℝ) (cost : Fin n → ℝ → X → ℝ)
(t : ImplTree n X) :
(∃ p : (Fin n → ℝ) → Fin n → ℝ, IsOSP D cost t p) ↔ ∀ i, NoNegCycle D cost t i := by sorry
end OSPMech.SqrtLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.