[EM] Simmons' multiwinner schemes based on ssf(x) ("Simmons staircase function")

Forest Simmons fsimmons at pcc.edu
Mon Dec 12 14:31:19 PST 2016


In the end game the compression factor should have been (1 - c) instead of
c, so the final result would be

Q2 = c +(1 - c)*Q1, which makes more sense.

It's hard to get these details right under pressure of time☺

Forest

On Mon, Dec 12, 2016 at 1:43 PM, Forest Simmons <fsimmons at pcc.edu> wrote:

> 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/777a9dce/attachment.htm>


More information about the Election-Methods mailing list