research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:PNP
TitleFull and Local Information in Distributed Decision Making
Bibtex cite IDRACTI-RU1-2007-17
Booktitle 5th Workshop on Approximation and Online Algorithms (WAOA 2007)
Series Lecture Notes in Computer Science
Year published 2007
Month October
Pages 156-169
Publisher Springer Verlag, LNCS
Location Eliat, Israel
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.
Panagopoulou, Panagiota
Spirakis, Paul
ddm.pdf (main file)
Short description of problem, previous work and result
Publication ID23