PaperlayerView exact revision on arXiv

Source-linked AI summary

Two-sided Market Design Meets Autobidding

Yang Cai, Christopher Liaw, Aranyak Mehta, Xizhi Tan, Mingfei Zhao

arXiv:2609.40267v1cs.GT

TL;DR

The paper asks how mechanism design changes when both buyers and sellers can be strategic autobidders, beyond the one-sided markets that dominate prior work. It analyzes prior-free guarantees and distribution-informed mechanism design, finding that first-best liquid welfare is achievable when at least one side has value maximizers.

  • Problem

    Most mechanism-design work for autobidders studies one-sided markets, leaving open whether mechanisms remain efficient when buyers and sellers are both strategic.

    Source: §1 · p. 2

  • Method

    The paper studies prior-free repeated double auctions with Trade Reduction and develops a distribution-informed mechanism for matching markets with downward-closed feasibility.

    Source: §1.1 · pp. 3–4

  • Results

    Trade Reduction has unbounded LGFT PoA but liquid-welfare PoA 2 + O(1/r) with one value-maximizing side and 3 + O(1/r) with both; with distributions, a BIC, IR, WBB mechanism attains first-best liquid welfare when at least one side has value maximizers.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    Trade Reduction retains a liquid-welfare guarantee despite its LGFT limitation, while distribution-informed design reaches first-best liquid welfare in matching markets with value maximizers.

    Source: §1.1 · pp. 3–4

    The stated Trade Reduction welfare analysis assumes repeated double auctions with r ≥ 2, hybrid buyers, and utility-maximizing sellers.

    Source: §4 · p. 15

Abstract

from arXiv · show

Autobidding has become a dominant paradigm in online advertising by enabling advertisers to set high-level goals while algorithms handle real-time bid optimization. A prominent example is the Return-on-Spend (RoS) value maximizer, which maximizes total value subject to an aggregate value-per-spend constraint. While most work on mechanism design for autobidders focuses on one-sided markets, many real-world platforms involve strategic behavior on both sides. We initiate the study of two-sided markets with autobidders. We first establish a stark negative result: for the challenging objective of liquid gains from trade (LGFT) in the prior-free setting, broad classes of utility-truthful, budget-balanced mechanisms have unbounded Price of Anarchy (PoA) once value-maximizing agents are present, even in double-auction environments. We then give two positive results. In the prior-free repeated double-auction setting, McAfee's Trade Reduction mechanism has unbounded PoA for LGFT but achieves constant PoA for liquid welfare under RoS bidding, showing that off-the-shelf mechanisms retain meaningful welfare guarantees. With distributional information regarding the private costs and values, we design a two-sided mechanism that is incentive compatible for each agent under its corresponding objective, individually rational, ex-ante weakly budget balanced, and achieves first-best liquid welfare, equivalently optimal LGFT, whenever at least one side of the market consists of RoS value maximizers. This result applies to matching markets with general downward-closed feasibility constraints. It contrasts sharply with the Myerson--Satterthwaite impossibility theorem~\citep{MS83}, which rules out first-best efficiency with incentive compatibility, individual rationality, and budget balance even in bilateral trade when both the buyer and the seller are quasi-linear utility maximizers.

1 Introduction

The introduction asks how two-sided strategic behavior changes mechanism design for autobidders, a setting not captured by work focused on one-sided markets. It previews prior-free limits and welfare guarantees, alongside distribution-informed mechanisms that attain first-best liquid welfare.

1 Introduction

  • Two-sided platforms require mechanisms to account for strategic buyers and sellers while remaining budget balanced.The paper frames this as a gap because prior work largely studies one-sided auctions.Source: §1 · p. 2
  • The paper initiates two-sided mechanism design with value-maximizing agents and asks whether utility-maximizer mechanisms remain efficient or efficient mechanisms can be designed for autobidders.Source: §1 · p. 2

1.1 Our Results

  • LGFT is more demanding to approximate than liquid welfare, so a liquid-welfare guarantee does not imply the corresponding LGFT guarantee.An approximation guarantee for LGFT does imply the same-factor guarantee for liquid welfare.Source: §1.1 · p. 3
  • In prior-free double auctions, no DSIC and WBB mechanism, including Trade Reduction, has bounded LGFT PoA when value maximizers are present.Trade Reduction nevertheless achieves liquid-welfare PoA 2 + O(1/r) with one value-maximizing side and 3 + O(1/r) with both sides.Source: §1.1 · p. 3
  • With distributional information, a BIC, IR, WBB mechanism achieves first-best liquid welfare when one or both market sides comprise value-maximizing agents.The result extends to matching markets with downward-closed feasibility constraints.Source: §1.1 · p. 4

1.2 Related Work

  • Related work studies autobidding auction design and two-sided welfare or gains-from-trade mechanisms, while this paper connects autobidders with two-sided markets.Source: §1.2 · pp. 4–5

2 Preliminaries

The preliminaries model repeated two-sided trade and evaluate efficiency using target-normalized liquid welfare and liquid gains from trade. They also distinguish value-maximizing agents from utility-maximizers and assess mechanisms at pure Nash equilibria.

2 Preliminaries

  • The repeated market has T rounds, n buyers, and m sellers; agents submit bid vectors, with no history-dependent strategies across rounds.The repeated setting aggregates values, payments, and RoS/RoC constraints across market instances.Source: §2 · pp. 5, 7
  • Value-maximizing buyers maximize received value subject to an aggregate RoS constraint, while value-maximizing sellers maximize traded cost subject to an aggregate RoC constraint.Utility-maximizers instead optimize quasi-linear utility: value minus payment for buyers, and payment minus cost for sellers.Source: §2 · pp. 5–6
  • Liquid welfare sums participants’ target-normalized value, while liquid gains from trade (LGFT) measures the increase in liquid welfare created by trades.Maximizing liquid welfare is equivalent to maximizing LGFT, though the objectives can differ in approximation settings.Source: §2 · pp. 6–7
  • Target normalization makes liquid welfare and LGFT ordinary welfare and GFT in normalized units, not raw welfare or GFT when targets differ.Approximation guarantees therefore apply to liquid objectives rather than necessarily to the original unnormalized benchmarks.Source: §2 · p. 7
  • The prior-free analysis evaluates mechanisms at pure Nash equilibria, where no agent can improve payoff by changing its bid vector alone.For value-maximizers, a feasible bid vector must satisfy the agent’s RoS or RoC constraint.Source: §2 · pp. 6–8

3 Unbounded Price of Anarchy for GFT

In repeated double auctions, value-maximizers can make LGFT PoA unbounded even for truthful, individually rational, budget-balanced mechanisms. The constructions nevertheless retain good truthful Trade Reduction outcomes, while the source of failure is equilibrium behavior under aggregate RoS/RoC constraints.

3 Unbounded Price of Anarchy for GFT

  • For deterministic, anonymous, monotone, ex-post WBB, IR, uIC mechanisms, LGFT PoA is unbounded with value-maximizers on at least one side, while truthful Trade Reduction retains a constant-factor guarantee.The mechanism is applied identically in every round and gives zero transfers to nontrading agents.Source: §3 · p. 9
  • Global RoS/RoC constraints let a profitable trade in one round subsidize an unprofitable trade in another, which utility-truthful mechanisms cannot distinguish under identical bids.The proof constructs equilibria whose LGFT tends to zero while optimal LGFT stays bounded away from zero.Source: §3 · p. 9
  • In the deterministic construction, truthful Trade Reduction obtains at least a quarter of first-best LGFT, while the equilibrium ratio diverges as ε approaches zero.The constructions cover both buyer-side and seller-side value-maximizers.Source: §3 · p. 11
  • For uIC, IR, ex-post WBB mechanisms, one value-maximizing side suffices for unbounded LGFT PoA, even though truthful Trade Reduction attains first-best LGFT.This result covers randomized mechanisms when exactly one side is value-maximizing.Source: §3 · p. 11
  • The lower bounds use explicitly verified pure Nash equilibria, and their failure reflects equilibrium behavior under global RoS/RoC constraints rather than an absence of good trades.Truthful Trade Reduction obtains a constant-factor approximation in the deterministic construction and first-best LGFT in the randomized construction.Source: §3 · pp. 13–14
  • Whether prior-free mechanisms tailored to autobidding without utility incentive compatibility can achieve finite LGFT PoA remains open.The authors leave this possibility unresolved.Source: §3 · p. 14

4 Welfare Price of Anarchy of Trade Reduction

This section analyzes Trade Reduction’s welfare price of anarchy across hybrid and value-maximizing agents, including bounds under different benchmarks and equilibrium conditions.

4 Welfare Price of Anarchy of Trade Reduction

  • Wel-PoA(TR) = 2 − β + 1/(r−1) with hybrid buyers and utility-maximizing sellers, where r ≥ 2 is the smallest optimal matching size.This bound is tight for every common β ∈ [0, 1].Source: §4 · p. 15, §4.1 · p. 18
  • 3 − β − (2 − β)/(r + 1) ≤ Wel-PoA(TR) ≤ 3 − β + 1/(r−1) with hybrid buyers and value-maximizing sellers.The lower bound holds for every common β ∈ [0, 1] and integer r ≥ 2.Source: §4 · p. 15, §4.1 · p. 18

4.1 Welfare bounds and proofs

  • The bounds extend to heterogeneous hybrid buyer parameters and mixtures of utility-maximizing and value-maximizing sellers, using the value-seller upper bound for the latter case.The analysis uses pure equilibria with hybrid buyers not underbidding and value-maximizing sellers not overasking; it charges missing optimal welfare to buyer payments and uses RoS, IR, and budget-balance constraints.Source: §4 · pp. 14, 16
  • With utility-maximizing buyers and value-maximizing sellers, the welfare ratio can approach 2 − 1/(r + 1), while every pure equilibrium has PoA at most 2 + 1/(r−1).The lower-bound construction can use truthful buyer reports; the ratio approaches 2 as r grows.Source: §4.1 · p. 19

4.2 Price of Anarchy with Respect to Truthful TR Welfare

  • Against truthful Trade Reduction welfare, rather than first-best welfare, the benchmark is TR with all agents reporting their true target-normalized values and costs.The subsection identifies value-maximizing buyers and utility-maximizing sellers as a setting but provides no further result in the supplied passages.Source: §4.2 · p. 20
  • 2 is the tight truthful-TR welfare PoA when buyers or sellers are value-maximizers and the opposite side utility-maximizes.Both the lower and upper bounds are 2 in each configuration.Source: §4.2 · pp. 20–21
  • 3 is the tight truthful-TR welfare PoA when both buyers and sellers are value-maximizers.The lower and upper bounds match at 3.Source: §4.2 · p. 22
  • With hybrid buyers, truthful-TR liquid-welfare PoA is at most 2 − β with utility-maximizing sellers and 3 − β with value-maximizing sellers, tight for common β_i = β.The stated bounds are tight when all buyers share the same β parameter.Source: §4.2 · p. 22

4.3 Existence of Equilibria for Trade Reduction

  • Pure Nash equilibria satisfying no-dominated-bids exist with hybrid buyers and utility-maximizing sellers, and with utility-maximizing buyers and value-maximizing sellers.The existence results assume Trade Reduction with a fixed tie-breaking rule.Source: §4.3 · pp. 23–24
  • The existence argument does not establish pure-equilibrium existence when both sides are value-maximizers; the welfare bounds apply to qualifying pure equilibria that exist.The paper notes that the one-pass invariant may fail because bid changes on either side can affect the other side’s posted prices or revenues; the lower-bound constructions explicitly exhibit qualifying equilibria.Source: §4.3 · p. 24

5 Full GFT Mechanism for Bayesian Matching Markets

Using distributional information, the paper designs a mechanism for matching markets that achieves first-best liquid welfare and optimal LGFT while meeting incentive, participation, and budget-balance requirements. The construction extends to value-maximizing sellers and general downward-closed feasibility constraints.

5 Full GFT Mechanism for Bayesian Matching Markets

  • The result contrasts with Myerson–Satterthwaite: tailoring payments to RoS behavior permits first-best efficiency where utility-maximizer mechanisms face an impossibility.The cited impossibility applies to quasi-linear utility maximizers.Source: §5 · p. 25

5.1 Model Setup

  • The model uses independently distributed private values and costs and matching feasibility constraints that are downward closed, including double auctions as a special case.For value-maximizing buyers, truthfulness is defined globally over the expectation across buyers’ values and sellers’ costs.Source: §5.1 · pp. 25–26

5.2 The Mechanism

  • The mechanism selects a maximum-weight feasible matching using bid-minus-ask edge weights, pays utility-maximizing sellers threshold payments, and scales buyer threshold payments to bind truthful buyers’ RoS constraints.The buyer-specific ex-ante scaling constant is chosen to make the buyer’s global RoS constraint bind.Source: §5.2 · p. 26
  • Theorem 5.6 achieves optimal LGFT and liquid welfare ex post while satisfying the stated truthfulness, individual-rationality, and ex-ante budget-balance requirements.The mechanism is vBIC-B for value-maximizing buyers and BIC-S for utility-maximizing sellers.Source: §5.2 · p. 29

5.3 Value-Maximizing Sellers

  • With value-maximizing sellers, the extended mechanism preserves incentive compatibility, individual rationality, and ex-ante weak budget balance; when all sellers are value maximizers, expected broker profit equals first-best LGFT.The extension scales seller payments so truthful reporting binds each seller’s RoC constraint.Source: §5.3 · pp. 29, 31

A Motivation for Value-Maximizing Sellers

A value-maximizing seller prioritizes sales volume, utilization, or cost-weighted goods sold, subject to a revenue-over-cost constraint.

A Motivation for Value-Maximizing Sellers

B.1 Preliminaries for the Bayesian Setting

The Bayesian setting is a single-dimensional two-sided matching market with privately known values and costs drawn from public distributions. It distinguishes utility maximizers from RoS/RoC value maximizers and specifies feasibility, truthfulness, participation, and budget conditions.

B.1 Preliminaries for the Bayesian Setting

  • The market has unit-demand buyers and unit-supply sellers, with independently distributed private values and costs and downward-closed matching feasibility.Feasible allocations are sets of buyer-seller pairs, and any subset of a feasible allocation remains feasible.Source: §B.1 · p. 37
  • The section defines Bayesian incentive compatibility for utility-maximizing buyers and sellers, alongside ex-ante individual rationality and weak budget balance.For value-maximizing agents, truthful reporting must attain the objective subject to the RoS or RoC constraint.Source: §B.1 · p. 38
  • RoS/RoC value maximizers optimize expected traded value or cost subject to their respective expected return constraints, while utility maximizers have quasi-linear objectives.Target normalization rescales values or costs so all RoS/RoC targets are one.Source: §B.1 · pp. 37–38
  • For utility-maximizing agents, implementable allocation rules are monotone in bids or reported costs and use threshold payments, with finite integrals under bounded cost supports.The buyer rule is nondecreasing in bids; the seller rule is nonincreasing in reported costs.Source: §B.1 · pp. 38–39
  • A buyer-side characterization of vBIC requires a nonnegative constant per buyer and truthful satisfaction of the RoS constraint with complementary slackness.The stated equivalence is subject to the standard Slater/nondegeneracy condition.Source: §B.1 · p. 39

B.2 Truthfulness of Value-Maximizing Sellers

The seller-side sufficient condition establishes truthful reporting as optimal for a value-maximizing seller among globally RoC-feasible deviations. It relies on a positive rescaling constant and complementary slackness at truth.

B.2 Truthfulness of Value-Maximizing Sellers

  • The argument works by rescaling payments so seller truthfulness is quasi-linear incentive compatible while the truthful RoC constraint binds.This is the abstract form of the seller-side argument described in the section.Source: §B.2 · p. 39
  • A value-maximizing seller truthfully reports optimally among globally RoC-feasible deviations under the stated sufficient conditions.The conditions include a positive seller-specific constant and truthful satisfaction of the RoC constraint with complementary slackness.Source: §B.2 · pp. 39–40
  • The proof compares truthful reporting with any globally RoC-feasible randomized deviation by taking expectations of the seller-side condition and extending it by linearity.The positive rescaling constant and complementary slackness yield the truthfulness conclusion.Source: §B.2 · p. 40

Related papers

Loading 2609.40267v1…