Log in

No account? Create an account
Paul Resnick's Occasional Musings
[Most Recent Entries] [Calendar View] [Friends View]

Tuesday, June 13th, 2006

Time Event
ACM EC 06: Fudenberg invited lecture
I'm at the ACM EC conference for the next couple days. Computer Science theory/algorithms/AI people looking at economic incentive issues.

This talk: "Stable Superstitions and Rational Steady State Learning", given by Drew Fudenberg (joint work with Levine)

(These are scattered notes taken during the actual talk. If it seems to the reader that it's getting at something interesting, you can probably get better intuitions about it, and more accurate characterization of results, from a paper, or a set of slides posted by Levine.)

Context: Learning in games. Anonymous random matching. Some history of previous papers that went too fast to capture.

"Self-confirming equilibrium"; less restrictive than Nash. No one can do better with "rational experimentation." Nash requires people to know what would happen if you deviate.

Agents off equlibirum path play infrequently, so have much less incentive to experiment. Wrong steps one step off equilibrium can't be stable, but wrong steps two off equilibrium can.

Illustration: Hmmurabi's second law. Accused person is thrown in river. If lives, accuser is killed. if dies, accuser gets their property.
Superstition: guilty are more likely to drown than innocent. This supersition is stable, because accusers rarely get to find out, because if they believe it, they won't accuse the innocent, and they don't get to find out.
Alternative supersitition: guilty will be struck by lightning. This superstition is not stable. Kids try petty crime and discover they're not struck by lightning.

Rational Steady-State Learning
Agent's decision problem: each agent in role i expects to play T times. Agent observes only terminal node each time. Agent believes faces time-invariant distribution of opponents' strategies. (This is wrong, but hopefully a reasonable model of how people would actually be thinking.) Steady states are where people play strategies that are optimal given the information they have from the previous rounds.

Results focus on characterizing steady states as T tends to infinity-- most players have lots of observations of play (but only rational experimentation in those rounds of play), and htere are few novices in the game in any round.

Asymptotic result for Hammurabi caes: there will be no crimes (in the limit of arbitrarily long lifetimes). With long but finite T, some crimes are committed, some false accusations take place, and people making false accusations learn that they work. But if there are few opportunities for being a witness, then there's no rational interest in experimenting with false accusation, because you won't get to do it very often even if you find out that the false accusation works.

Model highlights the role of experimentation in determining when a superstition is likely to survice.

David Parkes: question about applications to Sponsord Search design-- implications for encouraging experimentation or sharing information learned from experimentation.
Sponsored Search Auction Mechanisms
Current session has several papers on auction mechanisms for conducting auctions for which ads will be displayed in sponsored search.

Lahaie, analysis of alternative auction designs, including Yahoo and Google's current mechanisms. Offers an overview of the design space.

Mahdian and Saberi, MSR. Online algorithm, meaning that you have to decide which advertiser gets each search without knowing how many more searches there will be. Based on picking a single price to charge all advertisers. May be missing something, but the problem setup doesn't seem to match real advertising allocation problems, and the solution seems to unnecessarily restrict to fixed-price for all advertisers, rather than the kinds of mechanisms in the previous and next papers.

Aggarwal, Google presentation, Aggarwal et al.. Current mechanism: Advertiser makes a per-click dollar bid (for a particular search keyword). Google orders the bids based on bid*estimated-clickthru-percentage. If you're in slot j, you pay the rate based on the bid of slot j+1. This seems like it might be a nice generalization of 2nd price auction mechanism, but it's not-- it's not incentive-compatible. Presented design for a new mechanism in which truthful bidding is best, assuming others are bidding truthfully. For some reason, she said you can't use a VCG mechanism unless a "separability" condition holds. But the actual mechanism she presented is, I think, a VCG mechanism. Perhaps I'm missing something, or perhaps she has a more restricted idea of what a VCG mechanism is. The mechanism she presents is only incentive-compatible if there are no budget constraints that tie different auctions together or repeated-game effects from revealing your preferences today impacts on tomorrow's auction behavior of your opponents.

Estimating click-through rates for ads, without actually paying the full cost of putting your ad up and measuring it. This estimate is useful for optimizing your bidding.

<< Previous Day 2006/06/13
Next Day >>
Paul Resnick's homepage   About LiveJournal.com