Invariance to affine transformations, keeping cardinal honest
Good news - I'm almost done with my non-EM big project, and so I should
be able to create some strategy simulations soon to investigate which
Friendly variants are good :-)
But here's a thought that I've talked about earlier, that came up in a
private mail response.
Suppose that von Neumann-Morgenstern utilities are the best we can do as
far as interpersonal comparisons go.
Then we can imagine that every cardinal method has an idealized
(Platonic, so to speak) form that operates not on ballots with discrete
ratings, but on real ratings. E.g. the idealized version of Range
involves giving each candidate a rating on [0...1), and the candidate
with the highest mean wins.
Then vNM utilities are unique up to some affine scaling. Let u(v, X) be
voter v's utility should X be elected, on an objective scale that we
can't access due to interpersonal comparison problems. Then if v is
asked to rate X, he would rate X as r(v, X) = a_v * u(v, X) + b_v, where
a_v and b_v are the positive scaling constants for that voter.
For something like Range, suppose that when v goes to vote, v chooses
some a and b so that every rating fits on the scale, then submits that vote.
For an idealized method, we can then propose the following invariance
property:
- Affine invariance: The outcome of the election should not depend on
the particular a and b constants chosen by the voter.
Methods that pass affine invariance plus anonymity and symmetry satisfy
a type of one-man-one-vote because expanding your scale is equivalent to
making the a constant larger. Hence such a method, if it accepts
ratings, doesn't have to limit itself to a bounded scale, though the
user interface is probably more pleasant if it does.
Furthermore, these methods have another property that there exists one
honest ballot, which solves rb-j's objection of how much a voter should
vote his second favorite if he's honest. Every such method that I know
of fails IIA, but that's better than the sort of "I pass IIA but the
outcome still depends on who's in the running" thing that Range does.
What methods pass this criterion?
Well, ranked methods clearly do. No amount of positive affine scaling
can turn r(v, X) > r(v, Y) into r(v, X) < r(v, Y).
In addition, there's this "double normalized Range": the voter has to
fill in a ballot where at least one candidate is rated max and at least
one is rated min. The rules are otherwise as Range.
Each forced rating gets rid of one degree of freedom, so forcing two
candidates fixes both a and b. The intermediate candidates' ratings can
be found as follows:
Suppose Best is the best candidate, and Worst is the worst, and the
scale is from 1 being best to 0 being worst. Then for any other
candidate X, rate X at p if you're indifferent between getting Best with
probability p and Worst with probability 1-p, and getting X for sure.
Incentivizing honesty here would be hard, though.
(Perhaps a Ranked Pairs-like algorithm is possible for triples rather
than pairs.)
I also had an idea that perhaps we could find the best VSE affine
invariant method by something like my "optimum strategy" search, but
over the space of cardinal ballots instead of ordinal ones, for a small
number of candidates. In particular, the results for three candidates
could be interesting.
We couldn't use the idealized method because there are infinite reals on
a bounded interval. But the observation about double normalized Range
above suggests that we could replace the ballot format for three
candidates with:
(Who's min), (Who's max), (the p value for the third candidate),
or really, one of:
(A: X, B: 0, C: 10)
(A: X, B: 10, C: 0)
(A: 0, B: X, C: 10)
(A: 10, B: X, C: 0)
(A: 0, B: 10, C: X)
(A: 10, B: 0, C: X)
for a scale of 0..10, where X is an integer between 0 and 10 inclusive.
This gives each voter 60 different ballots to choose between (contrasted
with 6 per voter for ordinal).
So for e.g. 10 voters, 3 candidates, there are about (60+10-1) choose 10
= 3e11 elections. There are 3003 ordinal ones. Perhaps a rating scale of
0..10 is too high for an integer programming search. The trick would be
to find a quantization level that's high enough that the search is
feasible, yet low enough that it's possible to interpolate to an
idealized method, somewhat like I did with fpA-fpC.
Finally, I'd say it is perhaps possible to go beyond vNM, but I'm not
entirely sure how to do it, much less how to do it in a
strategy-resistant manner. On the other hand, there may be limitations
beyond vNM itself: e.g. it might be hard to tell who would be a better
winner between Stalin and Ivan the Terrible, because they're both so
thoroughly awful as to saturate the scale.
Great!
One way to extend the reals to allow comparison of quantities that are
"incommensurate" with standard real ratings ... is to allow polynomials in
epsilon as ratings.
Another thought ... the Ultimate Lottery method allows ballots to be
arbitrary positively homogeneous functions of the lottery probability
variables ...
f(p1, p2, ... p_n)
The Ultimate Lottery is the point P of real n-space that maximizes the
product of the ballots, subject to the non-negativity constraints p_k >=0,
and the normalization to unity of the Sum p_k .
The one person, one vote condition is that all of the ballots have the same
degree d of homogeneity.
f(lambda*p)=f(p)*lambda^d
-Forest
On Mon, Oct 31, 2022, 5:41 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Good news - I'm almost done with my non-EM big project, and so I should
be able to create some strategy simulations soon to investigate which
Friendly variants are good :-)
But here's a thought that I've talked about earlier, that came up in a
private mail response.
Suppose that von Neumann-Morgenstern utilities are the best we can do as
far as interpersonal comparisons go.
Then we can imagine that every cardinal method has an idealized
(Platonic, so to speak) form that operates not on ballots with discrete
ratings, but on real ratings. E.g. the idealized version of Range
involves giving each candidate a rating on [0...1), and the candidate
with the highest mean wins.
Then vNM utilities are unique up to some affine scaling. Let u(v, X) be
voter v's utility should X be elected, on an objective scale that we
can't access due to interpersonal comparison problems. Then if v is
asked to rate X, he would rate X as r(v, X) = a_v * u(v, X) + b_v, where
a_v and b_v are the positive scaling constants for that voter.
For something like Range, suppose that when v goes to vote, v chooses
some a and b so that every rating fits on the scale, then submits that
vote.
For an idealized method, we can then propose the following invariance
property:
- Affine invariance: The outcome of the election should not depend on
the particular a and b constants chosen by the voter.
Methods that pass affine invariance plus anonymity and symmetry satisfy
a type of one-man-one-vote because expanding your scale is equivalent to
making the a constant larger. Hence such a method, if it accepts
ratings, doesn't have to limit itself to a bounded scale, though the
user interface is probably more pleasant if it does.
Furthermore, these methods have another property that there exists one
honest ballot, which solves rb-j's objection of how much a voter should
vote his second favorite if he's honest. Every such method that I know
of fails IIA, but that's better than the sort of "I pass IIA but the
outcome still depends on who's in the running" thing that Range does.
What methods pass this criterion?
Well, ranked methods clearly do. No amount of positive affine scaling
can turn r(v, X) > r(v, Y) into r(v, X) < r(v, Y).
In addition, there's this "double normalized Range": the voter has to
fill in a ballot where at least one candidate is rated max and at least
one is rated min. The rules are otherwise as Range.
Each forced rating gets rid of one degree of freedom, so forcing two
candidates fixes both a and b. The intermediate candidates' ratings can
be found as follows:
Suppose Best is the best candidate, and Worst is the worst, and the
scale is from 1 being best to 0 being worst. Then for any other
candidate X, rate X at p if you're indifferent between getting Best with
probability p and Worst with probability 1-p, and getting X for sure.
Incentivizing honesty here would be hard, though.
(Perhaps a Ranked Pairs-like algorithm is possible for triples rather
than pairs.)
I also had an idea that perhaps we could find the best VSE affine
invariant method by something like my "optimum strategy" search, but
over the space of cardinal ballots instead of ordinal ones, for a small
number of candidates. In particular, the results for three candidates
could be interesting.
We couldn't use the idealized method because there are infinite reals on
a bounded interval. But the observation about double normalized Range
above suggests that we could replace the ballot format for three
candidates with:
(Who's min), (Who's max), (the p value for the third candidate),
or really, one of:
(A: X, B: 0, C: 10)
(A: X, B: 10, C: 0)
(A: 0, B: X, C: 10)
(A: 10, B: X, C: 0)
(A: 0, B: 10, C: X)
(A: 10, B: 0, C: X)
for a scale of 0..10, where X is an integer between 0 and 10 inclusive.
This gives each voter 60 different ballots to choose between (contrasted
with 6 per voter for ordinal).
So for e.g. 10 voters, 3 candidates, there are about (60+10-1) choose 10
= 3e11 elections. There are 3003 ordinal ones. Perhaps a rating scale of
0..10 is too high for an integer programming search. The trick would be
to find a quantization level that's high enough that the search is
feasible, yet low enough that it's possible to interpolate to an
idealized method, somewhat like I did with fpA-fpC.
Finally, I'd say it is perhaps possible to go beyond vNM, but I'm not
entirely sure how to do it, much less how to do it in a
strategy-resistant manner. On the other hand, there may be limitations
beyond vNM itself: e.g. it might be hard to tell who would be a better
winner between Stalin and Ivan the Terrible, because they're both so
thoroughly awful as to saturate the scale.
Election-Methods mailing list - see https://electorama.com/em for list
info
On 11/1/22 04:58, Forest Simmons wrote:
Great!
One way to extend the reals to allow comparison of quantities that are
"incommensurate" with standard real ratings ... is to allow polynomials
in epsilon as ratings.
Another thought ... the Ultimate Lottery method allows ballots to be
arbitrary positively homogeneous functions of the lottery probability
variables ...
f(p1, p2, ... p_n)
The Ultimate Lottery is the point P of real n-space that maximizes the
product of the ballots, subject to the non-negativity constraints p_k
=0, and the normalization to unity of the Sum p_k .
The one person, one vote condition is that all of the ballots have the
same degree d of homogeneity.
f(lambda*p)=f(p)*lambda^d
I think you'll have to explain that in more steps :-)
What would polynomial ratings look like in practice? Would they have a
different ballot format, or ask for different data, than vNM type
ballots? And would there exist a way for an honest voter to provide an
unambiguous honest ballot consistent with his state/preferences?
The Ultimate Lottery sounds a bit like the Nash solution for envy-free
division, where you maximize the product of utilities. But I don't know
all that much about the subject.
-km
On Tue, Nov 1, 2022, 2:36 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 11/1/22 04:58, Forest Simmons wrote:
Great!
One way to extend the reals to allow comparison of quantities that are
"incommensurate" with standard real ratings ... is to allow polynomials
in epsilon as ratings.
Another thought ... the Ultimate Lottery method allows ballots to be
arbitrary positively homogeneous functions of the lottery probability
variables ...
f(p1, p2, ... p_n)
The Ultimate Lottery is the point P of real n-space that maximizes the
product of the ballots, subject to the non-negativity constraints p_k
=0, and the normalization to unity of the Sum p_k .
The one person, one vote condition is that all of the ballots have the
same degree d of homogeneity.
f(lambda*p)=f(p)*lambda^d
I think you'll have to explain that in more steps :-)
In due time ...
What would polynomial ratings look like in practice? Would they have a
different ballot format, or ask for different data, than vNM type
ballots?
A polynomial can be represented as a sequence of coefficients, each of them
a rating on a scale of zero to 99, with an understanding that the k-th
coefficient is multiplied by epsilon^k.
Addition is by addition of the sequences, which, in this case are functions
from non negative integers into the whole numbers between zero and 99. So
you add them the way you add functions.
Comparisons of magnitudes are by ignoring the higher degree terms except
when the lower degree terms are tied.
And would there exist a way for an honest voter to provide an
unambiguous honest ballot consistent with his state/preferences?
Since affine combinations of polynomials are by addition, multiplication,
and division by positive reals, I don't see a problem ... we need to
explore it to see if there are unanticipated problems. But I'm sure this
has already been done.
The Ultimate Lottery sounds a bit like the Nash solution for envy-free
division, where you maximize the product of utilities.
In this case the product of the expectations of the respective ballot
ratings. I don't know if Nash thought of this election methods
application, but we called it the Nash Lottery in our second voting lottery
article.
The Ultimate Lottery is a generalization.
In the Nash lottery a ballot is a function of the form
p-->f(p)=r•p
So obviously f(lambda p)=lambda f(p), which shows f to be homogeneous of
degree one.
p-->(Sum (a_k*p_k)^n)^n
Is also homogeneous of degree one.
As n approaches infinity, this L_n norm approaches the sup norm
Max(a_k*p_k), which is also homogeneous of degree one.
When proving the Nash lottery to be a proportional lottery, you define the
Lagrangian to be
Sum log(f(p))-lambda(Sum(p_k)-1), and set its gradient to zero for
stationarity. The lambda is the lagrange multiplier for constraining total
probability to unity.
Follow your nose and the Nash allocation of probabilities falls right into
your lap.
After going through that for the Nash Lottery, do the same thing for the
Ultimate Lottery, making use of Euler's Partial Differential Equation for
homogeneous functions when it is needed; You can derive it for yourself by
taking the gradient of both sides of the homogeneity condition ...
f(lambda p)=f(p)lambda^d
All of this is somewhere in the EM List archives about ten years back. But
it'll be easier to recreate it by following your nose, than to find it in
the archives. We never did publish it; our paper was already too long and
detailed for the reviewers.
But I don't know
all that much about the subject.
The wikipedia article on homogeneous functions is good ... including their
treatment of Euler's Theorem.
The main thing for our immediate purpose is that you can multiply a ratings
ballot by any positive number without changing its contribution to the Nash
or Ultimate lottery probability.
-km