MIT + Social Media + Red Balloons

The DARPA network challenge begins tomorrow: They will place 10 red balloons throughout the country, and the first team to find them all wins $40,000.

The MIT team is operating through a social-network experiment: if you find a balloon for the team, you get some money. Whoever recruited you to the team gets half that amount, and whoever recruited them gets half of that again. So on and so forth.

So sign up as my recruit, recruit people yourself, and win money from DARPA.

http://balloon.media.mit.edu/Aaron/

Bomb detection

The STOC deadline approaches quickly. But in the mean time, be glad you don't live in Iraq: http://www.nytimes.com/2009/11/04/world/middleeast/04sensors.html?hp

Apparently the Iraqi government has spent tens of millions of dollars on bomb detection "technology" that seems just to be an expensive stick that works "on the same principle as a Ouija board" The devices cost up to $60,000 each. What do they do?

ATSC’s promotional material claims that its device can find guns, ammunition, drugs, truffles, human bodies and even contraband ivory at distances up to a kilometer, underground, through walls, underwater or even from airplanes three miles high. The device works on “electrostatic magnetic ion attraction,” ATSC says.

To detect materials, the operator puts an array of plastic-coated cardboard cards with bar codes into a holder connected to the wand by a cable. “It would be laughable,” Colonel Bidlack said, “except someone down the street from you is counting on this to keep bombs off the streets.”

Proponents of the wand often argue that errors stem from the human operator, who they say must be rested, with a steady pulse and body temperature, before using the device.

Then the operator must walk in place a few moments to “charge” the device, since it has no battery or other power source, and walk with the wand at right angles to the body. If there are explosives or drugs to the operator’s left, the wand is supposed to swivel to the operator’s left and point at them.

If, as often happens, no explosives or weapons are found, the police may blame a false positive on other things found in the car, like perfume, air fresheners or gold fillings in the driver’s teeth.

Most distressingly, apparently for the price of one of these devices, it would be possible to buy as many as 6 bomb-sniffing dogs, which actually do work (but take more time).

China

I'm leaving tomorrow (on a 6am flight) for Beijing, where I'm going to attend China Theory Week, at Tsinghua University. There are going to be a huge number of great talks, and I'm looking forward to seeing Tsinghua and the rest of Beijing. I'll get to see a bunch of friends there, although its amusing that I'll have to travel so far to see them. The most likely point of failure seems to be travelling from the airport at Beijing to the hotel: It will be me, Moritz Hardt, and David Steurer (none of us speak a word of Chinese) trying to convince a cab driver to take us to the hotel. We will have a printed picture of the name of the hotel in Chinese, which we can show the driver. If this doesn't work, I'm out of ideas.

If we successfully make it to the hotel, however, and find that blogger isn't blocked in China, then hopefully I will be able to upload a few updates from the conference!

God, morality, and general sum games.

There is a good editorial by Robert Wright in the New York Times. Read it here.

Briefly, the article is about why evolution and theology might not be incompatible, and that both the religious and the non-religious might understand this better if they understood the evolutionary algorithm (his phrasing) to be more powerful a process than they currently do.

Its an interesting article because it is written very much from an algorithmic perspective. In addition to referring to evolution as an algorithm (which is great!), Wright focuses on human morality as an illustrative example: he claims that morality is a sticking point between the religious and the scientific: Extremists on one side take the existence of a universal human moral code as proof of the existence of God, and as something that is incompatible with Darwin's theory of evolution. Extremists on the other side take evolution to justify moral relativism, to believe that morality is a quirk of human evolution, and not universal or "true" in any sense.

Wright gives a nice summary of the argument that human morality can be explained as a mechanism to allow people to play non-zero-sum games. On the one hand, we feel badly about betraying others, and on the other hand, have an urge to punish those that have betrayed us. This is exactly the incentive system that is necessary to play repeated prisoner's dilemma at the socially optimal equilibrium, and when put this way, seems like a perfectly reasonable outcome for an evolutionary process.

So a moral code provides an algorithm to play a repeated game. Now Wright supposes that we might live in a nicely behaved world, in which there exists some unique algorithm that is optimal in repeated self play. And perhaps it can always be found with local search. And perhaps we've already got an epsilon-approximation to the optimal moral code. (I am now deviating a bit from his exposition... But this is basically what he is supposing. It is in these assumptions that his argument is weakest.) If you believe all that, then given enough time, the evolutionary algorithm will always produce a species with the same moral code.

In this case, the argument for moral relativism goes out the window. Human morality isn't arbitrary, it is optimal, and in that sense, it exists "out there" as a universal truth independent of humanity. On the other side of the coin, if you believe that evolution is an algorithm which is guaranteed to result in the true moral code inscribed by God, because morality yields a survival advantage, then you can better believe that God created life merely by beginning the process of evolution. He could do this with certainty that it would converge to the optimal solution, which he designed by setting out the initial conditions.

Ok, so its a philosophical argument that has been rehashed over and over again, and isn't going to convince anybody of anything. But its nice to hear it rehashed as viewed through the algorithmic lens.

New CS/game theory blog

Sam Ganzfried, a colleague of mine and a student of Tuomas Sandholm, has just started a new blog: Game Theory in Practice. Sam is an avid poker player, and also studies poker professionally, trying to solve for its equilibria and derive optimal play. Sam says:

This blog will probably cover a wider range of topics such as poker and gambling theory, computer science, and game theory.

His will be the first blog I know of covering game theory and computer science from the AI perspective.

Maybe we're all the same

Every once in a while, a heated debate pops up in the CS theory blogosphere about whether or not our publication culture inhibits actual scientific progress. The concern is that we care too much about getting publications as an end in and of itself, and not about the progress of the field. In this last particular debate over at the complexity blog, some anonymous commenters compared the culture in the algorithmic game theory community unfavorably to that of the game theorists in the economics community.

But my guess is that computer scientists aren't so different than everyone else. In any case, it gives some perspective to see economists having the exact same debate about their own publication culture: here.

Asynchronous Games

I'm heading off to California for the week where I will present my paper with Moshe Babaioff and Liad Blumrosen, "Auctions with Online Supply", at the ad-auctions workshop that preceeds EC. If you are going to be around, you should come to my talk!

But this is a post on something fun that I was thinking about this past semester at Microsoft research, with Nina Balcan, Adam Kalai, and Yishay Mansour.

In game theory it often goes without saying that when we are talking about an (infinitely) repeated interaction amongst agents, that we are assuming that the agents are acting syncronously: that is, we implicitely have a universally known sequence of discrete clock ticks, and every agent acts simultaniously at each clock tick, without knowledge of the other's actions. Think about this standard model as modelling what goes on when you play "Rock, Paper, Scissors". I'm not sure why simultanious move repeated games became the standard historically -- my guess is that they are just easier to think about. But its not obvious that when modelling interactions (say) on the internet, that the simultanious move model is the right one -- perhaps some model that has players acting asynchronously, with knowledge of previous actions, is more realistic -- often we are without any syncronizing mechanism.

There is another reason why the simultanious move model might not be the best -- the complexity results in this model have been almost universally negative. It turns out to be hard to compute the Nash equilibria of even a 1-shot (non-repeated) two-player n x n game in which the payoffs are restricted to be in {0,1}. You might think that it is easier to compute the equilibria of a repeated game (since due to the "Folk Theorem", almost anything is an equilibrium in a repeated simultanious move game!), but for n > 2 players, that's known to be hard as well. In addition to accurately modelling the games we are interested in, we would like our solution concepts to be computationally plausible, and simultanious move Nash equilibria often seem to fail in both counts.

A reasonable first pass at a model of asynchrony in a two player game might go as follows: The game is still defined by an action set A for player 1, B for player 2, and utility functions u_i :AxB -> [-1,1]. Every day, a random player gets to perform an action from his action set, with full knowledge of the past history. If I (player 1) play action 'a' today, and my opponent last played action 'b', I get payoff u_1(a,b), and my opponent gets payoff u_2(a,b). And vice versa. We keep playing forever, and what we care about is our average per-day payoff in the limit, as time goes to infinity.

So how should I think about equilibria in this model? It turns out that this model is strategically equivalent to the model in which the two players take turns alternately making moves, instead of getting to make moves in a random order (informally, this is because if I get two turns in a row, it doesn't make sense to change my action, so equilibria from one model can be converted to equilibria in the other model and vice versa). This sounds like good news -- if we were only playing for finitely many rounds, this would just be a game of "perfect information", and we could find equilibria of the game just by "solving it", starting from the last round and working backwards. (Of course the game tree might be pretty big, so lets hope "finite" means "really small")

What about the infinitely repeated case? It turns out that infinitely repeated alternating move games always admit a particularly appealing kind of equilibrium: one in which each player plays according to a stationary strategy: a unit-memory strategy in which the next action is just a (possibly randomized) function of the opponent's last action. If these stationary strategies are not randomized (pure), they are even simpler to think about: they eventually lead game play into a deterministic cycle of actions, and players just care about their average payoff along this cycle.

We show the following in this alternating move model:

• All but a negligible fraction (smaller than any inverse polynomial) of games actually do admit equilibria in pure stationary strategies.
• If a game admits equilibria in pure stationary strategies, there is a PTAS to compute epsilon-approximate equilibria in pure stationary strategies.
• In any game, there is an FPTAS to compute epsilon-approximate equilibria in (non-stationary) pure strategies, even for n > 2 players.

This last bullet confirms the "backwards induction" intuition that alternating move games are actually more tractable than simultanious move games: there isn't an FPTAS for computing equilibria in simultanious move repeated games with n > 2 players unless PPAD = P.

So how about finding exact equilibria? My intuition is that there should be an algorithm to efficiently compute exact equilibria in these games, but I have no idea how to do it. Even for the special case of zero-sum games, the problem of computing -exact- policy equilibria seems to be closely related to a long-standing open problem in model checking, so solving the problem might be hard...

But I think that this model deserves more attention than it has recieved: why should we restrict our attention to a model that (often artificially) assumes simultanious play, when this restriction is making our lives computationally much harder than they need to be?

(One reason is that simultanious move equilibria have a nice simple description that makes analyzing things like the price of anarchy particularly easy. Unfortunately, since the model is computationally intractable, those price of anarchy guarantees might not always be so predictive... It would be cool if someone came up with a good technique for studying the price of anarchy in alternating move games, or in another tractable model.)

Oh, Pittsburgh

From the Post Gazette: 

Our mayor, Luke Ravenstahl, has begun the process to officially change his name to Luke Steelerstahl. Why would he do such a thing? Its because on Sunday the Pittsburgh Steelers will be playing the Baltimore Ravens. According to our mayor:

On behalf of the Steelers Nation, I've decided to remove the word 'Ravens' from my name just like the Steelers will remove them from the AFC Championship.

Stahl, of course, means "Steel" in German.