Optimal, Distributed Decision-Making: The Case of No Communication

of a natural class of distributed optimization problems
that involve decision-making by a collection of n distributed
agents in the presence of incomplete information; such
problems were originally considered in a load balancing
setting by Papadimitriou and Yannakakis (Proceedings of
the 10th Annual ACM Symposium on Principles of Distributed
Computing, pp. 61-64, August 1991). Within our framework
we are able to settle completely the case where no
communication is allowed among the agents. For that
case, for any given decision protocol, our framework
allows to obtain a combinatorial inclusion-exclusion
expression for the probability that no "overflow"
occurs, called the winning probability, in terms
of the volume of some simple combinatorial polytope.

Within our general framework, we offer a complete
resolution to the special cases of oblivious algorithms,
for which agents do not "look at" their inputs, and
non-oblivious algorithms, for which they do, of the
general optimization problem. In either case, we
derive optimality conditions in the form of combinatorial
polynomial equations. For oblivious algorithms, we
explicitly solve these equations to show that the
optimal algorithm is simple and uniform, in the sense
that agents need not "know" n. Most interestingly,
we show that the optimal non-oblivious algorithms must
be non-uniform: we demonstrate that the optimality
conditions admit different solutions for particular,
different "small" values of n; however, these solutions
improve in terms of the winning probability over the
optimal, oblivious algorithm. Our results demonstrate
an interesting trade-off between the amount of knowledge
used agents and uniformity for optimal, distributed
decision-making with no communication.