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!

Alice, Bob, a Simple Game, a Surprise, and a Paradox

Consider the following simple game:

Alice thinks of two integers, not both equal. She writes them down, and places one (at random) in each of her hands. She presents both of her closed hands to Bob, who gets to pick one. Alice will show Bob the integer in the hand he picks. Now Bob has to guess which hand contains the larger integer. This is a very simple game, but has some very interesting properties.

A Surprise

First, suppose that Bob knows nothing of the process that Alice uses to pick her integers -- he doesn't know her distribution, or any bounds on the values she might choose. Can he win more than 50% of the time? It would seem that he cannot -- If he picks one of her hands, and sees some number i, for every distribution that she might be using so that he would expect i to be the smaller number, there is another translated distribution such that he would expect i to be the larger number. Now what if Alice has a spy, and gets to hear Bob's strategy before the game begins, and can change her strategy accordingly? Does Bob have any hope now?

Well, Bob can of course guarantee that he wins 50% of the time, even if Alice knows his strategy, by simply guessing a hand at random and guessing that it contains the larger integer (And this is the basic rationale for randomized algorithms -- Alice can't thwart this strategy even if she knows what Bob will do). In fact, to do this, Bob doesn't even have to look at the number in Alice's hand when she shows it to him. But it turns out that if he does look, he can guarantee that he wins with probability strictly more than 50%, no matter what Alice does, even if she knew his strategy ahead of time. Here's one thing Bob can do: Before the game begins, Bob can pick a random integer Q from some distribution that has support over all of the integers (Say he flips a coin i times until he gets a heads, and then flips another coin. If it comes up heads, his number is i, otherwise it is -i). Bob then picks one of Alice's hands at random, and looks at the number in it. Bob pretends that the number in Alice's other hand is Q + 0.5, and plays accordingly. That's it.

Why does this work? Its funny that an overactive imagination can help Bob win a game like this -- after all, he doesn't really have any idea what number is in Alice's other hand. But as we will see, it does work. Suppose Alice's numbers are L and R, and that L is less than R.

Q+0.5 less than L less than R: Then Bob wins with probability 50%, since he always guesses that the hand he picked is the larger one, and he picks the larger one initially half the time.

L less than R less than Q+0.5: Then Bob wins half the time again, since he always guesses that the hand he picked is the smaller one, which again, occurs initially 50% of the time.

L less than Q+0.5 less than R: In this case, Bob wins whichever hand he picks! If he guesses the smaller hand, he imagines (correctly) that the other hand is larger. If he guesses the larger hand, he imagines (correctly!) that the other hand is smaller.

The point is, the third case occurs with positive probability no matter what numbers Alice picked, because Bob picked Q from a distribution with support over all of the integers! Say case 3 occurs with probability p > 0. Then Bob's probability of winning is (1-p)*0.5 + p = 0.5 + p/2 > 0.5!

A Paradox

Strangely, things can get funnier if Bob knows Alice's strategy. Lets change Bob's incentives a bit: Suppose now, Bob gets paid an amount of money equal to the value in the hand that he guessed was larger, minus the value in the hand that he guessed was smaller (So if Bob guesses correctly he wins money, but if he guesses incorrectly, he loses money). Suppose Alice picks her integers as follows: With probability 1/2, she picks (1, 3). With probability 1/4 she picks (3, 9). With probability 1/8, she picks (9, 27). In general, with probability 1/2^i she picks (3^(i-1), 3^i). It is easy to verify that this is a well-defined probability distribution (In fact, Alice can implement it by simply flipping a coin i times until she gets a heads).

Now how should Bob play? If he picks a hand, and sees a '1', he knows that Alice's other hand must contain a 3, and so he should guess her other hand is larger, guaranteeing a payoff of 2 (rather than a guaranteed loss of 2). Suppose he sees a '3'? In this case, he knows that in her other hand, she has either a 1 (with probability 2/3), or a 9 (with probability 1/3). His expected value for guessing that the other hand is larger is (1/3)*(9-3) - (2/3)*(3-1) = 2/3. His expected value for guessing that the hand he sees is larger is -2/3. In general, conditioned on seeing 3^i for i > 0, the event that Alice's other hand contains a larger number is twice as half as likely as the event that Alice's other hand contains a smaller number, and we can calculate that Bob's expected value for switching hands is 2*3^(i-2), while his expected value for not switching is -2*3^(i-2). So what should Bob do?

He should pick a hand at random. He should look at the number. If he sees a 1, he should switch hands. Otherwise, he should calculate the expected value of switching, and if it is higher than the expected value of staying, he should switch. Equivalently, he should pick a hand at random, and look at the number. If he sees a 1, he should switch hands. Otherwise, he should switch hands (Since we calculated that the expected value of switching is ALWAYS larger, no matter what Bob saw). Equivalently, he should pick a hand, look at the number, and switch hands. Equivalently, he should pick a hand, NOT look at the number, and switch hands (since we calculated that the value he would see is immaterial to his decision). So we have argued that his expected value by picking a hand at random and guessing that the other one contains the larger number has a positive expected value, and that picking a hand at random and guessing that IT contains the larger number has a negative expected value.

But wait a minute -- the two strategies are clearly equivalent -- both of them involve picking the left hand with probability 50%, and picking the right hand with probability 50% -- they must both yield the same expected value. What gives? Surely the value of Bob's strategy isn't affected by the physical act of looking at the number in the hand that he picks (since he won't act on it). Yet we have just argued that two clearly equivalent strategies have different expected values... Hm...

This is sometimes referred to as a variant of the two envelopes paradox. You can read some supposed explanations of it, and decide whether they are convincing (I'm not completely convinced). It seems related to the St. Petersburg "paradox".

The human-computer algorithm

The New York Times has published this ode to the algorithm. They write:

Algorithms, as closely guarded as state secrets, buy and sell stocks and mortgage-backed securities, sometimes with a dispassionate zeal that crashes markets. Algorithms promise to find the news that fits you, and even your perfect mate. You can’t visit Amazon.com without being confronted with a list of books and other products that the Great Algoritmi recommends.

The article is in a section titled "Artificial Intelligence - Computers and the Internet", but the focus of the article is the trend of algorithmically harnessing human intelligence -- the goal of Luis Von Ahn. They mention his Google Image Labeller, which is an explicit algorithm with human subroutines. But perhaps more interestingly, they describe Wikipedia as a human algorithm --

A constantly buzzing mechanism with replaceable human parts. Submit an article or change one and a swarm of warm- and sometimes hot-blooded proofreading routines go to work making corrections and corrections to the corrections.

Generally Wikipedia is thought of as an entirely human project, but is it a giant distributed fault-tolerant algorithm? Why not? I think that it is good that algorithms should be thought of as ideas, rather than software code. Algorithms can exist independently of computer hardware, as entities (worthy of study) entirely unto themselves. After all, we don't think of algebraic fields as objects whose existence is inherently tied to paper or chalkboards. Why should algorithms exist only in silicon?

For other takes on this article, see here.

The Hunt for a New Solution Concept

The Hunt is On:

In 2006, Daskalakis, Goldberg, and Papadimitriou published a proof that computing Nash Equilibria in matrix games is complete for the complexity class PPAD. For the purposes of this blog entry, lets take that to mean that there is no efficient algorithm to find Nash equilibria in general games (although I'm not sure how strong the consensus is that PPAD is intractable). More recently, it was shown that computing equilibria even in infinitely repeated games (despite the seeming prevalence of such equilibria) is also PPAD complete.



What these results do is to cast doubt upon the Nash equilibrium as a plausible solution concept: Do we really expect a set of disorganized, computationally bounded, possibly ill-informed players to perform a massive intractable computation in some kind of distributed way? This is a call for theory building: As computer scientists, we have to find a solution concept that is as appealing as Nash's, but that is also feasible in a world with computational limitations.



What are we Looking For?

Fabrikant and Papadimitriou have just published a paper that outlines in its introduction three criteria we would like for a good solution concept. It's a good list. In summary:

1. Realism: We are looking, after all, for a solution concept that will help us predict the behavior of selfish agents. The solutions that fall our of our models should be plausibly rational. Pure strategy Nash equilibria have this property (if we can find them): Since everyone is simultaneously playing a best response to everyone else, it is plausible that no one should want to deviate (although one might also wish to model players who are not perfectly rational, or who wish to deviate from a Nash so as to jolt the system into a more favorable Nash). Mixed Nash are sometimes less plausible: They might require that players randomize among equally good alternatives so as to induce the same behavior in other players -- so that players are optimizing not only their own payoff, but the stability of the system. (On the other hand, in large population games, you can imagine mixed Nash as modeling the behavior of a much larger, but deterministic set of players)


2. Ubiquity: We would like that our solution concept always exist. Nash proved that mixed Nash always exist, but unfortunately pure Nash equilibria do not (Try to find the pure strategy equilibria in rock-paper-scissors).


3. Tractability: This is the viewpoint that computer scientists bring to the field, but perhaps this requirement should really be the same as 1: We can't really consider a solution concept to be a realistic model of selfish behavior if it is computationally intractable to find. Unfortunately, neither pure nor mixed Nash equilibria are computationally tractable to find (modulo some big surprises).

We might add a fourth bullet:

4. Flexibility: Playing your part in a Nash equilibrium only gives a meaningful guarantee if everyone else is simultaneously playing their part. If someone deviates from the Nash profile, all bets are off. But do we really expect everyone in a large population game to behave how we predict they will? What if some are irrational, ill-informed, adversarial, mistake-prone, or just have a slightly different objective function than we think they do? It would be nice to be able to still make some predictions about behavior. Degradation in some global objective function due to selfishness is referred to as the Price of Anarchy -- it is odd that existing bounds based on Nash equilibria only hold if everyone is acting in a proscribed manner. Where is the anarchy?

What Have We Got?

There have been some recent attempts at defining new solution concepts. All of them make assumptions about the dynamics of the game, and so really are modeling repeated games. So far, none of them satisfy the full list of desiderata:

Sink Equlibria: A solution concept suggested by Goemans, Mirrokni, and Vetta, sink equilibria live in the better-response graph of a game. Each vertex in the graph corresponds to an action profile, assigning an action to each player. Edges correspond to better-response moves: There is an edge from u to v (with label i) if u and v differ only in the action of player i, and by changing her action from u_i to v_i, player i increases her utility. In the best-response graph (which is what GMV actually study), each player has at most one edge from each vertex, corresponding to the action that improves her payoff the most.

The best-response graph models a dynamic in which players move sequentially, each making a myopic best response (they care only about their immediate payoff). We may imagine play proceeding as a random walk on the graph. Pure strategy Nash equilibria correspond to sinks in the graph (since everyone is playing a best response already, the corresponding vertex has no outgoing edges). Such sinks do not necessarily exist (think rock paper scissors). However, if we imagine collapsing each maximal connected component (Those parts of the graph that we might enter, but can never leave) into a single vertex, the graph is now guaranteed to have sinks. These sinks are the sink equilibria of the game, and their value is the expected value of a random walk on the sink component. The idea is, a random walk in this best-response graph will eventually get caught in a sink, and the value of the game will be dominated by the expected value of the sink.

1. Realism: This model assumes that players are myopic -- they strategize only to the extent that they greedily pick the best payoff in the next time step. This is limiting in that it sometimes leads to foolish play, and would seem to underestimate the rationality of the player. On the other hand, this might be an ok first order approximation, and in many games it at least allows the players to calculate their next move efficiently, which is an important criteria in realism.


2. Ubiquity: By construction, sink equilibria always exist (although they may include every state in the game, and so be of limited value).


3. Tractability: Unfortunately, the FP paper shows that in a large class of concicely representable games, even identifying whether a given game state is part of a sink is PSPACE complete, and so it seems we are no better off than when we started, in terms of computational efficiency.


4. Flexibility: This model assumes that players play on a best-response graph, and sinks are defined with respect to the graph. But if players deviate -- perhaps they incorporate randomness into their play, fail to calculate their best-response move, or strategize more than one move ahead, the graph that the players are playing on changes, as do the sinks. As a result, this model is brittle to unmodeled behavior.

CUREs: The FP paper suggests another model for repeated games. Imagine that players commit to a strategy that is determined by a restricted class of finite automata, that FP call Unit Recall Strategies. The states of the URS for player i correspond to player i's actions, and the automata reads a tape that at time t tells it what action all the other players are playing at time t. The URS is defined by a set of transitions from action profiles to actions. (So the strategy that a player is committing to is limited by the fact that it must specify an action to play at time t+1 given only the state of the game at time t -- it may not remember anything else). If each player commits to an URS, then we have a completely specified set of game dynamics. Since each player's strategy is a finite automata, game play will eventually loop, and the payoff to player i is defined to be her average payoff of state sin this loop. A Unit Recall Equilibria (URE) is a set of URS such that no player can unilaterally improve her payoff by switching to another URS. A component-wise Unit Recall Equilibria (CURE) is a set of URS such that no player can unilaterally improve her payoff by switching only a single transition rule in her existing URS.

1. Realism: The model assumes that players commit to a restricted class of finite automata strategies. In general, this is a reasonable assumption, although the restriction that player strategies cannot have memory seems a bit strong. CURE seem particularly restrictive in that they assume myopic play the same way the sink-equilibria do: Even if players may only switch one transition in their automata strategy per timestep, the CURE concept is assuming that they also cannot plan more than one time-step into the future.


2. Ubiquity: FP show that unfortunately, the more realistic solution concept of the URE need not necessarily exist. The less realistic one, the CURE, however, always exists.


3. Tractability: FP conjecture that finding an example of the more realistic solution concept, the URE, is in polynomial time, although prove only that it is in NP. It is easy, however, to find a CURE. Unfortunately, the CURE that FP show how to construct is a good example of why the CURE lacks realism as a solution concept -- it depends critically on the fact that players are not permitted to think beyond one step into the future.


4. Flexibility: The model depends on all players using restricted finite automata strategies. If any player deviates, URE guarantees no longer apply, and CUREs are no longer equilibria if any player may change more than one transition at a time, or may anticipate more than one move into the future.

No Regret Play: Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and I have proposed the following solution concept: We imagine that players behave so that they have no regret. By that, we mean the following: In retrospect, after seeing (and fixing) how all of the other players played, no player should have been able to improve his payoff by playing the same fixed action at every turn. Except for this restriction, they may play arbitrarily. This definition is appealing for several reasons.

a) It is strictly a generalization of the one-shot-game Nash equilibrium, because if players repeatedly play a Nash equilibrium, they will satisfy the no-regret property.

b) Although we make no assumptions about the particulars of how players behave, there are simple and efficient algorithms that players could use to guarantee that they have no regret, regardless of how other players behave.

c) Our generalization is enough to get strong guarantees. In particular, in valid games, traffic routing games (both atomic and nonatomic), generalized Hotelling games, average-load-balancing, and presumably others, the "price of anarchy" for no regret play matches the price of anarchy for Nash equilibria.

d) Proving a no-regret price-of-anarchy upper bound implies a price-of-anarchy upper for pure and mixed Nash equilibria, and is often simpler than proving the result directly for mixed Nash.

1. Realism: The model makes only the assumption that players play so as to have no regret. How realistic is this? Well, its strictly a generalization of the one-shot Nash equilibrium (both pure and mixed), so in this sense its strictly more realistic. In most large-player games, it is rational to desire no regret, in the sense that if you have regret to some fixed action a, you would have been better off pursuing some other strategy (such as playing a the whole time), and there are efficient algorithms that you could run to get this guarantee. On the other hand, the no-regret assumption implicitly assumes that your actions have a negligible affect on other players actions. For example, in a repeated prisoners dilemma game, the (lucrative) collaborative strategy of both players cooperating every round is not no-regret -- both players would have regret to defecting, not realizing that had they defected every round, they would have changed the behavior of their opponent, thus not truly obtaining a higher payoff. So it seems that the no-regret assumption is a realistic model of rational behavior, but only in games for which ones own actions have a minimal affect on the actions of others. (Perhaps formalizing what such games look like would be a fruitful area of research).
2. Ubiquity: Every game has a no-regret history of play. The proof of this is simply the existence of algorithms that give each player the no-regret guarantee.
3. Tractability: It is easy for players to guarantee that they have no regret (and thus find no-regret histories of play) in most classes of games. In particular, we can do this in polynomial time for any game that has only a polynomial number of actions for players, and also in some games that have an exponential number of actions per player (such as routing games, and many valid games).
4. Flexibility: The no-regret property is flexible enough to allow occasional random behavior (A player could build up 'negative regret', and then occasionally spend it with 'irrational' behavior). Since we don't assume players use particular algorithms, players could also use arbitrary strategies that just happen to generate no-regret histories (even if they don't explicitly guarantee this). Perhaps most significantly, we can often prove "price-of-anarchy" style bounds even when only a subset of the players experience no-regret, and others behave arbitrarily (or adversarially). This flexibility seems essential when quantifying "anarchy".

A Common Thread

Each of these solution concepts postulate dynamic equilibria -- none of them require that play 'converge' in the sense that the same action profile be played round after round. This is a property that is probably necessary if we want to take into account "irrational" behavior.

Each solution restricts the set of allowable player strategies, to greater or lesser degree. While this might be necessary for tractable analysis, if we wish to model reality, we should aim for models that are minimally restrictive.

So the hunt is on. A successful model will probably have properties that lend themselves to easy mathematical analysis, but hopefully will also be a convincing description of selfish behavior. Perhaps some experimental work is in order? In large scale networks, do people appear to be playing sequentially in sink equilibria? Can their actions be modeled by simple finite automata? Do they have regret?

(Thanks to the SODA paper announcements here here and here that led me to discover the FP paper which instigated this post)

Licensed

As of today I am licensed to drive and registered to vote in the state of Pennsylvania. I was a bit worried about having all of the identification that was required... To demonstrate that I am who I am, I needed both my passport and social security card. I had the passport (no problem!), but I had actually never seen my social security card before -- my passport had always sufficed. I got a hold of my social security card (never detached from its flimsy paper form!), so I was all set on that front. To demonstrate that I live where I live was harder... I need two forms of proof, one of which is the lease agreement (which I have -- but it actually says the wrong address on it because of a photocopy error). The other was harder... I could use a W2, but those are in Boston. I could use a utility bill, but those are in Joseph's name. But a printed scanned copy of a W2 turned out to work.

So was I missing anything after all that? I had no way to pay them the $26 they charge for a license... They don't take cash! They don't take plastic! They only take checks or money orders!

Fortunately, in the same mall was a counter to buy money orders, for a fee... I think PennDOT is in league with this company...

SODA

I was looking up the submission deadline for FOCS 07 (a CS theory conference), and Google carefully picked out the ads that it should show me. I guess no one bid on the keyword FOCS, but Google was smart enough to know that people who search for FOCS often also search for SODA (another theory conference). Moreover, Google knew that I was in Pittsburgh. The result? The second ad shown above, for Pittsburgh Soda -- local establishments where I can buy Dr. Pepper in bulk. Not quite what I want, but sophisticated...

I'm the guy that looks things up

When I worked at Google, and people would ask me what I did there, I would tell them that I was the guy that got all the queries, and then quickly looked up good results and entered them in, in time for a response for each user. Ha ha ha.

Apparently, there actually is a search engine like that. As far as I can tell, the service they provide is a 5-10 minute time delay between you and Google. Awesome!

Its called ChaCha. Go there, type in a query, and click on "Search with Guide".

Game Theory

There is an ongoing investigation into the murder of the wife of a University of Pennsylvania game theorist. The game theorist is currently considered a suspect. The damning piece of evidence in the case seems to be his profession. Not to worry -- the district attorney, Bruce Castor, is considering all of the evidence:

According to what Castor has been able to glean, Game Theory is an economic philosophy wherein a person can apply factual scenarios for a desired outcome."In a criminal context, somebody applying it would calculate all the angles and then go ahead and commit the crime," said Castor. "It could also be a coincidence, too (that Robb taught classes on Game Theory)."

So while I suppose it could be a coincidence, its awfully suspicious. I wonder how Castor was able to glean this... Very impressive.

Full Story: http://www.timesherald.com/site/news.cfm?newsid=17646875&BRD=1672&PAG=461&dept_id=33380&rfi=6

Awards and Honors

Browsing Barnes and Noble today, I was reminded of an important award that I forgot to list on my NDSEG application! I was the Time Magazine Person of the Year (shared) for 2006!

Drat.

Fellowship Applications Submitted

As of yesterday, I am done with applying for things (hopefully for a little while). I sent off my application for the NDSEG fellowship, which was a request that the defense department give me about a hundred thousand dollars.

Applying for these fellowships is a funny thing, because at least in the sciences (and particularly at the CS department at Carnegie Mellon), no one needs them. We are already well paid. Receiving this fellowship will not allow me to pursue groundbreaking research for the benefit of our nation that I would not be able to otherwise. The benefit would mostly go to Carnegie Mellon and to my advisers -- they would no longer have to pay me, and as a result, could more easily support other students. Because of this, its interesting that the government has chosen to distribute money through graduate fellowships like this, rather than just giving it directly to academic departments of their choice.

The whole thing is a study in incentives. The main benefit of the fellowship goes to the school, but I apply because it will provide me with a line on my resume and a few hundred dollars extra a month. To apply, students need recommendations, and who better to write them than their advisers? But of course, advisers have a vested interest in having their students receive outside support.

We find out in April.

Abra-Kadabra, nonlinear alakazam!

An article today in the New York Times about algorithmic trading gives a very very silly description of machine learning, and uses the word "nonlinear" as if it means magic. "Higher-level computer science" indeed.

The result was nonlinear decision making processes more akin to how a brain operates. So-called “neural networks” and “genetic algorithms” have become common in higher-level computer science. Neural networks permit computers to create new rules and automatically change underlying assumptions by experimenting with thousands of random sequences and processes. Genetic algorithms encourage software to “evolve” by letting different rules compete, and combining the most successful outcomes.
Wall Street has rushed to mimic the techniques. Because arbitrage opportunities disappear so quickly now, neural networks have emerged that can consider thousands of scenarios at once. It is unlikely, for instance, that Microsoft will begin selling ice-cream or I.B.M. will declare bankruptcy, but a nonlinear system can consider such possibilities, and thousands of others, without overtaxing computers that must be ready to react in milliseconds.

Trader Joe's

Trader Joe's just opened in Pittsburgh! The mayor was there for the ribbon cutting ceremony on friday.

This is fabulous; Its lack of Trader Joe's was one of Pittsburgh's major failings. Now it is alleviated!

I would write a longer post, but I have portobello and ricotta ravioli to eat.

High School Math and Computer Science Curriculum

I went to Brookline High School, which had a very good math and science program. Still, though, (as I expect it is almost everywhere) the focus of the math was on calculations. We saw proofs in geometry, and calculus, but these are often technical, and only steps along the way to deriving some theorem that can help solve some poorly motivated practical problem (Why do I want to calculate the rate that water rises while filling a solid created by a swept polygon??). Also, ideas from computer science were completely missing.

Its not that the more beautiful ideas in mathematics are out of reach of high schoolers -- indeed, my favorite proofs are short, simple, and profound.

If I were designing a highschool senior level introduction to mathematics, I would include:
-- The infinitude of primes
-- The uncountability of reals
-- The notion of polynomial time computation, NP completeness, and the power of randomness
-- The idea of undecidability, through the halting problem

Each of these topics can be presented with elementary mathematics, and each seems to say something profound about the universe. I think that with a course like this, rather than another course focussing on calculation, mathematics and computer science would seem like sexier topics.

Maybe the course could be called "The Nature of Infinity and the Possible"