In the Positive Theory Of Capital (1889), Austrian economist Bohm Bawerk constructs an imaginary market for horses with eight sellers and 10 buyers. Each seller has a minimum ask price for their horse and every buyer, a maximum bid price for each horse. Provided the maximum bid of a buyer is greater than the minimum ask of a seller, a transaction can take place. The difference between the bid and the ask prices represents the surplus generated. Bawerk asks what assignments of horses to buyers would result in a maximization of the total surplus.
The auction for internet ad spaces on search returns can be recast as an “assignment game”, studied by Lloyd Shapley and Martin Shubik in a 1972 paper. Imagine you are searching for a flight from Bengaluru to Goa. Alpha, Charlie and Beta are online travel agents vying for the first and second position in the two ads that will be shown. Every combination of an advertiser with a position yields a certain surplus, equal to the number of clicks the ad attracts multiplied by the profit per click (see table). This surplus has to be shared between the advertiser and the search engine. As in the horse market, the aim is to maximize the total surplus by assigning the right advertiser to each position.
Check that total surplus is maximized at a level of Rs1,300 when Alpha is assigned to position one (P1), Beta to position two (P2), and Charlie gets left out. But the appropriate sharing of that surplus between advertisers and the search engine is crucial to ensuring the stability of this outcome.
A revenue of Rs600 for P1 and Rs375 for P2 for the search engine (leaving Rs200 for Alpha and Rs125 for Beta) is feasible. But a revenue of Rs450 for P1 and Rs300 for P2 for the search engine (leaving Rs350 for Alpha, and Rs200 for Beta) is not feasible. Note that if Beta occupied P1 the total surplus would reduce from Rs800 to Rs700. Yet, Beta could offer to pay Rs475 for P1, which is higher than what Alpha is paying, leaving Rs225 for itself—making itself better off, and destabilizing the assignment.
A similar line of reasoning will show that a revenue of Rs600 for P1 and Rs250 for P2 for the search engine is not feasible. Alpha who is in P1 in the optimal assignment could switch to P2 while, simultaneously, paying more than what Beta is paying and making itself better off. Further, the share of P1 cannot be less than Rs400, and the share of P2 cannot be less than Rs200, for otherwise, Charlie, who is the wallflower in the party, could break in and offer more for either of those positions while also earning a little bit for itself.
The optimal assignment along with the set of divisions of the surplus which are immune to these kinds of destabilization constitute the “core” of the game. The core has an interesting property: there must exist an element of the core that is most preferred by all advertisers and least preferred by the search engine. There must also be another element which is most preferred by the search engine and least preferred by all advertisers. In this example, one extreme point gives the search engine a revenue of Rs750 for P1 and Rs500 for P2. You may like to calculate the other extreme point yourself!
Given this conflict of interest between the two sides of the market, we can ask if the mechanism of the second price auction currently in use for internet auctions tends to favour the advertisers or the search engine. Demange, Gale, and Sotomayor, in a 1986 paper, show that in assignment games, the pay-offs of buyers (advertisers in this case) in the buyer-optimal stable assignment coincide with their pay-offs in the “Vickrey-Clark Groves (VCG) mechanism”, which is the mechanism that incentivizes truthful reporting of values. Recall the second price auction does not incentivize truth telling in the case of internet ad auctions . Therefore, it leads to different pay-offs from the VCG and shifts the equilibrium towards outcomes more favourable to the search engine. The avoidance of the VCG, in other words, may not just be driven by the fact that its rules are a tad too difficult to understand for a mass market.
But, surely, the elephant (or the horse) in the room as far as the internet advertising market is the “sponsored search” return, Google’s own comparison shopping service, that appears in the search return along with regular advertisers and organic returns thrown up by Google’s algorithm. While the European Commission has fined Google €2.42 billion for this conflict of interest, the US Federal Trade Commission has ruled that there are insufficient grounds for intervention. The future of the internet could rest on the resolution of such dichotomies in the $50 billion market for ads.
Rohit Prasad is a professor at MDI, Gurgaon, and author of Blood Red River. Game Sutra is a fortnightly column based on game theory.