Iterated Majority Voting
Stéphane Airiau, Ulle Endriss

Abstract:
We study a model in which a group of agents make a sequence of 
collective decisions on whether to remain in the current state
of the system or switch to an alternative state, as proposed by one of
them. Examples for instantiations of this model include the step-wise
refinement of a bill of law by means of amendments to be voted on, as
well as resource allocation problems, where agents successively alter the
current allocation by means of a sequence of deals. We specifically focus
on cases where the majority rule is used to make each of the collective
decisions, as well as variations of the majority rule where different 
quotas need to be met to get a proposal accepted. In addition, we allow
for cases in which the same proposal may be made more than once. As
this can lead to infinite sequences, we investigate the effects of 
introducing a deadline bounding the number of proposals that can be made. 
We use both analytical and experimental means to characterise situations
in which we can expect to see a convergence effect, in the sense that the
expected payoff of each agent will become independent from the initial
state of the system, as long as the deadline is chosen large enough.