Lemma 4.13 — nearby type vectors at which every agent's utility maximizer is unique
ProvedAlgMechDesign.Local.generic_unique_maximizersalgorithmic-game-theorymechanism-designp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a truthful mechanism for task scheduling. For every positive type vector and every there is a positive type vector with
such that, for every agent , the set is the unique maximizer of 's utility among the sets attainable against .
The lemma turns the weak inequalities of Lemma 4.7 into strict ones at a type vector arbitrarily close to any given one; the lower-bound argument for local mechanisms starts from such a type vector.
Formalization Note is Mathlib's norm on Fin n → Fin k → ℝ, the sup norm over agents and tasks. The mechanism is arbitrary: no measurability of the allocation or payment functions is assumed.
Preamble
import Mathlib import Definitions.Def_AlgMechDesign_Local_Model import Definitions.Def_AlgMechDesign_Local_Prices
Formal statement
namespace AlgMechDesign.Local
/-- Lemma 4.13, p. 180: for a truthful mechanism, every positive type vector `t` and every
`ε > 0` there is a positive type vector `t'` with `‖t − t'‖ < ε` (sup norm) at which, for every
agent `i`, `xⁱ(t')` is the unique maximizer of `i`'s utility among the attainable sets. -/
theorem generic_unique_maximizers {n k : ℕ} (alloc : (Fin n → Fin k → ℝ) → (Fin k → Fin n))
(pay : (Fin n → Fin k → ℝ) → Fin n → ℝ) (htr : IsTruthful alloc pay)
(t : Fin n → Fin k → ℝ) (ht : IsType t) (ε : ℝ) (hε : 0 < ε) :
∃ t' : Fin n → Fin k → ℝ, IsType t' ∧ ‖t - t'‖ < ε ∧
∀ i : Fin n, IsUniqueMaximizer alloc pay t' i := by sorry
end AlgMechDesign.Local
Source
Nisan, Ronen, Algorithmic Mechanism Design, Games Econ. Behav. 35, 2001, p. 180, Lemma 4.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.