Notes from a Medium-Sized Island [entries|archive|friends|userinfo]
Jason

 [ website | My Website ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

[Oct. 17th, 2006|05:53 pm]
Jason
 [ Tags | math ]

Here's a bit of math vaguely related to voting systems:

Say a vector v in Rn is nontrivial if

1. vi ≠ vj for all i ≠ j
2. vi - vj ≠ vI - vJ for all i,j,I,J so long as i ≠ j, I ≠ J, (i,j) ≠ (I,J).
For nontrivial vectors v, w in Rn, say v ~ w if for all i,j,I,J,
vi - vj < vI - vJ
if and only if
wi - wj < wI - wJ

The intuition is that v is a scalar vote, supposedly indicating how much the voter likes each of the n candidates, but obviously vulnerable to strategic voting — if you really used R, it would be a game of name the biggest number. Range voting, the topic of an interesting (but mildly repetitive) talk I just saw, limits this to some interval. Nonetheless, it is vulnerable to strategic exageration, and reduces, with a completely strategic electorate, to approval voting. I got curious about the properties of systems that make dishonesty harder, but I haven't checked the literature, so I may be naively reinventing wheels here.

The idea of the equivalence relation ~ is that it throws away a lot of information, but not as much as ordinal voting as found in Condorcet and other systems. It retains the ordering of candidates, and also an ordering of the gaps between candidates. Some questions:

1. [probably just some combinatorics] How many ~-equivalence classes are there in Rn? Doing some hand calculations I count 1,1,2,12,240 for n=0..4, which sadly I didn't find in the encyclopedia of integer sequences.
2. What's a better way to define these classes intrinsically instead of by reference to vectors in R?
3. Are there any voting systems that take in one such ~-equivalence class from each voter, and output a social choice of the same type, and satisfy suitable IIR, monotonicity, and no-dictator axioms?

ETA: Man, I wish I knew more combinatorics. this stuff by Brignall, Ruskuc, and Vatter looks really neat.

 From: 2006-10-17 10:25 pm (UTC) (Link)
Bad Jcreed! No feeding Psyfe maf until after he finishes his NSF app. >:|
 From: 2006-10-17 11:23 pm (UTC) (Link)
I'd be willing to guess that it's actually this sequence (the minus first term should be one I think).

Also, you don't need R, you can do this all in Z+ (and with vn at most 2n). I suspect that if you just reduce them in some natural way and you'll get the sequence above.

The more interesting question is what "suitable IIR" would be here.
 From: 2006-10-18 03:24 am (UTC) (Link)
Yeah, I just picked R kind of arbitrarily. I believe Z+, I don't know if I believe 2n, but it sounds plausible.

As for "suitable IIR", what I really want to do is say a notion of a ballot is a convtravariant functor F from FinOrd from some category C. Then IIR is the naturality condition on saying that a social choice function is a natural transformation Fn → F, where n is the population of voters.

Arrow's theorem is just the statement that the only natural transformations that have the diagonal map F → Fn as a right inverse are projections, i.e. dictatorships.