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.

CS theory in 60 minutes for highschool students

I might have the opportunity to give a talk at a high school, as part of a "what is science" style seminar. The audience would presumably tilt towards the more nerdy (since attendance is voluntary), but still probably wouldn't have more than a standard high school background in math or computer science (which means, likely, that they have never heard of computer science).  So I'd like to give a talk that introduces them to computer science as the study of computation, and I'd like to make it sound cool. So there should be perhaps some proofs of cool theorems, but all of the proofs should be simple enough to do by picture on a powerpoint slide. I'm looking for suggestions for what to present.

My first thought is a talk titled something like "What we can't do, infinity, and even bigger". It would cover two proofs that I think have a particularly high coolness to complicatedness ratio: Cantor's proof of the uncountability of reals, and Turing's proof of the undecidability of the halting problem. The outline would perhaps be something like:

1) Infinities are not all equal. There are lots of integers, but there are WAY more real numbers. Spend 20 minutes explaining diagonalization, and what it means.

2) Computer programs can do a lot, but not everything. 

Spend 20 minutes explaining the halting problem, and what it means to be undecidable. I'd probably avoid defining Turing Machines, since that seems like a mess, and just talk about it in terms of computer programs, which are hopefully a little more familiar

3) The punch line: Computer programs are countable, like the integers, but the problems that you might want to solve (languages) are uncountable, like the reals. So although computer programs can solve lots of things, actually, most things can't be solved. Hopefully this can be done in 10 minutes given that I've already talked about uncountability and undecidability.

I like these proofs since they don't require any machinery, and seem like they can be done visually with some animations. Thoughts?

Incentives, computation, and privacy

What do computer scientists bring to the study of game theory? One thing is simply a computer science style of analysis: worst case input, competitive ratios, approximation factors, etc. Perhaps the more interesting thing, however, is the study of how incentive constraints and computation interact: since we want to actually implement any mechanism we might dream up (in principle), it is subject not only to traditional game theoretic constraints such as truthfulness, but also standard computational limitations.

One fundamental question is: What can be computed by algorithms that satisfy constraint X, and it is natural to substitute "incentive compatibility" for "constraint X". An interesting study along these lines appeared in the last FOCS: "On The Hardness of Being Truthful"by Papadimitriou, Schapira, and Singer. This paper gives an example of a natural NP hard problem that can be well approximated efficiently, can be implemented truthfully, but cannot be efficiently well approximated by a truthful implementation: that is, they show that for this problem, truthfulness and computational limitation restrict what is algorithmically possible, although neither limitation is insurmountable on its own. 

They call the problem the "Combinatorial Public Projects Problem" (CPPP), although it is really just submodular maximization. In the CPPP, there are n agents, and m potential public goods. a mechanism for the CPP problem will select a subset of k of these goods. The agents have an opinion over which subsets are best: each agent i has a submodular valuation function f_i over sets of goods. The mechanism wishes to maximize the social welfare: it wants to pick the set of k goods that maximizes the sum of the agents valuation functions. We'll call this sum F.    Notice that since each f_i is submodular, F is submodular as well, and so the problem the mechanism faces is simply submodular maximization, and it is easy to show that the greedy algorithm (which selects at each stage the good that produces the largest marginal utility, until k goods are selected) achieves a (1-1/e) approximation. Not bad! But also not truthful -- agents may be incentivized to misreport their valuations. Whats more, the classic VCG mechanism achieves perfect social welfare, and enforces truthfulness -- but of course cannot be implemented efficiently, since it involves solving an NP hard problem exactly. What Papadimitriou, Schapira, and Singer show is that no truthful efficient algorithm can guarantee social welfare better by any polynomial factor than Sqrt(m) -- a huge gap from what is possible with either constraint alone.

Now whenever you see a striking impossibility result like this, its tempting to ask how resilient it is. Does it still hold if no player by himself constitutes a large fraction of the total social welfare? What if we relax truthfulness to approximate truthfulness, so that perhaps players can benefit by lying, but can't gain more than some small epsilon?

It turns out this particular problem is no longer so hard when we relax some of our constraints. Anupam Gupta, Katrina Ligett, Frank McSherry, Kunal Talwar, and I have a mostly unrelated paper, called "Differentially Private Approximation Algorithms". In this paper we also ask "What can be computed by algorithms that satisfy constraint X?", but in this paper, constraint X is differential privacy. We get mostly positive results: many NP hard problems, including the CPPP problem can be well approximated efficiently by privacy preserving algorithms. So what does this have to do with truthfulness?

In their 2007 FOCS paper "Mechanism Design via Differential Privacy", Mcsherry and and Talwar observed that mechanisms that satisfy differential privacy are also approximately truthful: privacy guarantees that any single player who changes his input does not change the probability of any output by more than a (1+epsilon) factor; therefore, he cannot increase his utility by more than a (1+epsilon) factor by deviating from a truthful input. In general, lets say that a mechanism satisfies gamma-truthfulness if no agent can benefit by more than an additive gamma factor by deviating from truthful behavior. So suppose in the CPP problem we scale every agent's valuation function so that her maximum valuation is 1. As a corollary of one of our approximation results, we show that for any gamma, there exists an efficient, gamma-truthful mechanism that achieves an additive O(k log m * log(1/gamma)/gamma) approximation factor. (Contrasting with the impossibility result of a multiplicative Sqrt(m) factor for 0-truthful mechanisms). In particular, for instances in which we have OPT = Ω(k log m * log(1/gamma)/gamma), this is an approximately truthful constant factor approximation algorithm.

I think that computer scientists are just starting to scratch the surface of the interplay between game theory and computation. It seems that there is a rich theory of incentive compatible computation waiting to be discovered, and that algorithmic game theory will prove to fit in nicely with the rest of theoretical computer science as a discipline that studies the fundamental abilities and limits of computation.

 

Computer science in the news

The New York Times magazine has a feature this week on the NetFlix challenge:  http://www.nytimes.com/2008/11/23/magazine/23Netflix-t.html?pagewanted=1&hp

Its actually puts computer science in a pretty nice light -- it makes it seem very exciting. In particular, it seems to take the position that complex machine learning systems have something approaching real intelligence -- or at least that they are complex enough that they aren't fully understood by their own creators:

There’s a sort of unsettling, alien quality to their computers’ results. When the teams examine the ways that singular value decomposition is slotting movies into categories, sometimes it makes sense to them — as when the computer highlights what appears to be some essence of nerdiness in a bunch of sci-fi movies. But many categorizations are now so obscure that they cannot see the reasoning behind them. Possibly the algorithms are finding connections so deep and subconscious that customers themselves wouldn’t even recognize them. At one point, Chabbert showed me a list of movies that his algorithm had discovered share some ineffable similarity; it includes a historical movie, “Joan of Arc,” a wrestling video, “W.W.E.: SummerSlam 2004,” the comedy “It Had to Be You” and a version of Charles Dickens’s “Bleak House.”  For the life of me, I can’t figure out what possible connection they have, but Chabbert assures me that this singular value decomposition scored 4 percent higher than Cinematch — so it must be doing something right.

The author is definitely giving the computer too much credit for these anomylous clusters (and holds up "singular value decomposition" throughout the article as some sort of magical technique), but the point made is the right one. The difference between real intelligence and "just an algorithm" does in large part seem to be whether or not you can anticipate what its going to do. When you create a program that can come up with output that surprises you, thats pretty cool.

Auctions with Unknown Supply

Its been a long time since my last post; I spent the summer at Microsoft Research in Silicon Valley, which was tons of fun, and since then I've been writing up some of the work I did there. Oh, and I've also been wasting an inordinate amount of time reading political blogs. But all of these things are now over, and its time for a post. Today, I'll write about one of the cool projects I worked on at Microsoft, with Moshe Babaioff and Liad Blumrosen.

Lots of people have heard talks about truthful auctions by now: A seller has some object he wants to sell, and bidders each have some private value for the item. The seller wants to sell the item to the highest bidder. How should he do it? If he just asks for bids and sells to the highest bidder, charging the bidder his own bid, buyers will lie about how much they value the item, and the item may not actually go to the person who values it the most. A classic result of Vickrey says that the seller should solicit bids, and give the item to the highest bidder, but charge him the second highest price. Then, the bidders can't do any better for themselves by lying about their valuations -- they should all just tell the truth! Auctions that have this property are called truthful auctions. Its easy to generalize this to the case in which the seller has not just a single item, but instead is selling k identical items.

This is all well and good -- the problem of selling items seems solved. And now that auctions are used to sell billions of advertisements on the internet, the theory of truthful auctions can be put to good use.

Unfortunately, there are some characteristics of these auctions that haven't been modelled. Even if we abstract away the details of particular ad systems (different slots worth different amounts, etc.), the items we are selling are page views, and page views are peculiar items indeed: First and foremost, we don't know how many items we will have available to sell! The items arrive online as users make clicks, and since we can't delay showing the user a page, we must decide on the allocation and price of each item as soon as it arrives, before we know how many future items will arrive. So the auctions we really want to study are online. And unlike previous work on online auctions, the auctioneer knows who the bidders are -- its the items that arrive online.

The Vickery auction maximizes social welfare -- the sum of the valuations of the bidders who recieve items. A basic question is how well we can approximate the optimal social welfare when items arrive online. At first blush, it seems that perhaps we can achieve optimal social welfare: After all, if we knew bidders' valuations, the greedy algorithm which simply allocated items as they came in to the unsatisfied bidder with the highest bid would achieve this. The problem is designing a payment rule that incentivizes bidders to actually bid their true values.

But lets step back -- what do we mean, anyway, when we say that the supply is unknown to the mechanism? There are several things we might mean. Perhaps, as is standard in the analysis of online algorithms, we mean that the supply is adversarial -- items arrive one at a time, but may stop at any time, and we want good guarantees on social welfare regardless of how many items arrive. However, this might not be totally realistic. After all, if we are Microsoft (or, lets see... Google?), we're running lots of these auctions every day, and we have good distributional information about how many items arrive each day. So another thing we might mean is that the total number of items that will arrive in any given day is drawn from a distribution that is known to the auctioneer. In this case, we only want good welfare guarantees in expectation over this distribution.  

And this gets to the heart of our result: distributional information is -really- important. What we show is that in the adversarial setting, its impossible to get a constant approximation to social welfare. In fact, no deterministic truthful mechanism gets better than the trivial n-approximation in the worst case. Even randomized truthful mechanisms can't achieve better than an Ω(loglog(n)) approximation.  On the other hand, in the stochastic setting, it is possible to get a constant approximation to social welfare. For any distribution that satisfies a technical condition known as monotone hazard rate (and many distributions do), there is a deterministic truthful mechanism which achieves a ~ 16 approximation. 

So what is the take home message? Pay attention to distributional information, at least when it comes to your supply. Economists often make distributional assumptions about the values of the bidders, and our result shows that this is less important in our setting -- we don't need this to get a good approximation to welfare. This is good, because a search engine has direct access to the distribution over clicks and page views, but must do some guessing to figure out the true values of its bidders (as distinct from their bids). And this is how it should be -- if we have a model in which what we want to accomplish is impossible, we should fix it with the information that we have right under our noses.

Grim Trigger

It seems that the late army scientist turned anthrax suspect Bruce Ivins was not just a microbiologist, he was a game theorist. In an article today in the New York Times, we learn that before the FBI focused its anthrax investigation on him, he wrote a will, requesting that in the event of his death, his remains be cremated and scattered. But talk is cheap, and he wasn't sure that his wife and children would honor his request. 

It turns out that Ms. Ivins, his wife, was an anti-abortion activist and a former president of Frederick County Right to Life, a pro-life organization. So Ivins wrote the following into his will:

“If my remains are not cremated and my ashes are not scattered or spread on the ground, I give to Planned Parenthood of Maryland $50,000"

or about 1/3 of his estate. 

His concern seems to have stemmed from the fact that cremation is discouraged by Catholic doctrine, and in the case of cremation, ashes must be buried in sacred ground rather than scattered. But the threat-from-beyond-the-grave has worked, and it seems that Ivin will get his wish. So consider this a victory of game theory over theology.

Presidential politics

Since my last post, there was a presidential primary in Pennsylvania, and despite running into Bill Clinton hanging out in front of my polling station, I voted for Barack Obama. One of the things that has particularly bothered me about the Republican administration over the last 8 years (excluding an ill-conceived war, the loss of a major US city, etc.) has been the prevailing atmosphere of anti-intellectualism. Our administration has cut funding for basic research, and has dismissed scientific evidence when making policy decisions. It has come to the point where distinguished educational credentials are liabilities when running for public office. Part of why I like Obama is that he speaks in complete sentences rather than in soundbites, and seems in general to hold education and reason in high regard (this has caused him to be attacked as elitist). Although Hillary has proposed significant increases in scientific funding (including raising the stipend of the NSF fellowship to $40,000!), and although she is also a product of an elite educational system, she has recently recast herself as a populist. Unfortunately, that seems to mean distancing herself from expert knowledge. I was disappointed to find this article: Clinton Spurns "Elite" Economists on Gas Tax. When did Elite become a bad word? A quote from the article:

Clinton used her appearance on ABC's "This Week" to raise questions about Obama's ability to connect with working-class Americans while dismissing economists who have said her plan to suspend gas taxes over the summer would do little good.

"I'm not going to put my lot in with economists," the New York senator said when asked to name a credible economist who supported her proposal.

"We've got to get out of this mind-set where somehow elite opinion is always on the side of doing things that really disadvantage the vast majority of Americans," said Clinton, a former first lady who would be the first woman president.

In other news, my Price of Malice paper was rejected from EC. Well, no worries. I'm not about to put my lot in with computer scientists.

Malice, Anarchy, and Regret

Its been a long time since my last post -- I've been busy doing a lot of things, including attending part of this very interesting workshop on data privacy, and laboriously adding my own random coins to the PhD admissions process at CMU. Now that the next class has been admitted (Welcome!), I will hopefully have some time to get back to research.

There are some interesting things going on in the world of privacy, but that is a topic for another post. Since the terminology used by the algorithmic game theory community is much more colorful, I'll write a little about something I have been thinking about recently: The price of malice!

Recall that the price of anarchy is a measure of the degradation of social welfare in the face of selfish behavior. Specifically, it is the worst case ratio of the optimal social welfare to the social welfare in a Nash equilibrium. One of the problems with this measure is that it is really quite brittle -- it assumes that everyone is perfectly self interested and rational. But in actual games (say, computer networks), although many people are selfish and wish to minimize their own delay, others exhibit different behaviors. Some are oblivious to network traffic, and so may seem to be irrational. Some are explicitly malicious, and seek to increase the delay of others (see denial of service attacks). Enter the price of malice: an attempt to define a quantity that measures the effect on social welfare of these malicious players. So how should we define it?

Well, its been studied in several papers, and they define it differently! Moscibroda, Schmid, and Wattenhofer define a price of malice that is parameterized by the number of malicious players, k. PoM(k) is the ratio of the cost in a game with k malicious players, and n-k rational (selfish) players, to the worst case social cost with n rational (selfish) players. Babaioff, Kleinberg, and Papadimitriou give a different, unparameterized definition (also, of course, called the price of malice!) Their price of malice is essentially the first derivative of PoM(k), evaluated at k=0: That is, it is the worst case marginal cost of converting an epsilon fraction of the players from selfish to malicious.

But what does it mean to have a game with rational and malicious players? Both papers define an equilibrium model by assigning the malicious players a utility function equal to the negation of the social welfare function. This is natural when we are talking about Nash Equilibrium, but leads to perhaps an awkward definition of a malicious player: because the malicious players are myopically seeking to minimize social welfare, sometimes malicious players can fall into equilibria with rational players that actually improve social welfare (as compared to equilibria with rational players alone)! Both papers observe this phenomenon, and Babaioff, Kleinberg, and Papadimitriou call it "the windfall of malice". This is a pretty cool and counterintuitive phenomenon, but somehow it doesn't seem like a satisfying definition of malicious play -- after all, if a truly malicious adversary was helping you by acting adversarialy, he could (if nothing else) act `rationally' and avoid giving you this boost. What we really want is an adversary who we allow to behave arbitrarily -- we want to take the worst case over all possible adversaries, who might engage in sophisticated counterspeculation.

So, to add to the clutter, in a recent paper, I have given yet another definition of the price of malice. I use the framework from the recent paper on the price of total anarchy to define the price of malice (an analogue of Moscibroda et al.'s definition), and the differential price of malice (an analogue of Babaioff et al.'s definition) with weaker assumptions. First, imagine that players are playing in a repeated game, rather than a one-shot game. This allows us to weaken the assumption that players are playing according to a one-shot Nash equilibrium and consider each player individually, assuming only that each rational player experiences no "regret". That is, no player "regrets" not playing some fixed action -- each player is doing at least as well as she would have been had she retroactively changed her play history to repeatedly play any fixed action. Note that by the definition of a Nash equilibrium, if all players were repeatedly playing according to a Nash, all players would be experiencing no regret (and so this is a weaker assumption than that players play according to a Nash equilibrium). This weakened assumption has two benefits. First, it makes the predicted behavior computationally plausable: while finding a Nash equilibrium is PPAD complete in general games, there are efficient algorithms players can use to unilaterally guarantee that they have regret quickly tending to 0. But that isn't the main point here: It also allows us to define rational play on a player by player basis, rather than defining rational play over an entire population (by saying that they all play according to a Nash equilibrium). This allows us to analyze games in which only a fraction of the players are `rational', and the rest are behaving arbitrarily. So we can now study the price of malice -- in which k players are Byzantine -- players about whom we make no assumptions, and who may engage in sophisticated malicious play. Now that we are taking the worst case over all possible adversaries, we can no longer observe a windfall of malice. This should be what we want -- after all, we want to bound the cost of malicious players who may be smart enough not to help us out.

Of course, depending on the situation, our adversaries might be myopic, and so the equilibria models of the price of malice also are interesting quantities to study. Fortunately, the no-regret definitions are backwards compatable: since they make strictly weaker assumptions, upper bounds on the price of malice and differential price of malice in the no-regret model also serve as upper bounds on Moscibroda et al.'s and Babaioff et al.'s price of malice (respectively).

Useful Privacy

Privacy

A little while ago I wrote about Dwork et al.'s differential privacy as a good definition for characterizing what exactly we intend to convey by the word 'privacy'. Databases of 'private' information are very valuable sources of information (for example, we might want to be able to learn that smoking correlates to lung cancer, despite the fact that people want to keep their health records private). Therefore, we would like a definition of privacy that allows us to learn such facts about the distribution (that smoking correlates to lung cancer) but does not allow us to learn particulars about database entries (that Alice has lung cancer). epsilon-Differential privacy approaches this by guaranteeing that two databases that differ in only a single element yield answer-distributions that differ nowhere by more than exp(epsilon) when accessed by a privacy-preserving mechanism. But why not address the issue directly?

A database-access mechanism "A" preserves (epsilon,delta)-distributional privacy if for every distribution D, and any two databases D1, D2 with entries drawn from D, answer-distributions of A on D1 and D2 differ nowhere by more than exp(epsilon), except with probability delta. That is, if we imagine that databases (say, medical records of particular individuals) are drawn from some distribution (the set of all individuals), then we should only be able to learn things about the distribution, not about the individuals: We should get the same answers to any questions we might ask, from any database drawn from that distribution.

This is the privacy definition proposed in a recent paper by Avrim Blum, Katrina Ligett, and me. So how does it relate to differential privacy? On the one hand, it seems like we are making a stronger guarantee: Differential privacy guarantees close answer distributions only when databases differ on few elements, while our databases D1 and D2 could differ in all of their elements. On the other hand, it seems like we are claiming something weaker: we make the assumption that our databases are drawn from a distribution, and we allow privacy violations with some probability delta (which we generally think of as exponentially small). In fact, it turns out that distributional privacy is a strictly stronger guarantee than differential privacy -- with appropriate parameters, all distributionally-private mechanisms are also differentially-private, but not vice versa.

Usefulness

Of course, a stronger definition of privacy is no good if we can't do anything useful with it -- after all, we could insist that all database access mechanisms simply ignored the database, and answered questions randomly, but such a notion of privacy would not be useful. What do we mean by useful anyway?

Past work on privacy preserving data release doesn't seem to have addressed this, and has instead just tried to answer all queries with answers that are as close to the true answer as possible. But from learning theory, we get natural definitions of usefulness: Given a database D, we could say that an output database D' is (epsilon,delta)-useful with respect to a class of queries C, if with probability 1-delta, for every query q in C, |q(D) - q(D')| < epsilon.

By clarifying what we want to achieve by 'useful' data release, we make previous lower bounds on data release seem less scary. Results by Dinur and Nissim and Dwork et al. make release of static databases seem inconsistent with the goals of privacy, because they show it is possible to reconstruct almost the entire original database with a small number of almost-correct "subset sum" queries. But once we clarify what we mean by 'usefulness', its clear that we might still hope to statically release databases that are still 'useful' for a class of queries that does not include subset-sum queries, while still preserving privacy.

Well, maybe. In the paper, we consider the class of halfspace queries (a generalization to higher dimensions of queries of the type "what fraction of Americans are taller than 6'2''?"). We can show that its impossible to release a database useful for halfspace queries while preserving even differential-privacy. However, if we are willing to relax our definition of usefulness (With high probability, for every query q, |q(D') - q'(D)| < epsilon, for some query q' that is "close to" q), we can release a database "useful" for halfspace queries that preserves the stronger notion of distributional privacy.

So what is the take home message? Useful and private data release is still possible (despite strong impossibility results!) if we are willing to relax our definitions. We cannot hope to be simultaniously useful for all queries, but perhaps we can still be "useful" to many.

That new facebook box

From the New York Times today:

Millions of people in this country -- particularly young people -- already have surrendered anonymity to social networking sites such as MySpace and Facebook, and to Internet commerce. These sites reveal to the public, government and corporations what was once closely guarded information, like personal statistics and credit card numbers.

After I put up my cell-phone number on my facebook profile, filling in the extra fields about my credit card number and where I hide my spare key seemed only natural. But I may take them down after reading this article.

Smoothed Analysis of the Price of Anarchy

Given some system in which a lot of selfish agents are interacting (a game), we would like to predict what might happen. If we have some way of measuring the quality of an outcome, we might want to know how much worse an outcome the selfish players might light upon compared to the best solution possible. But what will the selfish players do? Typically, people assume that they will play according to a Nash equilibrium. This is a solution concept with lots of problems for computationally limited agents, that I have written about here. Lets just assume for a post that players do fall into Nash equilibrium (This isn't crazy in certain games (like potential games) in which natural iterative better-response play leads to a Nash equilibrium eventually.) Which Nash equilibrium will the agents end up in?

Typically we skirt this issue by defining the "price of anarchy" to be the ratio of the value of the worst equilibrium to the value of the optimal solution -- a pessimistic bound. Will we really end up in the worst Nash equilibrium?

A related problem comes up in the design of algorithms. How should we measure the running time of an algorithm? The worst case running time? Some notion of average case? Average case running time is misleading because our notion of 'average' probably won't coincide with the data's. But worst case running time can also be misleading if all worst-case inputs are somehow contrived and 'brittle' to small changes. Smoothed analysis is a compromise -- the smoothed complexity of an algorithm is measured by taking a worst case input, but then measuring the running time of the algorithm with respect to small perturbations of that worst-case input. The idea is, if the bad inputs are extremely brittle to perturbation, we are unlikely to actually encounter bad inputs.

So maybe we can do a smoothed analysis of the price of anarchy. In a recent paper, Christine Chung, Katrina Ligett, Kirk Pruhs, and I propose studying the stochastically stable states of a game -- the states that computationally simple agents, who make mistakes (noise) in their play with some small probability each turn. In general, the solution concept that this leads to can be completely different from the Nash equilibria of the game, but in potential games, it turns out that the stochastically stable states are a subset of the Nash equilibria. What does this mean? The stochastically stable states in these games are the Nash equilibria that are resilient to these occasional mistakes in play, and the price of anarchy taken over the worst case stochastically stable states ("the price of stochastic anarchy") can be viewed as a smoothed analysis of the price of anarchy -- The worst we are likely to encounter in a noisy, imperfect world.

Here's an example: Suppose Aaron and Bob have programs that they want to run on a computer, and there are two computers, X and Y. Aaron's program costs epsilon to run on X, and 1 to run on Y. Bob's program costs epsilon to run on Y, and 1 to run on X. Both players can choose what machine that they will run their programs on, and will pay the sum of the costs on the machine they picked. For example, if both Aaron and Bob pick machine X, they will both pay 1 + epsilon.

The optimal solution is obvious: Aaron plays on X, Bob plays on Y, and both pay epsilon. This is also a Nash equilibrium -- no player can unilaterally improve his payoff by switching machines (Bob could switch machines, but that would increase his cost from epsilon to 1 + epsilon).

If instead Aaron plays on Y and Bob plays on X, both players now pay 1, and this is again a Nash equilibrium, although a much worse one -- either player could switch machines, but because of congestion, would increase their cost from 1 to 1+epsilon.

So the price of anarchy of this game is 1/epsilon, which can be arbitrarily large. But is the bad equilibrium really realistic? If Aaron is playing on Y every turn, and Bob is playing on X, if Aaron makes a mistake one turn (and plays on X), then Bob can take advantage of this and increase his payoff by moving to X. The optimal equilibrium on the other hand is resilient to mistakes like this -- both players are already paying the smallest cost that they could ever pay in this game. It turns out that although the price of anarchy in the 2 player "load balancing" game that I just described is unbounded, but the price of stochastic anarchy is just 2. So the price of anarchy gave us an unrealistic measure of how bad things could get, because of the existence of bad, but brittle equilibria.

In our paper, we consider the general case of the n player m machine load balancing game, and prove that the price of stochastic anarchy is bounded. What other games could benefit from a 'smoothed' analysis of the price of anarchy?

UPDATE: Our paper is now available here.

What is Privacy?

Today there was a joint CMU-Microsoft Research workshop on privacy, and it opened up with discussion about various definitions of privacy. 'Privacy' is a word we might use every day, but what do we mean by it? Suppose you had some sensitive piece of information in a large database. What sorts of information about the database would you feel comfortable being released to the public, without a 'privacy' violation?

Cynthia Dwork began with an interesting toy example: Suppose you want to keep your 'height' private, and there exists a database of heights. It seems innocuous enough to release the average height of Norwegian women. But suppose your worst enemy already knows that you are two inches taller than the average Norwegian woman -- then the release of average heights has 'violated your privacy'.



But has it really? In this case, the 'violation of your privacy' could have occurred whether or not your height was included in the database or not. This suggests an elegant definition of differential privacy that Cynthia and others have been working with: If the database statistics released would not differ whether or not you were in the database, your privacy has not been violated. Formally, we want that for any two neighboring databases D and D' (differing in only one element), for any statistic Q(D) that might be released, and for any value of that statistic, x:



Pr[Q(D') = x](1- epsilon) < Pr[Q(D) = x] < Pr[Q(D') = x](1+ epsilon)



where probability is taken only over internal randomness of the information-release mechanism (no assumptions about the distribution of the database elements are made). What this definition implies, is that if you are considering whether or not to include your information in the database, you shouldn't fear that your decision will help compromise your privacy -- anything that someone could learn from the database with your information in it, they could also learn without your information.



What is that epsilon parameter anyhow? In crypto, you would generally take epsilon to be something like 1/2^n -- something so tiny that the two distributions were basically identical. But you can't achieve that here if you want the database to be at all useful. Since we can transition between any two databases through a path of n neighboring databases (just swap out one at a time elements from your original database for elements of your target database), query probabilities differ by at most n*epsilon between any two databases, and if we want to be able to meaningfully distinguish any two databases, we need epsilon to be something like 1/n.

So this seems like a pretty good definition -- it cleanly gets to the heart of the matter, and it is parametrized to allow you to cleanly trade off between privacy and usefulness (and makes explicit that there must necessarily be such a trade off...)

Are the Reals real?

We learn in elementary school about different sorts of numbers. Each seems to be named so as to disparage a larger class of numbers. We have:

• The Naturals. These consist of non-negative integers (negative integers are unnatural). We can define the naturals inductively. 0 is a natural number, and for every natural number x, (x+1) is also natural.
• The Rationals. These consist of numbers that can be written "as fractions" (Postulating the existence of any other sort of number would be irrational). We can define the rationals: for every two integers x and y, x/y is in the set of rationals.
• The Reals. These consist of numbers that can be written as (infinite) decimal expansions (Any other kind of number must be imaginary). We can define the reals as the limits of sequences of binary expansions (i.e. 3, 3.1, 3.14, 3.141, 3.1415,...). In this view, real numbers are actually functions from the naturals to the rationals: A real number f corresponds to the sequence whose i'th term is f(i).

In each case, we can perhaps ascribe the disparaging labels of these class of numbers to the closed-mindedness of the namers. After all, there have been times in history when negative numbers were considered unnatural, and the square root of 2 was actually thought of as not rational. But have we gone too far? Are real numbers really real?

Real numbers pose a problem for people with a computational world view -- those that believe that in principle physical phenomena can be simulated. If quantities in the universe such as position, mass, velocity, temperature, etc. are represented by (continuous) real values, then they can't be perfectly simulated.

The first and most obvious problem we encounter is representation size -- most reals can't be finitely represented. So in any simulation with finite memory, even barring any other problems, we're just not going to have the space to keep track of even a single value.

A second and more insidious problem is even worse -- most real numbers aren't computable. That is, there is no finitely representable procedure for calculating most real numbers, even if we were to avoid the first problem by granting our simulation infinite memory, and even if we were to allow your procedure an infinite amount of time. This is because, no matter what representation you choose for writing down your finite procedure (Turing Machines are popular), the set of such procedures is only countably infinite, whereas there are uncountably many reals.

A third (related) problem is that most anything we would want to do with our real values would be undecidable. Even the problem of comparing two reals is undecidable -- consider the process of comparing the real x_T to pi, where x_T is defined to be the real with the i'th digit of pi in its i'th decimal place for all i less than T_h, where T_h is the step at which Turing machine T halts, and with the i'th digit of e in its i'th decimal place for all i greater than or equal to T_h.

So is anything in our universe actually represented by "variables" defined over the reals? Believing this seems to entail believing that the universe is inherently non-computational, regularly resolves undecidable problems and maintains information to infinite precision.

P.S. Many people object to the axiom of choice, because although it is consistent with (and independent of) other mathematical axioms, it allows for things that go counter to our intuition. For example, the Banach-Tarski Paradox: One may partition a solid 3-dimensional sphere into finitely many non-overlapping pieces, and then with only rotations and translations can reassemble the pieces into two identical copies of the original ball. But maybe it isn't the axiom of choice that challenges our intuition ("we can choose an element from any nonempty set"), which after all, seems reasonable -- maybe it is the existence of the reals and other uncountably infinite sets. It is really only these sets that require the axiom of choice -- we can choose elements from countably infinite sets without resorting to the axiom (We can define a choice function by first putting the elements of our countable set in one to one correspondence with the integers. Then we may choose the smallest element in each nonempty set.)

Can we really choose an element from an uncountable set? It seems less reasonable. Consider the reals - an uncountable set. Remove from this set all reals that can be named (or defined) - a countable set. Now choose an element!