Back

Auction Mechanisms

By: Dr. Yan Xu – Technical Specialist, Data & Optimization

Auction

Rokt’s platform operates in the Transaction Moment™ : when a user is completing a transaction on one of our e-Commerce partner sites, we select a relevant offer to show the user. For each of these Transaction Moments, an auction happens. The results of this auction decides which campaigns and offers will be displayed, where to present those offers, and how much our advertising partners should pay if the user engages with one of these offers. This auction mechanism plays a critical role in the efficiency of the Rokt platform.

Problem Definition

Given user context X (consisting of age, gender, publisher site, etc), M number of slots to show offers and N number of bidders, each bidder has a private value, V, which is the amortized value to the bidder of each click. Each bidder has a bidding strategy, which determines its bid price based on its private value: B = f1(V). Each bidder is assigned a score S = f2(B, X). Slots are assigned to bidders based on their scores, a simple way being “the bidder with the highest score gets the first slot, the second-highest, the second slot and so on”. Bidders are charged for clicks with a price P = f3(B, S)*. An illustrative example with N=1 slot and M=3 bidders is shown below:
*Note: To reduce annotations, we do not differentiate singular values and vectors. S means scores of all bidders here.


Figure 1: An example auction with N=1 slot and M=3 bidders.

An ideal auction mechanism should:

  1. Encourage small bidders to join the auction, without worrying about systematic disadvantages compared with large bidders. Ideally, it should provide a theoretical optimal bidding strategy which could maximize bidders’ utilities and enable fast client on-boarding.
  2. Incentivize bidders to improve advertisement quality and user engagement rates.
  3. Incentivize partners/Rokt platform to bring more bidders into the market.
  4. Incentivize Rokt platform to improve its system efficiency (e.g. click prediction and auto-bid).

Besides, auction mechanism should be easy to understand and transparent to bidders and partners.

First-price Auction

In First-price auction (or first-price sealed-bid auction), the highest bidder is the winner and it pays its own bid price. First-price auction is used in some advertisement markets [3, 4]. First-price auction’s strength comes from its simplicity and transparency to buyers and sellers. However, first-price auction has a serious drawback: there is no dominant bid strategy to maximize utility for bidders. The winning bidder needs to reduce its bid price to check whether it could win the auction with a smaller cost. Since each bidder does not know other bidders’ bid prices, there is no way to efficiently determine its bid price to reach the Nash equilibrium with other bidders. It tends to significantly increase system inefficiency and raise the bar for new bidders to join the market.


(source: https://www.spotx.tv/resources/blog/product-pulse/programmatic-auction-dynamics-101)

Second-price Auction

In Second-price auction (or second-price sealed-bid auction, Vickrey auction), bidders are charged for clicks based on the follower bidder’s score. Here, the number of slots is one. General second-price auction with more slots is introduced in the next section. In Second-price auction, the dominant strategy for bidders is to bid their private value. There is no incentive to bid higher or lower than their private value1.


(source: https://www.spotx.tv/resources/blog/product-pulse/programmatic-auction-dynamics-101)

Generalized Second-price Auction

The generalized second-price auction is a variation of Second-price Auction, which is designed to deal with the cases that N > 1. In this type of auction, the bidder with the highest score gets the first slot, the second-highest, the second slot and so on, but bidders are charged for clicks based on the following bidder’s score.

The generalized second-price auction is very common in Advertisement markets, due to its simplicity. However, bidding private value is not the optimal strategy anymore. For the following example, assuming the click rate of those two slots are 100%. Advertiser 1 could lower its bid from 7 -> 5 and get the second slot for the price of 2, increasing its utility from 1 -> 5. It will reduce the exchange’s revenue from 8 -> 7.

Vickrey–Clarke–Groves (VCG) Auction

In order to encourage bidding private value, VCG Auction is designed as a replacement for generalized second-price auction. In this type of auction, the highest bidder gets the first slot, the second-highest, the second slot and so on, but bidders are charged based on the reduced total value they cause to other bidders.

For the same example, advertiser 1 and advertiser 2 won the auction. If advertiser 1 was removed, advertiser 2 & 3 will win the auction and the total value is $6 + $2 = $8. When advertiser 1 joins the auction, the total value of other bidders is $6. So, advertiser 1 needs to pay the “the reduced total value”, $2.

In VCG Auction, bidding private value is the optimal strategy. However, VCG Auction is not easy to understand and tends to hurt the partner/platform’s revenue, especially when the number of slots is large. VCG Auction is currently used in Facebook2.

Auction in the Rokt platform

At Rokt, we decided to use generalized second-price auction (GSP) as our foundation due to a number of reasons:

  • GSP auction is widely accepted as the industry standard, which is easy for clients to follow.
  • At Rokt, 95+% of campaigns are Rokt-managed (in 2018). This risk of gaming the Rokt auction system (to use lower than private value bid price and gain higher utility) is low.
  • At Rokt, we do not disclose bid price profile to any external bidder, the likelihood of self-managed campaigns being able to game Rokt auction system constantly is low.

References
[1] Jonathan Levin. 2004. Auction Theory. https://web.stanford.edu/~jdlevin/Econ%20286/Auctions.pdf
[2] https://www.wired.com/2015/09/facebook-doesnt-make-much-money-couldon-purpose
[3] https://adexchanger.com/online-advertising/google-switches-to-first-price-auction
[4] https://adexchanger.com/platforms/big-changes-coming-auctions-exchanges-roll-dice-first-price

ABOUT THE AUTHOR

Dr. Yan Xu is currently a technical specialist on the Machine Learning team at Rokt. His work focuses on auction system, click/conversion prediction, strategic bidding, price modelling and email optimisation. Before Rokt, he was working in Amazon AWS Networking, where his work focused on network operation automation and network safety modelling. Dr. Yan Xu holds a PhD in computer science from National University of Singapore, where his thesis was in scalable short-term traffic prediction. He has authored/co-authored several publications and patents in leading conferences and journals.