Shun-ichi Azuma1, Masaaki Nagahara2
10:20 - 10:40 | Wed 11 Dec | Athena | WeA25.2
Majority determination is one of the fundamental topics in multi-agent systems. The problem is quite simple: when agents initially vote "in favor" or "opposed" for some proposal, how can the agents cooperatively and distributedly determine the majority of the opinions? In the topic, it is an interesting issue to clarify the lowest resolution of communication among agents. This paper thus addresses a majority determination problem with binary-valued communication. To overcome the limitation of communication, we exploit 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.