Reflections on practical market design, by Moritz Hardt

Moritz Hardt reflects on the political parts of market design, in connection with some of his (more or less) recent, discouraging experience in proposing its use to the California Public Utilities Commission: Towards practicing differential privacy.

Long story short, the CPUC decided not to give data to some users rather than to adopt a privacy standard that would have allowed those users to get useful data.

It's a long post, well worth reading, about what went wrong and what could have been done better. I'll just summarize some of his subject headings, as he thinks about how he'll go about this in the future, in the second part of his post, called On practicing differential privacy:

Focus on win-win applications
"Apply differential privacy as a tool to provide access to data where currently access is problematic due to privacy regulations. Don’t fight the data analyst. Don’t play the moral police. Imagine you are the analyst
....
Don’t empower the naysayers
"for differential privacy to be a major success in practice it would be sufficient if it were successful in some applications but certainly not in all—not even in most.
...
Change your narrative
"Don’t present differential privacy as a fear inducing crypto hammer designed to obfuscate data access. That’s not what it is. Differential privacy is a rigorous way of doing machine learning, not a way of preventing machine learning from being done.
...
Build reliable code repositories
"A weakness of the differential privacy community has been the scarcity of available high quality code.
...
Be less general and more domain-specific
"... reading the scientific literature on differential privacy from the point of view of a domain expert can be very frustrating. Most papers start with toy examples that make perfect sense on a theoretical level, but will appear alarmingly naïve to a domain expert.
...
Be more entrepreneurial
"The CPUC case highlighted that the application of differential privacy in practice can fail as a result of many non-technical issues. These important issues are often not on the radar of academic researchers.
...
So, is differential privacy practical?
"I like the answer Aaron Roth gave when I asked him: It's within striking distance."

Differential privacy and the market for data, at the AAAS meeting tomorrow

If you are at the AAAS meetings in San Jose tomorrow, and interested in how the new data environment interacts with privacy concerns, you might want to check out this session::

Differential Privacy: Analyzing Sensitive Data and Implications

Saturday, 14 February 2015: 10:00 AM-11:30 AM

Room LL21C (San Jose Convention Center)

To realize the full potential of big data for societal benefit, we must also find solutions to the privacy problems raised by the collection, analysis, and sharing of vast amounts of data about people. As discussed in the 2014 AAAS Annual Meeting session "Re-Identification Risk of De-Identified Data Sets in the Era of Big Data," the traditional approach of anonymizing data by removing identifiers does not provide adequate privacy protection, since it is often possible to re-identify individuals using the seemingly innocuous data that remains in the dataset together with auxiliary information known to an attacker and/or present in publicly available datasets. Differential privacy offers the possibility of avoiding such vulnerabilities. It provides a mathematically rigorous formalization of the requirement that a datasharing or analysis system should not leak individual-specific information, regardless of what auxiliary information is available to an attacker. A rich body of work over the past decade has shown that a wide variety of common data analysis tasks are compatible with the strong protections of differential privacy, and a number of promising efforts are underway to bring these methods to practice. In addition, differential privacy has turned out to have powerful implications for questions outside of privacy, in areas such as economics and statistics. This symposium will discuss these facets of differential privacy.

Organizer:

Salil Vadhan, Harvard University 

Co-Organizer:

Cynthia Dwork, Microsoft Research, Silicon Valley 

Speakers:

Aaron Roth, University of Pennsylvania 
An Introduction to Differential Privacy

Sofya Raskhodnikova, Pennsylvania State University 
Differentially Private Analysis of Graphs and Social Networks

Moritz Hardt, IBM Almaden Research Center 
Guilt-Free Interactive Data Analysis

See more of: Information and Data Technology

Differential privacy at Apple

The MIT Technology Review has an article about Apple's use of differential privacy, that caught my eye for several reasons: Apple’s New Privacy Technology May Pressure Competitors to Better Protect Our Data: The technology is almost a decade-old idea that’s finally coming to fruition.

"On a quarterly investor call last week, Apple CEO Tim Cook boasted that the technology would let his company “deliver the kinds of services we dream of without compromising on individual privacy.” Apple will initially use the technique to track trends in what people type and tap on their phones to improve its predictive keyboard and Spotlight search tool, without learning what exactly any individual typed or clicked.
...
“It’s exciting that things we knew how to do in principle are being embraced and widely deployed,” says Aaron Roth, an associate professor at University of Pennsylvania who has written a textbook on differential privacy. “Apple seems to be betting that by including privacy protections, and advertising that fact, they will make their product more attractive.”

In the version of differential privacy Apple is using, known as the local model, software on a person’s device adds noise to data before it is transmitted to Apple. The company never gets hold of the raw data. Its data scientists can still examine trends in how people use their phones by accounting for the noise, but are unable to tell anything about the specific activity of any one individual.

Apple is not the first technology giant to implement differential privacy. In 2014 Google released code for a system called RAPPOR that it uses to collect data from the Chrome Web browser using the local model of differential privacy. But Google has not promoted its use of the technology as aggressively as Apple, which has this year made a new effort to highlight its attention to privacy (see “Apple Rolls Out Privacy-Sensitive Artificial Intelligence”)."

An interview with computer scientist Cynthia Dwork

Quanta Magazine, a publication of the Simons foundation, has an interview with Cynthia Dwork on differential privacy and fairness among other things.

How to Force Our Machines to Play Fair
The computer scientist Cynthia Dwork takes abstract concepts like privacy and fairness and adapts them into machine code for the algorithmic age.

Here are some earlier news stories about Apple's introduction of differential privacy to the iPhone,  which I've been following for a number of reasons.

From TechCrunch: What Apple’s differential privacy means for your data and the future of machine learning

From Wired: Apple’s ‘Differential Privacy’ Is About Collecting Your Data—But Not ​Your Data

Apple's differential privacy analyzes the group, protects the individual
Posted on June 21, 2016 

Aaron Roth on differential privacy

Penn News covers a recent presentation:
An Introduction to ‘Differential Privacy,’ from Penn Professor Aaron Roth

The ability to amass, store, manipulate and analyze information from millions of people at once has opened a vast frontier of new research methods. But, whether these methods are used in the service of new business models or new scientific findings, they also raise questions for the individuals whose information comprises these “big data” sets. Can anyone really guarantee that these individuals’ information will remain private?

Aaron Roth, assistant professor in the Department of Computer and Information Science in the University of Pennsylvania’s School of Engineering and Applied Science, is trying to answer that question.

Along with colleagues from Harvard University, Microsoft Research, Pennsylvania State University and IBM Research, he presented some of his ongoing research on “differentially private” algorithms at the American Association for the Advancement of Science Annual Meeting in San Jose, Calif.

The differential privacy approach ensures that people querying big databases see only representative trends and can’t game their searches to reveal information about specific individuals in the set.

This technique has implications for companies like Google, Facebook and Amazon, businesses which depend on gleaning insights from trends in users’ behavior while maintaining their trust that their personal data is not being exploited or compromised.  But it could extend beyond the tech giants and into the world of scientific publishing by addressing the so-called “false discovery” problem, where some scientific findings seem valid but cannot be reproduced. Such false discoveries stem from “overfitting” hypotheses to outlying individuals in a dataset, rather than generalizable trends that apply the population at large.        

“There’s this idea where the more privacy you have the less useful the data is,” Roth says. “There’s some truth to that, but it’s not quite so simple. Privacy can also increase the usefulness of data by preventing this kind of overfitting”

The “different” in its name is a reference to the guarantee a differentially private algorithm makes. Its analyses should remain functionally identical when applied to two different datasets: one with and one without the data from any single individual.

“The math behind differentially private algorithms gives you a provable guarantee that, even if you know everything else about the dataset, you can’t learn anything new about my data in particular,” Roth says. “The algorithm essentially can’t tell whether my data is in the set in the first place.”      

The very nature of large data sets makes privacy a dicey proposition. Stripping those records of common identifiers, such as names or email addresses, still leaves a trove of information that could, with some effort, be used to pinpoint data from a specific individual. Such “ad hoc” methods of protecting privacy in a data set are ultimately doomed in that the set’s owner can never predict what outside information would-be attackers might use to reverse-engineer the hidden data. 

“For example, at one point, it was shown that an attack on Amazon’s recommendation algorithm was possible,” Roth says, “If I knew five or six things you bought on Amazon, I could buy those same things, and all of a sudden, we’re now the two most similar customers in Amazon's recommendation algorithm. I could then start seeing what else you were buying, as whatever you bought would then be recommended to me.”

A differentially private recommendation algorithm would defend against such an attack because it would discount idiosyncratic trends as being just that: only representing an individual’s data rather than something that is statistically valid for the entire set.

Beyond protecting customers’ private information, such an algorithm would also be better at its job. 

“You don’t actually want something that is good at predicting what people have bought historically; that may just be an example of you overfitting the data,” Roth says. “You want something that predicts what they are going buy tomorrow — things that are not in the set yet, and the same applies to scientific findings.”

Generating and collecting data is often the most expensive and time-consuming part of a scientific study, so datasets are often shared among scientists. This altruism has a hidden downside, however, as it disrupts the scientific publishing system’s standard method of ascribing significance to a particular finding.      

“The way you normally determine if a finding is significant is by computing its ‘p-value,’” Roth says. “This tells you the probability that the correlation you observe would appear just as significant if it occurred by random chance. The standard level for significance is .05, but that also means that if you test 100 hypotheses, even if they’re all wrong, you’d expect five of them would appear significant.

“There are ways to correct for the fact that you test many hypotheses, but the existing methods only work if you came up with all of your hypotheses before anyone ever looked at the data. If scientists re-use the same datasets, these guarantees disappear.”

If rather than accessing raw data, scientists share access to a dataset but only allow it to be queried through a differentially private algorithm, then they recover the ability to protect against “false discoveries” that come from over-fitting the data. Roth and his colleagues Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi and Omer Reingold have theory proving the effectiveness of this approach, which will be presented this summer at the ACM Symposium on the Theory of Computing.

“You always want to have the conclusions you draw to be based on true statistical patterns in the data, rather than the idiosyncrasies of a single individual in the set,” Roth says. “This is the same thing you want in private data analysis, and this why differential privacy can also prevent false discoveries.”

Aaron Roth

Designing privacy (differential privacy) at the Institute for Advanced Study

Differential Privacy Symposium

Differential privacy disentangles learning about a dataset as a whole from learning about an individual data contributor. Just now entering practice on a global scale, the demand for advanced differential privacy techniques and knowledge of basic skills is pressing. This symposium will provide an in-depth look at the current context for privacy-preserving statistical data analysis and an agenda for future research. This event is organized by Cynthia Dwork, of Microsoft Research, with support from the Alfred P. Sloan Foundation.

Speakers include:

Helen Nissenbaum, Cornell Tech and NYU
Aaron Roth, University of Pennsylvania
Guy Rothblum, Weizmann Institute
Kunal Talwar, Google Brain
Jonathan Ullman, Northeastern University

Differential Privacy and Economics and the Social Sciences

Differential Privacy and Economics and the Social Sciences

SIMONS FOUNDATION

Thursday, March 7, 2013 from 9:00 AM to 9:30 PM (EST)

New York, NY

A day devoted to Economics and Social Sciences and the Science of Privacy will take place onThursday, March 7th in New York City. This event is funded by the Simons Foundation and the Alfred P. Sloan Foundation.

Tutorial on Differential Privacy 9:30 - 11:30 AM
LOCATION: Simons Foundation
Speaker: Aaron Roth (Computer Science, University of Pennsylvania).

Privacy and Issues in Mechanism Design 1:15 - 3:45 PM
LOCATION: Simons Foundation
Presentation by Alvin Roth (Economics, Stanford) on privacy issues in market design, a discussion, co-organized by Mallesh Pai (Economics, University of Pennsylvania) and Eric Budish (Booth School of Business, University of Chicago), on the issues raised by Roth.
Talks by by Scott Kominers (Becker Friedman Institute, University of Chicago) and Tim Mulcahy (NORC, University of Chicago

Topic-Specific Talks 4:45 - 5:50 PM
LOCATION: Simons Foundation
Talks by Julia Lane (American Institutes for Research), Ben Handel (Economics, Berkeley), and Hal Salzman (Public Policy, Rutgers) on privacy aspects of their research.

Evening Session 8:00 - 9:30 PM
LOCATION: Simons Foundation
An evening plenary session featuring a presentation by NYU Professor Steven Koonin, Director of the nascent Center for Urban Science and Progress, "a unique public-private research center that uses New York City as its laboratory and classroom to help cities around the world become more productive, liveable, equitable and resilient."  Remarks by Micah Altman (MIT and Brookings Institution) and Felix Wu (Benjamin Cardozo School of Law)

Registration is free and open to the public, on a first-come first-served basis. By registering you will confirm your attendance.

Incentives and privacy

A new paper by three computer scientists and an economist reports on some connections between privacy and incentive compatibility.

MECHANISM DESIGN IN LARGE GAMES: INCENTIVES AND PRIVACY
by
MICHAEL KEARNS, MALLESH M. PAI, AARON ROTH and JONATHAN ULLMAN
July 18, 2012


ABSTRACT
We study the design of mechanisms satisfying two desiderata— incentive compatibility and privacy. The first, requires that each agent should be incentivized to report her private information truthfully. The second, privacy, requires the mechanism not reveal ‘much’ about any agent’s type to other agents. We propose a notion of privacy we call Joint Differential Privacy. It is a variant of Differential Privacy, a robust notion of privacy used in the Theoretical Computer Science literature. We show by construction that such mechanisms, i.e. ones which are both incentive compatible and jointly differentially private exist when the game is ‘large’, i.e. there are a large number of players, and any player’s action affects any other’s payoff by at most a small amount. Our mechanism adds carefully selected noise to no-regret algorithms similar to those studied in Foster-Vohra [FV97] and Hart-Mas-Colell [HMC00]. It therefore implements an approximate correlated equilibrium of the full information game induced by players’ reports.
*********

As I understand it, adding appropriate randomness to regret learning algorithms doesn’t harm their long term equilibration properties, and gives them good privacy properties, which together give them good incentive properties.

Privacy and Economics

It appears that "privacy and economics" may be an emerging topic in computer science, to judge from a postdoc mentioned on a cs blog I follow:

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

Markets for buying and selling privacy

Noam Nisan at AGT/E reports on New Papers on Auctions by computer scientists, including this one that I find interesting for several reasons: it is about market design for markets in which privacy is sold.

Selling Privacy at Auction by Arpita Ghosh and Aaron Roth

We initiate the study of markets for private data, through the lens of differential privacy. Although the purchase and sale of private data has already begun on a large scale, a theory of privacy as a commodity is missing. In this paper, we propose to build such a theory. Specifically, we consider a setting in which a data analyst wishes to buy information from a population from which he can estimate some statistic. The analyst wishes to obtain an accurate estimate cheaply. On the other hand, the owners of the private data experience some cost for their loss of privacy, and must be compensated for this loss. Agents are selfish, and wish to maximize their profit, so our goal is to design truthful mechanisms. Our main result is that such auctions can naturally be viewed and optimally solved as variants of multi-unit procurement auctions. Based on this result, we derive auctions for two natural settings which are optimal up to small constant factors:
1. In the setting in which the data analyst has a fixed accuracy goal, we show that an application of the classic Vickrey auction achieves the analyst’s accuracy goal while minimizing his total payment.
2. In the setting in which the data analyst has a fixed budget, we give a mechanism which maximizes the accuracy of the resulting estimate while guaranteeing that the resulting sum payments do not exceed the analysts budget.
In both cases, our comparison class is the set of envy-free mechanisms, which correspond to the natural class of fixed-price mechanisms in our setting.
In both of these results, we ignore the privacy cost due to possible correlations between an individuals private data and his valuation for privacy itself. We then show that generically, no individually rational mechanism can compensate individuals for the privacy loss incurred due to their reported valuations for privacy.

National Medals of Science and Technology (including Cynthia Dwork for differential privacy)

 In one of the final acts of his administration, President Biden celebrates 25 distinguished scientists and engineers. (I'm particularly glad to see Cynthia Dwork recognized for her work on differential privacy.)

 Forbes has the story:

Biden Names 25 Recipients Of National Medals Of Science, Technology, by Michael T. Nietzel

In a statement from the White House, Biden said, “those who earn these awards embody the promise of America by pushing the boundaries of what is possible. These trailblazers have harnessed the power of science and technology to tackle challenging problems and deliver innovative solutions for Americans and for communities around the world.”

...

"The 14 recipients of the National Medal of Science are:

    Richard B. Alley, the Evan Pugh University Professor of Geosciences at Pennsylvania State University. Alley researches the great ice sheets to help predict future changes in climate and sea levels.
    Larry Martin Bartels, University Distinguished Professor of Political Science and Law and the May Werthan Shayne Chair of Public Policy and Social Science at Vanderbilt University. His scholarship focuses on public opinion, public policy, election science, and political economy.
    Bonnie L. Bassler, Squibb Professor in Molecular Biology and chair of the Department of Molecular Biology at Princeton University, for her research on the molecular mechanisms that bacteria use for intercellular communication.
    Angela Marie Belcher, the James Mason Crafts Professor of Biological Engineering and Materials Science and Engineering at MIT and a member of the Koch Institute for Integrative Cancer Research. She was honored for designing materials for applications in solar cells, batteries, and medical imaging.
    Helen M. Blau, Donald E. and Delia B. Baxter Foundation Professor and the Director of the Baxter Laboratory for Stem Cell Biology at Stanford University for her research on muscle diseases, regeneration and aging, including the use of stem cells for tissue repair.
    Emery Neal Brown, the Edward Hood Taplin Professor of Medical Engineering and Computational Neuroscience at MIT, was recognized for his work revealing how anesthesia affects the brain.
    John O. Dabiri, Centennial Chair Professor at the California Institute of Technology, in the Graduate Aerospace Laboratories and Mechanical Engineering. His research focuses on fluid mechanics and flow physics, with an emphasis on topics relevant to biology, energy, and the environment.
    Ingrid Daubechies, the James B. Duke Distinguished Professor Emerita of Mathematics at Duke University, was honored for her pioneering work on signal processing.
    Cynthia Dwork, Gordon McKay Professor of Computer Science at Harvard University, was recognized for research that has transformed the way data privacy is handled in the age of big data and AI.
    R. Lawrence Edwards, Regents and Distinguished McKnight University Professor, Department of Earth and Environmental Sciences at the University of Minnesota. Edwards is known for his refinement of radiocarbon dating techniques to study climate history and ocean chemistry.
    Wendy L. Freedman, the John and Marion Sullivan University Professor in Astronomy and Astrophysics at the University of Chicago, for her observational cosmology research, including pioneering uses of the Hubble Space Telescope.
    Keivan G. Stassun, Stevenson Professor of Physics & Astronomy at Vanderbilt University for his work in astrophysics, including the study of star formation and exoplanets.
    G. David Tilman is Regents Professor and the McKnight Presidential Chair in Ecology, Evolution, and Behavior at the University of Minnesota. He studies biological diversity, the structure and benefits of ecosystems and ways to assure sustainability despite global increases in human consumption and population.
    Teresa Kaye Woodruff is the MSU Research Foundation Professor of Obstetrics, Gynecology and Reproductive Biology and Biomedical Engineering at Michigan State University. She is an internationally recognized expert in ovarian biology and reproductive science.

The nine individual recipients of the National Medal of Technology and Innovation are:

    Martin Cooper for his work in advancing in personal wireless communications for over 50 years. Cited in the Guinness Book of World Records for making the first cellular telephone call, Cooper, known as the “father of the cell phone,” spent much of his career at Motorola.
    Jennifer A. Doudna, a Nobel Laureate in Chemistry and the Li Ka Shing Chancellor’s Chair in Biomedical and Health Sciences at the University of California, Berkeley. She is a pioneer of CRISPR gene editing.
    Eric R. Fossum is the John H. Krehbiel Sr. Professor for Emerging Technologies at Dartmouth College. He invented the CMOS active pixel image sensor used in cell-phone cameras, webcams, and medical imaging.
    Paula T. Hammond, an MIT Institute Professor, vice provost for faculty, and member of the Koch Institute, was honored for developing methods for assembling thin films that can be used for drug delivery, wound healing, and other applications.
    Kristina M. Johnson, former president of The Ohio State University was recognized for research in photonics, nanotechnology, and optoelectronics. Her discoveries have contributed to sustainable energy solutions and advanced manufacturing technologies.
    Victor B. Lawrence spent much of his career at Bell Laboratories, working on new developments in multiple forms of communications. He is a Research Professor and Director of the Center for Intelligent Networked Systems at Stevens Institute of Technology.
    David R. Walt is a faculty member of the Wyss Institute at Harvard University and is the Hansjörg Wyss Professor of Bioinspired Engineering at Harvard Medical School and Professor of Pathology at Harvard Medical School and Brigham and Women’s Hospital. He was honored for co-inventing the DNA microarray, enabling large-scale genetic analysis and better personalized medicine.
    Paul G. Yock is an emeritus faculty member at Stanford University. A physician, Yock is known for inventing, developing and testing new cardiovascular intervention devices, including the stent.
    Feng Zhang, the James and Patricia Poitras Professor of Neuroscience at MIT and a professor of brain and cognitive sciences and biological engineering, was recognized for his work developing molecular tools, including the CRISPR genome-editing system."

#########

Here's my post from ten years ago:

Saturday, February 7, 2015 Differential Privacy: an appreciation of Cynthia Dwork

 

Game theory and differential privacy

Here's a lecture on game theory and differential privacy, by Aaron Roth, an up and coming computer scientist whose work I've followed for a long time

DIMACS Tutorials - Oct 24, 2012: Aaron Roth - Game Theory and Differential Privacy

Equilibrium, mediation, and differential privacy

Here's a paper that caught my eye...

Robust Mediators in Large Games∗
Michael Kearns, Mallesh M. Pai, Ryan Rogers,  Aaron Roth, and Jonathan Ullman
December 14, 2015
Abstract
A mediator is a mechanism that can only suggest actions to players, as a function of all agents’ reported types, in a given game of incomplete information. We study what is achievable by two kinds of mediators, “strong” and “weak.” Players can choose to opt-out of using a strong mediator but cannot misrepresent their type if they opt-in. Such a mediator is “strong” because we can view it as having the ability to verify player types. Weak mediators lack this ability— players are free to misrepresent their type to a weak mediator. We show a striking result—in a prior-free setting, assuming only that the game is large and players have private types, strong mediators can implement approximate equilibria of the complete-information game. If the game is a congestion game, then the same result holds using only weak mediators. Our result follows from a novel application of  differential privacy, in particular, a variant we propose called joint differential privacy.

Ethics of machine learning--an interview with Michael Kearns and Aaron Roth

 Amazon Scholars Michael Kearns and Aaron Roth discuss the ethics of machine learning--Two of the world’s leading experts on algorithmic bias look back at the events of the past year and reflect on what we’ve learned, what we’re still grappling with, and how far we have to go.  By Stephen Zorio

"In November of 2019, University of Pennsylvania computer science professors Michael Kearns and Aaron Roth released The Ethical Algorithm: The Science of Socially Aware Algorithm Design. Kearns is the founding director of the Warren Center for Network and Data Sciences, and the faculty founder and former director of Penn Engineering’s Networked and Social Systems Engineering program. Roth is the co-director of Penn’s program in Networked and Social Systems Engineering and co-authored The Algorithmic Foundations of Differential Privacy with Cynthia Dwork. Kearns and Roth are leading researchers in machine learning, focusing on both the design and real-world application of algorithms.

Their book’s central thesis, which involves “the science of designing algorithms that embed social norms such as fairness and privacy into their code,” was already pertinent when the book was released. Fast forward one year, and the book’s themes have taken on even greater significance.

Amazon Science sat down with Kearns and Roth, both of whom recently became Amazon Scholars, to find out whether the events of the past year have influenced their outlook. We talked about what it means to define and pursue fairness, how differential privacy is being applied in the real world and what it can achieve, the challenges faced by regulators, what advice the two University of Pennsylvania professors would give to students studying artificial intelligence and machine learning, and much more."

Fairness in algorithms: Hans Sigrist Prize to Aaron Roth

 The University of Bern's Hans Sigrist Prize has been awarded to Penn computer scientist Aaron Roth, and will be celebrated today.

Here are today's symposium details and schedule:

The Hans Sigrist Symposium

Data Science: The Power of the Human Mind for the Sake of Humankind

Here's an interview:

Aaron Roth: Pioneer of fair algorithms  In December 2023, the most highly endowed prize of the University of Bern will go to the US computer scientist Aaron Roth. His research aims to incorporate social norms into algorithms and to better protect privacy.  by Ivo Schmucki 

"There are researchers who sit down and take on long-standing problems and just solve them, but I am not smart enough to do that," says Aaron Roth. "So, I have to be the other kind of researcher. I try to define a new problem that no one has worked on yet but that might be interesting."

"Aaron Roth's own modesty may stand in the way of understanding the depth of his contributions. In fact, when he authored his doctoral thesis on differential privacy about 15 years ago and then wrote on the fairness of algorithms a few years later, terms like “Artificial Intelligence” and “Machine Learning” were far from being as firmly anchored in our everyday lives as they are today. Aaron Roth was thus a pioneer, laying the foundation for a new branch of research.

"I am interested in real problems. Issues like data protection are becoming increasingly important as more and more data is generated and collected about all of us," says Aaron Roth about his research during the Hans Sigrist Foundation’s traditional interview with the prize winner. He focuses on algorithmic fairness, differential privacy, and their applications in machine learning and data analysis.

...

"It is important that more attention is paid to these topics," says Mathematics Professor Christiane Tretter, chair of this year's Hans Sigrist Prize Committee. Tretter says that many people perceive fairness and algorithms as two completely different poles, situated in different disciplines and incompatible with each other. "It is fascinating that Aaron Roth’s work shows that this is not a contradiction."

...

"The first step to improving the analysis of large data sets is to be aware of the problem: "We need to realize that data analysis can be problematic. Once we agree on this, we can consider how we can solve the problems," says Aaron Roth."

Recent NBER papers bearing on market design

Here are three:

The Effects of Mandatory Transparency in Financial Market Design: Evidence from the Corporate Bond Market

Paul Asquith, Thom Covert, Parag Pathak

NBER Working Paper No. 19417
Issued in September 2013
NBER Program(s):   AP   CF 

Many financial markets have recently become subject to new regulations requiring transparency. This paper studies how mandatory transparency affects trading in the corporate bond market. In July 2002, TRACE began requiring the public dissemination of post-trade price and volume information for corporate bonds. Dissemination took place in Phases, with actively traded, investment grade bonds becoming transparent before thinly traded, high-yield bonds. Using new data and a differences-in-differences research design, we find that transparency causes a significant decrease in price dispersion for all bonds and a significant decrease in trading activity for some categories of bonds. The largest decrease in daily price standard deviation, 24.7%, and the largest decrease in trading activity, 41.3%, occurs for bonds in the final Phase, which consisted primarily of high-yield bonds. These results indicate that mandated transparency may help some investors and dealers through a decline in price dispersion, while harming others through a reduction in trading activity.

The Impact of the Internet on Advertising Markets for News Media

Susan Athey, Emilio Calvano, Joshua Gans

NBER Working Paper No. 19419
Issued in September 2013
NBER Program(s):   IO   PR 

In this paper, we explore the hypothesis that an important force behind the collapse in advertising revenue experienced by newspapers over the past decade is the greater consumer switching facilitated by online consumption of news. We introduce a model of the market for advertising on news media outlets whereby news outlets are modeled as competing two-sided platforms bringing together heterogeneous, partially multi-homing consumers with advertisers with heterogeneous valuations for reaching consumers. A key feature of our model is that the multi-homing behavior of the advertisers is determined endogenously. The presence of switching consumers means that, in the absence of perfect technologies for tracking the ads seen by consumers, advertisers purchase wasted impressions: they reach the same consumer too many times. This has subtle effects on the equilibrium outcomes in the advertising market. One consequence is that multi-homing on the part of advertisers is heterogeneous: high-value advertisers multi-home, while low- value advertisers single-home. We characterize the impact of greater consumer switching on outlet profits as well as the impact of technologies that track consumers both within and across outlets on those profits. Somewhat surprisingly, superior tracking technologies may not always increase outlet profits, even when they increase efficiency. In extensions to the baseline model, we show that when outlets that show few or ineffective ads (e.g. blogs) attract readers from traditional outlets, the losses are at least partially offset by an increase in ad prices. Introducing a paywall does not just diminish readership, but it furthermore reduce advertising prices (and leads to increases in advertising prices on competing outlets).

Privacy and Data-Based Research

Ori Heffetz, Katrina Ligett

NBER Working Paper No. 19433
Issued in September 2013
NBER Program(s):   AG   LS   PE 

What can we, as users of microdata, formally guarantee to the individuals (or firms) in our dataset, regarding their privacy? We retell a few stories, well-known in data-privacy circles, of failed anonymization attempts in publicly released datasets. We then provide a mostly informal introduction to several ideas from the literature on differential privacy, an active literature in computer science that studies formal approaches to preserving the privacy of individuals in statistical databases. We apply some of its insights to situations routinely faced by applied economists, emphasizing big-data contexts.

Differential Privacy: an appreciation of Cynthia Dwork

On Thursday I heard Cynthia Dwork talk about differential privacy in San Diego, and here is an appreciation of her at the CS blog called Godel's lost letter and P=NP by Dick Lipton and Ken  Regan:

Cynthia Dwork and a Brilliant Idea

Here's their introductory paragraph:
"This concept is brilliant. It is, in our opinions, one of the greatest definitions of this century. Okay the century is just fifteen years old, but it is a terrific notion. She deserves credit for seeing that this simple one would have such far reaching consequences and for following through on it. Her paper—still in the 12-page ICALP 2006 proceedings format—begins with three prose pages of motivation that are a breath of fresh air. The definition originated from work with Frank McSherry in a prior paper also with Kobbi Nissim and Adam Smith, and has grown to fill a book joint with Aaron Roth."

Match Up 2017: April 20-21 at Microsoft Research New England

MATCH-UP 2017, the fourth workshop in the series of interdisciplinary and international workshops on matching under preferences, will take place April 20-21, 2017.

Venue:Microsoft Research New England Cambridge, MA 02142

	DAY 1
8:00 A.M.	Breakfast
8.45 A.M.	Invited Talk 1 —Estelle Cantillon, Université libre de Bruxelles The efficiency – stability tradeoff in school choice: Lessons for market design Abstract: A well-known result for the school choice problem is that ex-post efficiency and stability may not be compatible. In the field, that trade-off is sometimes small, sometimes big.  This talk will summarize existing and new results on the drivers of this trade-off and derive the implications for the design of priorities and tie-breaking rules.
9.30 A.M.	Session 1
10.30 A.M.	Break
10.50 A.M.	Session 2
12.30 P.M.	Lunch
1:00 P.M.	Outlook Talk 1 – Al Roth, Stanford Frontiers of Kidney Exchange Abstract: Kidney exchange is different from many market design efforts I’ve been involved in, because it affects the everyday conduct of transplant centers, so we’re constantly adapting to their big strategy sets…(in contrast to e.g. annual labor markets or school choice which don’t affect the daily conduct of residency programs and schools …)The early design challenges in kidney exchange mostly involved dealing with congestion (and the solutions involved long chains, standard acquisition charges, and attempts to better elicit surgeons’ preferences over kidneys).The current challenges to kidney exchange involve creating more thickness in the markets, and I’ll touch on several new initiatives: 1. Frequent flier programs to encourage transplant centers to enroll more of their easy to match pairs; 2. Global kidney exchange; 3. Information deserts: populations of Americans who don’t get transplants; 4. Deceased donor initiated chains ; a. Increasing deceased donation: military share, priority in Israel
2:00 P.M.	Session 3
3.40 P.M.	Break
4:00 P.M.	Session 4
5:00 P.M.	Invited Talk 2 – Aaron Roth, UPENN Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy) Abstract: In this talk, we will walk through a case study of how techniques developed to design “stable” algorithms can be brought to bear to design asymptotically dominant strategy truthful mechanisms in large markets, without the need to make any assumptions about the structure of individual preferences. Specifically, we will consider the many-to-one matching problem, and see a mechanism for computing school optimal stable matchings, that makes truthful reporting an approximately dominant strategy for the student side of the market. The approximation parameter becomes perfect at a polynomial rate as the number of students grows large, and the analysis holds even for worst-case preferences for both students and schools. Joint work with: Sampath Kannan, Jamie Morgenstern, and Zhiwei Steven Wu.
5.45 P.M.	Break
6:00 P.M.	Poster Lightning Talks
6.30 P.M.	Reception and Poster Session
8:00 P.M.	END
	DAY 2
8:00 A.M.	Breakfast
8.45 A.M.	Invited Talk 3 — Michael Ostrovsky, Stanford Matching under preferences: beyond the two-sided case Abstract: I will present an overview of several recent papers showing that most of the key results of matching theory generalize naturally to a much richer setting: trading networks. These networks do not need to be two-sided, and agents do not have to be grouped into classes (“firms”, “workers”, and so on). What is essential for the generalization is that the bilateral contracts representing relationships in the network have a direction (e.g., one agent is the seller and the other is the buyer), and that agents’ preferences satisfy a suitably adapted substitutability notion. For this setting, for the cases of discrete and continuous sets of possible contracts, I will discuss the existence of stable outcomes, the lattice structure of the sets of stable outcomes, the relationship between various solution concepts (stability, core, competitive equilibrium, etc.), and other results familiar from the literature on two-sided markets.
9.30 A.M.	Session 5
10.30 A.M.	Break
10.50 A.M.	Session 6
12.30 P.M.	Lunch
1:00 P.M.	Lunch w/Outlook Talk 2 — David Manlove, University of Glasgow Selected Algorithmic Open Problems in Matching Under Preferences Abstract: The research community working on matching problems involving preferences has grown in recent years, but even so, plenty of interesting open problems still exist, many with large-scale practical applications.  In this talk I will outline some of these open problems that are of an algorithmic flavour, thus giving an outlook on some of the research challenges in matching under preferences that the computer science community might seek to tackle over the next decade.
2:00 P.M.	Session 7
	Making it Safe to Use Centralized Markets: Epsilon - Dominant Individual Rationality and Applications to Market Design Speakers: Ben Roth and Ran Shorrer Abstract: A critical, yet under-appreciated feature of market design is that centralized markets operate within a broader context; often market designers cannot force participants to join a centralized market. Well-designed centralized markets must induce participants to join voluntarily, in spite of pre-existing decentralized institutions they may already be using. We take the view that centralizing a market is akin to designing a mechanism to which people may voluntarily sign away their decision rights. We study the ways in which market designers can provide robust incentives that guarantee agents will participate in a centralized market. Our first result is negative and derives from adverse selection concerns. Near any game with at least one pure strategy equilibrium, we prove there is another game in which no mechanism can eliminate the equilibrium of the original game. In light of this result we offer a new desideratum for mechanism and market design, which we term epsilon-dominant individual rationality. After noting its robustness, we establish two positive results about centralizing large markets. The first offers a novel justification for stable matching mechanisms and an insight to guide their design to achieve epsilon-dominant individual rationality. Our second result demonstrates that in large games, any mechanism with the property that every player wants to use it conditional on sufficiently many others using it as well can be modified to satisfy epsilon-dominant individual rationality while preserving its behavior conditional on sufficient participation. The modification relies on a class of mechanisms we refer to as random threshold mechanisms and resembles insights from the differential privacy literature.
3.40 P.M.	Break
4:00 P.M.	Session 8
5.20 P.M.	Break
5.30 P.M.	Invited Talk 4 — Marek Pycia, UCLA Invariance and Matching Market Outcomes Abstract: The empirical studies of school choice provide evidence that standard measures of admission outcomes are the same for many Pareto efficient mechanisms that determine the market allocation based on ordinal rankings of individual outcomes. The paper shows that two factors drive this intriguing puzzle: market size and the invariance properties of the measures for which the regularity has been documented. In addition, the talk will explore the consequences of these findings: the usefulness of non-invariant outcome measures and of mechanisms that elicit preference intensities.
6.15 P.M.	Closing Remarks
6.30 P.M.	END