Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy and Mechanism Design <s> We study the role that privacy-preserving algorithms, which prevent the leakage of specific information about participants, can play in the design of mechanisms for strategic agents, which must encourage players to honestly report information. Specifically, we show that the recent notion of differential privacv, in addition to its own intrinsic virtue, can ensure that participants have limited effect on the outcome of the mechanism, and as a consequence have limited incentive to lie. More precisely, mechanisms with differential privacy are approximate dominant strategy under arbitrary player utility functions, are automatically resilient to coalitions, and easily allow repeatability. We study several special cases of the unlimited supply auction problem, providing new results for digital goods auctions, attribute auctions, and auctions with arbitrary structural constraints on the prices. As an important prelude to developing a privacy-preserving auction mechanism, we introduce and study a generalization of previous privacy work that accommodates the high sensitivity of the auction setting, where a single participant may dramatically alter the optimal fixed price, and a slight change in the offered price may take the revenue from optimal to zero. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy and Mechanism Design <s> We study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a generic mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers. Underlying our mechanism is a lottery between two auxiliary mechanisms --- with high probability we actuate a mechanism that reduces players influence on the choice of the social alternative, while choosing the optimal outcome with high probability. This is where differential privacy is employed. With the complementary probability we actuate a mechanism that may be typically far from optimal but is incentive compatible. The joint mechanism inherits the desired properties from both. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy and Mechanism Design <s> We study a very general class of games -- multi-dimensional aggregative games -- which in particular generalize both anonymous games and weighted congestion games. For any such game that is also large, we solve the equilibrium selection problem in a strong sense. In particular, we give an efficient weak mediator: a mechanism which has only the power to listen to reported types and provide non-binding suggested actions, such that a it is an asymptotic Nash equilibrium for every player to truthfully report their type to the mediator, and then follow its suggested action; and b that when players do so, they end up coordinating on a particular asymptotic pure strategy Nash equilibrium of the induced complete information game. In fact, truthful reporting is an ex-post Nash equilibrium of the mediated game, so our solution applies even in settings of incomplete information, and even when player types are arbitrary or worst-case i.e. not drawn from a common prior. We achieve this by giving an efficient differentially private algorithm for computing a Nash equilibrium in such games. The rates of convergence to equilibrium in all of our results are inverse polynomial in the number of players n. We also apply our main results to a multi-dimensional market game. ::: ::: Our results can be viewed as giving, for a rich class of games, a more robust version of the Revelation Principle, in that we work with weaker informational assumptions no common prior, yet provide a stronger solution concept ex-post Nash versus Bayes Nash equilibrium. In comparison to previous work, our main conceptual contribution is showing that weak mediators are a game theoretic object that exist in a wide variety of games --- previously, they were only known to exist in traffic routing games. We also give the first weak mediator that can implement an equilibrium optimizing a linear objective function, rather than implementing a possibly worst-case Nash equilibrium. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy and Mechanism Design <s> Mechanism design is the study of algorithm design where the inputs to the algorithm are controlled by strategic agents, who must be incentivized to faithfully report them. Unlike typical programmatic properties, it is not sufficient for algorithms to merely satisfy the property, incentive properties are only useful if the strategic agents also believe this fact. Verification is an attractive way to convince agents that the incentive properties actually hold, but mechanism design poses several unique challenges: interesting properties can be sophisticated relational properties of probabilistic computations involving expected values, and mechanisms may rely on other probabilistic properties, like differential privacy, to achieve their goals. We introduce a relational refinement type system, called HOARe2, for verifying mechanism design and differential privacy. We show that HOARe2 is sound w.r.t. a denotational semantics, and correctly models (epsilon,delta)-differential privacy; moreover, we show that it subsumes DFuzz, an existing linear dependent type system for differential privacy. Finally, we develop an SMT-based implementation of HOARe2 and use it to verify challenging examples of mechanism design, including auctions and aggregative games, and new proposed examples from differential privacy. <s> BIB004
Mechanism design is a kind of game in which inputs are delivered by multiple agents. However, agents may manipulate their inputs, so the mechanisms design should ask agents to provide true inputs BIB004 . McSherry BIB001 first proposed a design for auction mechanisms using differentially private mechanisms as the building blocks. This private mechanism is only approximately truthful. Later, Nissim et al. BIB002 converted these private mechanisms into fully truthful mechanisms. Cummings et al. BIB003 studied the multi-dimensional aggregative games and solved the equilibrium selection problem. Barthe et al. BIB004 introduced a relational refinement system for verifying a mechanism's design in terms of differential privacy. This series of research focuses on mechanism design based on differential privacy. They are good representatives for the interdisciplinary area of differential privacy and game theory.