Theorem 2, p. 11 — for H > M/ϵ the (ϵ,H)-smoothed pacing game has a pure-strategy Nash equilibrium
ProvedMultPacing.Existence.theorem_2Consider a pacing game with valuations and budgets , a smoothing parameter and the -smoothed pacing game, in which a strategy of buyer is a multiplier . Let be an upper bound on the sum of every buyer's valuations including the artificial good, that is
If , the smoothed game has a pure-strategy Nash equilibrium: a profile such that for every buyer and every .
The equilibria of the smoothed games are the approximations whose limit, as and , gives the pacing equilibrium of Theorem 1.
Formalization Note The artificial good gives buyer the value , which is why the bound reads . Definition 3 assumes ; this follows from whenever there is a buyer (then ), and with no buyer the conclusion holds trivially, so it is not a separate hypothesis.
Differences from the source:
- encoding: "M any upper bound on the sum of a buyer's valuations, including those for the artificial good" →
∀ i, ∑ j, v i j + 2ε ≤ M; reason: the artificial good is worth per unit and a buyer receives at most one unit. - encoding: Definition 3's standing → not a hypothesis; reason: implied by when there is a buyer, and the conclusion is trivial when there is none.
import Mathlib import Definitions.Def_MultPacing_Existence_Smoothed
namespace MultPacing.Existence
theorem theorem_2 {N G : Type*} [Fintype N] [DecidableEq N] [Fintype G] (P : PacingGame N G)
(ε H M : ℝ) (hε : 0 < ε) (hM : ∀ i, ∑ j, P.v i j + 2 * ε ≤ M) (hH : M / ε < H) :
∃ α : N → ℝ, IsSmoothedPNE P ε H α := by sorry
end MultPacing.Existence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.