On Jan 25, 2010, at 8:49 PM, Abd ul-Rahman Lomax wrote:
At 05:59 AM 1/25/2010, Juho wrote:
Here's one simple approach.
- all voters rank all the rooms
- use Borda like personal utility values => last room = 0 points,
one but last = 1 point etc. (also other than this kind of linear
scale could be used)
- find the room allocation that gives the highest sum of utilities
- if there is a tie one can use seniority to break it
- the utility values of each voters are multiplied by some
seniority factor and then summed up again
- the factors could be quite small if one just wants to break
the ties (e.g. 1.0001, 1.0002)
This tie breaking approach is intended to work so that if there is
for example some room that all consider to be the best then that
room would be given to the most senior voter.
Any chances to work?
Sure. But equal ranking must be allowed, otherwise noise is
introduced. Borda with equal ranking (and therefore empty ranks,
otherwise equal ranked votes are reduced in strength) is Range. Why
not just use Range, allowing greater precision. One could use a
Range method with N*R resolution, where the "Borda" version has N
equal to 1.
Range style ratings would give more accurate utilities but I used
Borda style to get rid of strategies. Borda style utilities will
distort the true utilities somewhat but the end result may still be
quite fair. I didn't include equal rankings since that would not make
any big change in the level of distortion. Forcing the voters to
decide whether A>B or B>A is correct instead of allowing them to vote
A=B is quite ok. Picking a random order doesn't distort the outcome
too much even if the voter could not make up his/her mind on which one
of the two rooms is better. The method is thus already noisy as it is
and therefore equal rankings might not add very much. If equal
rankings will not add any complexity to the method they are ok though.
(DIfferent ways to count the points in case of equal rankings would
have different impact on the method.)
The allocation problem as "highest sum of utilities" is NP-hard,
though, I believe. I suspect that an iterative method would be
better. Use an approval method, which will divide up voters into
blocks. Then use more sophisticated analysis on each block. If you
are the only one to approve a particular room, perhaps you get the
room! So you would not over-approve at the first iteration. Standard
approval strategy when there is iteration.
I didn't describe the method how to find the winner but I'm quite ok
with method definitions that specify the ideal winner in a way that
may lead to problems with computational complexity when implemented,
if one can approximate the optimal result well enough. In this case
that means that since the method already has some noise due to the
Borda based ratings, the noise caused by imperfect algorithms seeking
the optimal room allocation would probably add only very little extra
noise. My first choice would therefore be to use a clear definition of
the ideal solution and then use approximate algorithms to find the
best result. Do you think there are some "iterative methods" that
would achieve more accurate results (or would be necessary for
efficiency or other reasons)?
Juho
----
Election-Methods mailing list - see http://electorama.com/em for list info
