[EM] Simmons' multiwinner schemes based on ssf(x) ("Simmons staircase function")
Forest Simmons
fsimmons at pcc.edu
Mon Dec 12 13:43:08 PST 2016
Here's a couple of additional examples based on the quality gauge given by
Q = integral over 0<x<1 of G(x)^(1/G(x))
We have already established that if G(x) is constantly p, then Q = p^(1/p),
which is the case when a faction making up fraction p of the population
gives full approval to the winner, and no other faction approves the winner.
And when every faction has precise approval of c, then G(x) is 100% for x
between zero and c, else zero. So Q is integral over x between zero and c
of 1, which is just c.
So a candidate with 100 percent approval on fifty percent of the ballots
gets a value of Q equal to .5^2, or 25 percent, while a candidate rated
fifty percent on 100 percent of the ballots gets a Q value of .5
The geometric mean of these two values is the square root of two divvided
by four, or about 35 percent.
Lets compare this with the Q value of a candidate whose ratings are
distributed uniformly between zero and one: in this cas the distribution
function satisfies F(x)=x.
So G(x) = 1 - x, and Q = integral over x between zero and one of
(1-x)^(1/(1-x)), which also turns out to be about 35 percent.
That makes sense considering that a uniform distribution is about halfway
between the all at fifty percent and half at 100 percent.
The more you play around with this quality gauge the more robust and
resilient it seems to be.
Now for the strong PR condition (on the assumption of weak PR).
Suppose that f2(x) = (c + (1-c)*f1(x)), then the respective distribution
functions are given by
G1(x) = Lambda[f1(x)>x)] and G2(t)=Lambda[c+(1-c)f(t)>t], where Lambda is
the Lebesgue measure operator.
I claim that the graph of G2(t) is constantly unity for 0<t<c, and
thereafter (for c<t<1) it is a replica of the graph of G1 horizontally
compressed by a factor of c:
For c<t<1, G2(t) = G1(t/c).
So Q2 = c + c*Q1.
It seems to me that this is precisely what is needed for strong PR, given
weak PR.
Check me on this!
Forest
On Mon, Dec 12, 2016 at 1:00 PM, Forest Simmons <fsimmons at pcc.edu> wrote:
> I think I have a way around the problem: make sure that the integrand does
> not rely explicitly on x, i.e. that it only relies on x through the
> cumulative distribution function F(x). Then the stair steps will adjust
> automatically to the strong PR condition given weak PR.
>
> So here's my current best guess for an "holy grail" PR quality gauge:
>
> Q = integral over 0<x<1 of H(G(x)),
>
> where where G(x) = 1 - F(x), and H(p)=p^(1/p).
>
> Why this choice of H ?
>
> It is qualitatively right, in that (1) H(p) = 1 when p = 1, and (2) the
> graph of y = H(p) has infinite contact with the p-axis (y = 0) at p= 0
> (limits from the right).
>
> This second condition is necessary because of the following considerations:
>
> Suppose that in a ten seat election the electorate is partitioned into ten
> equal sized factions, each of which is single-mindedly running its own set
> of ten candidates, i.e. each voter approves precisely (i.e. those and only
> those) ten candidates put forth by her own faction.
>
> Think of two extremes in the distribution of winners: (1) there is one
> from each faction. (2) all of the winners are from only one faction, say
> the first faction.
>
> What should be the corresponding values of Q?
>
> The value of Q for the first distribution should be about 10 percent,
> since each voter gets ten percent of her wish list. The value for the
> second distribution should be much smaller. How much smaller?
>
> Think of converting the first distribution into the second one by
> replacing winners one-by-one from the single winner factions with
> additional winners for the first faction.
>
> This process takes nine steps, and each step should decrease the quality Q
> by an order of magnitude, i.e. by a factor of ten.
>
> If the starting value of Q was 1/10, then the final value should be
> (1/10)^10, or p^(1/p) where p = 1/10.
>
> The same reasoning works when p = 1/n for n > 10. Q would go from a value
> of 1/n to 1/(n^n) which is the same as p^(1/p).
>
> So necessarily H(p) must be on the order of p^(1/p) for small p.
>
> So that is a necessary condition. Is it also sufficient to make the Q
> defined by this function H into a strong PR quality gauge?
>
> I hope that it is sufficient.
>
> Time will tell.
>
> Forest
>
>
> Date: Sat, 10 Dec 2016 11:24:14 -0800
>> From: Forest Simmons <fsimmons at pcc.edu>
>> To: Warren D Smith <warren.wds at gmail.com>, Jobst Heitzig
>> <jobst.heitzig at posteo.de>, Andy Jennings <
>> abjennings at gmail.com>,
>> Kristofer Munsterhjelm <km_elmet at t-online.de>, EM
>> <election-methods at lists.electorama.com>
>> Subject: Re: [EM] Simmons' multiwinner schemes based on ssf(x)
>> ("Simmons staircase function")
>> Message-ID:
>> <CAP29oncUs0L8a594XM_fwsx4GkswdLb6LgiQcogFD7r2jOLUww at mail.gm
>> ail.com>
>> Content-Type: text/plain; charset="utf-8"
>>
>>
>> Warren makes a good point here about the difficulty if not impossibility
>> of
>> achieving "strong PR" with a distribution based method along the lines of
>> what I proposed.
>>
>> After thinking about that I decided to try a linear decreasing density
>> function that does re-scale correctly, giving a Quality gauge
>>
>> Q = integral over 0<x<1 of (1-x)G(x)
>>
>> where G(x) is the percentage of ballot expectations greater than x.
>>
>> It turns out that (as Warren sugests) this is precisely equivalent to a
>> method that is just a sum over sum function of the individual ballot
>> expectations, one that we had already tried, namely
>>
>> Q = 1 - Sum over all ballots B in beta of E(B)-1)^2/#beta
>>
>>
>> If we restrict our search to methods of the type
>>
>> Q = Integral over x from zero to one of f(x)*G(x)
>>
>> then for f(x) to yield proportionality, it is necessary that when p+q=1,
>> then p*f(p)=q*f(q). One way to achieve this is for f(p) = 1/p .
>> Unfortunately, this is undefined at p = 0, and tends to give a divergent
>> integral.
>>
>> Another way to achieve this is to use the constraint p + q = 1 to re-write
>> p*f(p)=q*f(q) as (1-q)*f(p)=(1-p)*f(q), which will be satisfied as long
>> as
>> f(x) = 2 - 2x, for example.
>>
>> The condition for strong PR (given PR) is a rescaling condition: for each
>> positive c less than one, there must exist c2 and c3 such that
>>
>> f(x/c2+c)/c3 = f(x)
>>
>> This works for f(x) = 2 - 2x, but unfortunately the PR property appears to
>> hold only for two factions: If we have three, and if p + q + r = 1, then
>> we need pf(p)=qf(q)=r(f(r). In this case the substitution trick no longer
>> works. Is there another way to bypass this obstacle?
>>
>>
>>
>> On Thu, Dec 8, 2016 at 8:55 AM, Warren D Smith <warren.wds at gmail.com>
>> wrote:
>>
>> > I should have been clearer about the complaint I had in mind.
>> > I'll now try.
>> >
>> > It seems to me that ANY quality-function Q of the form
>> >
>> > Q = integral(x=0 to 1)of G( ssf(x), x ) dx
>> >
>> > where G(a,b) is any formula whatsoever,
>> > must fail to provide "strong PR."
>> >
>> > Why? Well, if we add "commonly rated candidates" to the picture,
>> > that cuts the ssf(x) staircase into two pieces (cut at the common
>> rating x)
>> > and rescales and repositions those two, with a new stairstep in between.
>> >
>> > To get strong PR, you need maximizing Q based on the G(ssf(x), x)
>> > function
>> > to act the same on those two cut staircase pieces, as it does on the
>> > original whole
>> > staircase, so that we still get PR on the
>> > NON-commonly-rated-subset of the candidates
>> > just like we did before. Since that is what "strong PR" means.
>> >
>> > Well, seems to me that simply does not happen... except for some
>> > trivial e.g. linear
>> > G formulae, which however failed to provide PR in the first place.
>> >
>> > You can also try using the inverse of the ssf(x) function in your
>> > definition of
>> > Q, and I tried a few games of that ilk, but it looked to me
>> > like you always lose. I.e. always necessarily fail to achieve "strong
>> PR."
>> >
>> > Am I confused? I might be: this argument I just made
>> > trying to refute you, is kind of a self-similarity argument.
>> > I.e. it argues that after the "cut the staircase into two then
>> > rescale & reposition pieces" operation, that maximizing Q
>> > has to behave the same, i.e. these operations need to
>> > be symmetries, sort of. Then it says: they ain't.
>> >
>> > However, you could fight back by arguing that you
>> > are only going to care (for PR purposes) about approval-style
>> > range voting only.
>> > In which case, the whole self-similarity argument I was trying
>> > to make, is about intermediate scores (between 0 and 1,
>> > non-approval-style) whose existence you just deny.
>> >
>> > In that case, you might be ok, with the right G(a,b) functions.
>> >
>> > --------
>> >
>> > Also, I'm not sure why writing Q's in this kind of way using integrals,
>> > is necessarily more desirable than the old ways we had of trying
>> > to write Q's using sums over all ballots and/or candidates,
>> > of functions of scores.
>> >
>> >
>> > --
>> > Warren D. Smith
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20161212/eced5a2f/attachment-0001.htm>
More information about the Election-Methods
mailing list