Majority Determination on Binary-Valued Communication Networks

Shun-ichi Azuma1, Masaaki Nagahara2

  • 1Nagoya University
  • 2The University of Kitakyushu

Details

10:20 - 10:40 | Wed 11 Dec | Athena | WeA25.2

Session: Multi-Agent Systems I

Abstract

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.