So You Want to be a Game Theory Ninja?

Per previous post, Stanford is offering a free online Game Theory course.  And this Ninja is hosting study sessions on Google+. And you’re invited!

What: Game Theory Ninjas in Training.
When: Tuesdays at 5pm PST, starting March 27th.
Where: Google Hangouts!

If you want to join us, add me on Google+ and comment on this post. I’ll add you to the study session circle. The invite for the hangout is going to be private to those in the circle; that will help us keep the conversation relevant to the class. That said, obviously feel free to invite anyone who’s taking the class to join us.

For those in the Bay Area/near Mountain View: If you want to join me live, let me know! I’ll be in a conference room on Google campus, and am happy to share the IRL collaboration love.

Post to indicate interest is here: https://plus.google.com/u/0/106776967321860936337/posts/d8rNckNCKyB

How to Survive on a Desert Island

Fish exhibiting swarming behavior. Or, what I imagine Bayes_Bots to look like.

For the last few months, a team and I have been aggressively competing* in the 2nd Social Learning Strategies Tournament. Here’s what it’s all about:

Suppose you find yourself in an unfamiliar environment where you don’t know how to get food, avoid predators, or travel from A to B. Would you invest time working out what to do on your own, or observe other individuals and copy them? If you copy, who would you copy? The first individual you see? The most succesful individual? The most common behaviour? Do you always copy, or do so selectively? If you could refine behaviours, would you invest time in that or let others do it for you? What if you then migrated – would you rely on your existing knowledge, or copy the locals?

The team consisted of a rocket scientist, a mathematician, a genetic engineer, and me.  Fortunately, the other three had enough brainpower to help us put together something interesting to submit.

The deadline for submission was Feb 28, 2012. Our team ended up using Baysian economics to put together a competitor.  If you’re interested, the abstract overview is below.

Bayes_Bots makes decisions based on the expected payoff of the moves in her arsenal: Observe, Innovate, Exploit, and, in the appropriate extension, Refine.  To decide which move to use, Bayes_Bots will look at the distribution of the learned payoffs from Innovate, and Observe.  Bayes_Bots uses Bayesian inference, to learn these distributions: she assumes that the values learned from Innovate and Observe can be modeled by an exponential distribution, and given a distribution on the payoffs associated with each arm, the means of the Observed distributions will follow a Beta distribution, while the payoffs from Observe follow an exponential distribution.  Bayes_Bots will discount older information as less reliable, using Pc as the probability that a given strategy’s payoff changes.

Bayes_Bots will Innovate rarely.  However, she will always Innovate on her first turn; this will help provide new raw information to the collective population of agents.

Observe_who. In the observe_who strategy, Bayes_Bots will not change her strategy.  The assumption is that information is equally valuable from all other agents in the field, regardless of their age, number of times they’ve been observed, etc.

Refine. Bayes_Bots will Refine one of her high-payoff moves at least once, in order to understand what benefit that might have to her overall expected payoffs.  Otherwise, Bayes_Bots will not change her strategy; if other agents refine their strategies, Bayes_Bots will learn the refined payoff.

Localization/Demes. When Bayes_Bots changes to a new deme, she will discard information about the distribution of payoffs from observed strategies.  She will retain information regarding the distribution of payoffs from innovated strategies, as well as the distribution of the means of the observed strategies, as these pieces of information are assumed to be useful across all demes.

If you want to read the full entry, let me know – I’m happy to share out the doc.  It also has our very complex math and equally complex Python code.

*by “aggressively competing” I mean “meet at a coffee shop once a week to pretend we know what we’re talking about and eat chocolate.”

Game Theory of the Burning Man Lottery

Burning Man is difficult to describe. Having never been to this event, I gather it’s a temporary city in the desert, full of art and often lacking in clothing.  Despite the somewhat disconcerting description, Burning Man is very popular.  To deal with this demand, Burning Man came up with a fairly convoluted lottery system.

The lottery system chosen by Burning Man is, like everything else related to this community, unconventional.  Let’s talk through some options Burning Man Organization could have used to deal with the increased demand for these tickets.

Players

    Burning Man Organization (BMORG) – the organizers of the event. If this were a traditional event, their goal would be to make money. However, BMORG also values fairness and equality, as well as access to the event. They just need enough money to host the event.
    Burners – the attendees of the event. Their motivation is fairly simple: they want to attend the event.

Constraints

    Really just one: number of Burners who can attend.  From what I can gather, this is approximately 53,000.

Possible Solutions -or- How can tickets be fairly distributed?

First Come, First Serve.  The easiest way to distribute tickets: BMORG sells tickets until there are none remaining.  This is the strategy they used until this year. It was discarded because tickets were selling out too quickly. Remember when I mentioned BMORG values fairness, equality, and access to the event? A first-come-first-serve model didn’t support that.

Highest Bidder. Tickets are auctioned off to whomever wants to pay top dollar for them.  This would capture the maximum amount of profit, while allowing Burners to indicate their willingness to pay for tickets. However, the Burning Man community tends to shy away from extreme-capitalist strategies.  This distribution option wouldn’t allow everyone equal access to the event.

Pure Lottery. A completely random, completely fair option. While this doesn’t allow for any sort of price discrimination on the part of the Burners, I’m honestly not sure why this method wasn’t chosen.

Hybrid Model -or - the solution they chose. The “Lottery” BMORG ended up with is a hybrid model of the three above options. You can read about it in detail here. A quick summary:

  • Round 1: Pure lottery, $420 per ticket. 3,000 tickets sold. Limit 4 tickets per entry.
  • Round 2: Pure lottery. Tickets sold in three tiers: $$390, $320, and $240. If you entered the lottery at a higher level, you were also entered into the lottery for the lower pricing levels. This captures willingness to pay of Burners. 40,000 tickets sold. Limit 2 tickets per entry.
  • Round 3: First-come-first-serve model, $390 per ticket. 10,000 tickets to be sold. Limit 4 tickets per entry.

Several Burners, knowing they weren’t guaranteed tickets this year, entered the Round 2 lottery several times, hoping one of their entries would garner them tickets. As a result, the pool of applicants was artificially inflated, generating a surge of false demand. The results of the Round 2 lottery were revealed yesterday. Right now, there are a lot of unhappy Burners who didn’t get tickets.

My Proposal -or- Not A Perfect Solution

Situations in which demand outstrips supply are tricky. For something like Burning Man, where people feel such an intense connection with the event, distributing tickets can become a very complex matter.

That being said, here’s a solution I like.  Again, it isn’t perfect, but it touches on a lot of the constraints and player values.

Of the 53,000 tickets, randomly distribute 47,700 of them, for free, via a random lottery. Fair, equitable, and allows equal access to all demographics. (I got to 47,700 because it’s 90% of the available tickets).

Auction the remaining 5,300 tickets to the highest bidder. The implication here is that the average price someone would be willing to pay for an auctioned ticket would be enough to offset the tickets given away for free. In this case, that price would be around $4,000 per ticket.  While that seems outrageous, I gather that there are some who would be willing to pay that much, especially if their ticket allowed nine other Burners to attend Burning Man for free.

Recap

The problem both Burners and BMORG face is too much demand for a product with limited supply. The motivations of each group are similar: attend a great event. However, the path to that outcome, for each group, are just different enough that seemingly simple problems like this become very complex, very quickly.

If you were solving the Burning Man Lottery problem, what solution would you propose?

Learn Game Theory, for Free, from Stanford Professors

Ever wanted to dip your toes into the ocean of Game Theory?  Want to do it for free?

Now you can! Stanford’s offering several free courses online, starting in February.  A few of my esteemed Google colleagues pointed me towards this Game Theory class. It’s being taught by the inestimable Matthew O. Jackson and Yoav Shoham.

Here’s a description of the class:

Popularized by movies such as “A Beautiful Mind”, game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Beyond what we call ‘games’ in common language, such as chess, poker, soccer, etc., it includes the modeling of conflict among nations, political campaigns, competition among firms, and trading behavior in markets such as the NYSE. How could you begin to model eBay, Google keyword auctions, and peer to peer file-sharing networks, without accounting for the incentives of the people using them? The course will provide the basics: representing games and strategies, the extensive form (which computer scientists call game trees), Bayesian games (modeling things like auctions), repeated and stochastic games, and more. We’ll include a variety of examples including classic games and a few applications.

There won’t be a lot of heavy math, and the lecture videos will broken into small chunks, usually between eight and twelve minutes each.

I signed up!  Let me know if you did, too, and we can work on this together.

You’re Narrow-minded if You Are This

Confirmation bias is one of the most interesting biases in behavioral economics. Confirmation bias suggests that most people only consider evidence if it supports a belief they already have.  Check it out:

Confirmation bias (also called confirmatory bias or myside bias) is a tendency for people to favor information that confirms their preconceptions or hypotheses regardless of whether the information is true. As a result, people gather evidence and recall information from memory selectively, and interpret it in a biased way. The biases appear in particular for emotionally significant issues and for established beliefs.

For example, in reading about gun control, people usually prefer sources that affirm their existing attitudes. They also tend to interpret ambiguous evidence as supporting their existing position. Biased search, interpretation and/or recall have been invoked to explain attitude polarization, belief perseverance, the irrational primacy effect, and illusory correlation. (via the illustrious Wikipedia)

From the fantastic webcomic Saturday Morning Breakfast Cereal comes this comic:

Want to learn more about cognitive biases?  Check out this sweet song about them.

Follow

Get every new post delivered to your Inbox.

Join 408 other followers