Joint Behavior and Common Belief
This addresses the problem of achieving joint behavior in multi-agent systems, where common belief is difficult to achieve, by proposing more practical alternatives, though it is incremental as it builds on existing theory.
The paper challenges the long-held view that common belief is necessary for joint behavior by demonstrating that joint behavior can occur without it, and introduces two variants of common belief, with action-stamped common belief shown to be necessary and sufficient for joint behavior.
For over 25 years, common belief has been widely viewed as necessary for joint behavior. But this is not quite correct. We show by example that what can naturally be thought of as joint behavior can occur without common belief. We then present two variants of common belief that can lead to joint behavior, even without standard common belief ever being achieved, and show that one of them, action-stamped common belief, is in a sense necessary and sufficient for joint behavior. These observations are significant because, as is well known, common belief is quite difficult to achieve in practice, whereas these variants are more easily achievable.