Lecture 6 -- Implementing Nash equilibria ex-post in incomplete information games (Part 2)

In Lecture 6 of our Privacy and Mechanism Design course, we continue our study of the use of differential privacy to implement equilibrium of complete information games -ex post- in settings of incomplete information augmented with an extremely weak "mediator".

Last class, we proved that to accomplish this task, it would be sufficient to design an algorithm that:

1. Satisfied (joint) differential privacy, and...
2. Computed an (asymptotic) Nash equilibrium of the complete information game induced by reported types. 

We also took a brief detour into private algorithmic techniques, and learned how to privately maintain a count on a stream of numbers. 

This class, we partially implement this agenda. We define large games and congestion games, and give an algorithm for privately computing Nash equilibrium in large congestion games, which uses our newly learned ability to count. We conclude that in such games, with the help of a weak mediator, we can enjoy the nice properties of the pure strategy Nash equilibria of these games in the complete information setting, even in incomplete information settings when player types can be arbitrary (i.e. not necessarily drawn from any prior distribution). 

There remains one more lecture in this series -- we will show that if we strengthen the power of our weak mediators somewhat, by giving them the ability to verify reported player types, then we can extend these results to arbitrary large games (i.e. not necessarily congestion games) by privately computing correlated equilibria. 

This last part will have to wait a couple of weeks though. Next week, we will have Jamie Morgenstern giving us a guest lecture on her very interesting recent work joint with Avrim Blum, Ankit Sharma, and Adam Smith. 

Lecture 4 -- The Empirical Implications of Privacy Aware Choice

Just barely out of order, the notes for Lecture 4 of our privacy and mechanism design class are now online.

In this lecture, Rachel Cummings told us about her very interesting work with Federico Echenique and Adam Wierman, studying what implications preferences for privacy might have in the revealed preferences setting.

The idea, in a nutshell, is this: suppose some entity is observing all of your purchase decisions online, and trying to deduce from them what your utility function over goods is. For example, if it observes you purchasing beer when you could have had milk for the same price, it will deduce that you strictly prefer beer to milk.

Now suppose that you understand that you are being observed, and you have preferences not only over the goods that you buy, but also over the set of deductions that the observer is going to make about you. Given a set of prices and a budget, you will choose which bundle of goods to buy to optimize this tradeoff between your utility for the bundle, and your cost for what is learned about you by the observer. As always, however, the observer only gets to see what you buy.

Can the observer tell whether or not you care about privacy? Can he deduce what your preferences over goods are? Can he prove that you are not buying goods totally at random?

One of the main results discussed in this lecture, is that for sufficiently general forms of the preferences that agents may hold, the answer to all of these questions is "no". Specifically, all sets of observations are rationalizable by some privacy-aware utility function.

Lecture 5 -- Implementing Nash equilibria ex-post in incomplete information games (Part 1)

Welcome back (after a brief hiatus) to the privacy and mechanism design course. Last week we had a guest lecture by Rachel Cummings about her work on the Empirical Implications of Privacy Aware Choice.  We will have notes and a blog post about that soon, but for now, welcome to Lecture 5!

In this lecture, we consider the following problem. Suppose we have an n player game. We might want to implement a Nash equilibrium of the complete information game (which often have nice properties), but naturally find ourselves in the common situation when the n players do not know each others types. Is there a modification of the game that can implement the complete-information game equilibrium as a simple ex-post Nash equilibrium, which does not require that players know anything about each others types, and which requires no coordination?

The modification of the game we consider is the introduction of a very weak "mediator", which essentially only has the power to listen and to give advice, but not to verify or to enforce. Players will have the option of reporting their type to the mediator, in which case it will suggest an action for them to play. However, they can:

1. Completely ignore the mediator and choose an action to play on their own
2. Lie to the mediator about their types, and/or
3. Use the mediator's suggestion however they like, not necessarily following it (i.e. the mediator can not enforce its suggestion)

What we would like is that players should all follow "good behavior", which involves

1. Truthfully reporting their type to the mediator, and then
2. Faithfully following the mediator's suggestion.

We prove that if the mediator offers its suggestions by computing a Nash equilibrium of the complete information game defined by players reported types, and satisfies (a variant of) differential privacy, then the mediator makes "good behavior" an asymptotic ex-post Nash equilibrium of the incomplete information game, and that in this ex-post equilibrium, players end up playing a Nash equilibrium of the original game of complete information (defined by the realized player types).

This leaves us with the minor task of actually figuring out how to compute a Nash equilibrium privately. Here, we realize that thus far in the class, we have been skating by knowing nothing about private algorithm design except for the exponential mechanism. So we take a detour to learn some more basics. We get as far as learning how to count, which turns out to be enough. This will set us up for next lecture, when we can actually implement this agenda and design a mediator that satisfies the hypotheses we need.

(The idea of designing a mediator by privately computing an equilibrium comes from joint work with Michael Kearns, Mallesh Pai, and Jon Ullman, which shows how to privately compute correlated equilibria in arbitrary large games. We will cover this later. The implication in this lecture about mediators that privately compute Nash equilibria comes from joint work with Ryan Rogers, which shows how to privately compute Nash equilibria in large congestion games. )

Lecture 3 -- Mechanism Design for arbitrary objective functions, and without money!

In the third lecture of our course on privacy and mechanism design, we go back to using differential privacy as a tool in mechanism design, and cover a remarkable result of Nissim, Smorodinsky, and Tennenholtz.

Traditionally in mechanism design, social welfare holds a special place in the pantheon of objective functions: this is because in any social choice setting, we can use the VCG mechanism to exactly optimize for social welfare while guaranteeing dominant strategy truthfulness. In general, it is not possible to truthfully optimize most other objective functions -- and even for social welfare, the VCG mechanism requires the ability to charge payments. It is the rare setting when we can achieve some objective truthfully without payments, and even rarer when that objective is not social welfare.

In todays lecture, we give a general mechanism that in any social choice setting (satisfying certain technical conditions) approximately optimizes any low-sensitivity objective function (social welfare satisfies this condition, but so do many others). Moreover, this mechanism is strictly dominant strategy truthful, and crucially does not require the use of payments. Of course, we can't get around classical impossibility results for free -- the tradeoff, as always, is that we are only optimizing our objective approximately up to some additive loss. However, in large economies, this loss will often become negligible as the size of the population grows.

After class, Rachel Cummings will give our theory seminar on her own work in privacy and mechanism design: The Empirical Implications of Privacy Aware Choice, which is joint work with Federico Echenique and Adam Wierman, both from Caltech. Be there or be square!

Lecture 2: Privacy as a Desideratum in Mechanism Design -- Making the Exponential Mechanism Truthful

For those of you following the privacy and mechanism design course at home, tomorrow's Lecture 2 is now online.

This lecture explores a different aspect of privacy and mechanism design. Last week, we considered the use of differential privacy purely as a tool, to design a prior free asymptotically truthful and revenue optimal mechanism for digital goods auctions. In this lecture, we motivate differential privacy as a desideratum for its own sake, and argue that it gives mechanisms (often at very little cost) a natural notion of robustness against the possibility of extra unmodeled parts of agents utility functions.

Finally, we derive a private version of the VCG mechanism, that for general social choice problems is simultaneously:

1. (Exactly) dominant strategy truthful
2. Differentially private
3. (Approximately) welfare optimal

This result is from Huang and Kannan 2012: "The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal". Although this is a recent paper, it is a basic, important, foundational result that "should" have been discovered earlier. It fits in very nicely at the beginning of the semester.

(And for those of you actually taking this class and looking for inspiration to do a course project, this paper started as Zhiyi Huang's course project in the 2011 privacy course I taught here at Penn)

Privacy + Mechanism Design course begins today

Today several students will endure the first (3 hour!) lecture in an experimental course I am teaching on privacy and mechanism design. Its a very new area -- whether or not there is enough material to cover a whole semester may depend on how many new theorems are proven during the semester that the course is running. (I already know of the existence of several papers I will want to teach, but haven't read yet since they aren't yet available!)

A secondary goal that I have is to produce a nice set of lecture notes, that will be accessible to people curious about getting into the field. I encourage people to read along, starting with today's Lecture 1. We're starting from basics -- I don't want to assume that readers know anything about either privacy, or mechanism design. In the first lecture, we introduce differential privacy from the perspective of a game theorist, and use it to solve an interesting problem: prior-free revenue maximization in a digital goods auction. Along the way we learn about a useful tool, "The exponential mechanism", that we will encounter again.

The digital goods auction setting is not only a nice introduction to many of the ideas underlying the privacy/mechanism design connection, it is also historically faithful: all of the results in Lecture 1 are from the seminal paper of McSherry and Talwar which introduced the connection between differential privacy and game theory: Mechanism Design via Differential Privacy.

COLT call for papers

Nina Balcan asked me to post the COLT 2014 call for papers. A couple of interesting things in the call: privacy is specifically mentioned as a constraint of interest on learning, and there is a call for papers on "Learning in other settings: e.g. social, economic, and game-theoretic".

The 27th Annual Conference on Learning Theory (COLT 2014) will take
place in Barcelona, Spain, on June 13-15, 2014

We invite submissions of papers addressing theoretical aspects of
machine learning and related topics. Submissions by authors who are
new to COLT are encouraged. We strongly support a broad definition of
learning theory, including, but not limited to:

• Design and analysis of learning algorithms and their generalization ability
• Computational complexity of learning
• Optimization procedures for learning
• Unsupervised, semi-supervised learning, and clustering
• Online learning
• Interactive learning
• Kernel Methods
• High dimensional and non-parametric empirical inference, including
sparsity methods
• Planning and control, including reinforcement learning
• Learning with additional constraints: E.g. privacy, time or memory
budget, communication
• Learning in other settings: E.g. social, economic, and game-theoretic
• Analysis of learning in related fields: natural language processing,
neuroscience, bioinformatics, privacy and security, machine vision,
data mining, information retrieval.

We are also interested in papers that include viewpoints that are new
to the COLT community. We welcome experimental and algorithmic papers
provided they are relevant to the focus of the conference by
elucidating theoretical results. Also, while the primary focus of the
conference is theoretical, papers can be strengthened by the inclusion
of relevant experimental results.

COLT will award both best paper and best student paper awards. Best
student papers must be authored or coauthored by a student. Authors
must indicate (using a footnote on the first page of the paper) at
submission time if they wish their paper to be eligible for a student
award. This does not preclude the paper to be eligible for the best
paper award. The program committee may decline to make these awards,
or may split them among several papers.

Papers that have previously appeared in journals or at other
conferences, or that are being submitted to other conferences, are not
appropriate for COLT. Papers that include work that has already been
submitted for journal publication may be submitted to COLT, as long as
the papers have not been accepted for publication by the COLT
submission deadline (conditionally or otherwise) and that the paper is
not expected to be published before the COLT conference (June 2014).

Accepted papers will be published electronically, in the JMLR Workshop
and Conference Proceedings series.

Rebuttal Phase
As in the previous years, we will have a rebuttal phase during the
review process. Initial reviews will be sent to authors before final
decisions have been made. Authors will have the opportunity to provide
a short response on the PC's initial evaluation. Final
acceptance/rejection decision will be made a week later.

Open Problems Session:
We also invite submission of open problems. A separate call for open
problems will be available at the conference website:
http://orfe.princeton.edu/conferences/colt2014/

Submission Instructions:
Submissions are limited to 12 JMLR-formatted pages, plus additional
pages for references and appendices. All details, proofs and
derivations required to substantiate the results must be included in
the submission, possibly in the appendices. However, the contribution,
novelty and significance of submissions will be judged primarily based
on the main text (without appendices), and so enough details,
including proof details, must be provided in the main text to convince
the reviewers of the submissions' merits.

Important Dates:
• Paper submission deadline: February 7th, 2014, 11:00 PM EST
• Author response period: April 5-10, 2014
• Author notification: April 19, 2014
• Conference: June 13-15, 2014

On behalf of the COLT 2014 organizers,

Program Chairs
• Maria-Florina Balcan (Georgia Institute of Technology)
• Csaba Szepesvári (University of Alberta)

Local Arrangements Chairs
•  Sébastien Bubeck (Princeton University)
•  Gábor Lugosi (ICREA and Pompeu Fabra University)

Publication Chair
• Vitaly Feldman (IBM Almaden Research Center)

Call for Postdocs

Penn's new Warren Center for Network and Data Sciences (warrencenter.upenn.edu) has multiple postdoc positions for the 2014-15 academic year and beyond. The application procedure (described below) requires candidates to be nominated internally by Center faculty affiliates, so interested candidates should first contact potential Penn faculty hosts in their areas of interest to facilitate a potential nomination.

Michael Kearns and Rakesh Vohra Directors, Warren Center for Network and Data Sciences warrencenter.upenn.edu

**************************************************************************************************************************************************************************

Penn's newly-launched Warren Center for Network and Data Sciences seeks nominations for 2014 Warren Postdoctoral Fellowships.

Warren Fellow candidates should have research interests in the subjects supported by the center, which include but are not limited to network science (including the study of social, technological, economic, organizational and biological networks, as well as underlying foundational areas such as graph theory, game theory, mechanism design) and data science (including machine learning, statistics, data privacy and security). The ideal candidate will have a strongly interdisciplinary research agenda with a demonstrated track record, and would be nominated by faculty affiliates of the Warren Center in two or more Penn departments who will act as hosts, advisors and collaborators of the candidate.

Warren Postdoctoral Fellows will receive generous and competitive stipends and research support, and will participate in a vibrant and growing community of Warren Center faculty affiliates, postdocs and students. We expect to fund multiple Warren Fellows for the 2014-15 academic year. Fellowships are for a one-year period, extendable to two by mutual agreement. In cases where the nominator or their department have partial funding for a nominee, the Warren Center may consider providing additional support to cover the balance of the costs.

Nominations from Penn faculty members affiliated with the Warren Center will be accepted immediately. The nominator's home department is expected to provide office space, administrative support and handle the logistics of employment of a successful candidate, including visa/immigration support where relevant. The nominator should send the following materials to admin@warrencenter.upenn.edu:

* A nomination letter indicating why the candidate is particularly suited to advance the goals of the Warren Center. * A supporting letter from the chair of the nominee's department outlining departmental support that will be provided. * Support letters from one or more other Warren Center faculty affiliates. * The candidate's CV, the candidate's external letters of reference, and a sample of the candidate's work (either as an electronic document or URL).

Please ensure all attachments are in .pdf format.

A committee to reviewing and select applications will be announced shortly. Selections will be made on a periodic and rolling basis, with the expectation that the first class of Fellows will begin in the Fall of 2014.

Michael Kearns and Rakesh Vohra Directors, 
Warren Center for Network and Data Sciences 
warrencenter.upenn.edu

Coordination when Information is Scarce: How Privacy can Help.

This post is the first in a (hopefully) series of posts about how tools and ideas from differential privacy can be useful in solving problems in game theory. The connection might at first be surprising, but is in fact very natural. The field of differential privacy studies algorithms whose inputs are generated by the reports of \(n\) players. It provides tools for bounding the sensitivity of the output of the algorithm in a precise, probabilistic sense to unilateral changes to the input by a single one of these players. This notion of unilateral deviations is very similar to the notions of stability at equilibrium that game theory is concerned about, and this is the root of the connection. For a general overview of the area, let me plug the survey on Differential Privacy and Mechanism Design that Mallesh and I wrote for the most recent issue of SIGecom Exchanges. In this post, I'll discuss a result that Michael Kearns, Mallesh Pai, Jon Ullman, and I have had kicking around for awhile. We only recently hit upon the interpretation of the result that I'll discuss here though, which I rather like. For more details, you can check out the arXiv paper, which we revised a couple of weeks ago. I should add that the story that accompanies our technical contributions is the result of discussions with many people as we've gone about and presented it. Tim Roughgarden and Ricky Vohra deserve special thanks.



In game theory, there are several popular abstractions for what players in a game know about their opponents.

• In games of complete information, players know exactly the utility functions that each of their opponents is trying to optimize. 
• In games of incomplete information, players don't know what their opponent's utility functions are. In Bayesian games, players utility functions are parameterized by "types", which are drawn from a known (possibly correlated) prior distribution. Agents know the distribution from which their opponents' types are drawn, but not the types themselves. 

In games of complete information, the standard solution concept is the Nash equilibrium: informally, everyone should be playing an action such that no single player can benefit by making a unilateral deviation. Players can randomize, so actions are evaluated in expectation over the random choices of one's opponents, but their utility functions are known.

In games of incomplete information, strategies are thought of as mappings from types to actions. The standard solution concept is the "Bayes Nash Equilibrium", which informally states that everyone should be playing a strategy such that no single player can benefit by making a unilateral deviation, where now strategies are evaluated in expectation both over the random choices of one's opponents, and also over the random realization of the types of one's opponents, as drawn from the known prior distribution.

Games of complete information are attractive for a number of reasons: not least of which that they are much cleaner and more analytically tractable than games of incomplete information. However, when talking about large \(n\) player games, where players don't all know each other, have limited abilities to communicate, and might think of their types as proprietary information, games of incomplete information are probably a more reasonable model of reality.

Unfortunately, the quality of Bayes Nash Equilibria can be much worse than the corresponding Nash equilibria of the full information game, even in the worst case over type realizations. The reason is that not knowing the utility functions of your opponents can make coordination very difficult. Consider the following toy example, borrowed from Bhawalkar and Roughgarden:

There are \(n\) players, and \(n + \sqrt{n}\) "goods" to be distributed. Each player \(i\) has utility \(u_{i,j} \in \{0,1\}\) for receiving a good \(j\). The game is played as follows: each player \(i\) names a single good \(s_i\). Each good \(j\) is allocated at random to one of the players that named it. Now suppose that types are drawn from the following distribution. The goods are randomly partitioned into two sets, \(S\) and \(T\), with \(|S| = n\) and \(|T| = \sqrt{n}\). For every player \(i\) and good \(j \in T\), \(u_{i,j} = 1\). A perfect matching \(\mu\) is selected at random between agents \(i\) and goods in \(S\). Agents have value \(u_{i,\mu(i)} = 1 \) for the good \(\mu(i) \in S\) that they are matched to, and value \(u_{i,j} = 0\) for every good \(j \neq \mu(i)\) in \(S\) that they are not matched to. In other words, every player has a "special" good in \(S\) that she uniquely desires, and everyone desires all of the goods in \(T\). If we are in the complete information setting, then since everyone has the option of requesting their special good \(s_i = \mu(i)\), in any reasonable equilibrium (with nobody requesting a good they don't want) \(n\) goods are allocated to bidders who desire them, for total social welfare of \(n\). However, in the incomplete information setting, because of the symmetry of the distribution, no player can distinguish their special good from amongst the \(\sqrt{n} + 1\) goods that they value. Its not hard to see that in this case, in equilibrium only \(O(\sqrt{n})\) goods get allocated.

So if we find ourselves in a setting of incomplete information, we might nevertheless prefer to implement an equilibrium of the game of complete information defined by the realized types of the players. How can we do that, especially if we have limited power to modify the game?

One tempting solution is just to augment the game to allow players to publicly announce their types (and thus make the game one of complete information). Of course equilibria of the complete information game might not be unique, so to help solve the coordination problem, we could introduce a weak "proxy" that players can choose whether or not to use. Players can "opt in" to the proxy, which means that they report their type to the proxy, which then recommends an action for them to play. At this point they are free to follow the recommendation, or not. Alternately, they can "opt out" of the proxy, which means they never report their type, and then just choose an action on their own. It would be nice if we could design a proxy such that:

1. Simultaneously for every prior on agent types, it is a Bayes-Nash equilibrium for agents to opt-in to the proxy, and then follow its suggested action, and
2. Given that all players behave as in (1), that the resulting play forms an equilibrium of the complete information game induced by the actual, realized types of the players. 

Its tempting to think that to design such a proxy, it is sufficient to have it compute a Nash equilibrium of the complete information game defined by types of the players who opt in, and then suggest that each player play her part of this Nash equilibrium. After all, if everyone is opting in and playing their part of a Nash equilibrium, how can you do better than to do the same? By definition, in a Nash equilibrium, your suggested action is a best response given what all other players are playing. And in fact, in the toy allocation example we discussed above, this works, since there is an equilibrium of the complete information game that is simultaneously optimal for all players.

In general, however, this approach fails. The flaw in our reasoning is that by opting out, you change what the proxy is computing: it is now computing a different equilibrium, for a different game, and so by opting out, you are not merely making a unilateral deviation from a Nash equilibrium (which cannot be beneficial), you are potentially dramatically changing what actions all other players are playing. The Nash equilibrium condition does not protect against deviations like that, and in fact its not hard to construct an example in which this is a real problem. Consider, e.g. toy example #2: There are \(n\) players who each have one of two types -- (M)ountain, or (B)each. Each player has two actions -- they can go to the beach, or go to the mountain. Players prefer the activity that corresponds to their own type, but they also like company. So if a \(p\) fraction of people go to the Mountain, an M type gets utility \(10\cdot p\) if he goes to the mountain, and \(5\cdot (1-p)\) if he goes to the beach. A B type gets utility \(5\cdot p\) if she goes to the mountain, and \(10 \cdot (1-p)\) if she goes to the beach. A proxy that suggests that all players go to the beach if type M is in the majority, and otherwise suggests that all agents go to the mountain always computes a Nash equilibrium of the complete information game defined by the reported types. Nevertheless, any player that is pivotal has incentive to opt-out of the proxy, since this causes the proxy to send all other players to her preferred location.

But what if it were possible to compute an equilibrium in such a way so that whether or not any player \(i\) opted in had very little affect on the distribution over actions suggested by the proxy to all other player \(j \neq i\)? In this case, the problem would be solved: any unilateral deviation from the all-opt-in-and-follow-the-proxy's-suggestion solution would not (substantially) affect the play of one's opponents, and so they would all continue playing their part of an equilibrium of the complete information game, defined on all player's realized types. The equilibrium condition would now directly guarantee that such a deviation could not be beneficial.

So to design a good proxy, its not enough to just have an algorithm that computes an equilibrium of the game defined by the reported types, but it is enough if that algorithm also satisfies a strong enough stability condition. It turns out that a sufficient "stability" condition is a variant on differential privacy: informally, that any unilaterial deviation by a single player \(i\) should not change (by more than a \( (1\pm \epsilon)\) factor) the probability that any particular profile of \(n-1\) actions is suggested to the \(n-1\) players \(j \neq i\).

And in fact it is possible to implement this plan, at least for certain classes of games. We study the class of "large games", which informally, are \(n\) player games in which the affect of any player \(i\)'s action on the utility of any player \(j \neq i \) is bounded by some quantity which is diminishing in \(n\). The Beach/Mountain example is of this type, as are many large population games.  Our main technical result is an algorithm satisfying the required differential privacy stability condition, which computes a correlated equilibrium of any large game. The upshot is that in large games, it is possible to design a very weak proxy (that doesn't have the power to make payments, force players to opt in, or enforce actions once they do opt in) that implements an \(\eta\)-approximate correlated equilibrium of the complete information game, as an \(\eta\)-approximate Bayes Nash equilibrium of the partial information game, no matter what the prior distribution on agent types is. Here \(\eta\) is some approximation parameter that is tending to zero in the size of the game -- i.e. as the game grows large, the equilibria become exact.

To emphasize the purely game theoretic aspects of this problem, I have ignored the fact that differential privacy of course also provides a good guarantee of "privacy". Aside from straightforward incentive issues, there are other reasons why players might be reluctant to announce their types and participate in a complete information game: perhaps their types are valuable trade secrets, or would be embarrassing admissions. Because our solution also happens to provide differential privacy, it is able to implement an equilibrium of the complete information game, while maintaining the privacy properties inherent in a game of incomplete information.

To conclude, differential privacy thus far has been primarily a problem-driven field, that has borrowed techniques from many other areas to solve problems in private data analysis. But in the process, it has also built up a strong conceptual and technical tool kit for thinking about the stability of randomized algorithms to small changes in their inputs. I hope that this and future posts serve to convince you that there is something to be gained by borrowing the tools of differential privacy and applying them to solve problems in seemingly unrelated fields.

Registration for EC is now open

Registration for EC 2013 is now open: http://www.sigecom.org/ec13/registration.html

Register before May 29 to get the early registration discount.

One day workshop in NYC on Differential Privacy, Social Science, and Economics

If you are in the New York City area and interested in the intersection of privacy, economics, and the social sciences, you should check out a workshop being held on March 7th at the Simons Foundation. It is open to the public, and tickets are free, but you must register by the end of February: http://econandsocialsciences.eventbrite.com/

I'll be giving a tutorial on differential privacy in the morning (no background assumed), and the rest of the day will be devoted to talks and discussion by a number of illustrious economists and social scientists. It should be lots of fun.

Differential privacy videos online!

Have you always wanted to learn about differential privacy, but haven't had the time/motivation to read all of the papers? Do you have 3 hours to kill? Well you are in luck! There are now 3 excellent tutorial videos online for you to enjoy! These are from the DIMACS workshop that Adam Smith and I ran last month.

1. Moritz Hardt gives a tutorial on multiplicative weights in differential privacy: http://youtu.be/VeY-fqaaQv4
2. Gerome Miklau gives a tutorial on the matrix mechanism and related work in differential privacy: http://youtu.be/FCIoJ77aTQ4
3. Benjamin Pierce gives a tutorial on differentially private programming languages: http://youtu.be/ci2aueqZ6CU
4. I give a tutorial on game theory and differential privacy: http://youtu.be/kqQ2qv0fYtQ

These tutorials all assume some familiarity with differential privacy (I don't think differential privacy is actually -defined- in any of them). For some light reading to fill in some of the background, you can check out my course notes.

The Fifth Annual New York Computer Science and Economics Day

Are you going to be near NYC in December? The fifth annual New York Computer Science and Economics Day will be held in the new Simons Foundation auditorium in NYC on Monday, December 3rd. The theme for this year is "The Economics of Big Data, Information, and Privacy". In addition to a terrific lineup of invited speakers, posters and short talks (up to 10 minutes long) are invited from students. Abstracts for these should be submitted by November 5th. (Conveniently, right after the STOC deadline). 

See the website for more information: nyce1212

DIMACS Workshop on Differential Privacy and Call for Student Participation

Adam Smith and I are running a 3 day interdisciplinary workshop on differential privacy at DIMACS (Rutgers), on October 24-26. This is immediately following FOCS, which is also being held at Rutgers. The workshop will begin with a day of tutorials on differential privacy as understood in various communities (Theory, databases, programming languages, and game theory), and will continue with two days of research talks and discussion. Details of the workshop can be found here: http://dimacs.rutgers.edu/Workshops/DifferentialPrivacy/ We have an extremely exciting program. (The program listed on the website is somewhat out of date -- there are a half dozen or so additional speakers confirmed).

As part of the program, we will also have a session of short (5-10 minute) talks from students, postdocs, and other interested parties. We encourage submission of abstracts for short talks. The solicitation is below.

See you all in October!


DIMACS Workshop on Differential Privacy across Computer Science
October 24-26, 2012
(immediately after FOCS 2012)

Call for Abstracts -- Short Presentations

The upcoming DIMACS workshop on differential privacy will feature
invited talks by experts from a range of areas in computer science as
well as short talks (5 to 10 minutes) by participants.

Participants interested in giving a short presentation should send an
email to asmith+dimacs@psu.edu containing a proposed talk title,
abstract, and the speaker's name and affiliation.  We wil try to
accommodate as many speakers as possible, but
a) requests received before October 1 will get full consideration
b) priority will be given to junior researchers, so students and
postdocs should indicate their status in the email.

More information about the workshop:

The last few years have seen an explosion of results concerning
differential privacy across many distinct but overlapping communities
in computer science: Theoretical Computer Science, Databases,
Programming Languages, Machine Learning, Data Mining, Security, and
Cryptography. Each of these different areas has different priorities
and techniques, and despite very similar interests, motivations, and
choice of problems, it has become difficult to keep track of this
large literature across so many different venues. The purpose of this
workshop is to bring researchers in differential privacy across all of
these communities together under one roof to discuss recent results
and synchronize our understanding of the field. The first day of the
workshop will include tutorials, representing a broad cross-section of
research across fields. The remaining days will be devoted to talks on
the exciting recent results in differential privacy across
communities, discussion and formation of interesting open problems,
and directions for potential inter-community collaborations.

A tentative program and registration information can be found at
http://dimacs.rutgers.edu/Workshops/DifferentialPrivacy/

Amazing new declassified document

Its been a long time since I've posted on this blog, but along comes a great opportunity. Michael Kearns (tipped off by Ron Rivest) pointed me to a document this morning: http://courses.csail.mit.edu/6.857/2012/files/H03-Cryptosystem-proposed-by-Nash.pdf

What this is, is a recently declassified correspondence between John Nash and the NSA from January 1955. In it, John Nash makes the distinction between polynomial time and exponential time, conjectures that there are problems that -cannot- be solved faster than in exponential time, and uses this conjecture as the basis on which  the security of a cryptosystem (of his own design) relies. He also anticipates that proving complexity lower bounds is a difficult mathematical problem:

"The nature of this conjecture is such that I cannot prove it, even for a special type of cipher. Nor do I expect it to be proven. But this does not destroy its significance. The probability of the truth of the conjecture can be guessed at on the basis of experiencing with enciphering and deciphering"


These letters predate even Godel's letter to Von Neumann, which goes into much less detail about complexity, and yet has also been taken to anticipate complexity theory and the P vs. NP problem.

Finally, an amusing aspect of this document is that it contains the NSA's internal notes on the correspondence. After a page or so of explanation as to why they are rejecting Nash's proposed system, they include the following offhand remark before finishing:

"An interesting pamphlet on Non-Cooperative Games, written by Mr. Nash was also sent to this Agency by the author for our information."

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