skip to main content
10.1145/2840728.2840767acmconferencesArticle/Chapter ViewAbstractPublication PagesitcsConference Proceedingsconference-collections
research-article
Public Access

Coordination Complexity: Small Information Coordinating Large Populations

Published: 14 January 2016 Publication History

Abstract

We initiate the study of a quantity that we call coordination complexity. In a distributed optimization problem, the information defining a problem instance is distributed among n parties, who need to each choose an action, which jointly will form a solution to the optimization problem. The coordination complexity represents the minimal amount of information that a centralized coordinator, who has full knowledge of the problem instance, needs to broadcast in order to coordinate the n parties to play a nearly optimal solution.
We show that upper bounds on the coordination complexity of a problem imply the existence of good jointly differentially private algorithms for solving that problem, which in turn are known to upper bound the price of anarchy in certain games with dynamically changing populations.
We show several results. We fully characterize the coordination complexity for the problem of computing a many-to-one matching in a bipartite graph. Our upper bound in fact extends much more generally to the problem of solving a linearly separable convex program. We also give a different upper bound technique, which we use to bound the coordination complexity of coordinating a Nash equilibrium in a routing game, and of computing a stable matching.

References

[1]
Noga Alon, Noam Nisan, Ran Raz, and Omri Weinstein. Welfare maximization with limited interaction. CoRR, abs/1504.01780, 2015.
[2]
Xavier Calsamiglia. Informational requirements of parametric resource allocation processes. Asociación Sudeuropea de Economía Teórica, 1984.
[3]
Rachel Cummings, Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. Privacy and truthful equilibrium selection for aggregative games. CoRR, abs/1407.7740, 2014.
[4]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference, TCC '06, pages 265--284, 2006.
[5]
Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In Proceedings of the 46th ACM Symposium on Theory of Computing, STOC '14, pages 233--242, 2014.
[6]
Xiaotie Deng, Christos Papadimitriou, and Shmuel Safra. On the complexity of equilibria. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 67--71. ACM, 2002.
[7]
Friedrich A. Hayek. The use of knowledge in society. American Economic Review, 35(4):519--530, 1945.
[8]
4}HHRRW14Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In Proceedings of the 46th ACM Symposium on Theory of Computing, STOC '14, pages 21--30, 2014.
[9]
Justin Hsu, Zhiyi Huang, Aaron Roth, and Zhiwei Steven Wu. Jointly private convex programming. CoRR, abs/1411.0998, 2014.
[10]
Elad Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium on Computational Complexity (ECCC), 14(088), 2007.
[11]
Leonid Hurwicz. Optimality and Informational Efficiency in Resource Allocation Processes. Mathematical Methods in the Social Sciences. Stanford University Press, 1960.
[12]
Alexander S Kelso and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, pages 1483--1504, 1982.
[13]
Eyal Kushilevitz and Noam Nisan. Communication complexity. Advances in Computers, 44:331--360, 1997.
[14]
Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21--49, 1999.
[15]
Michael Kearns, Mallesh M. Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: incentives and privacy. In Proceedings of the 5th Innovations in Theoretical Computer Science, ITCS '14, pages 403--410, 2014.
[16]
Thodoris Lykouris, Vasilis Syrgkanis, and Éva Tardos. Learning and efficiency in games with dynamic population. CoRR, abs/1505.00391, 2015.
[17]
Kenneth Mount and Stanley Reiter. The information size of message spaces. Journal of Economic Theory, 8(2):161--192, June 1974.
[18]
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS '07, pages 94--103, 2007.
[19]
Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory, 129(1):192--224, 2006.
[20]
Ryan M. Rogers and Aaron Roth. Asymptotically truthful equilibrium selection in large congestion games. In Proceedings of the 16th ACM Conference on Economics and Computation, EC '14, pages 771--782, 2014.
[21]
Ryan M. Rogers, Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Inducing approximately optimal flow using truthful mediators. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15--19, 2015, pages 471--488, 2015.
[22]
Ilya Segal. Communication in economic mechanisms. ECONOMETRIC SOCIETY MONOGRAPHS, 41:222, 2006.

Cited By

View all
  • (2024)On the computational complexity of ethics: moral tractability for minds and machinesArtificial Intelligence Review10.1007/s10462-024-10732-357:4Online publication date: 31-Mar-2024
  • (2023)Human-Robot Teaming: Grand ChallengesCurrent Robotics Reports10.1007/s43154-023-00103-14:3(81-100)Online publication date: 8-Aug-2023
  • (2022)Coordination and Flexibility in the Management of Software Development Processes for Start-Up CompaniesApplied Technologies10.1007/978-3-031-03884-6_30(412-425)Online publication date: 6-Apr-2022
  • Show More Cited By

Index Terms

  1. Coordination Complexity: Small Information Coordinating Large Populations

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
    January 2016
    422 pages
    ISBN:9781450340571
    DOI:10.1145/2840728
    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 ACM 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: 14 January 2016

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. coordination complexity
    2. privacy

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    ITCS'16
    Sponsor:
    ITCS'16: Innovations in Theoretical Computer Science
    January 14 - 17, 2016
    Massachusetts, Cambridge, USA

    Acceptance Rates

    ITCS '16 Paper Acceptance Rate 40 of 145 submissions, 28%;
    Overall Acceptance Rate 172 of 513 submissions, 34%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)On the computational complexity of ethics: moral tractability for minds and machinesArtificial Intelligence Review10.1007/s10462-024-10732-357:4Online publication date: 31-Mar-2024
    • (2023)Human-Robot Teaming: Grand ChallengesCurrent Robotics Reports10.1007/s43154-023-00103-14:3(81-100)Online publication date: 8-Aug-2023
    • (2022)Coordination and Flexibility in the Management of Software Development Processes for Start-Up CompaniesApplied Technologies10.1007/978-3-031-03884-6_30(412-425)Online publication date: 6-Apr-2022
    • (2021)More than PrivacyACM Computing Surveys10.1145/346077154:7(1-37)Online publication date: 18-Jul-2021

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media