PaperlayerView exact revision on arXiv

Source-linked AI summary

Pacing Equilibria in Abstract Mechanisms

Salam Afiouni, Christian Kroer

arXiv:2609.27285v1cs.GT

TL;DR

The paper asks whether first-price pacing’s strong single-item properties extend to richer platform mechanisms. It develops a theory across position auctions, bid-maximizing pay-your-bid mechanisms, and abstract mechanisms, finding both a failure of the single-item market-equilibrium interpretation and conditions that recover many favorable properties.

  • Problem

    It is unclear whether the structural and computational properties of first-price single-item pacing extend to richer platform mechanisms, where automated budget management governs participation across allocation opportunities.

    Source: §1 · p. 2, §7 · p. 25

  • Method

    The paper analyzes pacing equilibria across position auctions, bid-maximizing pay-your-bid mechanisms, and abstract mechanisms using convex-program characterizations, payment monotonicity, smoothing, and budget-adjustment dynamics.

    Source: §1.1.1 · p. 3, §1.1.3 · p. 4, §7 · p. 25

  • Results

    Even first-price position auctions can break the single-item market-equilibrium interpretation, while bid-maximizing pay-your-bid mechanisms retain uniqueness and convex-program characterizations under mild convexity assumptions.

    Source: §7 · p. 25

  • Takeaways & Limitations

    Pacing’s equilibrium properties depend on the mechanism that converts scaled bids into outcomes and payments, so the single-item model is not a reliable benchmark for richer platform mechanisms.

    Source: §7 · p. 25

    For the original abstract mechanism, equilibrium existence is guaranteed for some tie-breaking rule, not for every rule.

    Source: §5.1.4 · p. 16

Abstract

from arXiv · show

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

1 Introduction

The paper develops a mechanism-level theory of pacing equilibria: some single-item guarantees fail in richer settings, while suitable mechanism conditions recover important structural, computational, and economic properties.

1 Introduction

  • The paper’s motivation is that pacing controls spending across many allocation events, but simultaneous buyers’ expenditures interact through competition and mechanism rules.Pacing scales bids uniformly to manage campaign budgets; the market-level interaction determines implications for spending, revenue, welfare, stability, and computation.Source: §1 · p. 2

1.1 Contributions

  • The framework studies pacing across increasingly general mechanisms, from position auctions and bid-maximizing pay-your-bid mechanisms to abstract allocation and payment rules.The abstract setting includes mechanisms such as all-pay, entry-fee, and capacity-constrained resource-allocation mechanisms when the stated payment monotonicity condition holds.Source: §1 · p. 3, §1.1.3 · p. 4

1.1.1 A limitation of the single-item benchmark.

  • Multiple ranked slots can break the market-equilibrium interpretation of first-price pacing, even under utilities that account for position-auction structure.The paper identifies a sufficient failure condition involving positive-quality slots and distinct positive paced bids; the condition is generally met outside degenerate cases.Source: §1.1.1 · pp. 3–4

1.1.2 A convex-program theory for bid-maximizing pay-your-bid mechanisms.

  • Bid-maximizing pay-your-bid mechanisms admit pacing equilibria characterized by convex programs, extending tractability beyond single-item auctions.Under mild convexity assumptions, equilibria are unique and Pareto efficient, satisfy additive liquid-welfare guarantees, and can be approximated using a bid-maximization oracle.Source: §1.1.2 · p. 4

1.1.3 Existence and structure in abstract mechanisms.

  • For abstract mechanisms, payment monotonicity supports equilibrium existence, while smoothing and appropriate tie-breaking address discontinuities.With additional mild conditions and appropriate tie-breaking, the paper also establishes uniqueness, revenue maximization among budget-feasible pacing vectors, and shill-proofness.Source: §1.1.3 · p. 4

1.1.4 Spending-based equilibrium computation.

  • Spending-based updates converge to approximate pacing equilibria under payment-response conditions, using realized expenditure rather than full market or mechanism knowledge.The paper also establishes time-averaged approximate equilibrium for multiplicative-weights updates under a weaker payment regularity condition.Source: §1.1.4 · p. 5

1.2 Implications for Platform Design

  • Pacing’s equilibrium properties depend on how a mechanism translates scaled bids into allocations and payments, so the single-item model need not predict richer platform settings.The identified conditions are intended to guide automated budget management in complex environments, including large-scale ranking, matching, and constrained optimization routines.Source: §1.2 · p. 5

1.3 Additional Related Literature

  • The paper extends first-price pacing and Eisenberg-Gale equilibrium analysis beyond single-item auctions, and establishes liquid-welfare guarantees directly at pacing equilibrium.For bid-maximizing pay-your-bid mechanisms, every pacing equilibrium achieves at least one half of optimal liquid welfare.Source: §1.3 · p. 6

2 Model

The model represents each buyer with a budget and valuation over feasible outcomes, then applies a multiplier to scale bids before the mechanism determines allocations and payments.

Model

  • Each buyer has a hard budget and a bounded valuation over a compact feasible outcome space, with valuations closed under positive scaling.The buyer’s valuation depends only on her payoff-relevant component of the outcome.Source: §2 · p. 7
  • A pacing multiplier in [0, 1] scales each buyer’s valuation uniformly, and the mechanism maps the resulting bids to outcomes and payments.The model assumes individual rationality, invariance to zero bids, and continuity of a buyer’s payment as others’ bids vanish.Source: §2 · p. 7
  • A pacing vector is budget-feasible when every buyer’s payment is at most her budget; it is an equilibrium when buyers below budget are unpaced.The no-unnecessary-pacing condition requires a buyer’s multiplier to equal one if she would not exhaust her budget when bidding her true value.Source: §2 · p. 7
  • The model encompasses divisible goods, shared-capacity resources, and bundled allocations, including first-price single-item and position auctions as special cases.Examples include cloud, bandwidth, or inventory allocation, and bundles whose value need not decompose across their elements.Source: §2 · pp. 7–8

3 Position Auctions and the Market-Equilibrium Interpretation

The section models first-price position auctions with ranked slots and studies whether their pacing outcomes retain the single-item market-equilibrium interpretation. It shows that this correspondence can fail under standard quasilinear utilities.

Model.

  • A first-price position auction assigns ranked slots by sorting paced bids, with slot qualities determining buyers’ values and payments.Ties are split fractionally, and each buyer receives one slot per auction.Source: Model · p. 8

3.1 Relationship to Market Equilibrium

  • Under quasilinear utilities, an outcome may fail market equilibrium when a buyer receives part of a positive-quality slot while a lower-quality slot has a smaller positive price.The condition is generally met with at least two positive-quality slots and two distinct positive paced bids; tied positive bids or a single positive-quality slot are examples of degenerate cases.Source: §3.1 · p. 9
  • A position-auction pacing equilibrium can fail to be a position-aware market equilibrium, even when buyers’ demand accounts for the one-slot-per-auction constraint.The paper defines position-aware buyers as optimizing quasilinear utility over budget-feasible allocations subject to that constraint.Source: §3.1 · p. 9

3. Position Auctions and the Market-Equilibrium Interpretation

  • Moving from one advertising slot to multiple ranked positions is sufficient to break the single-item market-equilibrium interpretation and motivates mechanism-level conditions for guarantees.The broader theory identifies conditions that restore structural and computational guarantees for mechanisms including first-price position auctions.Source: §3 · p. 8, §3.1 · p. 10

4 Bid-Maximizing Pay-Your-Bid Mechanisms

Bid-maximizing pay-your-bid mechanisms extend first-price pacing beyond single-item auctions, with equilibrium and welfare guarantees under stated conditions. The section characterizes these equilibria through convex programs and establishes liquid-welfare bounds.

4 Bid-Maximizing Pay-Your-Bid Mechanisms

  • The class includes first-price single-item and position auctions, where the corresponding equilibria coincide with FPPE and Pos-FPPE, respectively.The mechanism selects an outcome maximizing total paced bid value and charges each buyer her paced bid for her allocation.Source: §4 · p. 10

4.1 Abs-PE via Convex Programming

  • If the feasible allocation set is non-convex but the mechanism can randomize, an equilibrium can be obtained as a distribution over bid-maximizing allocations.The distribution is supported on allocations that maximize paced bids in the original feasible set.Source: §4.1 · p. 10
  • Under mild assumptions, these mechanisms have a unique equilibrium pacing vector computable by convex programming, with an Eisenberg-Gale-type program recovering an equilibrium allocation.The results assume a nonempty, compact, convex feasible allocation set and affine valuations; the allocation itself need not be unique.Source: §4.1 · pp. 10–11
  • Every optimal solution of the Eisenberg-Gale-type program is Pareto efficient in buyer utilities and seller utility.The buyer utilities include leftover budgets, and seller utility is revenue.Source: §4.1 · p. 11

4.2 Liquid Welfare Guarantees

  • Under the convexity assumptions, the paper also gives additive liquid-welfare guarantees involving equilibrium multipliers and an equilibrium-independent bound using budgets and the valuation bound.The supplied passages do not include the complete formulas for these bounds.Source: §4.2 · p. 12
  • Equilibrium revenue equals liquid welfare, and every equilibrium allocation achieves at least half of optimal liquid welfare.The multiplicative guarantee is tight for this mechanism class: first-price single-item instances can have a ratio arbitrarily close to 1/2.Source: §4.2 · p. 12

5 General Abstract Mechanisms

This section studies pacing equilibria in abstract mechanisms, identifying payment and tie-breaking conditions for existence and further conditions for uniqueness, revenue and shill-proofness guarantees. It also examines budget-adjustment dynamics that approach approximate equilibria, including average convergence under a weaker responsiveness condition and the effect of tighter payment bounds on learning rates.

5 General Abstract Mechanisms

  • Assumptions 1–3 cover separable strictly increasing payment rules, standard rank-based first-price mechanisms, and bid-priority capacity mechanisms; Assumption 1 also covers monotone allocation-weighted power payments.Examples include all-pay formats, position auctions, and weighted proportional-sharing mechanisms.Source: §5 · p. 13

5.1.1 Join-semilattice property

  • Opponent inverse monotonicity makes the set of budget-feasible pacing vectors closed under componentwise maxima, forming a join-semilattice.Thus the componentwise maximum of any two budget-feasible vectors remains budget-feasible.Source: §5.1.1 · p. 14

5.1.2 Mechanism perturbation

  • Independent multiplicative perturbations of values make expected allocations and payments continuous in each buyer’s pacing multiplier.The perturbation draws each buyer’s multiplier independently from Unif[1 − δ, 1].Source: §5.1.2 · p. 15

5.1.3 Existence of δ-smooth Abs-PE

  • In the smoothed mechanism, the greatest budget-feasible multiplier vector is Pareto-dominant and satisfies the no-unnecessary-pacing condition, so it is a δ-smooth Abs-PE.The budget-feasible set is compact and closed under componentwise maxima, enabling the greatest-element characterization.Source: §5.1.3 · pp. 15–16

5.1.4 Existence of Abs-PE

  • Under opponent inverse monotonicity, every abstract mechanism admits an Abs-PE for some tie-breaking rule, though not necessarily for every tie-breaking rule.The result covers arbitrary allocation rules and possibly discontinuous mechanisms; limit-based tie-breaking transfers existence from the smoothed mechanism to the original.Source: §5.1 · p. 14, §5.1.4 · p. 16

5.2.1 Uniqueness and revenue-maximization

  • Collective strict monotonicity yields a unique Abs-PE, and adding monotone revenue makes that equilibrium revenue-maximizing among budget-feasible pacing vectors.These guarantees apply to the payment rule induced by the selected tie-breaking.Source: §5.2.1 · pp. 17–18

5.2.2 Shill-proofness

  • For some tie-breaking rule, the revenue-maximizing Abs-PE is shill-proof; in bid-maximizing pay-your-bid mechanisms, the guarantee also applies to the unique equilibrium under Assumption 3.Shill-proofness means adding fake buyers cannot raise seller revenue at the revenue-maximizing equilibrium.Source: §5.2.2 · p. 18

5.3 Computation of Abs-PE via Adaptive Bidding Algorithms

  • In the smoothed mechanism, budget-adjustment updates converge efficiently to a γ-approximate Abs-PE under common-scale responsiveness; multiplicative weights satisfy equilibrium conditions in time average under own-bid responsiveness.Standard first-price payments satisfy the common-scale condition with κ_i = 1.Source: §5.3 · p. 18, §5.3.1 · p. 19

5.3.1 Budget dynamics of Borgs et al. [2007]

  • Under Assumption 4, Borgs et al.’s budget dynamics on the smoothed mechanism eventually return a (δ, γ)-approximate Abs-PE.Theorem 5 guarantees this for sufficiently small step size η and all t ≥ Tγ.Source: §5.3.1 · p. 19

5.3.2 Multiplicative-weights algorithm

  • Under own-bid responsiveness, multiplicative weights converges on average to a (δ, γ)-approximate Abs-PE, with average budget feasibility and vanishing unnecessary pacing.The condition requires payments to increase sufficiently with a buyer’s own bid and is strictly weaker than Assumption 4 under opponent inverse monotonicity.Source: §5.3.2 · p. 20
  • Tighter coordinate-specific bounds on payment changes can allow multiplicative weights to use a larger range of learning rates.The generic step-size bound is recovered from the smoothing estimates.Source: §5.3.2 · pp. 20–21

6 Experiments

The experiments test demand violations at position-auction pacing-equilibrium prices, liquid-welfare losses in bid-maximizing pay-your-bid mechanisms, and convergence of approximate-equilibrium dynamics. They find market-structure-dependent demand gaps, small welfare losses in the tested settings, and convergence faster than worst-case bounds suggest.

6 Experiments

  • The experiments assess demand gaps, welfare loss, and dynamics across synthetic position-auction, matching, shared-capacity, and proportional-sharing environments.The study compares demand gaps with reoptimized utility at induced prices, Abs-PE welfare with the optimum, and observed dynamics with theoretical guarantees.Source: §6 · p. 21

6.1 Position Auctions and Market Equilibrium

  • As buyer-to-slot ratios rise, demand violations become less frequent and smaller; greater slot similarity and more slots instead increase their incidence and magnitude.Figure 1 reports the fraction of buyers with violations and the average relative demand gap across buyers.Source: Figure 1 · p. 22, §6.1 · p. 22

6.2 Liquid Welfare Performance of Abs-PE

  • Median relative liquid-welfare loss stays close to 5% in shared-capacity allocation and below 0.5% in matching, decreasing with market size in matching.Across the tested sizes, relative loss does not increase with market size and is smaller in matching than in shared-capacity allocation.Source: Figure 2 · p. 23, §6.2 · p. 23

6.3 Computing Approximate Abs-PE in Smoothed Mechanisms

  • In the reported specifications, average relative budget violation fell below γ = 0.1 after about 11% to 25% of the budget-feasibility horizon T BF, while approximate NUP violations reached zero within the corresponding guaranteed horizon.Figure 3 reports the dynamics for first-price proportional-sharing and position-auction mechanisms.Source: §6.3 · p. 24, Figure 3 · p. 24
  • Under power payments, time-averaged relative budget violations decline approximately as 1/H, and approximate NUP violations decline toward zero.At H = 3 × 10^4, both time-averaged equilibrium violations are small across all tested specifications.Source: §6.3 · p. 24

7 Conclusion

The paper shows that pacing properties do not automatically extend from first-price single-item auctions to richer mechanisms: even first-price position auctions can fail to yield the benchmark market-equilibrium interpretation. It identifies mechanism-level conditions that recover useful equilibrium, welfare, and computational guarantees, while emphasizing that no single design fits every platform.

7 Conclusion

  • Bid-maximizing pay-your-bid mechanisms recover unique pacing equilibria and convex-program characterizations under mild convexity assumptions, with efficiency and computational guarantees.For more general mechanisms, payment monotonicity, smoothing, and appropriate tie-breaking support equilibrium existence and expenditure-based adjustment dynamics.Source: §7 · p. 25
  • The framework identifies mechanism properties that support predictable and computable pacing, rather than prescribing one best mechanism or budget-management architecture for all platforms.Platforms differ in objectives, information environments, allocation constraints, and implementation requirements.Source: §7 · pp. 25–26

A.1.1 Proof of Theorem 1

  • A Pos-FPPE can fail to be a market equilibrium when a buyer receives a positive fraction of a positive-quality slot while a lower positive-quality slot has a strictly smaller nonzero paced bid.The proof explains that the buyer then does not maximize utility across the slot-goods at the induced prices.Source: §A.1.1 · p. 28

A.1.2 Proof of Proposition 1

A first-price position-auction pacing equilibrium need not induce a position-aware market equilibrium. Under the stated convexity and affine-value assumptions, bid-maximizing pay-your-bid mechanisms instead admit equilibrium computation through a convex program and an equivalent EG-style allocation program.

A.1.2 Proof of Proposition 1

  • Bidder 2 strictly prefers slot 3 to her assigned slot 2 at the induced prices, so this first-price position-auction pacing outcome is not a market equilibrium.Her net utilities are 0 for slot 2 and 0.8 for slot 3.Source: §A.1.2 · pp. 28–29

A.2.1 Proof of Theorem 2

  • With nonempty, compact, convex X and affine valuations, a bid-maximizing pay-your-bid mechanism has an Abs-PE obtained from the stated convex program.The proof identifies the program's solution as an Abs-PE with its induced outcome and payments.Source: §A.2.1 · p. 29

A.2.2 Proof of Proposition 2

  • The EG-style convex program yields the same optimal allocation as the dual pacing problem and thus the allocation at an Abs-PE.The auxiliary δ_i can represent leftover budget; positive δ_i corresponds to a buyer below budget.Source: §A.2.2 · pp. 29–30

A.2.3 Proof of Lemma 1

  • Any Abs-PE under Theorem 2's assumptions is an optimal solution of the pacing convex program (CP1).The proof verifies the program's KKT conditions using budget feasibility and no-unnecessary-pacing.Source: §A.2.3 · pp. 30–31

A.2.4 Proof of Theorem 3

Theorem 3 gives liquid-welfare guarantees for Abs-PE allocations in bid-maximizing pay-your-bid mechanisms. In particular, equilibrium revenue equals liquid welfare, which is at least half of optimal liquid welfare.

A.2.4 Proof of Theorem 3

  • Equilibrium revenue equals liquid welfare, and the Abs-PE allocation achieves at least half of optimal liquid welfare.The proof compares the equilibrium allocation with any feasible allocation and obtains the half-optimum bound.Source: §A.2.4 · pp. 31–32
  • When the assumptions of Theorem 2 hold, the supplied statement gives LW(x∗) ≥ OPTLW − P i∈N Bi log 1, though it does not fully specify the logarithmic term.Source: §A.2.4 · p. 31
  • The proof partitions buyers into those spending their budgets and those below budget, then uses bid maximization to compare liquid welfare across feasible allocations.Unpaced buyers have multiplier 1 under the no-unnecessary-pacing condition.Source: §A.2.4 · pp. 31–32

A.2.5 Proof of Lemma 2

The proofs establish a liquid-welfare gap for first-price pacing and derive smoothing-based continuity, existence, and compactness results, with additional conditions and tie-breaking yielding uniqueness, revenue maximization, and shill-proofness. The section concludes with the shill-proofness inequality for the pacing vector α*τ·v_N.

A.2.5 Proof of Lemma 2

  • An m-good, two-buyer first-price market admits an FPPE with liquid-welfare ratio exactly 1/(2 − ε), where ε = 1/m.Both buyers have budget 1; buyer 1 receives all goods, while an allocation splitting one good to buyer 1 and the rest to buyer 2 attains liquid welfare 2 − ε.Source: §A.2.5 · pp. 32–33

A.3.1 Proof of Proposition 3

  • With multiplicative uniform smoothing, each buyer’s expected allocation and payment are continuous in their own pacing multiplier.Expected payments also extend continuously to multiplier zero.Source: §A.3.1 · pp. 33–34

A.3.2 Proof of Proposition 4

  • Expected payments are log-Lipschitz on (0, 1]^n, with change bounded by nV̄/δ times the infinity norm of the log-multiplier difference.The bound applies to any two multiplier vectors α, α′ in (0, 1]^n.Source: §A.3.2 · p. 34

A.3.3 Proof of Lemma 4

  • The set of budget-feasible multipliers in the smoothed mechanism, Aδ, is compact.The proof establishes continuity of expected payments on the closed multiplier domain, making Aδ closed and bounded.Source: §A.3.3 · pp. 34–35

A.3.4 Proof of Proposition 5

  • The smoothed mechanism’s budget-feasible multipliers contain a coordinate-wise greatest, and therefore Pareto-dominant, element α∗.The proof uses closure under component-wise maximum and compactness of Aδ.Source: §A.3.4 · p. 35

A.3.5 Proof of Proposition 6

  • The Pareto-dominant multiplier α∗ has no unnecessarily paced buyers and is a δ-smooth Abs-PE.If a buyer were under budget while paced below 1, continuity would permit raising that buyer’s multiplier while preserving feasibility, contradicting maximality.Source: §A.3.5 · p. 35

A.3.6 Proof of Theorem 4

  • For any mechanism whose payments satisfy Assumption 1, some tie-breaking rule yields an Abs-PE for given valuations and budgets.The proof obtains this outcome as a limit of smoothed equilibria and selects a valid tie-breaking outcome at the limiting bids.Source: §A.3.6 · pp. 35–36

A.3.7 Proof of Proposition 7

  • If p′ satisfies Assumption 2, M′ has a unique Abs-PE pacing vector.The proof shows Abs-PE vectors are maximal budget-feasible vectors; their coordinate-wise maximum is feasible, forcing any two such vectors to coincide.Source: §A.3.7 · p. 36

A.3.9 Proof of Proposition 8

  • The proof concludes that P_i(α*τ·v_N) satisfies the desired shill-proofness inequality.Step 1 provides P_i( b̄), which is used in the argument.Source: §A.3.9 · p. 38

A.4.1 Proof of Theorem 5: Convergence of Algorithm 1

For mechanisms meeting the payment assumptions, the budget-adjustment algorithm on a smoothed mechanism eventually returns an approximate Abs-PE. Its updates adjust multipliers in response to budget overspending or underspending, while the convergence guarantee depends on the step size and approximation parameter.

A.4.1 Proof of Theorem 5: Convergence of Algorithm 1

  • After a finite threshold, Algorithm 1 returns a (δ, γ)-approximate Abs-PE when the step size satisfies η ≤ γ/C.The theorem applies to the smoothed mechanism and defines C using the number of buyers, valuation bound, δ, and minimum budget.Source: §A.4.1 · p. 38
  • If a buyer's payment exceeds her budget, the next update decreases it; if payment is within budget and the upward update is unclipped, payment increases.The payment changes by factors bounded using the responsiveness parameter κ_i and step size η.Source: §A.4.1 · p. 38
  • After sufficiently many iterations, no buyer exceeds budget by more than a factor of (1 + γ).The proof also establishes eventual bounds on unnecessary pacing, as required for approximate equilibrium.Source: §A.4.1 · pp. 38–39

A.4.2 Proof of Theorem 6: Convergence proof of Algorithm 2

The proof establishes that multiplicative-weights iterates converge on average to a (δ, γ)-approximate Abs-PE of the smoothed mechanism. Average budget feasibility and vanishing unnecessary pacing supply the two defining conditions.

A.4.2 Proof of Theorem 6: Convergence proof of Algorithm 2

  • Under Assumption 5 and the step-size conditions, unnecessary-pacing iterations are finite for each buyer.The proof shows these iterations propagate backward and are bounded in number.Source: §A.4.2 · pp. 40, 42, 43
  • MW converges on average to a (δ, γ)-approximate Abs-PE, with approximate average budget feasibility and unnecessary pacing on a vanishing fraction of rounds.The proof establishes these two conditions together as the convergence guarantee.Source: §A.4.2 · p. 40
  • A uniform positive lower bound on each buyer’s multiplier is used to prove average budget feasibility.The proof derives such a bound for every buyer and uses it in the average-payment argument.Source: §A.4.2 · p. 40
  • The MW update bounds consecutive log-multiplier movement by ηG, supporting the proof that unnecessary-pacing violations vanish over time.The log-step bound is used in the argument for vanishing unnecessary pacing.Source: §A.4.2 · pp. 40–42

B.1 Additional Results for Position-Auction Demand Gaps

In position auctions, higher buyer-to-slot ratios are associated with fewer and smaller demand violations, while the absolute number of slots has a weaker, less systematic effect. Demand gaps also vary with equilibrium pacing: they are small for heavily paced buyers and rise sharply near an unpaced multiplier.

B.1 Additional Results for Position-Auction Demand Gaps

  • Both the fraction of buyers with demand violations and the average relative demand gap decline as the buyer-to-slot ratio rises for each tested slot count.At a fixed ratio, the absolute number of slots has a weaker and less systematic effect.Source: §B.1 · p. 43, Figure 5 · p. 43
  • Demand gaps are small for heavily paced buyers and rise sharply as α∗ approaches one; at α∗ = 1, the gap equals one when reoptimization at induced prices yields positive utility.The unpaced buyer receives zero utility from her assigned pay-your-bid allocation in that case.Source: §B.1 · p. 44, Figure 6 · p. 44
  • After budgets double, the unpaced share increases from 27% to 68%, while the conditional relationship between pacing multipliers and demand gaps changes little.The experiment finds that looser budgets primarily shift the distribution of pacing multipliers.Source: §B.1 · p. 44

B.2 Tightness of the liquid welfare guarantees

Across simulated shared-capacity and one-to-one matching markets, realized liquid-welfare losses remain below the additive guarantee. The bound is tighter than the multiplicative guarantee in both environments, but realized losses approach it more closely under shared capacity.

B.2 Tightness of the liquid welfare guarantees

  • In both environments, the additive bound is tighter than the uniform relative-loss bound of 1/2.The simulations compare realized losses with both guarantees.Source: §B.2 · p. 45, Figure 8 · p. 45
  • Across 800 simulated markets, the normalized additive bound never exceeds 0.402, with median values of 0.075–0.10 for shared capacity and 0.13–0.17 for matching.The reported ranges are across the simulated markets in each environment.Source: §B.2 · p. 45, Figure 8 · p. 45
  • Realized liquid-welfare losses stay below the additive bound and realize 0.58–0.63 of it under shared capacity, versus 0.009–0.031 under matching.Under matching, the realized fraction also declines with market size.Source: §B.2 · p. 45

B.3 PACE in Bid-Maximizing Pay-Your-Bid Environments

PACE updates approach the convex-program benchmark in single-item, position-auction, and shared-capacity environments. At 300 iterations, multiplier errors are small and no buyers violate approximate no-unnecessary-pacing in any of the three environments.

B.3 PACE in Bid-Maximizing Pay-Your-Bid Environments

  • The PACE updates require only a bid-maximization oracle over the feasible allocation set and are evaluated against Abs-PE multipliers computed from the convex-program characterization.The benchmark multipliers are computed independently.Source: §B.3 · p. 46
  • The convergence evaluation covers pay-your-bid single-item, position-auction, and shared-capacity mechanisms.Figure 9 reports multiplier error, normalized budget violation, and the fraction of buyers violating approximate NUP.Source: Figure 9 · p. 46, §B.3 · p. 46
  • At T = 300, average relative multiplier error is 2.6 × 10−3 in single-item, 1.8 × 10−3 in position auctions, and 4.9 × 10−4 under shared capacity; no buyers violate approximate NUP.The updates approach the convex-program benchmark in all three environments.Source: §B.3 · p. 46, Figure 9 · p. 46

B.4 Additional Results on Pacing Dynamics

Worst-buyer diagnostics show that both the last-iterate and multiplicative-weights dynamics converge across buyers. The last-iterate violation falls below γ = 0.1 within part of the budget-feasibility horizon, while multiplicative-weights violations decline with the averaging horizon.

B.4 Additional Results on Pacing Dynamics

  • For the last-iterate dynamics, worst-buyer relative budget violation falls below γ = 0.1 after approximately 20%–36% of the budget-feasibility horizon T_BF.Figure 10(a) reports the largest relative budget violation across buyers.Source: §B.4 · p. 47, Figure 10 · p. 47
  • Figure 10 distinguishes worst-buyer budget violations for Borgs et al. dynamics from time-averaged budget violations and NUP-violating rounds for multiplicative weights.Blue curves denote proportional sharing and orange curves denote first-price position auctions.Source: Figure 10 · p. 47
  • For multiplicative-weights dynamics, maximum relative budget violation is below 2.5×10^-3 in every specification at H = 3×10^4.The maximum across buyers of the fraction of NUP-violating rounds also declines with the averaging horizon.Source: §B.4 · p. 47, Figure 10 · p. 47
Loading 2609.27285v1…