You are currently browsing the monthly archive for July 2011.

Now that the velvet rope around Google+ has fallen, hoi-polloi like myself can join. Apparently the ability to partition one’s acquaintances into various sets, i.e. circles, is a big part of the appeal. There are the obvious ones like `family’ and `friends’. One can also create new circles. An implicit assumption is that the labels of circles are `positive’. I toyed with other labels.

Second Circle


Mass Murderer

Waste of Space

Finally settled on `Educated Beyond Their Intelligence’. I added an individual, X, I have not met and am unlikely to do so that I thought unambiguously fit the definition and would, if called upon, be able to defend such a choice and waited to see what happened. It turns out that Google does not read the labels of the circles in the sense of understanding them. It has dutifully informed X that I have included him/her in a circle. I receive happy missives from X. Thus, the real benefit of Google+. One can now appear to be nice to people who one does not care for on-line rather than just in real life.

At an EC conference many years ago I made some remarks on the role of budgets in sponsored search auctions. Unsurprisingly, they fell on deaf ears. I lack the gravitas of a Maskin or a Myerson or I was (am) wrong. Following (Walter Scott’s version of) Robert the Bruce, I try again.

To recap, sponsored search is a form of advertising sold by auction. When a user queries a search engine like Bing (product placement) for ipod, advertisers bid to be featured alongside the search listings. The advertisements appear in a list in a section of the page designated as sponsored. Each position in the list is called a slot. Generally, advertisements that appear in a higher ranked slot garner more attention and clicks from users. Thus, all else equal, merchants generally prefer higher ranked slots to lower ranked slots. Advertisers pay only if a user clicks on their slot. Furthermore, advertises also have the opportunity to submit a budget.

The standard model has N bidders and K < N slots. The probability that someone clicks on slot i is C(i) and is called the click through rate (CTR). Assume that C(1) >  C(2) > ….> C(K), i.e., lower ranked slots have smaller CTR’s. Notice also that the CTR is assumed independent of the identity of advertisers. Furthermore, the CTR’s assumed to be common knowledge.

When a user clicks on a slot occupied by advertiser j, advertiser j earns a benefit of V(j). This benefit does not depend on whether the click came via the top slot, bottom slot or any slot in between. Furthermore, this benefit is the private information of the advertiser. Advertiser j, assigned to slot i, enjoys a benefit V(j)C(i). Thus, each advertiser prefers a higher ranked slot to a lower ranked slot. Advertisers submit bids that represent what they will pay for each click received. Controlling for advertiser quality, higher bids are assigned to higher slots.

The advantage of the standard model is that the standard machinery of auction theory can be brought to bear upon it. There are features of the model one can criticize like CTR’s being common knowledge, CTR’s are advertiser independent and so on. These are well known and attempts to address them have been made in the literature. I would like to direct attention to the investigations that incorporate budget constraints. I argue these are wrong headed.

1) My first argument is by based on reverent authority. Preston McAfee has claimed that budget constraints don’t matter.

2) My second argument is that if advertisers have budgets that bind something is awry in the standard model. Observer that whether a click comes on the top or bottom slot, it is worth the same to the advertiser. Thus, the slot an advertiser is assigned to, only determines the speed at which clicks arrive. If an advertiser does not care about speed, it does not matter which slot they are assigned to. Given a fixed budget, an advertiser will want to buy clicks as cheaply as possible. So, an advertiser would want to be on the bottom slot where prices are presumably the lowest! One can pick apart the assumptions I made (like hard budget constraint, infinite patience). My point is, that when one accounts for the fact that the advertiser is consuming a flow rather than a quantity, it is no longer clear that an advertiser prefers the slot with the highest CTR.

3) My third argument is related to the second. If the search engine is going to keep the advertiser on a slot until their budget is exhausted, then it is the budget that determines how much revenue the search engine makes. The click through rate determines the speed at which the budget is consumed. So, the search engine should be concerned with assigning advertisers to slots so as to maximize the rate at which $’s are generated.

To summarize. Either budgets don’t matter or they do in which case simply inserting them into the standard model is wrong.

Kudos to Eilon for organizing this great workshop. It was exciting to see the lecture hall in the English Literature building full every time I entered, and completely packed for Aumann’s talk. I had to sit on the stairs, as I used to do during my grad years when I was auditing rock-star professor Jerome Mandel’s Medieval English class and found out that the entire university were coalescing there to watch him performing the green knight’s entrance to King Arthur’s court. I only came to the afternoon sessions and still managed to attend talks about stochastic games, repeated games, implementations, auctions, coding, matching, decision theory, bounded rationality. I expected to meet mostly the math game theory community, but I recognized only a small fraction of the participants, who came from econ, math, cs, social sciences, philosophy. Is there any other discipline where a workshop can interest such a wide audience ? and is there any other discipline where a workshop in Israel can attract so many people from out of the country, including some of the big shots ?

I hear I missed an entertaining “ game theory whither” roundtable discussion. I am usually disappointed with these events, since all the seniors agree with each other about everything, and are often wrong about it to boot. But rumor has it that this time was different. The issue seems to have been the importance of cooperative game theory. One discussant suggested that a way to measure the impact of a topic is its coverage in textbooks, and a certain book was mentioned in which the core, Shapley value and bargaining are not even mentioned. I like this suggestion because of its circular nature: game theorists evaluate game theoretic ideas according to the impact they make on the same theorists who also produce these ideas. Wouldn’t life be easier if game theory was applicable for building bridges or curing cancer or making money in the stock market ? Easier perhaps, but not as interesting in my view. Anyway, the suggestion has caused some intellectual controversy. No food fight, but sufficiently close to be interesting.

And speaking of food, the humus you get in the cafeteria near the law school is an offense to all taste and decency, though non-Israelis still enjoyed it (no surprise, it’s still better than what you get in the states under `humus’). If you go to Jerusalem, Lina (just near the via dolorosa, where Jesus of Nazareth has walked twenty centuries ago) was pretty good. The best of the best is Ali Karawan in Jaffa, but I didn’t get to go there this time. And speaking of Jaffa, Rann Smorodinsky got our everlasting admiration for suggesting Haj Kahil for dinner. And btw, Rann didn’t invent Kalai-Smorodinsky bargaining solution when he was six, as somebody suggested to me. That Smorodinsky is the father.

A word about Aumann’s talk: He presented his argument in favor of correlated equilibrium, following his seminal 1987 paper and a more recent paper (pdf) in which he considers the interim stage, after the players receive some information, and asks what payoff  they can rationally expect to receive in the game. (The paper is quite known for his previous ambitious title “when all is said and done, how should you play and what should you expect”). Aumann starts by claiming that game theory should not tell you what to do (as in “play the Nash Equilibrium”) but should only tell you which procedure to follow, and the procedure is to maximize utility with respect to your beliefs. Presumably many readers of this blog are already aware of Aumann’s argument, so i’ll cut directly to the chase. The dubious part is the common prior assumption. To justify it Aumann appeals to a rational expectation argument. John Muth defined “rational expectations” as expectations that are the same as the predictions of the relevant economic theory. This is a seminal concept which in a way captures the essence of game theory and perhaps economics in general: The economic agent, the subject matter of economic theories, takes into account to the predictions of the theories. Whatever theory an economist uses to make predictions, the economic agents already respond to the same theory; Economists are no smarter than their subject matter (contrast with physicists who presumably are smarter than electrons.) But back to Aumann’s point: The prediction of the theory is, says Aumann, the common prior. But I have two reservations here: First, didn’t Aumann say that game theory doesn’t tell you what to do but only which procedure to follow ? So how come the common prior is a prediction about what players believe and what they do ? Second, there are many correlated equilibria in the game, so many possible predictions of the theory. How do the players know which one of them to respond to ?

Let me mention another presentation, by Michael Rabin, whose 1957 paper about computability in game theory I will take with me to a desert island . Rabin presented a simple (“even financiers understood it”) scheme for conducting seal bids auctions which preserves the secrecy of the bids but enables the auctioneers to prove to all participants the truthfulness of the outcome (pdf ). So for example in a second price auction, the auctioneer will verifiably announce the identity of the winner and inform the winner about his price without revealing any information to anybody else. What I found unsatisfactory in this paper — and this is not a criticism of the paper since it is probably completely unrelated to it goal — is the fact that it has nothing to do with game theory: the strategic aspects of auctions are irrelevant here. To my understanding, this is a paper about verifiable computation of a function when the input is distributed between several agents. Auctions are just an example. This is cryptology at its best, but I wish we would see some papers where cryptology is directly relevant for game theory.

Oh, and I need to register a caveat to my previous insinuation that you cannot make omelets out of game theory. Matching theory is an exception. Nobody will suggest to look at game theory textbooks to evaluate the importance of Gale Shapley, since this algorithm and its variations are actually used in real-life situations like assigning med grads to hospitals, kidney pair donation, matching students to public schools. Matching theory lives outside the GT-community circulation of ideas. There were two great matching talks in the workshop, one of Itai about two body problem in the residency program and one by Federico about testable implication of stable matching with and without monetary transfer from aggregate data.

Photos ? Unfortunately I didn’t take any during the workshop. But we have some from the trip. Here is one taken by Itai Ashlagi.
See if you can identify the location and the participants

That’s it folks, thanks to everybody who encouraged me to blog more. Will try.

Kellogg faculty blogroll