Targeting and Signaling in Ad Auctions
Abstract
Modern ad auctions allow advertisers to target more specific segments of the user population. Unfortunately,
this is not always in the best interest of the ad platform – partially hiding some information
could be more beneficial for the platform’s revenue. In this paper, we examine the following basic question
in the context of second-price ad auctions: how should an ad platform optimally reveal information
about the ad opportunity to the advertisers in order to maximize revenue? We consider a model in which
bidders’ valuations depend on a random state of the ad opportunity. Different from previous work, we
focus on a more practical, and challenging, situation where the space of possible realizations of ad opportunities
is extremely large. We thus focus on developing algorithms whose running time is polynomial
in the number of bidders, but is independent of the number of ad opportunity realizations.
We assume that the auctioneer can commit to a signaling scheme to reveal noisy information about
the realized state of the ad opportunity, and examine the auctioneer’s algorithmic question of designing
the optimal signaling scheme. We first consider that the auctioneer is restricted to send a public
signal to all bidders. As a warm-up, we start with a basic (though less realistic) setting in which the
auctioneer knows the bidders’ valuations, and show that an -optimal scheme can be implemented in
time polynomial in the number of bidders and 1/. We then move to a well-motivated Bayesian valuation
setting in which the auctioneer and bidders both have private information, and present two results.
First, we exhibit a characterization result regarding approximately optimal schemes and prove that any
constant-approximate public signaling scheme must use exponentially many signals. Second, we present
a “simple” public signaling scheme that serves as a constant approximation under mild assumptions.
Finally, we initiate an exploration on the power of being able to send different signals privately to
different bidders. In the basic setting where the auctioneer knows bidders’ valuations, we exhibit a
polynomial-time private scheme that extracts almost full surplus even in the worst Bayes Nash equilibrium.
This illustrates the surprising power of private signaling schemes in extracting revenue.
this is not always in the best interest of the ad platform – partially hiding some information
could be more beneficial for the platform’s revenue. In this paper, we examine the following basic question
in the context of second-price ad auctions: how should an ad platform optimally reveal information
about the ad opportunity to the advertisers in order to maximize revenue? We consider a model in which
bidders’ valuations depend on a random state of the ad opportunity. Different from previous work, we
focus on a more practical, and challenging, situation where the space of possible realizations of ad opportunities
is extremely large. We thus focus on developing algorithms whose running time is polynomial
in the number of bidders, but is independent of the number of ad opportunity realizations.
We assume that the auctioneer can commit to a signaling scheme to reveal noisy information about
the realized state of the ad opportunity, and examine the auctioneer’s algorithmic question of designing
the optimal signaling scheme. We first consider that the auctioneer is restricted to send a public
signal to all bidders. As a warm-up, we start with a basic (though less realistic) setting in which the
auctioneer knows the bidders’ valuations, and show that an -optimal scheme can be implemented in
time polynomial in the number of bidders and 1/. We then move to a well-motivated Bayesian valuation
setting in which the auctioneer and bidders both have private information, and present two results.
First, we exhibit a characterization result regarding approximately optimal schemes and prove that any
constant-approximate public signaling scheme must use exponentially many signals. Second, we present
a “simple” public signaling scheme that serves as a constant approximation under mild assumptions.
Finally, we initiate an exploration on the power of being able to send different signals privately to
different bidders. In the basic setting where the auctioneer knows bidders’ valuations, we exhibit a
polynomial-time private scheme that extracts almost full surplus even in the worst Bayes Nash equilibrium.
This illustrates the surprising power of private signaling schemes in extracting revenue.
Research Areas
