Coordination Complexity
Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu · 2016
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.