Truthful single-parameter mechanisms: monotone rules with critical-value payments
ProvedAGT.single_parameter_characterizationNormalized incentive compatible mechanisms on a single-parameter domain are exactly the monotone rules with critical-value payments — Theorem 9.36 of Algorithmic Game Theory, and this mission's goal. Bids are scalars in ; a player values winning alternatives (those in her win set ) at her bid and everything else at ; the mechanism is normalized: losing bids pay . Then truthfulness holds if and only if both:
- monotonicity — raising a winning bid, the others fixed, keeps it winning (Definition 9.34);
- critical-value payments — for each player and each profile of the others' bids there is a value that every winning bid pays; and whenever some bid in loses, is the least upper bound of the losing bids — the threshold below which the player loses and above which she wins (Definition 9.35).
A note on the rendering. The book defines the critical value as and flags it "undefined" when the player wins at every bid, requiring in that case only that winners pay some constant. The formal statement renders exactly this: the constant-payment clause always, the IsLUB clause guarded by nonemptiness of the losing set — no junk supremum anywhere. Quantifiers place after the player and the others' bids, so the critical value may depend on both, but not on the player's own bid.
import Definitions.Def_agt_mechanism
namespace AGT
/-- Normalized incentive compatible mechanisms on a single-parameter domain
are exactly the monotone rules with critical-value payments (Theorem 9.36
of *Algorithmic Game Theory*, the capstone of the mission). Bids are
scalars in `[t₀, t₁]`; a player values winning alternatives at their bid
and everything else at `0`; the mechanism is normalized (losers pay `0`).
Then incentive compatibility holds if and only if
1. the rule is monotone — raising a winning bid keeps it winning — and
2. every winning bid pays a value `c` depending only on the others' bids,
which, whenever some bid loses, is the critical value: the least upper
bound of the losing bids.
The critical value is rendered through `IsLUB` guarded by nonemptiness of
the losing set, matching the book's caveat for the case where the player
wins at every bid (there the payment is merely some constant). -/
theorem single_parameter_characterization {A ι : Type*} [Fintype ι]
[DecidableEq ι] (W : ι → Set A) (t0 t1 : ℝ) (h01 : t0 ≤ t1)
(f : (ι → ℝ) → A) (p : ι → (ι → ℝ) → ℝ)
(hnorm : SPNormalized W t0 t1 f p) :
SPIncentiveCompatible W t0 t1 f p ↔
SPMonotone W t0 t1 f ∧ SPCriticalPayments W t0 t1 f p := by
sorry
end AGTRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back: single_parameter_characterization
Setting. is a finite type of agents with decidable equality (possibly empty); is an arbitrary type of outcomes (no finiteness or nonemptiness assumed). Given: a family of "winning sets" ; real numbers (this inequality is an explicit hypothesis, so the interval is nonempty); an outcome rule mapping real-valued type profiles to outcomes; and payments . For a type profile , say is in the box if for every ; write for with coordinate replaced by (so ). Agent 's valuation with type is the single-parameter function
i.e. times the indicator of the winning set (this is the literal unfolding used below; if it is identically ).
Standing hypothesis (SPNormalized W t0 t1 f p). For every profile in the box and every agent : if , then — losing agents pay exactly zero at box profiles. Nothing is assumed about payments of winning agents or outside the box.
Assertion. Under that hypothesis, the following if and only if holds.
Left side — SPIncentiveCompatible W t0 t1 f p: for every profile in the box, every agent , and every report ,
Concretely: (the true type if the outcome under the deviated profile lies in , else ) minus the payment at the deviated profile, is at most (the true type if the truthful outcome lies in , else ) minus the payment at the truthful profile. Non-strict inequality; deviations restricted to .
Right side — the conjunction of two properties:
-
SPMonotone W t0 t1 f: for every profile in the box, every agent , and all with : if then . Winning is upward closed in one's own report, others' coordinates held fixed at 's values (the original is overwritten and plays no role in this clause). -
SPCriticalPayments W t0 t1 f p: for every profile in the box and every agent , there exists a real (depending on and ) such that:- every winning report pays : for all with , one has ; and
- if some report loses (), then is the least upper bound — in the
IsLUBsense: an upper bound that is every upper bound — of the set . The supremum condition does not require itself to be a losing (or any) report, and no equation relates to payments at losing reports (those are by the standing hypothesis, at box profiles).
Guards and degenerate cases. If no report in loses, the IsLUB clause is vacuous and is pinned down only as the common payment of winning reports; if no report wins, the constant-payment clause is vacuous and is required only to be the least upper bound of the losing set (which is all of , forcing ). If is empty, every quantified condition on both sides is vacuous and the biconditional holds trivially. If is empty, no into exists, so the statement is vacuous for lack of an . All conditions on both sides are confined to profiles in the box and reports in ; the behavior of and elsewhere is unconstrained and irrelevant. The equivalence is exactly between the displayed incentive inequality and the conjunction (1) ∧ (2), given normalization; normalization itself is a hypothesis, not part of either side.
Confirmed by the mission captain (proposal self-audit).