Designing the Auction Mechanism for the App Store Search Advertising System
This story shares my experience in designing the auction mechanism for the search advertising system of Cafe Bazaar, Iran’s third-party android marketplace.
Before digging into the details of the mechanism, I need to explain the search advertising model that the mechanism is designed for.
Search-Ads Model
Simply put, Search-ads — the app store search advertising system, would show the android application “a”, on the first row of the search results for the query keyword “q” which is searched by the user “u” using the app store search system as an ad.
If “u” clicks on the install bottom on the advertisement, “a” would be charged a price amount determined from the auction conducted on the (“q”, “u”) pair.
Given the above-mentioned, one can deduce that Search-ads is a pay-per-click advertising system, and its success factors rely on two sides:
- Users who are using the app store search system, and are looking to find their desired android application
- Developers who are investing their money to advertise their android applications
From now on, I will refer to the users of the app store who use it to download their desired android applications as Users, and android developers who put their android applications on the app store as Developers.
Search-ads is an advanced advertising system, meaning a system that every android app developer, who wants to advertise their application, should create a campaign with a start and end date, a budget amount, and some other identifiers. After creating the campaign, they bid on their desired search query and may use additional Search-ads features — like query suggestion, broad bidding, etc.
Search-ads conducts auctions on every search query that is searched by any user; and further chooses at most one winner app to be shown as an ad in the first row of the search result.
This system is aiming sophisticated bidding towards developers. They should precisely know what target queries to go for and manage their bids accordingly.
Auction
Auction is the core of Search-ads. Thinking about designing the auction mechanism will lead one to consider its characteristics. Therefore, regarding the advertisement goal for the app store, the mechanism design process lays a set of specific policies on its designer shoulders.
Search-ads’ auction must-have characteristics are:
- First, Search-ads’ advertising model is highly dependent on the users — ad clicks are the foremost moneymaking actions.
To deliver, a decent user experience, the search results have to be in line with the user query. Furthermore, Search-ads, as the most prominent result of the query, play a major part in delivering that experience. If anything interferes with doing so, user fidelity to search results is lost. This may be interpreted differently. Some may say the winner app should have a high quality, others may say that it should be as relevant as possible to the query, etc. Nevertheless, the first characteristic tells that first comes in the users. - Second, the model needs to have developers as participants in different auctions.
Developers are investing their money in an advertisement system that sells install clicks. So, it is safe to assume that their first and most important incentive is to have new and reliable users install their android application, leading to a growth in their business. With this in mind, the auction mechanism should be simple and robust in the sense that everyone with a naive understanding of game theory could use it. Developers’ satisfaction using the Search-ads would result in more engagement and investment. Thus, the second characteristic tells that second comes in the developers. - Last but not least, the model generates revenue for the app store. So, designing an auction mechanism that is optimum or near optimum in generating revenue is reasonable. This last characteristic tells that last comes in the app store.
It is not only the definitions of these characteristics are important, but also their order. Their order imposes a set of policies toward designing the auction mechanism.
Mechanism Design
For simplicity, fix the query keyword “q”. Let’s assume that there exist n developers who want to advertise their android apps on “q” using Search-ads. Say the ith developer is willing to pay Search-ads up to Vi — valuation price, per any clicks on “q”. Ideally, the maximal revenue that the mechanism could hope to achieve per click would be MAXi{Vi}. However, the catch is that clicks happen with users’ actions. To better understand this point, it helps to bear these two notions in mind:
- Impressions:
An impression occurs when an app is displayed as an ad on the search results of “q”. - Click-Through Rates (CTR):
CTR of the app “a” on query “q”, is the i.i.d. probability that “a” will be clicked if displayed as an ad on the search results of “q”.
Given the definitions above, let’s assume that the ith developer’s app has the CTR Pi on “q”. One way to interpret these CTRs is by considering them as direct feedback from users. So, using CTRs and introducing expectations to the mechanism would make the expected maximal revenue per impression be MAXi{Pi * Vi}. Specifically, this value is achievable if the auction mechanism knows both the bidders’ valuation price and CTR. However, it may not be possible to accurately have these two variables. First of all, developers are bidding in a strategic environment. Therefore, they may not use their true valuation price in the auction and may manipulate their bids. Secondly, evaluating a true CTR is a hard task by nature and one should estimate the associated distribution of clicks.
Before talking about the proposed auction mechanism, let’s first consider one effective way of estimating CTRs.
CTR Estimation
There exist many ways to take statistics and machine learning approaches into account for estimating the probability of clicks e.g. training a model with enough and reliable data, etc.
One approach for solving the CTR estimation problem is thinking of it as a reinforcement learning (RL) set up. Dealing with exploration vs. exploitation trade-off is one of the RL optimizations’ unique characteristics. Precisely, multi-armed bandit (MAB) algorithms help balance exploration and exploitation in the CTR estimation problem.
To estimate the probability of clicks for the app “a” on “q”, think of it as an arm in an MAB setting. Whenever “a” is displayed as an ad to a user on “q”, “a” has gotten an impression on “q” and the signal that if it was clicked, which is entirely up to the user, is received by their actions on “q”. This CTR can be estimated with the number of impressions and clicks that “a” has gotten on “q” in the following way:
- P=1 — the probability of clicks, is initialized at the start — assuming some constant factor c that “a” has gotten c number of impressions and clicks which leads to the probability of c/c.
- Whenever “a” is pronounced the winner in the auction and displayed as an ad to a user, the number of its impressions on “q” is increased by one and so if the user clicks on the advertisement, the number of its clicks on “q”. P is re-estimated using the upper bound confidence interval estimation of the number of clicks on the number of impressions — conversion rate.
The upper bound confidence interval estimation can be interpreted as if Search-ads put its trust on developers — arms in the MAB setting, and uses the highest possible probability of clicks for every developer.
Proposed Mechanism
Let’s assume that the user “u” searches “q”. Say the ith developer bids Bi on that single run of the auction on “q”. Search-ads, having estimated the ith developer’s app CTR Pi, would sort Bi*Pi values in descending order. Let’s assume that B1*P1 is the highest and the B2*P2 is the second-highest values in the auction. The developer with the B*P value matching to B1*P1 is the winner of the auction. Furthermore, their app is displayed as an ad for “u”. If “u” clicks on the advertisement, the winner of the auction is charged the price amount calculated as follows:
Mechanism Analysis
Regarding Search-ads’ auction mechanism policies, let’s go over the proposed mechanism. First of all, the mechanism uses users’ direct feedback for estimating CTRs which play a key role in determining ads’ expected revenue. Unquestionably, there is a cost of exploration in this setting, however, the mechanism learns to accurately estimate CTRs through users’ feedbacks, leading to a better ad allocation in the future. Secondly, the mechanism puts its trust in developers — bidders, estimating the upper bound confidence interval of their CTRs. Furthermore, it lowers the winner’s bid to the smallest amount which they could have bid and still won the auction and charges them that value if the click happens — which is similar to the philosophy behind Vickrey (second-price) auction. Finally, the mechanism tries to gain the highest expected income per any ad impression. These three analyses are aligned with Search-ads’ three policies. I encourage the reader to further read the auction mechanism introduced in [1] and carefully analyze the differences and similarities that apply to Search-ads’ auction mechanism.
Conclusion
In this post, I tried to specify important factors when it comes to designing an auction mechanism for a search advertising system in an app store and also present an auction mechanism based on these factors. I hope the reader finds this experience useful.
References
[1] Nikhil Devanur and Sham M. Kakade. The price of truthfulness for pay-per-click auctions. In 10th ACM Conf. on Electronic Commerce (EC), pages 99–106, 2009.
