Majority Determination on Binary-valued Communication Networks
Shun‐ichi Azuma, Masaaki Nagahara · 2019
Majority determination is to determine the majority of the opinions of agents in a distributed manner. This paper addresses a majority determination problem with binary-valued communication, in order to clarify the lowest resolution of communication among agents for determining the majority. To overcome the limitation of communication, we exploit here randomized communication, that is, sending either one of the values 0 or 1, selected according to a probabilistic distribution. Based on this idea, we develop consensus-type algorithms that approximately solve the problem with an arbitrarily prescribed accuracy.