Appendix A, proof of Proposition 1, p. 38 — rounding loses at most ε/δ of each payment: t(v′) ≥ t(v) − ε/δ
ProvedApproxIC.Rounding.payment_loss_boundapproximate-incentive-compatibilitymechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rounding
Let be an -incentive compatible, individually rational mechanism on , let , and let select maximizers
Then for every , with ,
In words: the menu item chosen by type after the payments are discounted by charges at most less than the item that type was originally assigned. This is the estimate that controls the revenue lost by Nisan's rounding.
Formalization Note The selection is the map vs, assumed to take values in and to attain the maximum for each , as on the page.
Preamble
import Mathlib import Definitions.Def_ApproxIC_Rounding_Setting
Formal statement
namespace ApproxIC.Rounding
/-- Appendix A, proof of Proposition 1, p. 38: for an ε-IC mechanism `m = (x, t)`, `δ ∈ (0,1)` and
`v′ = v⋆_δ(v) ∈ argmax_{w ∈ S} {v · x(w) − (1 − δ) t(w)}` (the map `vs`), one has
`t(v′) ≥ t(v) − ε/δ` for every `v ∈ S`. -/
theorem payment_loss_bound (M : Model) (hM : M.Standing) (ε δ : ℝ) (m : Mech)
(hm : m ∈ Mset M ε) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) (vs : ℝ → ℝ)
(hvs : ∀ v ∈ Set.Icc 0 M.vbar, vs v ∈ Set.Icc 0 M.vbar ∧
∀ w ∈ Set.Icc 0 M.vbar, v * m.x w - (1 - δ) * m.t w ≤ v * m.x (vs v) - (1 - δ) * m.t (vs v)) :
∀ v ∈ Set.Icc 0 M.vbar, m.t v - ε / δ ≤ m.t (vs v) := by sorry
end ApproxIC.Rounding
Source
Balseiro, Besbes, Castro, Mechanism Design under Approximate Incentive Compatibility, arXiv:2103.03403v2 (2022), p. 38, Appendix A, proof of Proposition 1, third display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.