?
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|]

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.
LinkReply

Comments:
[User Picture]From: psifenix
2006-10-17 10:25 pm (UTC)
Bad Jcreed! No feeding Psyfe maf until after he finishes his NSF app. >:|
(Reply) (Thread)
From: rdore
2006-10-17 11:23 pm (UTC)
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.
(Reply) (Thread)
[User Picture]From: jcreed
2006-10-18 03:24 am (UTC)
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.
(Reply) (Parent) (Thread)
[User Picture]From: cdtwigg
2006-10-18 12:17 am (UTC)
Man, I got into an argument once with some guy in my lab about approval voting that went on for over an hour. He just really didn't like the fact that people get to vote "more than once" and no amount of me saying "but it has lots of proveable properties!" would dissuade him :)
(Reply) (Thread)
(Deleted comment)
[User Picture]From: jcreed
2006-10-18 01:56 pm (UTC)
Yeah, I actually found myself thinking a little bit about them too. Wikipedia has some information on them, but no recurrence or closed form that I can find.

You can give a recurrence for the number of strict weak orders of size n with m different equivalence classes as

SW_nm = m(SW_(n-1)(m-1) + SW_(n-1)m)

and then sum over m, but that seems kind of complicated.
(Reply) (Parent) (Thread)