Proposition 2.1, p. 10 — ex-post IC-IR payments exist exactly for monotone allocations
ProvedInterdepSOS.RSV.proposition_2_1ex-post-incentive-compatibilitymechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let each agent's value of service be nonnegative, weakly increasing in all signals, and strictly increasing in her own signal. For any deterministic served-set rule , a payment rule depending only on reported signals makes ex-post incentive compatible and individually rational if and only if each agent's chance of being served is monotone in her own reported signal:
This characterization turns a monotonicity result for a deterministic allocation into an existence result for truthful and individually rational payments.
Preamble
import Mathlib import Definitions.Def_InterdepSOS_RSV_Setting
Formal statement
namespace InterdepSOS.RSV
theorem proposition_2_1 {n : ℕ} (v : Valuation n) (hv : IsValuation v)
(x : Allocation n) :
(∃ p : Payment n, IsExPostIC v x p ∧ IsExPostIR v x p) ↔
IsMonotoneAlloc x := by sorry
end InterdepSOS.RSV
Source
Eden, Feldman, Fiat, Goldner, Karlin, Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue, arXiv:1903.08384v2 (2019), p. 10, Proposition 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.