Postdoc in Economics of Privacy at UPenn

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

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

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

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

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

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

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

Bomb detection

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

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

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

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

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

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

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

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

China

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

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

God, morality, and general sum games.

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

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

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

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

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

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

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

New CS/game theory blog

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

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

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

Maybe we're all the same

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

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

Asynchronous Games

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

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

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

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

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

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

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

We show the following in this alternating move model:

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

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

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

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

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

Oh, Pittsburgh

From the Post Gazette: 

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

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

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

CS theory in 60 minutes for highschool students

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

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

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

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

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

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

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

Incentives, computation, and privacy

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

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

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

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

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

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

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

 

Computer science in the news

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

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

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

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

Auctions with Unknown Supply

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

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

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

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

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

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

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

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

Grim Trigger

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

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

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

or about 1/3 of his estate. 

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

Presidential politics

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

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

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

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

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

Malice, Anarchy, and Regret

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

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

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

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

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

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

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

Useful Privacy

Privacy

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

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

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

Usefulness

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

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

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

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

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

That new facebook box

From the New York Times today:

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

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