Publications

  • The Price of Malice in Linear Congestion Games. In Submission.
  • A Learning Theory Approach to Non-Interactive Database Privacy With Avrim Blum and Katrina Ligett. In STOC 08: The 40th ACM Symposium on the Theory of Computing.

    •                 We consider the problem of non-interactive database privacy: how can we release useful information about a database while preserving differential privacy? Motivated by learning theory, we circumvent existing lower bounds by considering usefulness relative to a concept class. We say that a sanitized database is useful with respect to a class of functions C, if every query in C gives approximately the same answer whether evaluated on the sanitized database or the real database. We show that it is possible to release a privacy-preserving database that is useful for any concept class with polynomial VC-dimension. Our proof, however, does not necessarily yield an efficient algorithm. We then give efficient algorithms to privately release databases useful for axis-aligned rectangles of constant dimension, and halfspaces (according to a relaxed definition of usefulness). The general question of computational efficiency is left open.

  • The Price of Stochastic Anarchy. With Christine Chung, Kirk Pruhs, and Katrina Ligett. In SAGT'08: The First Annual Symposium on Algorithmic Game Theory.

    •                 We study the price of anarchy of the load balancing game on unrelated machines with respect to its stochastically stable states (as opposed to its Nash equilibria). Stochastic stability is a solution concept from evolutionary game theory that avoids many of the pitfalls of Nash equilibria: Unlike Nash, the stochastically stable states of a game are always the result of natural dynamics of computationally bounded and decentralized agents, and are resilient to deviations from perfect play (noise). In potential games, the stochasticly stable states are a subset of the Nash equilibria, and so distinguish between the equilibria that are resilient to imperfect play from those that are brittle. In such games, the price of stochastic anarchy can therefore be viewed as a smoothed analysis of the price of anarchy (which I discuss a bit here.) In particular, even for only two players and two machines, the price of anarchy of the load balancing game on unrelated machines is unbounded, but the price of stochastic anarchy is 2. We give (non-matching) upper and lower bounds on the price of stochastic anarchy in the general n-player m-machine case.

  • Regret Minimization and the Price of Total Anarchy. With Avrim Blum, MohammadTaghi Hajiaghayi, and Katrina Ligett. In STOC 08: The 40th ACM Symposium on the Theory of Computing.

    •                 Traditionally when studying price of anarchy, it is assumed that selfish players will play according to a Nash equilibrium. This is often unrealistic, and brittle to the introduction of Byzantine players. We show that under strictly weaker assumptions about rational agents, it is still possible to prove guarantees about the social welfare of a game, which we term “the price of total anarchy”. We study three broad classes of games, and show that in many cases, the price of total anarchy exactly matches the price of anarchy, while at the same time allowing for Byzantine (irrational, arbitrary, adversarial, etc.) players, about whom we make no assumptions. I discuss this research direction a bit here.

    Talks and Presentations

    • A Machine Learning Perspective on Differential Privacy. (Work with Avrim Blum and Katrina Ligett) CMU/Microsoft Research MindSwap on Privacy, October 19, 2007 [Poster]
    • Selfishness without Nash: Two Alternatives to the Price of Anarchy. CMU Theory Lunch, May 16, 2007 [Powerpoint Slides]