Proof of Theorem 1, "The allocation is feasible", p. 12 — the limit allocation is feasible, full when valued, and goes to highest bidders
ProvedMultPacing.Existence.theorem_1_feasiblelimit-of-equilibriap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pacingsmoothed-game
Fix a pacing game and a convergent sequence of smoothed equilibria as in the proof of Theorem 1: , , , , , a pure-strategy Nash equilibrium of the -smoothed game, and , , , . Then the limit allocation is feasible:
- for every good ;
- for every good such that some buyer has ;
- if then is at least tied for the highest limit bid on :
These are the allocation conditions of Definition 2 at the limit point.
Formalization Note The sequence and its limits are bundled in IsSmoothedLimit; the sequence is assumed convergent, which is the paper's passage to a convergent subsequence.
Differences from the source:
- encoding: "this sequence must have a subsequence with a limit point … replace the sequence by this subsequence" → the sequence itself is assumed to converge; reason: the claims are stated after that replacement.
Preamble
import Mathlib import Definitions.Def_MultPacing_Existence_Limit
Formal statement
namespace MultPacing.Existence
theorem theorem_1_feasible {N G : Type*} [Fintype N] [DecidableEq N] [Fintype G]
(P : PacingGame N G) (ε H : ℕ → ℝ) (M : ℝ) (α : ℕ → N → ℝ) (αs : N → ℝ)
(xs ps ss : N → G → ℝ) (hlim : IsSmoothedLimit P ε H M α αs xs ps ss) :
(∀ j, ∑ i, xs i j ≤ 1) ∧
(∀ j, (∃ i, 0 < P.v i j) → ∑ i, xs i j = 1) ∧
(∀ i j, 0 < xs i j → ∀ k, αs k * P.v k j ≤ αs i * P.v i j) := by sorry
end MultPacing.Existence
Source
Conitzer, Kroer, Sodomka & Stier-Moses, Multiplicative Pacing Equilibria in Auction Markets, arXiv:1706.07151v5, p. 12 (PDF 12), proof of Theorem 1, claim "The allocation is feasible"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.