Paul Resnick (presnick) wrote,
Paul Resnick

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.
Comments for this post were disabled by the author