skip to main content
10.1145/2764468.2764509acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Inducing Approximately Optimal Flow Using Truthful Mediators

Published: 15 June 2015 Publication History

Abstract

We revisit a classic coordination problem from the perspective of mechanism design: how can we coordinate a social welfare maximizing flow in a network congestion game with selfish players? The classical approach, which computes tolls as a function of known demands, fails when the demands are unknown to the mechanism designer, and naively eliciting them does not necessarily yield a truthful mechanism. Instead, we introduce a weak mediator that can provide suggested routes to players and set tolls as a function of reported demands. However, players can choose to ignore or misreport their type to this mediator. Using techniques from differential privacy, we show how to design a weak mediator such that it is an asymptotic ex-post Nash equilibrium for all players to truthfully report their types to the mediator and faithfully follow its suggestion, and that when they do, they end up playing a nearly optimal flow. Notably, our solution works in settings of incomplete information even in the absence of a prior distribution on player types. Along the way, we develop new techniques for privately solving convex programs which may be of independent interest.

References

[1]
Ashlagi, I., Monderer, D., and Tennenholtz, M. 2009. Mediators in position auctions. Games and Economic Behavior 67, 1, 2--21.
[2]
Beckmann, M. J., McGuire, C., and Winsten, C. 1956. Studies in the economics of transportation. Yale University Press.
[3]
Bhaskar, U., Ligett, K., Schulman, L. J., and Swamy, C. 2014. Achieving target equilibria in network routing games without knowing the latency functions. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on. IEEE, 31--40.
[4]
Caragiannis, I., Kaklamanis, C., and Kanellopoulos, P. 2006. Taxes for linear atomic congestion games. In Algorithms--ESA 2006. Springer, 184--195.
[5]
Cole, R., Dodis, Y., and Roughgarden, T. 2003. How much can taxes help selfish routing? In Proceedings of the 4th ACM conference on Electronic commerce. ACM, 98--107.
[6]
Cummings, R., Kearns, M., Roth, A., and Wu, Z. S. 2014. Privacy and truthful equilibrium selection for aggregative games. CoRR abs/1407.7740.
[7]
Dwork, C., McSherry, F., Nissim, K., and Smith, A. 2006. Calibrating noise to sensitivity in private data analysis. In TCC '06. 265--284.
[8]
Dwork, C., Rothblum, G. N., and Vadhan, S. 2010. Boosting and differential privacy. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. 51--60.
[9]
Fleischer, L. 2005. Linear tolls suffice: New bounds and algorithms for tolls in single source networks. Theoretical Computer Science 348, 2, 217--225.
[10]
Fleischer, L., Jain, K., and Mahdian, M. 2004. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on. IEEE, 277--285.
[11]
Fotakis, D., Karakostas, G., and Kolliopoulos, S. G. 2010. On the existence of optimal taxes for network congestion games with heterogeneous users. In Algorithmic Game Theory. Springer, 162--173.
[12]
Freund, Y. and Schapire, R. 1996. Game theory, on-line prediction and boosting. 325--332.
[13]
Hsu, J., Huang, Z., Roth, A., Roughgarden, T., and Wu, Z. S. 2014a. Private matchings and allocations. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 21--30.
[14]
Hsu, J., Huang, Z., Roth, A., and Wu, Z. S. 2014b. Jointly private convex programming. arXiv preprint arXiv:1411.0998.
[15]
Kannan, S., Morgenstern, J., Roth, A., and Wu, Z. S. 2015. 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, San Diego, CA, USA, January 4--6, 2015. 1890--1903.
[16]
Karakostas, G. and Kolliopoulos, S. G. 2004. Edge pricing of multicommodity networks for heterogeneous selfish users. In FOCS. Vol. 4. 268--276.
[17]
Kearns, M., Pai, M., Roth, A., and Ullman, J. 2014. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th ACM SIGact Innovations in Theoretical Computer Science (ITCS).
[18]
McSherry, F. and Talwar, K. 2007. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20--23, 2007, Providence, RI, USA, Proceedings. 94--103.
[19]
Monderer, D. and Shapley, L. 1996. Potential games. Games and Economic Behavior 14, 1, 124--143.
[20]
Monderer, D. and Tennenholtz, M. 2003. k-implementation. In Proceedings of the 4th ACM conference on Electronic commerce. ACM, 19--28.
[21]
Monderer, D. and Tennenholtz, M. 2009. Strong mediated equilibrium. Artificial Intelligence 173, 1, 180--195.
[22]
Nissim, K., Smorodinsky, R., and Tennenholtz, M. 2012. Approximately optimal mechanism design via differential privacy. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ACM, 203--213.
[23]
Peleg, B. and Procaccia, A. D. 2010. Implementation by mediated equilibrium. International Journal of Game Theory 39, 1--2, 191--207.
[24]
Raghavan, P. and Thompson, C. D. 1987. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 4, 365--374.
[25]
Rogers, R. M. and Roth, A. 2014. Asymptotically truthful equilibrium selection in large congestion games. In ACM Conference on Economics and Computation, EC '14, Stanford, CA, USA, June 8--12, 2014. 771--782.
[26]
Rozenfeld, O. and Tennenholtz, M. 2007. Routing mediators. In IJCAI. 1488--1493.
[27]
Slater, M. 1959. Lagrange multipliers revisited. Cowles Foundation Discussion Papers 80, Cowles Foundation for Research in Economics, Yale University.
[28]
Swamy, C. 2007. The effectiveness of stackelberg strategies and tolls for network congestion games. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1133--1142.
[29]
Zinkevich, M. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21--24, 2003, Washington, DC, USA. 928--936.

Cited By

View all
  • (2021)More than PrivacyACM Computing Surveys10.1145/346077154:7(1-37)Online publication date: 18-Jul-2021
  • (2020)Differentially Private Call Auctions and Market ImpactProceedings of the 21st ACM Conference on Economics and Computation10.1145/3391403.3399500(541-583)Online publication date: 13-Jul-2020
  • (2020)Mechanisms for Cooperative Freight Routing: Incentivizing Individual ParticipationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2019.291554921:5(2155-2166)Online publication date: May-2020
  • Show More Cited By

Index Terms

  1. Inducing Approximately Optimal Flow Using Truthful Mediators

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EC '15: Proceedings of the Sixteenth ACM Conference on Economics and Computation
    June 2015
    852 pages
    ISBN:9781450334105
    DOI:10.1145/2764468
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 June 2015

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. algorithms
    2. differential privacy
    3. mechanism design

    Qualifiers

    • Research-article

    Funding Sources

    • NSF

    Conference

    EC '15
    Sponsor:
    EC '15: ACM Conference on Economics and Computation
    June 15 - 19, 2015
    Oregon, Portland, USA

    Acceptance Rates

    EC '15 Paper Acceptance Rate 72 of 220 submissions, 33%;
    Overall Acceptance Rate 664 of 2,389 submissions, 28%

    Upcoming Conference

    EC '25
    The 25th ACM Conference on Economics and Computation
    July 7 - 11, 2025
    Stanford , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)More than PrivacyACM Computing Surveys10.1145/346077154:7(1-37)Online publication date: 18-Jul-2021
    • (2020)Differentially Private Call Auctions and Market ImpactProceedings of the 21st ACM Conference on Economics and Computation10.1145/3391403.3399500(541-583)Online publication date: 13-Jul-2020
    • (2020)Mechanisms for Cooperative Freight Routing: Incentivizing Individual ParticipationIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2019.291554921:5(2155-2166)Online publication date: May-2020
    • (2018)Near optimal jointly private packing algorithms via dual multiplicative weight updateProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175291(343-357)Online publication date: 7-Jan-2018
    • (2016)Learning and efficiency in games with dynamic populationProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884444(120-129)Online publication date: 10-Jan-2016
    • (2016)Coordination ComplexityProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science10.1145/2840728.2840767(281-290)Online publication date: 14-Jan-2016

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media