Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding Theory and Evidence from ROI-Constrained Online Advertising Markets Juncheng Li and Pingzhong Tang

2025-04-26 0 0 3.07MB 24 页 10玖币

侵权投诉

Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding: Theory

and Evidence from ROI-Constrained Online Advertising Markets

Juncheng Li and Pingzhong Tang

Tsinghua University

{lijuncheng13, kenshinping}@gmail.com

Abstract

Most of the work in the auction design literature

assumes that bidders behave rationally based on

the information available for every individual auc-

tion, and the revelation principle enables designers

to restrict their efforts to incentive compatible (IC)

mechanisms. However, in today’s online advertis-

ing markets, one of the most important real-life ap-

plications of auction design, the data and compu-

tational power required to bid optimally are only

available to the platform, and an advertiser can only

participate by setting performance objectives and

constraints for its proxy auto-bidder provided by

the platform. The prevalence of auto-bidding ne-

cessitates a review of auction theory. In this pa-

per, we examine the markets through the lens of

ROI-constrained value-maximizing campaigns. We

show that second price auction exhibits many un-

desirable properties (computational hardness, non-

monotonicity, instability of bidders’ utilities, and

interference in A/B testing) and loses its domi-

nant theoretical advantages in single-item scenar-

ios. In addition, we make it clear how IC and

its runner-up-winner interdependence contribute to

each property. We hope that our work could bring

new perspectives to the community and beneﬁt

practitioners to attain a better grasp of real-world

markets.

1 Introduction

Auto-bidding has become a corner stone of modern adver-

tising markets. For better end-to-end performance and cus-

tomer experience, platforms now provide algorithmic agents

to set ﬁne-grained bids for advertisers, who only need to sub-

mit campaign-level optimization objectives and constraints.

As a result, the community has seen a surge of publications

on auto-bidding in recent years.

One of the most notable features of the auto-bidding

paradigm is the change of roles played by advertisers and

platforms. Traditionally advertisers are assumed to bid ratio-

nally for each individual ad slot, and thus the real-time bid-

ding (RTB) literature focuses on developing algorithms for

advertisers to maximize their objectives subject to different

constraints and auction rules, while the auction design liter-

ature, anticipating the best response of advertisers or RTB

algorithms, explores new auction rules to optimize various

goals of the platform. However, in auto-bidding markets,

most of the technical components are under the management

of the platform: auto-bidders provided by the platform will

compete with each other, based on valuations predicted by

the platform, under auction rules that are also designed by

the platform. Such a greater control over the market imposes

a more diverse set of requirements upon the designer. The

auction design literature has long been focusing on incentive

compatibility and welfare/revenue guarantee, but the desider-

ata of an auto-bidding mechanism are far beyond these two.

Google AdSense’s partial shift at 2021 from second to ﬁrst

price auction1might serve as an exemplary demonstration of

this perplexity.

Despite the evolution of ecosystems, ﬁrst and second price

auction remain as the dominant mechanisms used in practice.

In this paper, we study the mathematical model abstracted

from real-world ﬁrst and second price auction markets with

ROI-constrained auto-bidders. In addition to theoretic inter-

ests, our work are also motivated by real-world observations.

Traditional interpretations of some phenomena may confuse

both sides of the market and lead to business choices detri-

mental in the long run. Our goal is thus to develop a deeper

understanding of auto-bidding at the market scale, and pro-

vide practitioners a more holistic view to facilitate decision

making. We will show, through a series of theoretical and em-

pirical results, that the dominant advantage of second price

auction over ﬁrst price is, in many regards, reversed in the

world of auto-bidding. It will be made clear throughout the

journey how IC, instead of simplifying the reasoning of both

bidders and auctioneers, unnecessarily complicates the game

in a profound way.

1.1 ROI-Constrained Auto-bidding Markets and

Related Works

Previously much effort was spent on the study of auto-bidders

with budget constraints [Karande et al., 2013; Charles et

al., 2013; Balseiro and Gur, 2019; Gao and Kroer, 2020;

1In November 17, 2021, Google moves the AdSense auction for

Content, Video, and Games from second price auction to ﬁrst price,

while keeping Search and Shopping as before [Google, 2021].

arXiv:2210.06107v6 [cs.GT] 11 May 2024

Chen et al., 2021a; Balseiro et al., 2021b; Conitzer et al.,

2022a; Conitzer et al., 2022b], but Return-on-Investment

(ROI), another widely adopted auto-bidding option, received

much less attention until very recently [Golrezaei et al., 2021;

Balseiro et al., 2021c; Deng et al., 2021]. For campaigns

with ROI-constraints, advertisers should submit either a tar-

get ROI, a target Return-on-Ad-Spend or a target Cost-

per-Action (tROI/tROAS/tCPA).2The objective of the auto-

bidder is then to maximize the acquired value while keep-

ing the average spend for each unit of value below the target

threshold. ROI-constrained auto-bidders are dominating in

market share in many regions of the world. There is also re-

cent empirical evidence [Golrezaei et al., 2021]from Google

AdX that advertisers are indeed ROI-constrained.

An advertiser’s value for an ad slot (to which we will refer

as a generic good throughout the rest of the paper) is typi-

cally given by the product of the conversion-rate (predicted

by the platform) and the value of each conversion. For ROI-

constrained campaigns, the latter part is the amount of money

that the advertiser is willing to pay the platform for each

(unit of) conversion.2Truthful bidding for each individual

auction is ex-post optimal for non-constrained quasi-linear

utility-maximizing bidders. But for ROI-constrained value-

maximizers, it is possible to raise bids above values to win

more while keeping the average spend of each conversion be-

low the threshold. In this paper, auto-bidders will take values

as given and be restricted to the multiplicative pacing strat-

egy,2wherein the bids of each bidder could only be generated

through scaling the values for all goods by a common mul-

tiplier of its choice. There is always a multiplier that is ex-

post bidder-optimal in second price auction, and the strategy

is one of the most implemented in the industry regardless of

auction formats (in particular, it remains popular in ﬁrst price

auction3).

Table 1 positions our market model within the growing lit-

erature on auto-bidding. Existing works differ in the mod-

eling of advertisers’ valuations and utilities. Traditionally

the valuation of each bidder is modeled as being drawn

from a stochastic process independently of each other. We

adopt a framework ﬁrst studied by Conitzer et al. [2022b;

2022a], where the valuation is given as the (ﬁxed) input and

can be viewed as a discretized density function or a real-

ized sample of an arbitrary joint distribution. In particular,

the correlation prevalent in advertising can thus be captured.

For utilities, previous research mainly focuses on budget-

constraints, and our paper complements the recent line of

work on ROI-constraints. Babaioff et al. [2021]also con-

sider ROI, but they model bidding behaviors with respect to

the marginal ROI of each individual auction rather than the

average ROI across.

Deng et al. [2021]and its follow-up work [Balseiro et al.,

2021a]study a model that largely coincide with ours. Their

goal is to design mechanisms having revenue and welfare

2See Appendix B for more notes on terminology.

3Possibly surprisingly, we will show in Section 6 that it will not

bring incentive issues for ﬁrst price auction and it is in the interests

of a platform to enforce so. In contrast, both bidders and sellers have

incentives to deviate from it in second price auction (Appendix J.3).

guarantees when the designer has fairly accurate signals on

the valuation. Though we will also report some results on rev-

enue and welfare, we emphasize that, for today’s large scale

auto-bidding systems, auction (combined with auto-bidding

strategies) acts more like an efﬁcient distributed algorithm

to match demand with supply and compute market-clearing

prices. With this mentality, our work covers a broader range

of properties and focuses heavily on their possible practical

impacts on advertisers and platforms. We also differ in the

adopted solution concept. We allow fractional allocation and

incorporate the tie-breaking rule into the solution concept,

which is not only well-motivated, but also guarantees the ex-

istence of equilibrium even though the market is discrete and

discontinuous. In contrast, Balseiro et al. [2021a]break ties

lexicographically and more complex auctions like VCG and

GSP are considered there. So they choose a weaker solution

concept called undominated bids and avoid the discussion of

existence. Nonetheless, this distinction diminishes for large

markets as the result of a single auction becomes negligible.

Auto-bidding or RTB algorithms have been studied for a

long time. Such works typically assume a stationary environ-

ment and optimize various objectives for a single advertiser.

They fail to capture other bidders’ responses invoked by the

action of the focal agent, and the resulting equilibrium out-

come may not fulﬁll the initial design goal if all the bidders

implement the same strategy (see, e.g., Appendix L.1). One

notable exception is the work by Aggarwal et al. [2019], who

were aware of this problem and tried to prove the existence of

an equilibrium. But their treatment of equilibrium is incom-

plete (see a discussion in Appendix C).

Researchers have shown that the computation of equilib-

rium bears some inherent hardness with budget-constrained

multiplicative pacing bidders. For computing any equilib-

rium, we improve previous result to show that it is PPAD-

hard to approximate within constant parameters (for budget-

constraints, it was shown to be hard to approximate within

polynomially small parameters [Chen et al., 2021a]). Our re-

sult is built on a more concise reduction quite distinct from

the previous one. We also improve the NP-hardness result of

optimizing revenue/welfare [Conitzer et al., 2022b]to APX-

hardness. Moreover, the source of these hardness and the vul-

nerabilities of IC are demonstrated more clearly with our con-

structions, which we believe could help both researchers and

practitioners better extrapolate our techniques and insights.

1.2 Single-round Incentive Compatibility

The classic revelation principle ensures us that, when design-

ing single-item auctions, any implementable allocation rule

could be implemented in an incentive compatible way by di-

rectly eliciting bidders’ private information (in most cases

only the valuations to the item to be sold are needed). By

focusing on IC mechanisms, the designer loses nothing while

bidders could be prevented from strategic behaviors. In com-

parison, the characterization and computation of equilibrium

in ﬁrst price auction is notoriously hard (see, e.g., [Filos-

Ratsikas et al., 2021]and the survey therein).

Though second price auction is only IC for single-item

auctions, it possesses another fascinating property in auto-

bidding markets: from a single bidder’s perspective, each in-

Utility model Valuations

Deterministic, correlated Stochastic, independent

ROI-constrained

value-maximizer

Our model, Balseiro et al. [2021a]Balseiro et al. [2021c], Golrezaei et al.

[2021]

Budget-constrained utility-

maximizer

Conitzer et al. [2022a; 2022b], Chen et al.

[2021a], Gao and Kroer [2020]

Balseiro and Gur [2019], Balseiro et al.

[2021b]

ROI&budget-constrained

value-maximizer

Deng et al. [2021], Aggarwal et al. [2019]

Table 1: Common auto-bidder types and valuation assumptions in the literature.

dividual auction comes with a winning price independent of

its own bid (which is essentially an equivalent statement of

IC). As a consequence, the (ex-post/ofﬂine) task of each auto-

bidder is a linear program for bidders with linear constraints

like ROI and budget. The optimal solution can be well ap-

proximated by the multiplicative pacing strategy, which is

simple to implement and performs well even in the online

setting [Balseiro and Gur, 2019; Balseiro et al., 2022]. This

provides second price auction an illusory strategyproofness

that could be called ex-post IC: every advertiser could truth-

fully report its tROI and happily accept the equilibrium bids

given by its proxy auto-bidder as deviating unilaterally will

not bring extra proﬁt at the moment.

Nonetheless, even long before the advent of the auto-

bidding era, experiments have revealed that bidders’ behav-

iors in second price auction are far from truthful (see, e.g.,

[Kagel and Levin, 2011]). Recall that, in second price auc-

tion, the price is set by the runner-up, but paid by the winner.

In some senses, both the winner and the runner-up care lit-

tle about the absolute magnitudes of their own bids: only the

ranking (ﬁrst and second) is important. This can also be seen

from the linear program optimizing utility for the auto-bidder

(see, e.g., [Aggarwal et al., 2019]), where no decision vari-

able denoting bids appears and the solution only prescribes

whether each auction should be won or not. However, the bid

of the runner-up always means a lot to the winner. A well-

known enemy of IC due to this runner-up-winner interdepen-

dence is externality, i.e., the utility of a bidder depends on the

allocation and payment of not only itself, but also others.

It should not be surprising that externality makes manip-

ulation worthwhile since IC is not designed for the job. In

our auto-bidding markets, the objective of each auto-bidder

is deﬁned clearly without externality.4However, auto-bidders

adjust bids based on the overall performance across all auc-

tions. Even though at equilibrium changing bids unilaterally

could not beneﬁt the manipulator immediately, it may trigger

a cascade of responses that shift the whole market state. This

creates a kind of externality that is internalized into the out-

come of the shifted equilibrium. It is worthwhile to point

out that, for some results in this paper, it seems to be the

multiplicative pacing strategy that leads to a property. Actu-

ally it is irrelevant of the speciﬁc bidding strategy or even the

4Another common scenario where IC fails is that bidders do not

have complete knowledge of their valuations. This is not an issue

either in our case.

ROI-constraint: for simultaneous auctions with single-round

IC, bidders will always bid strategically across all auctions,5

which is enough to establish those results.

Letting the (bids of) opponents determine the payment of

the winner is the key to establish IC for single-item auctions,

but it is also the key to open the Pandora’s box in auto-bidding

markets, as will be detailed in the remainder of this paper.

1.3 Contributions

In this paper, we consider the auto-bidding market where

ROI-constrained value-maximizing bidders compete with

each other in simultaneous auctions. Our main focus is sec-

ond price auction: behaviors of auto-bidders within ﬁrst price

auction markets will be discussed at the very end.

We start by formulating our own solution concept of the

market (and its approximate version), named auto-bidding

equilibrium, since a pure Nash equilibrium may not always

exist. The equilibrium reasonably captures the expected

steady-state that the auto-bidders intend to reach collectively,

and its guaranteed existence puts our study on a solid theoret-

ical footing. Our most important results are as follows:

• It is PPAD-hard to ﬁnd an approximate auto-bidding

equilibrium within constant parameters.

• It is APX-hard to optimize revenue or welfare over all

auto-bidding equilibria.

• Non-monotonicity: an advertiser who raises its

tROI/tROAS (or equivalently, lowers the tCPA) at the

equilibrium could end up with a higher revenue after de-

viation (through a natural equilibrium transition process

to resolve multiplicity).

Besides their own signiﬁcance, the constructions used in es-

tablishing these results reveal many crucial structures of the

market and highlight the role played by IC. They serve as the

foundation to comprehend and interpret other characteristics

of the market.

We proceed to explore several practical concerns of great

consequence. For advertisers, we show that the market suf-

fers severe utility instability and input sensitivity issues. For

platforms, we demonstrate that biases exist broadly in the

widely-used A/B testing. Finally, we give a comprehensive

comparison between ﬁrst and second price auction, and show

5Even a non-constrained utility-maximizer could manipulate if

one of its opponents has constraints. Truthful reporting is secure

only when all the other bidders are insensitive to each other’s bid.

that ﬁrst price auction is generally exempted from the above

undesirable properties and performs better. As an application

of our results, we give our guess about why Google AdSense

moves from second to ﬁrst price auction in a partial manner.

2 Markets and Equilibria

We consider a market where a set of bidders N={1, . . . , n}

compete for a set of divisible goods M={1, . . . , m}. With-

out loss of generality, the tROIs of all bidders are set to

zero (equivalently, tROAS of one),6i.e., each bidder’s spend

should be no more than its acquired value. We use vi,j to de-

note the value of bidder ito good j. For each good j, there

is at least one bidder isuch that vi,j >0. The platform si-

multaneously runs a single-item second price auction for ev-

ery good. Auto-bidders are restricted to apply multiplicative

pacing strategies: the action space of bidder iis the set of

undominated multipliers αi∈[1, A],7and its bid for good j

is αivi,j . Multiplicative pacing is ex-post bidder-optimal, as

shown in Proposition 1. The omitted proof follows from a lin-

ear programming formulation of the ROI-constrained value

maximization problem, and the result is widely known in both

the literature and the industry.

Proposition 1. Suppose that bidders can bid arbitrarily

across auctions. Holding all other bidders’ bids, each bidder

has a best response wherein bids are generated by scaling its

valuations of all goods by a uniform multiplier, given that it

could freely choose to win any fraction of a good of which it

is a tied winner.

To complete the picture, one’s ﬁrst intuition may be to

specify a tie-breaking rule, make the allocation x∈[0,1]n×m

(where xi,j is the fraction of good jallocated to bidder i)

uniquely determined by α, deﬁne bidder’s utility as the ROI-

constrained valuation:

ui(α) = Pjxi,j vi,j ,if Pjxi,j pj≤Pjxi,j vi,j ;

−∞,otherwise;

and study the pure Nash equilibrium (PNE) of the game.

However, in Appendix D, we will give an example where, no

matter how ties are broken, a PNE does not exist. On closer

inspection, we ﬁnd that the steady-state of the market can be

captured instead by the solution concept deﬁned below.

Deﬁnition 1. An auto-bidding equilibrium (α, x)consists of

multipliers α∈[1, A]nand allocation x∈[0,1]n×msuch

that

•bidders with the highest bid win the good: if xi,j >0,

αivi,j = maxkαkvk,j for all i, j;

•winner pays the second price: if xi,j >0, then pj=

maxk̸=iαkvk,j for all i, j;

•full allocation of goods: Pixi,j = 1 for all j;

•ROI-feasible: Pjxi,j pj≤Pjxi,j vi,j for all i;

6See Appendix D on why this is WLOG. Later we may some-

times change the tCPA of a bidder by a factor λ, by which we mean

all the valuations of this bidder is scaled by λ.

7Fixing other bidders’ bids, αi= 1 always weakly dominates

any αi<1. The cap Acan safely be replaced by +∞for most

cases. See more discussion in Appendix D.

•maximal pacing: unless αi=A,Pjxi,j pj=

Pjxi,j vi,j for all i.

The auction rules and ROI-constraints are directly imposed

by the ﬁrst four conditions, while the best responses among

bidders are encoded in the maximal pacing condition in a less

straightforward way. To see this, note that, from bidder i’s

perspective, given the winning price of each good, αiacts

as a marginal-ROI threshold: it will win all goods in whole

with a marginal ROI strictly larger than 1

αi−1and lose those

with ROI strictly lower. At any auto-bidding equilibrium, if

αi>1,αi(and the resulting vector of bids with bi=αivi,j )

is exactly a best response since the marginal ROI of any good

lost or tied is strictly lower than zero, and winning anymore

will deﬁnitely violate the ROI-constraint. If, however, αi= 1

and bidder iis only allocated a fraction of some good as in

the example given in Appendix D, αiis technically not a best

response (for the normal form game) but the maximal pac-

ing condition is still satisﬁed. For such bidders, their oppo-

nents could always oscillate their multipliers around the equi-

librium point to achieve the corresponding stable allocation.

Theorem 1. An auto-bidding equilibrium always exists.

The proof is in Appendix F. In addition, the deﬁnition and

existence result can be extended to incorporate reserve prices

and additive boosts (see Appendix E), both of which are com-

mon practice in the industry.

The relaxed version of the equilibrium, named (η, δ)-

approximate auto-bidding equilibrium, is deﬁned as follows:

• bidders with bids close enough to the highest can win

the good: if xi,j >0,αivi,j ≥(1 −η) maxkαkvk,j (if

there is a reserve price rj, winner’s bid should also be

no less than (1 −η)rj);

• winner pays the second price (even if it is the bidder

with the second highest bid; if there is a reserve price,

the price is the maximum of the reserve price and the

second price);

• full allocation of goods;

• approximately ROI-feasible: Pjxi,j pj≤(1 +

δ)Pjxi,j vi,j for all i;

• approximately maximal pacing: unless αi=A,

Pjxi,j pj≥(1 −δ)Pjxi,j vi,j for all i.

3 Computational Complexities

In this section, we demonstrate two different kinds of in-

tractability or unpredictability of the market. Our ﬁrst result

shows that, in general, it is hard for a market to reach a sta-

ble state. But even for cases where an equilibrium is easy to

achieve, the difference among equilibria may be large, and the

second result tells us that, in general, it is hard to determine

how large the difference is.

At a high level, the interdependence that the (bid of)

runner-up determines the payment of the winner endows the

market with a structure similar to Boolean operators (elec-

tronic components and conductive wires). In digital electron-

ics, a functionally complete set of operators can be assembled

goods w1w2w3u¯u

input bidder w11/14

input bidder w21/14

input bidder w31/14

gate bidder u1/3 1/3 1/3 1/2 1/4

reserve price 1/7 1/7 1/71 1

Table 2: Valuation proﬁle to encode gate u.

to compute any Boolean function. In our model, it is PPAD-

hard to ﬁnd an equilibrium since it can encode any stable

state of a circuit that is continuous. When optimizing revenue

or welfare, the circuit structure collapses to discrete choices

that correspond to equilibrium selection, and the problem be-

comes NP-hard (and APX-hard since the correspondence is

almost exact). Note that hardness does not only exist in the

family of instances constructed in the reduction: for a gen-

erally hard problem, it is possible but usually non-trivial to

identify a meaningful subset of instances that are computa-

tionally tractable.

Our focus here is the many complex structures brought into

the market by IC. Nonetheless, to explore equilibrium proper-

ties quantitatively, we develop two algorithms (see Appendix

I for details) to compute equilibrium. Their own properties

are beyond the scope of this paper.

3.1 Complexity of Finding Any Equilibrium

Theorem 2. It is PPAD-hard to ﬁnd an (η, δ)-approximate

auto-bidding equilibrium for some constant η, δ > 0.

The full proof is in Appendix G. We will use equilibria

in a properly constructed market to encode feasible states

of a circuit, which is one of the most fundamental and fre-

quently used objects in complexity theory [Chen et al., 2009;

Rubinstein, 2018]. Papadimitriou and Peng [2021]show that

a circuit consisting only of a continuous version of NAND

(NOT-AND) gate is enough to capture PPAD-hardness, in

analogy to the functional completeness of NAND gate in dig-

ital electronics. The continuous gate computes the function

that sums all (at most 3) inputs and inverts the result: for a

gate u, given all the input values ywof its incoming gates

w∈Nu, its own value yushould satisfy that

yu∈





{0},if Pw∈Nuyw>0.5;

{1},if Pw∈Nuyw<0.5;

[0,1],otherwise.

An assignment yof values to gates is feasible if the above

constraints are satisﬁed for all gates. The key construction of

our reduction is given in Table 2. (This is a simpliﬁed version:

in the full proof we will remove the reliance on reserve prices

and take approximation into account.) We will associate each

gate uwith a bidder of the same name and use its multiplier

αuto encode the gate’s value yu(with yu=αu/2−1). The

valuation proﬁles are calibrated such that bidder uwould al-

ways win all input goods w1, w2, w3but at varying prices,

determined by (multipliers of) their corresponding input bid-

ders. The correspondence between bidder uand gate uis

almost straightforward:

• If the sum of input prices is too high, to satisfy its ROI-

constraint, bidder ucould not even win good uin whole

and thus won’t raise αuabove 2.

• If the sum is too low, good ¯uis required to satisfy bidder

u’s appetite for more valuation, which forces αuto be

ﬁxed at 4.

• If input prices sum to exactly 0.5, bidder ucan freely

choose αuas long as it is allocated uin whole but not ¯u

at all.

Intuitively, the hardness of ﬁnding a feasible state of a cir-

cuit lies in the coordination among the interconnected gates.

Given any value assignment, for each unsatisﬁed gate u, the

corresponding αuin the constructed market is either too large

(input goods are too expensive and ROI-constraint is violated)

or too small (input goods are too cheap and bidder uhas the

incentive to win ¯u). Consider hypothetically that we apply a

naive search algorithm8where, for each non-equilibrium as-

signment y, we choose some unsatisﬁed u, lower αuby a

small amount if it is too large, and raise it if it is too small.

As we adjust αu(or yu) for a bidder (gate), the payments

(sums of inputs) of its outgoing neighbors change accord-

ingly, which may also change their directions of adjustment

(e.g., a bidder goes from ROI-feasible to infeasible). As gates

can be assembled arbitrarily, we can imagine how hard it is to

ﬁnd a state that satisﬁes the constraints of all bidders/gates.

In retrospect, IC requires the payment of the winner to be

determined externally by other bidders. As a result, nothing

is local in the market and we can connect bidders in a way

that encodes any circuit perfectly. You may think that the

market constructed in the reduction can be simpliﬁed, e.g.,

by setting a reserve price for the input good such that its price

would no longer be affected by the input bidder and an equi-

librium could be easier to ﬁnd. However, this requires much

knowledge of the speciﬁc market a priori such as an upper

bound of a bidder’s multiplier, which is typically impossible.

In general markets, the aforementioned chasing behavior is

even more complex: e.g., if a gate bidder lowers its multiplier,

the consequence is simply lowering payments for its outgo-

ing neighbors and increase their ROIs, but in general markets

it may also lose goods it previously won and instead decrease

ROI for the opponent who now wins the item with a negative

marginal ROI. See the non-monotonicity instance in Section

4 for an example of this complex cascading phenomenon.

3.2 Complexity of Finding Revenue or Welfare

Optimal Equilibrium

Theorem 3. It is APX-hard to ﬁnd the optimal revenue or

welfare over all auto-bidding equilibria.

8Theoretically, any problem in PPAD can be reduced to the

generic End-Of-The-Line problem (by which the class is deﬁned),

where we are given (1) a directed graph consisting solely of non-

intersecting directed paths (lines) and (2) a vertex with no predeces-

sor (the start of a line). The task is to ﬁnd a vertex with no successor

(the end of a line). There is a natural algorithm (inevitably inefﬁ-

cient if PPAD ̸=P) that simply searches along any path. The search

procedure we depict here shares a similar spirit, but it may (or may

not) circulate and is only used to give some intuition.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

VulnerabilitiesofSingle-RoundIncentiveCompatibilityinAuto-bidding:TheoryandEvidencefromROI-ConstrainedOnlineAdvertisingMarketsJunchengLiandPingzhongTangTsinghuaUniversity{lijuncheng13,kenshinping}@gmail.comAbstractMostoftheworkintheauctiondesignliteratureassumesthatbiddersbehaverationallybasedonthei...

展开>> 收起<<

Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding Theory and Evidence from ROI-Constrained Online Advertising Markets Juncheng Li and Pingzhong Tang.pdf

共24页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Vulnerabilities of Single-Round Incentive Compatibility in Auto-bidding Theory and Evidence from ROI-Constrained Online Advertising Markets Juncheng Li and Pingzhong Tang

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: