Re: Request for comments [voting amendment]

[Anthony Towns]

On Sat, Nov 16, 2002 at 05:54:59AM +0100, Matthias Urlichs wrote:
> > > Another alternative might have been to have the default option win if
> > > it's _ever_ a member of the Scwartz set, rather than if it's a member
> > > of the Schwartz set after the sequential dropping phases are complete.
> That rule might be equivalent to the "drop all options defeated by the
> default option" rule, or it might not be. I think it is, based on gut
> feeling, but I don't know.

It's not. Consider the case where there are three options:

A, B, D

D being the default option. Suppose people vote:

40 A B D
30 B D A
20 D A B

then we end up with:

60:30 A > B
70:20 B > D
50:40 D > A

thus eliminating A, and having B win, although if you went through the
SSD process you'd eliminate D>A, and A would win.

If the 30 people who'd voted "BDA" weren't sincere in that choice,
and really meant "BAD", then that's allowing strategic voting to ensure
their candidate wins. I'm not really sure that's such a bad thing, since
it requires a majority of voters to engage in the tactic of ranking
the default option above some other option, and even if you declare
the above vote to have no result and go back to further discussion it
doesn't stop the same 50 people ensuring A continues to not win (which
is desirable -- if a majority of developers don't want to do something,
they should be able to make sure that we don't do it).

If people start taking this plan too seriously, we just end up with votes
like:

40 A D B
30 B D A
20 D A B

with
60:30 A > B
50:40 D > A
60:30 D > B

and all our votes end up without results.

> I'd rather run the algorithm with the full set of votes first, and _then_,
> if the default option wins, have a separate rule on what to do next.

Nope: see the first vote listed above. You _don't_ want to declare a
result when the majority of developers would prefer further discussion
or "none of the above". I suppose you could hack things so that "the
default option defeats X" is never considered the weakest defeat, but
I'm not sure that would do you much good.

Cheers,
aj

-- 
Anthony Towns <[EMAIL PROTECTED]> 
I don't speak for anyone save myself. GPG signed mail preferred.

 ``If you don't do it now, you'll be one year older when you do.''


pgpOZ4eUIYoS8.pgp
Description: PGP signature

Re: voting mechanics draft update

[Anthony Towns]

On Sat, Nov 16, 2002 at 05:23:13AM +0100, Matthias Urlichs wrote:
> >v. If this new Schwartz set contains only one option, that
> >   option wins.
> > 
> As per the definition, there is no such thing as a one-option Schwartz
> set, so actually you'll have to restart with step 5. You might therefore
> replace the last two sections with a simple

]   i. All options not in the Schwartz set are eliminated.
]
]  Definition: An option C is in the Schwartz set if there is no 
]  other option D such that D transitively defeats C AND C does
]  not transitively defeat D.

Uh, if C is the Condorcet winner, or becomes the Condorcet winner after
ignoring some defeats of it, the Schwartz set has only one option.

Consider the vote:
20 A B C D
30 B C A D
40 C A B D
the weakest defeat is C > A (50:40), which gets eliminated leaving A >
B and B > C (and A,B,C > D), and the second Schwartz set is {A}.

Cheers,
aj

-- 
Anthony Towns <[EMAIL PROTECTED]> 
I don't speak for anyone save myself. GPG signed mail preferred.

 ``If you don't do it now, you'll be one year older when you do.''

Re: Request for comments [voting amendment]

[Matthias Urlichs]

Hi,

Anthony Towns:
> > I'd rather run the algorithm with the full set of votes first, and _then_,
> > if the default option wins, have a separate rule on what to do next.
> 
> Nope: see the first vote listed above. You _don't_ want to declare a
> result when the majority of developers would prefer further discussion
> or "none of the above".

Thanks for the counter-example; I retract my statement.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/


pgpXqnRC8KJ0W.pgp
Description: PGP signature

Re: voting mechanics draft update

[Jochen Voss]

Hello,

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
>   Definition: An option F transitively defeats an option G if G
>   defeats F or if there is some other option H where H defeats
>   G AND F transitively defeats H.

There is a mistake: "... if G defeats F ..." should be replaced by
"... if F defeats G ...".

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpRc9gEixZJH.pgp
Description: PGP signature

Re: voting mechanics draft update

[Jochen Voss]

Hello

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
>Definition: A proposition is a defeat, or a pair of options
>where both have received votes explicitly comparing the two
>options but neither option is able to defeat the other.

Sorry, but I do not understand this definition at all.

Is a proposition a pair of options with special properties?
And in this case: does "A proposition is a defeat" mean,
that a pair of options A and B where one defeats the other
is a proposition?

Confused,
Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpnHRM2LXQQz.pgp
Description: PGP signature

Re: voting mechanics draft update

[Jochen Voss]

Hello,

even more confusion on my side :-(

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> 1. Each ballot orders the options being voted on in the order
>specified by the voter.  If the voter does not rank some options,
>this means that the voter prefers all ranked options over the
>unlisted options.  Any options unranked by the voter are treated
>as being equal to all other unranked options.

What does "Any options unranked by the voter are treated as
being equal to all other unranked options." mean?  How does
it differ from "All unranked options are treated as being
equal"?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpL8v19CzjGY.pgp
Description: PGP signature

Attempt at logical english definition for CSSD (using beatpath winner).

[Clinton]

Heres an attempt to describe the winner of a CSSD election logically, 
using the beatpath winner implimentation. I've tryed to structure it so 
that removing the parenthesis gives a plain english definition. Any 
comments would be appresiated.


---

In the following definition all occurances of A and B refer to options.

(A is prefered over B on vote X) if
   (A is ranked higher than B on vote X) OR
   ((A is ranked on vote X) AND (B is not ranked on vote X))

(A beats B by X) if
   (X > 0) where
   X = number of unique votes Y such that (A is prefered over B on vote 
Y) -

   number of unique votes Z such that (B is prefered over A on vote Z)

(A has a beatpath to B by X) if
   (A beats B by X)

(A has a beatpath to B by X) if
   (A beats C by Y) AND (C has a beatpath to B by Z) where
   X = minimum of Y and Z

(A has a strongest beatpath to B by X) where
   Z is the set of unique elements Y such that (A has a beatpath to B by Y)
   X = largest element of Z, 0 if Z is empty.  


(A has a beatpath win to B) if
   (A has a strongest beatpath to B by Y) AND
   (B has a strongest beatpath to A by Z) AND
   (Y > Z)

(A is tied winner) if
   there is no B such that (B has a beatpath win to A)

(A is a winner) if
   there is no B such that (B is prefered over A on the casting vote)

---

Clinton

Re: Another draft of A.6

[Raul Miller]

On Fri, Nov 15, 2002 at 09:48:55PM -0500, Branden Robinson wrote:
> I am sorry if this tries your patience, but I do not understand this
> statement.  Can you give an example with numbers?  Specifically, I don't
> understand what would distinguish a "weak" pairwise tie from a non-weak
> one.

Well.. I'm not actually sure how to cook up a set of ballots which
gives me a non-weak tie.

However, consider the following propositions:

  125:29  D:E
  117:37  B:C
  117:37  A:B
  116:38  F:A
  116:20  E:F
  107:47  C:D
  105:49  D:F
   98:56  A:C
   96:58  E:A
   96:58  C:E
   88:66  F:B
   88:66  B:D
   85:69  D:A
   78:76  F:C
   77:77  E:B
   77:77  B:E

77:77 is a weak proposition since every other proposition has more
than 77 votes on one side of the comparison.

77:77 is also the weakest proposition since no proposition with 77
votes has more than 77 opposing votes.  Obviously, if a tie is a weak
proposition, it has to be the weakest proposition.

If there had been a proposition like 76:75, then 77:77 wouldn't
be a weak proposition, because 76 is less than 77.

Does that help any?

-- 
Raul

Re: voting mechanics draft update

[Raul Miller]

Raul Miller:
> >iv. If eliminating the weakest propositions would not eliminate
> >all votes, a new Schwartz set is found based on the newly
> >revised set of propositions.

On Sat, Nov 16, 2002 at 05:23:13AM +0100, Matthias Urlichs wrote:
> Note that ALL propositions are considered here, not just those
> participating in the Schwartz set.

Hmm.. that's not what I was trying to say.  Thanks.

> >v. If this new Schwartz set contains only one option, that
> >   option wins.
> > 
> As per the definition, there is no such thing as a one-option Schwartz
> set, so actually you'll have to restart with step 5. You might therefore
> replace the last two sections with a simple

Hmm... I think Isee what you mean.  Thanks again.

-- 
Raul

Re: voting mechanics draft update

[Raul Miller]

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> >   Definition: An option F transitively defeats an option G if G
> >   defeats F or if there is some other option H where H defeats
> >   G AND F transitively defeats H.
> 
On Sat, Nov 16, 2002 at 09:04:42AM +0100, Jochen Voss wrote:
> There is a mistake: "... if G defeats F ..." should be replaced by
> "... if F defeats G ...".

*blush*  Oops.

Thanks.

> On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> >Definition: A proposition is a defeat, or a pair of options
> >where both have received votes explicitly comparing the two
> >options but neither option is able to defeat the other.

On Sat, Nov 16, 2002 at 09:11:37AM +0100, Jochen Voss wrote:
> Sorry, but I do not understand this definition at all.
> 
> Is a proposition a pair of options with special properties?
> And in this case: does "A proposition is a defeat" mean,
> that a pair of options A and B where one defeats the other
> is a proposition?

I'll try to come up with a better definition.  A proposition is
a pair of options where there are votes which mention one of
the options over the other.

> On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> > 1. Each ballot orders the options being voted on in the order
> >specified by the voter.  If the voter does not rank some options,
> >this means that the voter prefers all ranked options over the
> >unlisted options.  Any options unranked by the voter are treated
> >as being equal to all other unranked options.

On Sat, Nov 16, 2002 at 09:20:15AM +0100, Jochen Voss wrote:
> What does "Any options unranked by the voter are treated as
> being equal to all other unranked options." mean?  How does
> it differ from "All unranked options are treated as being
> equal"?

I was trying to say zero votes without saying zero votes.  Obviously
that was a mistake.

Thanks.

-- 
Raul

Re: Attempt at logical english definition for CSSD (using beatpath winner).

[Raul Miller]

On Sun, Nov 17, 2002 at 03:47:01AM +1100, Clinton wrote:
> Heres an attempt to describe the winner of a CSSD election logically, 
> using the beatpath winner implimentation. I've tryed to structure it so 
> that removing the parenthesis gives a plain english definition. Any 
> comments would be appresiated.

I'd like to see a version of this which is written in english (with no
non-alphabetic symbols with mathematical significance, such as "()>=-",
and with proper grammar).

I think I've almost got the language nailed down for the version I'm
proposing, but even if yours doesn't come out to be shorter and easier
to understand than mine, just seeing how somebody else expresses these
concepts can help.

Thanks,

-- 
Raul

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Raul Miller:
> On Sat, Nov 16, 2002 at 05:23:13AM +0100, Matthias Urlichs wrote:
> > Note that ALL propositions are considered here, not just those
> > participating in the Schwartz set.
> 
> Hmm.. that's not what I was trying to say.  Thanks.
> 
The reason for this to be a problem is that the dropping step only considers
the _innermost_ Schwartz set. There may be more than one, though off-hand
I couldn't invent a suitable example -- I'm sure one exists in the
literature somewhere, though.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/

Nov 16 draft of voting mechanics

[Raul Miller]

More silliness fixed:  The word "tie" is now only used in one context.
The definition of "transitive defeats" is fixed.  The language defining
propositions has been cleaned up.

If anyone feels that draft is too hard to understand, please write me
a letter indicating the first part that you have trouble understanding,
and something about the nature of the problem you're having.


  A.6 Vote Counting

1. Each ballot orders the options being voted on in the order
   specified by the voter.  If the voter does not rank some options,
   this means that the voter prefers all ranked options over the
   unlisted options.  Any options unranked by the voter are treated
   as being equal to all other unranked options.

2. Options which do not defeat the default option are eliminated.

   Definition: Option A defeats option B if more voters prefer A
   over B than prefer B over A.

3. If an option has a quorum requirement, that option must defeat
   the default option by the number of votes specified in the quorum
   requirement, or the option is eliminated.

4. If an option has a supermajority requirement, that option must
   defeat the default option by the ratio of votes specified in the
   supermajority requirement, or the option is eliminated.  That is,
   if a an option has a 2:1 supermajority requirement, then there
   must be twice as many votes which prefer that option over the
   default option than there are votes which prefer the default
   option over that option.

5. If one remaining option defeats all other remaining options,
   that option wins.

6. If more than one option remains after the above steps, we use
   Cloneproof Schwartz Sequential Dropping to eliminate any cyclic
   ambiguities and then pick the winner.  This procedure and must
   be carried out in the following order:

   i. All options not in the Schwartz set are eliminated.

  Definition: An option C is in the Schwartz set if there is no
  other option D such that D transitively defeats C AND C does
  not transitively defeat D.

  Definition: An option F transitively defeats an option G if F
  defeats G or if there is some other option H where H defeats
  G AND F transitively defeats H.

   ii. Unless this would eliminate all options in the Schwartz set,
   the weakest propositions are eliminated.

   Definition: A proposition is a pair of options J and K
   from the Schwartz set which are considered along with
   the number of voters who prefer J to K and the number
   of voters who prefer K to J.

   Definition: The dominant strength of a proposition is the
   count of votes in a proposition which is not smaller than
   the other vote count in that proposition.

   Definition: a weak proposition is a proposition which
   has a dominant strength greater than zero and no larger
   than that of any other proposition.

   Definition: a weakest proposition is a weak proposition where
   the vote count in the proposition which is not larger than
   the other vote count is also no smaller than that of any
   other weak proposition.

   Definition: A proposition is eliminated by treating both
   of its vote counts as zero from this point forward.

   iii. If eliminating the weakest propositions would eliminate all
votes represented in the Schwartz set, a tie exists and the
person with the casting vote picks from among the options
represented in this Schwartz set.

   iv. If eliminating the weakest propositions would not eliminate
   all votes, a new Schwartz set is found based on the newly
   revised set of propositions.

   v. If this new set of propositions allows one option to 
  defeat all other options in the Schwartz set, that
  option wins.

   vi. Otherwise, these steps (i-vi) are repeated with this new
   Schwartz set.


Thanks,

-- 
Raul

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Anthony Towns:
> > >v. If this new Schwartz set contains only one option, that
> > >   option wins.
> > > 
> > As per the definition, there is no such thing as a one-option Schwartz
> > set

> Uh, if C is the Condorcet winner, or becomes the Condorcet winner after
> ignoring some defeats of it, the Schwartz set has only one option.

Actually you're right, the definition allows that. I was thinking not of
the definition but of the list of steps we're going through, and we're
using the "if there's a clear winner, then we're done, else build a
Schwartz set" method, as opposed to the equivalent "build a Schwartz set,
and if that has only one member, that's the winner" procedure.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/


pgpB0Aqgp1jrx.pgp
Description: PGP signature

Re: voting mechanics draft update

[Raul Miller]

On Sat, Nov 16, 2002 at 06:56:37PM +0100, Matthias Urlichs wrote:
> The reason for this to be a problem is that the dropping step only considers
> the _innermost_ Schwartz set. There may be more than one, though off-hand
> I couldn't invent a suitable example -- I'm sure one exists in the
> literature somewhere, though.

The Schwartz set is the set of innermost unbeatened sets.  There cannot
be more than one Schwartz set at any one time for any one set of votes.

See http://www.barnsdle.demon.co.uk/vote/condor2.html for a more extensive
discussion of this subject.

Or, if  you think I'm wrong, please explain your reasoning in more depth.

Thanks,

-- 
Raul

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello,

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 1. [...] Any options unranked by the voter are treated
>as being equal to all other unranked options.
I still do not understand the "other unranked options".
Could we simply write "Any options unranked by the voter are treated
as being equal" or would this be something else.

> 6. [...] This procedure and must be carried out in the following order:
  ^^^
The "and" seems spurious to me.

I'm getting further with the draft.  Especially I understand
"proposition" and "weak proposition", now.  But ...

>Definition: a weakest proposition is a weak proposition where
>the vote count in the proposition which is not larger than
>the other vote count is also no smaller than that of any
>other weak proposition.
... this is hard stuff.  What about "minimum of the two vote counts"
instead of "the vote count in the proposition which is not larger than
the other vote count"?

I seem to understand the remaining parts of the text :-)

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgptlWOUvHpq5.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Raul Miller]

Hello,
> On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> > 1. [...] Any options unranked by the voter are treated
> >as being equal to all other unranked options.

On Sat, Nov 16, 2002 at 07:47:39PM +0100, Jochen Voss wrote:
> I still do not understand the "other unranked options".
> Could we simply write "Any options unranked by the voter are treated
> as being equal" or would this be something else.

That sounds fine.

Thanks.

> > 6. [...] This procedure and must be carried out in the following order:
>   ^^^
> The "and" seems spurious to me.

Yes.

> I'm getting further with the draft.  Especially I understand
> "proposition" and "weak proposition", now.  But ...
> 
> >Definition: a weakest proposition is a weak proposition where
> >the vote count in the proposition which is not larger than
> >the other vote count is also no smaller than that of any
> >other weak proposition.
> ... this is hard stuff.  What about "minimum of the two vote counts"
> instead of "the vote count in the proposition which is not larger than
> the other vote count"?

I think that would be fine.

Thanks again,

-- 
Raul

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 2. Options which do not defeat the default option are eliminated.
> 
>Definition: Option A defeats option B if more voters prefer A
>over B than prefer B over A.

Is the default option supposed to be in the list of options for which
we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
should replace "Options" by "Non-default options" in this paragraph?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpdgSGt7nb6Y.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello again!

Another one:

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 3. If an option has a quorum requirement, that option must defeat
>the default option by the number of votes specified in the quorum
>requirement, or the option is eliminated.

We did not define the term "defeat by a number of votes".  If the
quorum requirement is Q, does this mean that at least Q votes must
prefer the option over the default option?  Or does it mean that the
number of votes which prefer the option in question over the default
option must exceed the number of votes which prefer the default option
over the current option by at least Q?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgptwU95Vt1IU.pgp
Description: PGP signature

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Raul Miller:
> The Schwartz set is the set of innermost unbeatened sets.  There cannot
> be more than one Schwartz set at any one time for any one set of votes.
> 
> See http://www.barnsdle.demon.co.uk/vote/condor2.html for a more extensive
> discussion of this subject.
> 
Thanks for the link.

> Or, if  you think I'm wrong, please explain your reasoning in more depth.
> 
No you aren't, we're just not used to talking about that topic and thus
misunderstandings creep up when we aren't looking.  ;-)

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/

Re: Nov 16 draft of voting mechanics

[Matthias Urlichs]

Hi,

Raul Miller:
>Definition: The dominant strength of a proposition is the
>count of votes in a proposition which is not smaller than
>the other vote count in that proposition.
> 
Please replace "not smaller" with "larger or equal to", and vice versa,
throughout the text. Those negatives make thinking about whatever it is
that the text actually means ;-) more difficult.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sat, Nov 16, 2002 at 09:31:08PM +0100, Jochen Voss wrote:
> Is the default option supposed to be in the list of options for which
> we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
> should replace "Options" by "Non-default options" in this paragraph?

For an option to be in the Schwartz set, it must either tie or 
beat at least one other option in the Schwartz set.

The default option can never be in the Schwartz set, because any
option which does not defeat the default option is eliminated
before the first Schwartz set is created..

Thanks,

-- 
Raul

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sat, Nov 16, 2002 at 10:47:43PM +0100, Matthias Urlichs wrote:
> Please replace "not smaller" with "larger or equal to", and vice versa,
> throughout the text. Those negatives make thinking about whatever it is
> that the text actually means ;-) more difficult.

Actually, based on a suggestion by Jochen Voss, I'm planning on
changing the "not smaller" language with a phrase using "maximum".

Thanks,

-- 
Raul

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello Raul,

trying to actually implement the algorithm from the draft turns out to
be a good test :-)

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
>ii. Unless this would eliminate all options in the Schwartz set,
>the weakest propositions are eliminated.
>[...]
>
>Definition: A proposition is eliminated by treating both
>of its vote counts as zero from this point forward.
> 
>iii. If eliminating the weakest propositions would eliminate all
> votes represented in the Schwartz set, a tie exists [...]

What does "eliminate all options" and "eliminate all votes" mean
in this context?  Could we formalise this?

Example: (X is the default option)

ABCDX
   A-   24   17   25   31
   B   25-   26   24   29
   C   31   24-   31   30
   D   25   26   18-   27
   X   15   18   15   18-

If my algorithm is correct, than just before step 6.ii the
Schwartz set consists of options B, C, and D and the
weakest propositions are (B,C) and (B,D).

This leads to the following new matrix:

 BCD 
   B -00 
   C 0-   31 
   D 0   18- 

I guess that C is the winner here.  But what condition should my
program check to see whether "this would eliminate all options in the
Schwartz set"?  Maybe whether all entries in the matrix become zero?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpJu9AZ2QHrP.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello Raul,

On Sat, Nov 16, 2002 at 05:44:40PM -0500, Raul Miller wrote:
> On Sat, Nov 16, 2002 at 09:31:08PM +0100, Jochen Voss wrote:
> > Is the default option supposed to be in the list of options for which
> > we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
> > should replace "Options" by "Non-default options" in this paragraph?
> 
> For an option to be in the Schwartz set, it must either tie or 
> beat at least one other option in the Schwartz set.
> 
> The default option can never be in the Schwartz set, because any
> option which does not defeat the default option is eliminated
> before the first Schwartz set is created..
Ok, this is a proof.

But the change I suggested above would make a (theoretical) difference
nevertheless: if the default option could survive step 2 it could
become the winner in step 5.  If the default option cannot survive
step 2, it never could become the winner.

Do we intend that the default option actually can win the vote?
Am I correct that this only could happen via step 5?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html


pgpmRz7rxSRlC.pgp
Description: PGP signature

example implementation of the new voting machinery draft

[Jochen Voss]

Hello,

I spent some time implementing the voting mechanism as described
in Rauls draft.  Maybe this is useful for somebody who wants to
play with the new voting system.

I append a preliminary version of the program here.  The second
attachment is an example input file.  The program is modelled
closely after the voting mechanics draft.  It not meant to be
fast or efficient.  My priority was to correctly implement the
behaviour as described by the current draft.

Some code is missing (see my other mails to this list).  Questions,
which come into mind are:

1) Did I understand the voting draft correctly?
2) Is my implementation correct.
3) What should I fill in for the missing pieces.

I would be glad to receive comments about the program.

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html
#! /usr/bin/env python
# vote.py - implement the voting mechanism form the Debian constitution
#
# Copyright 2002  Jochen Voss <[EMAIL PROTECTED]>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

import sys, fileinput
from copy import copy

options=['A', 'B', 'C', 'D', 'X']
default='X'
quorum={}
supermajority={}

# You may set some quorum or supermajority here, e.g.
#quorum['A']=15
#supermajority['B']=2.0/1.0

##
# 1. Each ballot orders the options being voted on in the order
#specified by the voter.  If the voter does not rank some options,
#this means that the voter prefers all ranked options over the
#unlisted options.  Any options unranked by the voter are treated
#as being equal to all other unranked options.

votecount={}
for o1 in options:
for o2 in options: votecount[o1+o2]=0

def print_propositions():
"Print the vote counts in tabular form."
print
print "",
for o2 in options:
print " %3s"%o2,
print
for o1 in options:
print "%4s"%o1,
for o2 in options:
if o1==o2:
print "   -",
else:
print " %3d"%votecount[o1+o2],
print

def register_vote(str):
"""Feed a single vote into the data structures.
STR must be a word, composed of option letters.
The value AB, for example indicates that A is prefered
over everything, B is prefered over all unlisted options,
and all unlisted options are equal."""
for o in str:
if not o in options: raise "invalid option '%s'"%o
for i in range(0,len(str)-1):
o1=str[i]
for o2 in str[i+1:]: votecount[o1+o2]+=1
for o2 in options:
if o2 in str: continue
for o1 in str: votecount[o1+o2]+=1

## Read the votes, either from stdin or from file.
for line in fileinput.input():
if line[0] == "#": continue
register_vote(line.strip())

print_propositions()

##
# 2. Options which do not defeat the default option are eliminated.

# Definition: Option A defeats option B if more voters prefer A over B
#than prefer B over A.
def defeats(o1,o2):
return votecount[o1+o2]>votecount[o2+o1]

active=[]
for o in options:
if defeats(o,default):
active.append(o)
else:
print "option %s does not defeat default option -> eliminated"%o
options=active

##
# 3. If an option has a quorum requirement, that option must defeat
#the default option by the number of votes specified in the quorum
#requirement, or the option is eliminated.

# TODO: is this correct?
def matches_quorum(o,q):
return votecount[o+default]>votecount[default+o]+q

active=[]
for o in options:
if (o not in quorum) or matches_quorum(o,quorum[o]):
active.append(o)
else:
print ("option %s does not match "%o
   + "the quorum requirement (%d)"%quorum[o]
   + " -> eliminated")
options=active

##
# 4. If an option has a supermajority requirement, that option must
#defeat the default option by the ratio of votes specified in the
#supermajority requirement, or the option is eliminated.  That is,
#if a an option has a 2:1 supermajority requireme

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sun, Nov 17, 2002 at 12:12:53AM +0100, Jochen Voss wrote:
> trying to actually implement the algorithm from the draft turns out to
> be a good test :-)

Ok.  Note that I've not sat down and read your implementation, yet.

> On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> >ii. Unless this would eliminate all options in the Schwartz set,
> >the weakest propositions are eliminated.
> >[...]
> >
> >Definition: A proposition is eliminated by treating both
> >of its vote counts as zero from this point forward.
> > 
> >iii. If eliminating the weakest propositions would eliminate all
> > votes represented in the Schwartz set, a tie exists [...]
> 
> What does "eliminate all options" and "eliminate all votes" mean
> in this context?  Could we formalise this?

Uh... 

> Example: (X is the default option)
> 
> ABCDX
>A-   24   17   25   31
>B   25-   26   24   29
>C   31   24-   31   30
>D   25   26   18-   27
>X   15   18   15   18-

Just as a note: in my view of the world, where you put a "-",
I'd put a "0".  In principle this shouldn't matter, but maybe
that has something to do with what you consider ambiguous?

> If my algorithm is correct, than just before step 6.ii the
> Schwartz set consists of options B, C, and D and the
> weakest propositions are (B,C) and (B,D).

I ran through the steps by hand, and I agree.  [You didn't say,
but the rows in your matrix have to represent the vote count "for"
an option, and the columns the vote count "against", otherwise
the default option would defeat everything else.]

Out of curiosity, how did you generate that set of tallies?  Did you start
from some set of ballots, or did you just randomly generate some numbers?

> This leads to the following new matrix:
> 
>  BCD 
>B -00 
>C 0-   31 
>D 0   18- 
> 
> I guess that C is the winner here.  But what condition should my
> program check to see whether "this would eliminate all options in the
> Schwartz set"?  Maybe whether all entries in the matrix become zero?

I had meant to change ii. so that it read something like:

"Unless this would eliminate all vote counts in the propositions of the
Schwartz set, the vote counts of the weakest propositions are eliminated."

Is that better?

Thanks,

-- 
Raul

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sun, Nov 17, 2002 at 12:23:11AM +0100, Jochen Voss wrote:
> Do we intend that the default option actually can win the vote?
> Am I correct that this only could happen via step 5?

You're right, I should it so that the default option doesn't need to
defeat the default option.

The interpretation that the default option could eliminate itself might
work, but I'd prefer less ambiguity.

Thanks,

-- 
Raul

Re: voting mechanics draft update

[Jochen Voss]

Hello,

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
>   Definition: An option F transitively defeats an option G if G
>   defeats F or if there is some other option H where H defeats
>   G AND F transitively defeats H.

There is a mistake: "... if G defeats F ..." should be replaced by
"... if F defeats G ...".

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01949/pgp0.pgp
Description: PGP signature

Re: voting mechanics draft update

[Jochen Voss]

Hello

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
>Definition: A proposition is a defeat, or a pair of options
>where both have received votes explicitly comparing the two
>options but neither option is able to defeat the other.

Sorry, but I do not understand this definition at all.

Is a proposition a pair of options with special properties?
And in this case: does "A proposition is a defeat" mean,
that a pair of options A and B where one defeats the other
is a proposition?

Confused,
Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01950/pgp0.pgp
Description: PGP signature

Re: voting mechanics draft update

[Jochen Voss]

Hello,

even more confusion on my side :-(

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> 1. Each ballot orders the options being voted on in the order
>specified by the voter.  If the voter does not rank some options,
>this means that the voter prefers all ranked options over the
>unlisted options.  Any options unranked by the voter are treated
>as being equal to all other unranked options.

What does "Any options unranked by the voter are treated as
being equal to all other unranked options." mean?  How does
it differ from "All unranked options are treated as being
equal"?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01951/pgp0.pgp
Description: PGP signature

Attempt at logical english definition for CSSD (using beatpath winner).

[Clinton]

Heres an attempt to describe the winner of a CSSD election logically, 
using the beatpath winner implimentation. I've tryed to structure it so 
that removing the parenthesis gives a plain english definition. Any 
comments would be appresiated.

---

In the following definition all occurances of A and B refer to options.

(A is prefered over B on vote X) if
   (A is ranked higher than B on vote X) OR
   ((A is ranked on vote X) AND (B is not ranked on vote X))

(A beats B by X) if
   (X > 0) where
   X = number of unique votes Y such that (A is prefered over B on vote 
Y) -
   number of unique votes Z such that (B is prefered over A on vote Z)

(A has a beatpath to B by X) if
   (A beats B by X)

(A has a beatpath to B by X) if
   (A beats C by Y) AND (C has a beatpath to B by Z) where
   X = minimum of Y and Z

(A has a strongest beatpath to B by X) where
   Z is the set of unique elements Y such that (A has a beatpath to B by Y)
   X = largest element of Z, 0 if Z is empty.  

(A has a beatpath win to B) if
   (A has a strongest beatpath to B by Y) AND
   (B has a strongest beatpath to A by Z) AND
   (Y > Z)

(A is tied winner) if
   there is no B such that (B has a beatpath win to A)

(A is a winner) if
   there is no B such that (B is prefered over A on the casting vote)

---

Clinton


--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Another draft of A.6

[Raul Miller]

On Fri, Nov 15, 2002 at 09:48:55PM -0500, Branden Robinson wrote:
> I am sorry if this tries your patience, but I do not understand this
> statement.  Can you give an example with numbers?  Specifically, I don't
> understand what would distinguish a "weak" pairwise tie from a non-weak
> one.

Well.. I'm not actually sure how to cook up a set of ballots which
gives me a non-weak tie.

However, consider the following propositions:

  125:29  D:E
  117:37  B:C
  117:37  A:B
  116:38  F:A
  116:20  E:F
  107:47  C:D
  105:49  D:F
   98:56  A:C
   96:58  E:A
   96:58  C:E
   88:66  F:B
   88:66  B:D
   85:69  D:A
   78:76  F:C
   77:77  E:B
   77:77  B:E

77:77 is a weak proposition since every other proposition has more
than 77 votes on one side of the comparison.

77:77 is also the weakest proposition since no proposition with 77
votes has more than 77 opposing votes.  Obviously, if a tie is a weak
proposition, it has to be the weakest proposition.

If there had been a proposition like 76:75, then 77:77 wouldn't
be a weak proposition, because 76 is less than 77.

Does that help any?

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: voting mechanics draft update

[Raul Miller]

Raul Miller:
> >iv. If eliminating the weakest propositions would not eliminate
> >all votes, a new Schwartz set is found based on the newly
> >revised set of propositions.

On Sat, Nov 16, 2002 at 05:23:13AM +0100, Matthias Urlichs wrote:
> Note that ALL propositions are considered here, not just those
> participating in the Schwartz set.

Hmm.. that's not what I was trying to say.  Thanks.

> >v. If this new Schwartz set contains only one option, that
> >   option wins.
> > 
> As per the definition, there is no such thing as a one-option Schwartz
> set, so actually you'll have to restart with step 5. You might therefore
> replace the last two sections with a simple

Hmm... I think Isee what you mean.  Thanks again.

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: voting mechanics draft update

[Raul Miller]

On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> >   Definition: An option F transitively defeats an option G if G
> >   defeats F or if there is some other option H where H defeats
> >   G AND F transitively defeats H.
> 
On Sat, Nov 16, 2002 at 09:04:42AM +0100, Jochen Voss wrote:
> There is a mistake: "... if G defeats F ..." should be replaced by
> "... if F defeats G ...".

*blush*  Oops.

Thanks.

> On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> >Definition: A proposition is a defeat, or a pair of options
> >where both have received votes explicitly comparing the two
> >options but neither option is able to defeat the other.

On Sat, Nov 16, 2002 at 09:11:37AM +0100, Jochen Voss wrote:
> Sorry, but I do not understand this definition at all.
> 
> Is a proposition a pair of options with special properties?
> And in this case: does "A proposition is a defeat" mean,
> that a pair of options A and B where one defeats the other
> is a proposition?

I'll try to come up with a better definition.  A proposition is
a pair of options where there are votes which mention one of
the options over the other.

> On Fri, Nov 15, 2002 at 06:51:47PM -0500, Raul Miller wrote:
> > 1. Each ballot orders the options being voted on in the order
> >specified by the voter.  If the voter does not rank some options,
> >this means that the voter prefers all ranked options over the
> >unlisted options.  Any options unranked by the voter are treated
> >as being equal to all other unranked options.

On Sat, Nov 16, 2002 at 09:20:15AM +0100, Jochen Voss wrote:
> What does "Any options unranked by the voter are treated as
> being equal to all other unranked options." mean?  How does
> it differ from "All unranked options are treated as being
> equal"?

I was trying to say zero votes without saying zero votes.  Obviously
that was a mistake.

Thanks.

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Attempt at logical english definition for CSSD (using beatpath winner).

[Raul Miller]

On Sun, Nov 17, 2002 at 03:47:01AM +1100, Clinton wrote:
> Heres an attempt to describe the winner of a CSSD election logically, 
> using the beatpath winner implimentation. I've tryed to structure it so 
> that removing the parenthesis gives a plain english definition. Any 
> comments would be appresiated.

I'd like to see a version of this which is written in english (with no
non-alphabetic symbols with mathematical significance, such as "()>=-",
and with proper grammar).

I think I've almost got the language nailed down for the version I'm
proposing, but even if yours doesn't come out to be shorter and easier
to understand than mine, just seeing how somebody else expresses these
concepts can help.

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Raul Miller:
> On Sat, Nov 16, 2002 at 05:23:13AM +0100, Matthias Urlichs wrote:
> > Note that ALL propositions are considered here, not just those
> > participating in the Schwartz set.
> 
> Hmm.. that's not what I was trying to say.  Thanks.
> 
The reason for this to be a problem is that the dropping step only considers
the _innermost_ Schwartz set. There may be more than one, though off-hand
I couldn't invent a suitable example -- I'm sure one exists in the
literature somewhere, though.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Nov 16 draft of voting mechanics

[Raul Miller]

More silliness fixed:  The word "tie" is now only used in one context.
The definition of "transitive defeats" is fixed.  The language defining
propositions has been cleaned up.

If anyone feels that draft is too hard to understand, please write me
a letter indicating the first part that you have trouble understanding,
and something about the nature of the problem you're having.


  A.6 Vote Counting

1. Each ballot orders the options being voted on in the order
   specified by the voter.  If the voter does not rank some options,
   this means that the voter prefers all ranked options over the
   unlisted options.  Any options unranked by the voter are treated
   as being equal to all other unranked options.

2. Options which do not defeat the default option are eliminated.

   Definition: Option A defeats option B if more voters prefer A
   over B than prefer B over A.

3. If an option has a quorum requirement, that option must defeat
   the default option by the number of votes specified in the quorum
   requirement, or the option is eliminated.

4. If an option has a supermajority requirement, that option must
   defeat the default option by the ratio of votes specified in the
   supermajority requirement, or the option is eliminated.  That is,
   if a an option has a 2:1 supermajority requirement, then there
   must be twice as many votes which prefer that option over the
   default option than there are votes which prefer the default
   option over that option.

5. If one remaining option defeats all other remaining options,
   that option wins.

6. If more than one option remains after the above steps, we use
   Cloneproof Schwartz Sequential Dropping to eliminate any cyclic
   ambiguities and then pick the winner.  This procedure and must
   be carried out in the following order:

   i. All options not in the Schwartz set are eliminated.

  Definition: An option C is in the Schwartz set if there is no
  other option D such that D transitively defeats C AND C does
  not transitively defeat D.

  Definition: An option F transitively defeats an option G if F
  defeats G or if there is some other option H where H defeats
  G AND F transitively defeats H.

   ii. Unless this would eliminate all options in the Schwartz set,
   the weakest propositions are eliminated.

   Definition: A proposition is a pair of options J and K
   from the Schwartz set which are considered along with
   the number of voters who prefer J to K and the number
   of voters who prefer K to J.

   Definition: The dominant strength of a proposition is the
   count of votes in a proposition which is not smaller than
   the other vote count in that proposition.

   Definition: a weak proposition is a proposition which
   has a dominant strength greater than zero and no larger
   than that of any other proposition.

   Definition: a weakest proposition is a weak proposition where
   the vote count in the proposition which is not larger than
   the other vote count is also no smaller than that of any
   other weak proposition.

   Definition: A proposition is eliminated by treating both
   of its vote counts as zero from this point forward.

   iii. If eliminating the weakest propositions would eliminate all
votes represented in the Schwartz set, a tie exists and the
person with the casting vote picks from among the options
represented in this Schwartz set.

   iv. If eliminating the weakest propositions would not eliminate
   all votes, a new Schwartz set is found based on the newly
   revised set of propositions.

   v. If this new set of propositions allows one option to 
  defeat all other options in the Schwartz set, that
  option wins.

   vi. Otherwise, these steps (i-vi) are repeated with this new
   Schwartz set.


Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: voting mechanics draft update

[Raul Miller]

On Sat, Nov 16, 2002 at 06:56:37PM +0100, Matthias Urlichs wrote:
> The reason for this to be a problem is that the dropping step only considers
> the _innermost_ Schwartz set. There may be more than one, though off-hand
> I couldn't invent a suitable example -- I'm sure one exists in the
> literature somewhere, though.

The Schwartz set is the set of innermost unbeatened sets.  There cannot
be more than one Schwartz set at any one time for any one set of votes.

See http://www.barnsdle.demon.co.uk/vote/condor2.html for a more extensive
discussion of this subject.

Or, if  you think I'm wrong, please explain your reasoning in more depth.

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Anthony Towns:
> > >v. If this new Schwartz set contains only one option, that
> > >   option wins.
> > > 
> > As per the definition, there is no such thing as a one-option Schwartz
> > set

> Uh, if C is the Condorcet winner, or becomes the Condorcet winner after
> ignoring some defeats of it, the Schwartz set has only one option.

Actually you're right, the definition allows that. I was thinking not of
the definition but of the list of steps we're going through, and we're
using the "if there's a clear winner, then we're done, else build a
Schwartz set" method, as opposed to the equivalent "build a Schwartz set,
and if that has only one member, that's the winner" procedure.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/



msg01960/pgp0.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello,

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 1. [...] Any options unranked by the voter are treated
>as being equal to all other unranked options.
I still do not understand the "other unranked options".
Could we simply write "Any options unranked by the voter are treated
as being equal" or would this be something else.

> 6. [...] This procedure and must be carried out in the following order:
  ^^^
The "and" seems spurious to me.

I'm getting further with the draft.  Especially I understand
"proposition" and "weak proposition", now.  But ...

>Definition: a weakest proposition is a weak proposition where
>the vote count in the proposition which is not larger than
>the other vote count is also no smaller than that of any
>other weak proposition.
... this is hard stuff.  What about "minimum of the two vote counts"
instead of "the vote count in the proposition which is not larger than
the other vote count"?

I seem to understand the remaining parts of the text :-)

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01961/pgp0.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Raul Miller]

Hello,
> On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> > 1. [...] Any options unranked by the voter are treated
> >as being equal to all other unranked options.

On Sat, Nov 16, 2002 at 07:47:39PM +0100, Jochen Voss wrote:
> I still do not understand the "other unranked options".
> Could we simply write "Any options unranked by the voter are treated
> as being equal" or would this be something else.

That sounds fine.

Thanks.

> > 6. [...] This procedure and must be carried out in the following order:
>   ^^^
> The "and" seems spurious to me.

Yes.

> I'm getting further with the draft.  Especially I understand
> "proposition" and "weak proposition", now.  But ...
> 
> >Definition: a weakest proposition is a weak proposition where
> >the vote count in the proposition which is not larger than
> >the other vote count is also no smaller than that of any
> >other weak proposition.
> ... this is hard stuff.  What about "minimum of the two vote counts"
> instead of "the vote count in the proposition which is not larger than
> the other vote count"?

I think that would be fine.

Thanks again,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 2. Options which do not defeat the default option are eliminated.
> 
>Definition: Option A defeats option B if more voters prefer A
>over B than prefer B over A.

Is the default option supposed to be in the list of options for which
we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
should replace "Options" by "Non-default options" in this paragraph?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01963/pgp0.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello again!

Another one:

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> 3. If an option has a quorum requirement, that option must defeat
>the default option by the number of votes specified in the quorum
>requirement, or the option is eliminated.

We did not define the term "defeat by a number of votes".  If the
quorum requirement is Q, does this mean that at least Q votes must
prefer the option over the default option?  Or does it mean that the
number of votes which prefer the option in question over the default
option must exceed the number of votes which prefer the default option
over the current option by at least Q?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01964/pgp0.pgp
Description: PGP signature

Re: voting mechanics draft update

[Matthias Urlichs]

Hi,

Raul Miller:
> The Schwartz set is the set of innermost unbeatened sets.  There cannot
> be more than one Schwartz set at any one time for any one set of votes.
> 
> See http://www.barnsdle.demon.co.uk/vote/condor2.html for a more extensive
> discussion of this subject.
> 
Thanks for the link.

> Or, if  you think I'm wrong, please explain your reasoning in more depth.
> 
No you aren't, we're just not used to talking about that topic and thus
misunderstandings creep up when we aren't looking.  ;-)

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Matthias Urlichs]

Hi,

Raul Miller:
>Definition: The dominant strength of a proposition is the
>count of votes in a proposition which is not smaller than
>the other vote count in that proposition.
> 
Please replace "not smaller" with "larger or equal to", and vice versa,
throughout the text. Those negatives make thinking about whatever it is
that the text actually means ;-) more difficult.

-- 
Matthias Urlichs | noris network AG | http://smurf.noris.de/


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sat, Nov 16, 2002 at 09:31:08PM +0100, Jochen Voss wrote:
> Is the default option supposed to be in the list of options for which
> we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
> should replace "Options" by "Non-default options" in this paragraph?

For an option to be in the Schwartz set, it must either tie or 
beat at least one other option in the Schwartz set.

The default option can never be in the Schwartz set, because any
option which does not defeat the default option is eliminated
before the first Schwartz set is created..

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sat, Nov 16, 2002 at 10:47:43PM +0100, Matthias Urlichs wrote:
> Please replace "not smaller" with "larger or equal to", and vice versa,
> throughout the text. Those negatives make thinking about whatever it is
> that the text actually means ;-) more difficult.

Actually, based on a suggestion by Jochen Voss, I'm planning on
changing the "not smaller" language with a phrase using "maximum".

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello Raul,

trying to actually implement the algorithm from the draft turns out to
be a good test :-)

On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
>ii. Unless this would eliminate all options in the Schwartz set,
>the weakest propositions are eliminated.
>[...]
>
>Definition: A proposition is eliminated by treating both
>of its vote counts as zero from this point forward.
> 
>iii. If eliminating the weakest propositions would eliminate all
> votes represented in the Schwartz set, a tie exists [...]

What does "eliminate all options" and "eliminate all votes" mean
in this context?  Could we formalise this?

Example: (X is the default option)

ABCDX
   A-   24   17   25   31
   B   25-   26   24   29
   C   31   24-   31   30
   D   25   26   18-   27
   X   15   18   15   18-

If my algorithm is correct, than just before step 6.ii the
Schwartz set consists of options B, C, and D and the
weakest propositions are (B,C) and (B,D).

This leads to the following new matrix:

 BCD 
   B -00 
   C 0-   31 
   D 0   18- 

I guess that C is the winner here.  But what condition should my
program check to see whether "this would eliminate all options in the
Schwartz set"?  Maybe whether all entries in the matrix become zero?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01969/pgp0.pgp
Description: PGP signature

Re: Nov 16 draft of voting mechanics

[Jochen Voss]

Hello Raul,

On Sat, Nov 16, 2002 at 05:44:40PM -0500, Raul Miller wrote:
> On Sat, Nov 16, 2002 at 09:31:08PM +0100, Jochen Voss wrote:
> > Is the default option supposed to be in the list of options for which
> > we do "Cloneproof Schwartz Sequential Dropping" below?  Maybe we
> > should replace "Options" by "Non-default options" in this paragraph?
> 
> For an option to be in the Schwartz set, it must either tie or 
> beat at least one other option in the Schwartz set.
> 
> The default option can never be in the Schwartz set, because any
> option which does not defeat the default option is eliminated
> before the first Schwartz set is created..
Ok, this is a proof.

But the change I suggested above would make a (theoretical) difference
nevertheless: if the default option could survive step 2 it could
become the winner in step 5.  If the default option cannot survive
step 2, it never could become the winner.

Do we intend that the default option actually can win the vote?
Am I correct that this only could happen via step 5?

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html



msg01970/pgp0.pgp
Description: PGP signature

example implementation of the new voting machinery draft

[Jochen Voss]

Hello,

I spent some time implementing the voting mechanism as described
in Rauls draft.  Maybe this is useful for somebody who wants to
play with the new voting system.

I append a preliminary version of the program here.  The second
attachment is an example input file.  The program is modelled
closely after the voting mechanics draft.  It not meant to be
fast or efficient.  My priority was to correctly implement the
behaviour as described by the current draft.

Some code is missing (see my other mails to this list).  Questions,
which come into mind are:

1) Did I understand the voting draft correctly?
2) Is my implementation correct.
3) What should I fill in for the missing pieces.

I would be glad to receive comments about the program.

Jochen
-- 
 Omm
  (0)-(0)
http://www.mathematik.uni-kl.de/~wwwstoch/voss/privat.html

#! /usr/bin/env python
# vote.py - implement the voting mechanism form the Debian constitution
#
# Copyright 2002  Jochen Voss <[EMAIL PROTECTED]>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

import sys, fileinput
from copy import copy

options=['A', 'B', 'C', 'D', 'X']
default='X'
quorum={}
supermajority={}

# You may set some quorum or supermajority here, e.g.
#quorum['A']=15
#supermajority['B']=2.0/1.0

##
# 1. Each ballot orders the options being voted on in the order
#specified by the voter.  If the voter does not rank some options,
#this means that the voter prefers all ranked options over the
#unlisted options.  Any options unranked by the voter are treated
#as being equal to all other unranked options.

votecount={}
for o1 in options:
for o2 in options: votecount[o1+o2]=0

def print_propositions():
"Print the vote counts in tabular form."
print
print "",
for o2 in options:
print " %3s"%o2,
print
for o1 in options:
print "%4s"%o1,
for o2 in options:
if o1==o2:
print "   -",
else:
print " %3d"%votecount[o1+o2],
print

def register_vote(str):
"""Feed a single vote into the data structures.
STR must be a word, composed of option letters.
The value AB, for example indicates that A is prefered
over everything, B is prefered over all unlisted options,
and all unlisted options are equal."""
for o in str:
if not o in options: raise "invalid option '%s'"%o
for i in range(0,len(str)-1):
o1=str[i]
for o2 in str[i+1:]: votecount[o1+o2]+=1
for o2 in options:
if o2 in str: continue
for o1 in str: votecount[o1+o2]+=1

## Read the votes, either from stdin or from file.
for line in fileinput.input():
if line[0] == "#": continue
register_vote(line.strip())

print_propositions()

##
# 2. Options which do not defeat the default option are eliminated.

# Definition: Option A defeats option B if more voters prefer A over B
#than prefer B over A.
def defeats(o1,o2):
return votecount[o1+o2]>votecount[o2+o1]

active=[]
for o in options:
if defeats(o,default):
active.append(o)
else:
print "option %s does not defeat default option -> eliminated"%o
options=active

##
# 3. If an option has a quorum requirement, that option must defeat
#the default option by the number of votes specified in the quorum
#requirement, or the option is eliminated.

# TODO: is this correct?
def matches_quorum(o,q):
return votecount[o+default]>votecount[default+o]+q

active=[]
for o in options:
if (o not in quorum) or matches_quorum(o,quorum[o]):
active.append(o)
else:
print ("option %s does not match "%o
   + "the quorum requirement (%d)"%quorum[o]
   + " -> eliminated")
options=active

##
# 4. If an option has a supermajority requirement, that option must
#defeat the default option by the ratio of votes specified in the
#supermajority requirement, or the option is eliminated.  That is,
#if a an option has a 2:1 supermajority requirem

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sun, Nov 17, 2002 at 12:12:53AM +0100, Jochen Voss wrote:
> trying to actually implement the algorithm from the draft turns out to
> be a good test :-)

Ok.  Note that I've not sat down and read your implementation, yet.

> On Sat, Nov 16, 2002 at 12:48:07PM -0500, Raul Miller wrote:
> >ii. Unless this would eliminate all options in the Schwartz set,
> >the weakest propositions are eliminated.
> >[...]
> >
> >Definition: A proposition is eliminated by treating both
> >of its vote counts as zero from this point forward.
> > 
> >iii. If eliminating the weakest propositions would eliminate all
> > votes represented in the Schwartz set, a tie exists [...]
> 
> What does "eliminate all options" and "eliminate all votes" mean
> in this context?  Could we formalise this?

Uh... 

> Example: (X is the default option)
> 
> ABCDX
>A-   24   17   25   31
>B   25-   26   24   29
>C   31   24-   31   30
>D   25   26   18-   27
>X   15   18   15   18-

Just as a note: in my view of the world, where you put a "-",
I'd put a "0".  In principle this shouldn't matter, but maybe
that has something to do with what you consider ambiguous?

> If my algorithm is correct, than just before step 6.ii the
> Schwartz set consists of options B, C, and D and the
> weakest propositions are (B,C) and (B,D).

I ran through the steps by hand, and I agree.  [You didn't say,
but the rows in your matrix have to represent the vote count "for"
an option, and the columns the vote count "against", otherwise
the default option would defeat everything else.]

Out of curiosity, how did you generate that set of tallies?  Did you start
from some set of ballots, or did you just randomly generate some numbers?

> This leads to the following new matrix:
> 
>  BCD 
>B -00 
>C 0-   31 
>D 0   18- 
> 
> I guess that C is the winner here.  But what condition should my
> program check to see whether "this would eliminate all options in the
> Schwartz set"?  Maybe whether all entries in the matrix become zero?

I had meant to change ii. so that it read something like:

"Unless this would eliminate all vote counts in the propositions of the
Schwartz set, the vote counts of the weakest propositions are eliminated."

Is that better?

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]

Re: Nov 16 draft of voting mechanics

[Raul Miller]

On Sun, Nov 17, 2002 at 12:23:11AM +0100, Jochen Voss wrote:
> Do we intend that the default option actually can win the vote?
> Am I correct that this only could happen via step 5?

You're right, I should it so that the default option doesn't need to
defeat the default option.

The interpretation that the default option could eliminate itself might
work, but I'd prefer less ambiguity.

Thanks,

-- 
Raul


-- 
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]