Abstract | We consider the following distributed optimization problem: three agents i =
1; 2; 3 are each presented with a load drawn independently from the same known prior distribution.
Then each agent decides on which of two available bins to put her load. Each bin has
capacity �, and the objective is to find a distributed protocol that minimizes the probability
that an overflow occurs (or, equivalently, maximizes the winning probability).
In this work, we focus on the cases of full information and local information, depending on
whether each agent knows the loads of both other agents or not. Furthermore, we distinguish
between the cases where the agents are allowed to follow different decision rules (eponymous
model) or not (anonymous model ). We assume no communication among agents.
First, we present optimal protocols for the full information case, for both the anonymous and
the eponymous model.
For the local information, anonymous case, we show that the winning probability is upper
bounded by 0.622 in the case where the input loads are drawn from the uniform distribution.
Motivated by [3], we present a general method for computing the optimal single-threshold protocol
for any continuous distribution, and we apply this method to the case of the exponential
distribution.
Finally, we show how to compute, in exponential time, an optimal protocol for the local
information, eponymous model for the case where the input loads are drawn from a discretevalued,
bounded distribution. |