Optimal, distributed decisionmaking: The case of no communication
Date
1999ISSN
03029743Source
12th International Symposium on Fundamentals of Computation Theory, FCT 1999Volume
1684Pages
293303Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
We present a combinatorial framework for the study of a natural class of distributed optimization problems that involve decisionmaking 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. 6164, August 1991). For any given decision protocol and assuming no communication among the agents, our framework allows to obtain a combinatorial inclusionexclusion 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 nonoblivious 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 optimal nonoblivious algorithms must be nonuniform: 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 tradeoff between the amount of knowledge used by agents and uniformity for optimal, distributed decisionmaking with no communication. © SpringerVerlag Berlin Heidelberg 1999.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.

Article
Classes of nonlinear partially observable stochastic optimal control problems with explicit optimal control laws
Charalambous, Charalambos D.; Elliott, R. J. (1998)This paper introduces certain nonlinear partially observable stochastic optimal control problems which are equivalent to completely observable control problems with finitedimensional state space. In some cases the optimal ...

Conference Object
Optimization of fully observable nonlinear stochastic uncertain controlled diffusion: Monotonicity properties and optimal sensitivity
Rezaei, F.; Charalambous, Charalambos D.; Kyprianou, Andreas (2004)This paper is concerned with fully observable nonlinear stochastically controlled diffusions, in which uncertainty is described by a relative entropy constraint between the nominal measure and the uncertain measure, while ...

Conference Object
Towards optimal CMOS lifetime via unified reliability modeling and multiobjective optimization
Papadopoulos, A.; Theocharides, Theocharis; Michael, Maria K. (2011)