How to Survive on a Desert Island

March 7, 2012 Leave a comment

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.”

Filed under Opinion Tagged with , , , , , , , ,

Separating Facebook users: 4.74 Degrees

January 11, 2012 5 Comments

Remember my less-than-epic, although very entertaining, quest to confirm or deny the famous Six Degrees of Separation experiment, originally conducted by Stanley Milgrim?  My goal was to send out letters, as in the original experiment, and have those recipients do their best to get those letters to a named someone in Boston.  Each link in the chain would write down their name on the letter, and, by the end, we’d have a list of how many people the letter went through to get to that final person.

You might remember that not one letter made it to my contact in Boston.

Many other groups have turned to Facebook to answer the question. Several failed, fake, or ineffective “Six Degrees” Facebook groups have popped up.

However, just a few months ago, the University of Milan partnered with Facebook to report that the average number of acquaintances separating any two people in the world was not six, but 4.74.

The new research used data from 721 million Facebook users, more than one-tenth of the world’s population. Facebook posted the results on their data facebook page.

From the New York Times article:

The experiment took one month. The researchers used a set of algorithms developed at the University of Milan to calculate the average distance between any two people by computing a vast number of sample paths among Facebook users. They found that the average number of links from one arbitrarily selected person to another was 4.74. In the United States, where more than half of people over 13 are on Facebook, it was just 4.37.

That being said, Facebook users are probably a self-selected bunch.  In this case, the people who use Facebook are those who have online access and choose to use Facebook.  They might be better connected individuals than those who do not use Facebook.

Importantly, this study raises questions about definitions like “friend,” “acquaintance,” or “guy you met one time on the bus.”  Which of those actually counts as a connection?

Either way, it’s pretty exciting to know that we’re only a few introductions away from people like Hugh Laurie and David Cameron.*

*If anyone here is Facebook friends with them, let me know.

Filed under news, Opinion, review, trends Tagged with , , , , , , ,

Learn Game Theory, for Free, from Stanford Professors

December 15, 2011 1 Comment

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.

Filed under conference, news, video Tagged with , , , , , ,

Social Learning Strategies Tournament – Join the GTN Team

September 28, 2011 2 Comments

Game Theory Ninja is putting together a team to compete in the 2nd Social Learning Strategies Tournament.  From the website:

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?

Interested in joining the team? If you’re in the Bay Area and can commit to meeting up for at least an hour a week, send a quick email with a paragraph about yourself to lisa@gametheoryninja.com.  We move fast in Silicon Valley; submissions are due Wednesday, Sept 28 at 5pm PST.

Can’t join the team?  We’re still looking for a team name.  Leave suggestions in the comments.  The more ridiculous, the better.

Filed under Competition, news, Opinion Tagged with , , , , , , , ,

The Shortest Monopoly Game Possible

August 22, 2011 3 Comments

When was the last time you played Monopoly?  How long did it take you to finish the game?  I bet it took longer than 21 seconds.

According to Daniel J. Myers, a professor of sociology at Notre Dame University, the shortest Monopoly game possible requires just four turns and nine rolls of dice.  That’s what we just saw above.

“One player moves around the board very quickly, to buy Boardwalk and Park Place, and places houses on them,” Myers explained. “And the other one ends up drawing a Chance card that sends them to Boardwalk, and they don’t have enough money to pay the rent with three houses, and the game is over.”

Statistically, this happens once every 253,899,891,671,040 games.  That’s 253 quadrillion games of Monopoly.

Dibs on the Top Hat.

Filed under news, Opinion, review Tagged with , , ,

← Older posts

Follow

Get every new post delivered to your Inbox.

Join 408 other followers