Adventures in Computation

Postdoc in Economics of Privacy at UPenn

2011-06-19T16:23:00.003-04:00

We have another postdoc position available at Penn for theorists interested in studying the foundations of privacy, and developing a theory of how privacy and economic incentives should interact!

Applications are invited for a postdoc position in the theory of privacy and economics at the University of Pennsylvania. An outline of the hosting project is below.

The ideal candidate will have a Ph.D. in Computer Science, Economics, or Statistics and a strong record of publication. To apply, please send a CV, research statement, and the names of three people who can be asked for letters of reference to Aaron Roth (aaroth@cis.upenn.edu). Both the term of the postdoc and the starting date are negotiable.

Inquiries can be directed to any of the PIs:

Sham Kakade

Michael Kearns

Mallesh Pai

Aaron Roth

---

In the last decade private data has become a commodity: it is gathered, bought and sold, and contributes to the primary business of many Internet and information technology companies. At the same time, various formalizations of the notion of ‘privacy’ have been developed and studied by computer scientists. Nevertheless, to date, we lack a theory for the economics of digital privacy, and we propose to close this important gap.

Concretely, we propose to develop the theory to address the following questions:

How should a market for private data be structured? How can we design an auction that accommodates issues specific to private data analysis: that the buyer of private data often wishes to buy from a representative sample from the population, and that individuals value for their privacy can itself be a very sensitive piece of information?

How should we structure other markets to properly account for participants concerns about privacy? How should we properly model privacy in auction settings, and design markets to address issues relating to utility for privacy?

Studying economic interactions necessitates studying learning – but what is the cost of privacy on agent learning? How does the incomplete information that is the necessary result of privacy preserving mechanisms affect how individuals engaged in a dynamic interaction can learn and coordinate, and how do perturbed measurements affect learning dynamics in games? How can market research be conducted both usefully and privately?

Our investigation of these questions will blend models and methods from several relevant fields, including computer science, economics, algorithmic game theory and machine learning.

The proposed research directly addresses one of the most important tensions that the Internet era has thrust upon society: the tension between the tremendous societal and commercial value of private and potentially sensitive data about individual citizens, and the interests and rights of those individuals to control their data. Despite the attention and controversy this tension has evoked, we lack a comprehensive and coherent science for understanding it. Furthermore, science (rather than technology alone) is required, since the technological and social factors underlying data privacy are undergoing perpetual change. Within the field of computer science, the recently introduced subfield of privacy preserving computation has pointed the way to potential advances. The proposed research aims to both broaden and deepen these directions.

Differential Privacy Postdoc at UPenn

2011-06-02T08:54:00.003-04:00

We are building a differential privacy group at UPenn! Below is the announcement for a postdoc position in the theory and practice of differential privacy. If you are a theorist who wants to actually put your contributions into practice as well, please apply.

There will be another announcement soon for another pure-theory postdoc position in the exciting new area of "privacy and economics". Stay tuned, and contact me if you are interested.

--------------------------------

Applications are invited for a postdoc position in the theory and practice of differential privacy at the University of Pennsylvania. An outline of the hosting project is below.

The ideal candidate will have a Ph.D. in Computer Science, a combination of strong theoretical and practical interests, and expertise in at least two of: programming languages, theoretical computer science, and systems software. The position is for one year in the first instance, with possible renewal up to four years. Starting date is negotiable. Applications from women and members of other under-represented groups are particularly welcome.

To apply, please send a CV, research statement, and the names of three people who can be asked for letters of reference to Benjamin Pierce (bcpierce@cis.upenn.edu). Inquiries can be directed to any of the PIs:

Andreas Haeberlen
Benjamin C. Pierce
Aaron Roth

-------------------------------------------------------------------------------------------------
Putting Differential Privacy to Work

A wealth of data about individuals is constantly accumulating in various databases in the form of medical records, social network graphs, mobility traces in cellular networks, search logs, and movie ratings, to name only a few. There are many valuable uses for such datasets, but it is difficult to realize these uses while protecting privacy. Even when data collectors try to protect the privacy of their customers by releasing anonymized or aggregated data, this data often reveals much more information than intended. To reliably prevent such privacy violations, we need to replace the current ad-hoc solutions with a principled data release mechanism that offers strong, provable privacy guarantees. Recent research on DIFFERENTIAL PRIVACY has brought us a big step closer to achieving this goal. Differential privacy allows us to reason formally about what an adversary could learn from released data, while avoiding the need for many assumptions (e.g. about what an adversary might already know), the failure of which have been the cause of privacy violations in the past. However, despite its great promise, differential privacy is still rarely used in practice. Proving that a given computation can be performed in a differentially private way requires substantial manual effort by experts in the field, which prevents it from scaling in practice.

This project aims to put differential privacy to work---to build a system that supports differentially private data analysis, can be used by the average programmer, and is general enough to be used in a wide variety of applications. Such a system could be used pervasively and make strong privacy guarantees a standard feature wherever sensitive data is being released or analyzed. Specific contributions will include ENRICHING THE FUNDAMENTAL MODEL OF DIFFERENTIAL PRIVACY to address practical issues such as data with inherent correlations, increased accuracy, privacy of functions, or privacy for streaming data; DEVELOPING A DIFFERENTIALLY PRIVATE PROGRAMMING LANGUAGE, along with a compiler that can automatically prove programs in this language to be differentially private, and a runtime system that is hardened against side-channel attacks; and SHOWING HOW TO APPLY DIFFERENTIAL PRIVACY IN A DISTRIBUTED SETTING in which the private data is spread across many databases in different administrative domains, with possible overlaps, heterogeneous schemata, and different expectations of privacy. The long-term goal is to combine ideas from differential privacy, programming languages, and distributed systems to make data analysis techniques with strong, provable privacy guarantees practical for general use. The themes of differential privacy are also being integrated into Penn's new undergraduate curriculum on Market and Social Systems Engineering.

Abe's blog

2010-04-17T13:27:00.003-04:00

Abe Othman has been writing a blog for a couple weeks now, but he just now opened it up to comments. Abe is a student of Tuomas Sandholm, and works on building markets. Its a very interesting blog -- I've greatly enjoyed reading all of his posts, and I can't wait to read all of the upcoming anonymous comments. So far, he's written posts voicing the following opinions: Nash equilibria (and all solution concepts -- and maybe John Nash) are stupid, AI might just be bad theory, and Ray Kurzweil is bad for AI. Agree? Disagree? Comment anonymously!

Abe's blog: Constructive Economics

MIT + Social Media + Red Balloons

2009-12-04T22:21:00.002-05:00

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

2009-11-04T11:47:00.002-05:00

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

2009-09-16T21:28:00.002-04:00

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.

2009-08-23T00:30:00.002-04:00

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

2009-08-13T14:22:00.002-04:00

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

2009-08-08T19:49:00.002-04:00

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

2009-07-05T10:00:00.001-04:00

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

2009-01-15T17:37:00.002-05:00

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

2008-12-03T17:18:00.005-05:00

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

2008-11-28T10:30:00.003-05:00

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

2008-11-21T15:13:00.002-05:00

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

2008-11-08T14:56:00.004-05:00

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

2008-09-13T11:09:00.003-04:00

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

2008-05-04T15:51:00.002-04:00

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

2008-02-10T10:56:00.005-05:00

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

2007-11-27T01:43:00.000-05:00

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

2007-11-11T13:10:00.001-05:00

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

2007-11-04T12:02:00.000-05:00

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?

2007-10-19T16:12:00.000-04:00

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?

2007-09-24T22:15:00.000-04:00

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

2007-09-23T13:27:00.000-04:00

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

2007-09-23T13:04:00.000-04:00

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

2007-09-10T12:39:00.000-04:00

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:

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)

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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

2007-04-14T16:18:00.000-04:00

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

2007-03-12T17:43:00.000-04:00

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

2007-01-02T11:42:00.000-05:00

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

2006-12-30T11:51:00.000-05:00

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

2006-12-28T00:10:00.000-05:00

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

2006-12-26T21:46:00.000-05:00

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!

2006-11-25T00:51:00.000-05:00

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

2006-10-29T22:21:00.000-05:00

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

2006-06-28T16:03:00.000-04:00

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"

The government is creepy

2006-06-15T21:57:00.000-04:00

New Jersey has filed subpoenas to telephone service providers to try and discover if they violated New Jersey consumer protection acts when they disclosed thousands of phone records to the NSA. The federal government, however, has filed a lawsuit to block these subpoenas.
Check out this quote from the Times:

"Compliance with the subpoenas issued by those officers would first place the carriers in a position of having to confirm or deny the existence of information that cannot be confirmed or denied without causing exceptionally grave harm to national security," wrote Irene Dowdy, an assistant United States Attorney, in the 14-page lawsuit. "And if particular carriers are indeed supplying foreign intelligence information to the Federal Government, compliance with the subpoenas would require disclosure of the details of that activity."

I cannot imagine what sort of "grave harm" it would do to national security for the public to know exactly what data was given to the government, and under what circumstances. Given all of the publicity that has surrounded this, if I were a terrorist, I would have to assume at this point that the NSA has all of the data that is available about all of my electronic communications. What seems to be at issue now is whether the NSA did this legally. Perhaps the grave harm that will be done if the truth is revealed is that the government will be forced to abide by its own laws? If this is the case, the correct course of action should be to change the laws, not prevent state investigations into violations of those laws...

New CS Building

2006-04-25T02:26:00.000-04:00

Carnegie Mellon will be joining the long list of schools to have a CS building named after Bill Gates. (I'm counting Harvard's Maxwell-Dworkin, which is named after his mom...) See the new building here. The thing won't be complete for at least another two years, so I will still have to do my time in a windowless basement office, but it sounds nice -- collaborative areas, lots of natural light, etc. And BEST of all, "The main north-south axis, however, will make it so that the building can still be easily navigated" -- this is great! It will be possible to navigate the building!

I can't help but think that this is a not-so-subtle jab at MIT's Stata center, which is -not- easy to navigate. Otherwise, this seems like a building feature that would go without saying...

Theory and Systems

2006-04-25T01:36:00.000-04:00

A very nice post about the need to study systems, even for theorists. This is good to hear; Some of the people I know are spending all summer studying theory, beginning their research. This gives me hope that learning about engineering challenges at Google will be a fruitful experience as well.

This is getting serious

2006-04-19T02:11:00.000-04:00

We graduate in less than a month. On May 16th, John McCain (hopefully) will come speak to us on class day, and I will have a diploma in hand. Or rather, the opportunity to wait in a long line to get a diploma, which will otherwise be mailed to me (Why do I need a diploma anyhow?) All well and good.

On May 18th, Columbia throws me out on the street. So I've got about a month to find an apartment in the city.

Its official.

2006-04-12T11:56:00.000-04:00

Without too much extra thought, I just emailed Carnegie Mellon and let them know that I will be enrolling in the fall. I guess this is it then -- I'm going to Carnegie Mellon. This will be exciting!

But first... My summer internship at Google.

Carnegie Mellon

2006-04-12T01:40:00.000-04:00

I'm almost there. I sent out emails today turning down Penn and Princeton. In the emails I said I was choosing Carnegie Mellon. I've filled out the acceptance form for CMU. I just have to mail it, and then turn down Stanford and Berkeley (Ouch)

Fiber and making life changing decisions with very little information.

2006-04-10T17:53:00.000-04:00

What is the daily recommended fiber intake? Before my graph theory class, I ate a bag of potato chips and a bag of popcorn. The bag of potato chips contained 1 g of fiber, which translated into 4% of my daily value. The bag of popcorn contained 1 g of fiber, which translated into 5% of my daily value. Is this roundoff error, or does the popcorn company play fast and loose with the fiber rules?

I'm leaning very heavily towards Carnegie Mellon now. I'll almost certainly go there. I notified some of the schools yesterday that I would not be attending them (Harvard, Michigan, Washington, Brown). I still have a bit of nagging doubt though... There are still so many areas of computer science that I haven't been exposed to, and maybe I will love. CMU is the best place to do learning/mechanism design. Where is the best place to discover new interests? Today in information theory we covered network coding. Never seen it before. Looks cool. CMU has you take your courses after you pick your advisor, Berkeley does it the other way around. Why can't the faculty I'm interested in work at Berkeley? Then the choice would be clear.

In other news, there's a new young faculty member who might end up at CMU next year, who seems very interesting. He's not going there for sure, but he's definitely not going to Berkeley, so I can add 50% of his value, in expectation, to CMU's column...

Decision in 5 days.

Theory Girl

2006-04-07T13:42:00.000-04:00

I just found the University of Washington's rendition of theory girl today (set to the tune of uptown girl). As computer science music goes, its pretty good. Of course the mathematicians may still have us beat with the love ballad "Finite Simple Group (Of Order Two)" , by the Klein Four Group (But aren't there 5 of them?) I like "theory girl" much better than the work of MC++ though -- he's got higher production values, but borders more closely on bad rap than funny CS rap.

Also good: "The Longest Path"