Title: Flexible Level-1 Consensus Ensuring Stable Social Choice: Analysis and Algorithms,
Abstract: Level-1 Consensus is a property of a preference-profile. Intuitively, it
means that there exists a preference relation which induces an ordering of all
other preferences such that frequent preferences are those that are more
similar to it. This is a desirable property, since it enhances the stability of
social choice by guaranteeing that there exists a Condorcet winner and it is
elected by all scoring rules.
In this paper, we present an algorithm for checking whether a given
preference profile exhibits level-1 consensus. We apply this algorithm to a
large number of preference profiles, both real and randomly-generated, and find
that level-1 consensus is very improbable. We support these empirical findings
theoretically, by showing that, under the impartial culture assumption, the
probability of level-1 consensus approaches zero when the number of individuals
approaches infinity.
Motivated by these observations, we show that the level-1 consensus property
can be weakened while retaining its stability implications. We call this weaker
property Flexible Consensus. We show, both empirically and theoretically, that
it is considerably more probable than the original level-1 consensus. In
particular, under the impartial culture assumption, the probability for
Flexible Consensus converges to a positive number when the number of
individuals approaches infinity.