Conference rusure::math

1632.0. "Coalitions and Voting" by TRACE::GILBERT (Ownership Obligates) Thu Jun 25 1992 13:14

Here's a series of ideas and questions concerning coalitions and voting
that Andrew Buchanan sent in.  It looked interesting.

-------------------------------------------------------------------------------

Suppose that you've got a legislative assembly, consisting of n >= 3 political
parties, who vote on various bills.   Each party has a certain number of
members, p_i, and the party as a whole will vote for or against the a bill.
Simple majority will determine whether the vote caries.   For simplicity we'll
ignore the possibility of ties.   To break symmetry, we'll make the important
constraint that:
	 p_1 > p_2 > p_3 > ..., etc.

Now, what I want to explore are the possible coalitions of parties.   Let
N = {1, 2, ..., n} be the set of parties.   Let S be a subset of N.   Fairly
obviously, we can define S to be a coalition if: 
	sum(s in S) p_s > sum(s in N) p_s

So let's look at a few for instances if if n=5.   

	S'={1,2,3} is *always* a coalition, whatever the precise values of the 
p_i.   This is easy to see since: 
		party 1 outvotes party 4
		party 2 outvotes party 5
		and I've got party 3 left over!
	Call sets like S' *Universal Coalitions* (or UC)

	The complement of S', {4,5}, is for similar reasons *never* a coalition,
whatever the values of the p_i.

	There are also some subsets of N which are *sometimes* coalitions, and
sometimes not.   For instance S"={1} (or its complement, {2,3,4,5}).   If party
1 is larger than all the other parties put together, S" will be a coalition.   
But if p_1 is less than p_2+p_3+p_4+p_5, then that's enough for {2,3,4,5} to
be a coalition instead.   Call such a subset *indeterminate*.

	+--------------------------------------------------+
	| Q1: Find an analytic (ie, non-recursive) formula |
	| for the number of possible UCs for a given n.    |
	+--------------------------------------------------+

	Now, some coalitions are quite unlikely.   For instance, it's not
probable that the coalition {1,2,3,4} is going to last very long to bully the
smallest party 5.   To formalize this notion, let's say, for a given set
of values for p_i, that a coalition C is:

	*overmanned*, if there's a subset C' of C which is also a coalition.

	*overweight*, if there's a member i of C which can be replaced by an
element j not in C with p_j < p_i (ie i < j) such that: 
		C"=Cu{j}\{i} is a coalition.

	Define that a set S of parties is *unstable* if, for each possible set
of values of p_i for which S is a coalition, S is either overmanned or 
overweight.   Otherwise S is stable.

	+--------------------------------------------------+
	| Q2: Prove:  S is indeterminate <=> S is stable   |
	+--------------------------------------------------+

	(There's an interesting special case to one half of this proof.)

	This to me is a surprising result!   It says that a plausible
coalition is exactly one which won't work "all the time", but works for just
some of the range of possible p_i.

	So let's focus on the stable S, and forget the other kinds of coalition
which will never occur naturally.   Let P be the vector (p_1,p_2, ..., p_n}
and define a stable set S to be *fit* for P if it is a coalition that is
neither overmanned nor overweight.   Let Q(P) be the set of fit coalitions
for P.

	+--------------------------------------------------+
	| Q3: For a given n, varying P, what is the max    |
	| value that |Q(P)| can attain?			   |
	+--------------------------------------------------+

	I have not explored this third question fully, but have some good
techniques.   Two fit coalitions for the same P must have non-zero intersection,
for instance.

	As an example, for n=5, |Q(P)| is at most 3.   

The indeterminate (= stable) sets are:
		{1}	{1,2}	{1,3}	{1,4}	{1,5}	{2,3}
and their complements.   For any P, Q(P) will be one of:

{ {1} }

{ {2,3} }

{ {3,4,5} }

{ {2,4,5} {1,2} }

{ {1,4,5} {2,3,5} {1,3} }

{ {2,3,4} {1,4} }

{ {2,3,4,5} {1,5} }

	This suggests a few interesting lines to muse along.

	We can describe {3,4,5} as *exclusive*.   P can never permit another
fit coalition at the same time as it permits {3,4,5}.

	+--------------------------------------------------+
	| Conjecture: Q exclusive <=> Q has the form:      |
	|		{x, x+1, ... 2x-1}		   |
	+--------------------------------------------------+

	Hope you find this interesting.

Cheers,
Andrew.

There's an obvious typo in the first equation; it should read:

	sum(s in S) p_s > sum(s in N\S) p_s