×

zbMATH — the first resource for mathematics

Privacy and truthful equilibrium selection for aggregative games. (English) Zbl 1404.91048
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 286-299 (2015).
Summary: 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.
For the entire collection see [Zbl 1326.68026].

MSC:
91A43 Games involving graphs
91A06 \(n\)-person games, \(n>2\)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121–164 (2012) · Zbl 1283.68414 · doi:10.4086/toc.2012.v008a006
[2] Ashlagi, I., Monderer, D., Tennenholtz, M.: Mediators in position auctions. Games Econ. Behav. 67(1), 2–21 (2009) · Zbl 1168.91366 · doi:10.1016/j.geb.2008.11.005
[3] Azevedo, E.M., Budish, E.: Strategyproofness in the large as a desideratum for market design. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, p. 55 (2012) · doi:10.1145/2229012.2229021
[4] Babichenko, Y.: Best-reply dynamic in large aggregative games. SSRN (2013). abstract 2210080 · Zbl 1282.91038
[5] Barman, S., Ligett, K.: Finding any nontrivial coarse correlated equilibrium is hard. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 2015, pp. 815–816 (2015) · doi:10.1145/2764468.2764497
[6] Blum, A., Morgenstern, J., Sharma, A., Smith, A.: Privacy-preserving public information for sequential games. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, pp. 173–180 (2015) · Zbl 1364.91027 · doi:10.1145/2688073.2688100
[7] Chen, X., Durfee, D., Orfanou, A.: On the complexity of Nash equilibria in anonymous games. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 381–390 (2015) · Zbl 1322.91005 · doi:10.1145/2746539.2746571
[8] Chen, Y., Chong, S., Kash, I.A., Moran, T., Vadhan, S.: Truthful mechanisms for agents that value privacy. In: Proceedings of the 14th ACM Conference on Electronic Commerce, EC 2013, pp. 215–232 (2013) · doi:10.1145/2492002.2482549
[9] Cummings, R., Kearns, M., Roth, A., Wu, Z.S.: Privacy and truthful equilibrium selection for aggregative games, CoRR, abs/1407.7740 (2014) · Zbl 1404.91048
[10] Daskalakis, C., Papadimitriou, C.H.: Discretized multinomial distributions and Nash equilibria in anonymous games. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 25–34 (2008) · doi:10.1109/FOCS.2008.84
[11] Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theoret. Comput. Sci. 9(3–4), 211–407 (2014)
[12] Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 265–284. Springer, Heidelberg (2006) · Zbl 1112.94027 · doi:10.1007/11681878_14
[13] Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 381–390 (2009) · Zbl 1304.94050 · doi:10.1145/1536414.1536467
[14] Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 51–60 (2010) · doi:10.1109/FOCS.2010.12
[15] Ghosh, A., Ligett, K.: Privacy and coordination: computing on databases with endogenous participation. In: Proceedings of the 14th ACM Conference on Electronic Commerce, EC 2013, pp. 543–560 (2013) · doi:10.1145/2492002.2482585
[16] Hardt, M., Rothblum, G.N.: A multiplicative weights mechanism for privacy-preserving data analysis. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 61–70 (2010) · doi:10.1109/FOCS.2010.85
[17] Hsu, J., Roth, A., Roughgarden, T., Ullman, J.: Privately solving linear programs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 612–624. Springer, Heidelberg (2014) · Zbl 1410.68109 · doi:10.1007/978-3-662-43948-7_51
[18] Kannan, S., Morgenstern, J., Roth, A., Wu, Z.S.: Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1890–1903 (2015) · Zbl 1372.91073 · doi:10.1137/1.9781611973730.126
[19] Kearns, M., Mansour, Y.: Efficient Nash computation in large population games with bounded influence. In: Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, UAI 2002, pp. 259–266 (2002)
[20] Kearns, M., Pai, M., Roth, A., Ullman, J.: Mechanism design in large games: incentives and privacy. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, pp. 403–410 (2014) · Zbl 1364.91010 · doi:10.1145/2554797.2554834
[21] McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, pp. 94–103 (2007) · Zbl 1232.68047 · doi:10.1109/FOCS.2007.66
[22] Monderer, D., Tennenholtz, M.: k-implementation. In: Proceedings of the 4th ACM Conference on Electronic Commerce, EC 2003, pp. 19–28 (2003) · Zbl 1059.91009 · doi:10.1145/779928.779931
[23] Monderer, D., Tennenholtz, M.: Strong mediated equilibrium. Artif. Intell. 173(1), 180–195 (2009) · Zbl 1180.68272 · doi:10.1016/j.artint.2008.10.005
[24] Roger, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981) · Zbl 0496.90099 · doi:10.1287/moor.6.1.58
[25] Nissim, K., Orlandi, C., Smorodinsky, R.: Privacy-aware mechanism design. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, pp. 774–789 (2012) · doi:10.1145/2229012.2229073
[26] Nissim, K., Smorodinsky, R., Tennenholtz, M.: Approximately optimal mechanism design via differential privacy. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 203–213 (2012) · Zbl 1348.91124 · doi:10.1145/2090236.2090254
[27] Pai, M.M., Roth, A.: Privacy and mechanism design. SIGecom Exch. 12(1), 8–29 (2013) · doi:10.1145/2509013.2509016
[28] Rogers, R.M., Roth, A.: Asymptotically truthful equilibrium selection in large congestion games. In: Proceedings of the 15th ACM Conference on Economics and Computation, EC 2014, pp. 771–782 (2014) · doi:10.1145/2600057.2602856
[29] Xiao, D.: Is privacy compatible with truthfulness? In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 67–86 (2013) · Zbl 1361.68076 · doi:10.1145/2422436.2422448
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.