[EM] Introducing Pivot

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] Introducing Pivot

Carl Schroedl

Hello Election Methods List!


Greetings from Madison, Wisconsin, USA. I’m Carl Schroedl. By day I’m a professional software engineer. By night I volunteer on the Pivot Libre open source project. The project has produced an open source library called Tideman for calculating Ranked Pairs election results and an open source web app called Pivot that lets people execute ad-hoc Ranked Pairs elections via their web browser. I invite you to try it out here:

https://pivot.vote


If you don't want to create an account, you can simulate elections with textual ballots here:

https://pivot.vote/open/try


It’s seeing more usage than we thought. While most usages are non-governmental, a committee in the municipal legislature of Madison used it to nominate an interim legislator. Since the city of Madison is currently reevaluating its fundamentals through a Task Force on Government Structure, I’m hoping this app encourages the adoption of alternative voting systems. We already have a lot of tests to ensure our system is correct, but in light of this success, we’d like to further increase our confidence.


I know we’re not the first people to verify the correctness of their electronic voting system, and I doubt we’ll be the last. How would list members recommend we proceed? Julien Boudry (https://condorcet.vote) and I were considering creating a repository of machine-readable test ballots with expected election outcomes so that multiple projects could run the same tests. Does such a resource exist? If not, would anyone be interested in collaborating?


All the best,


Carl


--

----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

[EM] Introducing Pivot

Kristofer Munsterhjelm-3
On 2018-11-30 16:00, Carl Schroedl wrote:

> Hello Election Methods List!
>
>
> Greetings from Madison, Wisconsin, USA. I’m Carl Schroedl. By day I’m a
> professional software engineer. By night I volunteer on the Pivot Libre
> open source project. The project has produced an open source library
> called Tideman for calculating Ranked Pairs election results and an open
> source web app called Pivot that lets people execute ad-hoc Ranked Pairs
> elections via their web browser. I invite you to try it out here:
>
> https://pivot.vote
>
>
> If you don't want to create an account, you can simulate elections with
> textual ballots here:
>
> https://pivot.vote/open/try
>
>
> It’s seeing more usage than we thought. While most usages are
> non-governmental, a committee in the municipal legislature of Madison
> used it to nominate an interim legislator. Since the city of Madison is
> currently reevaluating its fundamentals through a Task Force on
> Government Structure, I’m hoping this app encourages the adoption of
> alternative voting systems. We already have a lot of tests to ensure our
> system is correct, but in light of this success, we’d like to further
> increase our confidence.
>
>
> I know we’re not the first people to verify the correctness of their
> electronic voting system, and I doubt we’ll be the last. How would list
> members recommend we proceed? Julien Boudry (https://condorcet.vote) and
> I were considering creating a repository of machine-readable test
> ballots with expected election outcomes so that multiple projects could
> run the same tests. Does such a resource exist? If not, would anyone be
> interested in collaborating?

For something as simple as a voting method, it might be possible to
formally prove the code correct. Such a proof would be better than any
collection of tests, as it would show the method correct for every
possible ballot. However, I don't know enough about formal verification,
so I couldn't tell you how to actually do it.

Beyond that, a collection of tests would be a good idea. I don't know of
any such colection. Articles that show that methods fail certain
criteria may contain ballot sets to demonstrate the failure, e.g.
http://alumnus.caltech.edu/~seppley/Independence%20from%20Pareto-dominated%20Alternatives.htm
shows an example where Borda fails IPDA, and so (implicitly) contains a
test election along with the outcome that Borda should give that test
election.

I could probably adjust my program
(https://github.com/kristomu/quadelect) to output elections that
distinguish between different methods. Creating tests to exercise
methods would be tougher, as we'd have to know how one may design the
methods incorrectly. Perhaps the best approach would be to take many
implementations that have already been written and test them on random
elections to see when they give different results.

I'd like to make a test set, but I've recently found myself rather short
on spare time, so I don't think I could contribute much, at least not at
the moment.
----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Kristofer Munsterhjelm-3
On 12/12/2018 21.20, Kristofer Munsterhjelm wrote:

> I'd like to make a test set, but I've recently found myself rather short
> on spare time, so I don't think I could contribute much, at least not at
> the moment.

Here's a test entry that I made while constructing a Smith,Minmax
mono-add-top failure example with as few voters as possible:

Election 1:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C

The Smith set is {A, B, D}. C is the Plurality winner and also the
Minmax winner. Schulze elects A.

Election 2:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C
1: A>B>C>D
1: A>C>D>B

The Smith set consists of all four candidates, and the outcomes should
be the same.

This is a Smith,Minmax failure example because C is automatically
disqualified in the first election since C is not in the Smith set; but
adding some A-first ballots gets C into the Smith set, after which it wins.

Incidentally, I haven't been able to find a four-candidate Smith,Minmax
failure example that also fails MAM. That might be a good challenge to
either show impossible or to devise.

Finally, there are example elections where every positional system
except Plurality fails Majority. Could those be good test cases?
----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Carl Schroedl
Hi Kristofer!

Sorry for the delayed reply. I agree that formal verification would be more rigorous. I don't know how to do formal verification either, but I would be open to collaborating with someone who had experience doing it.

I'm glad you are excited about the idea of a collection of implementation-independent tests! A few different Pivot Libre projects have been using one format for ranked ballots and ranked results. I posted a draft specification of the format here:

Folks who are handy with git and GitHub are welcome to discuss and propose changes to the source file here: 
I'm also open to discussing it over email; either on the list or privately.

Some of the many open questions:
 * Should the spec say something about how head-to-head matchup matrices are encoded? If it's relevant to include, I'm hoping something standard like a JSON array or map could be used so that we don't have to write a parser, but I'm open to other ideas.

 * Should the ballots and the expected result (and possibly the head-to-head matchup matrix) for a single test election all be in one file together? All in separate files?

 * What lessons can be learned from previous attempts to standardize in this space? Most notably Election Markup Language https://en.wikipedia.org/wiki/Election_Markup_Language .

One of our group members had a somewhat similar idea to you about generating random ballots. His work-in-progress tool generates random graphs with a Condorcet winner and then calculates the BFF ballots needed to generate such a graph.
He's not on this mailing list yet, so let me know if you want to be introduced.

Thanks for pointing me to Steve's examples, for pointing me to your program, and for drafting a few test ballots of your own! I admire the drive to create a useful test scenario with a minimal number of ballots. I'll be slower to reply to emails over the holidays, but I look forward to further discussion and collaboration!

Wishing you all the best,

Carl

On Wed, Dec 19, 2018 at 4:07 PM Kristofer Munsterhjelm <[hidden email]> wrote:
On 12/12/2018 21.20, Kristofer Munsterhjelm wrote:

> I'd like to make a test set, but I've recently found myself rather short
> on spare time, so I don't think I could contribute much, at least not at
> the moment.

Here's a test entry that I made while constructing a Smith,Minmax
mono-add-top failure example with as few voters as possible:

Election 1:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C

The Smith set is {A, B, D}. C is the Plurality winner and also the
Minmax winner. Schulze elects A.

Election 2:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C
1: A>B>C>D
1: A>C>D>B

The Smith set consists of all four candidates, and the outcomes should
be the same.

This is a Smith,Minmax failure example because C is automatically
disqualified in the first election since C is not in the Smith set; but
adding some A-first ballots gets C into the Smith set, after which it wins.

Incidentally, I haven't been able to find a four-candidate Smith,Minmax
failure example that also fails MAM. That might be a good challenge to
either show impossible or to devise.

Finally, there are example elections where every positional system
except Plurality fails Majority. Could those be good test cases?


--

----
Election-Methods mailing list - see http://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Carl Schroedl
Hi Kristofer,

Thanks again for the example election scenarios. I created a repository for ranked ballot test scenarios on GitHub and added your examples.

I've been thinking about this project a bit more broadly. In many disciplines it is difficult for engineers to create practical beneficial solutions from science's discoveries. Engineers' implementations can be incorrect or lag behind the latest science. I'm hoping this ranked ballot scenarios repository will make it easy for software engineers to faithfully implement the best and latest election science. Viewed another way, I'm hoping the repository will make it easy for the work of election scientists to be adopted more widely, correctly, and quickly.

Does the structure I proposed support that goal? How could it be improved?

All the best,
Carl


On Thu, Dec 20, 2018 at 5:41 PM Carl Schroedl <[hidden email]> wrote:
Hi Kristofer!

Sorry for the delayed reply. I agree that formal verification would be more rigorous. I don't know how to do formal verification either, but I would be open to collaborating with someone who had experience doing it.

I'm glad you are excited about the idea of a collection of implementation-independent tests! A few different Pivot Libre projects have been using one format for ranked ballots and ranked results. I posted a draft specification of the format here:

Folks who are handy with git and GitHub are welcome to discuss and propose changes to the source file here: 
I'm also open to discussing it over email; either on the list or privately.

Some of the many open questions:
 * Should the spec say something about how head-to-head matchup matrices are encoded? If it's relevant to include, I'm hoping something standard like a JSON array or map could be used so that we don't have to write a parser, but I'm open to other ideas.

 * Should the ballots and the expected result (and possibly the head-to-head matchup matrix) for a single test election all be in one file together? All in separate files?

 * What lessons can be learned from previous attempts to standardize in this space? Most notably Election Markup Language https://en.wikipedia.org/wiki/Election_Markup_Language .

One of our group members had a somewhat similar idea to you about generating random ballots. His work-in-progress tool generates random graphs with a Condorcet winner and then calculates the BFF ballots needed to generate such a graph.
He's not on this mailing list yet, so let me know if you want to be introduced.

Thanks for pointing me to Steve's examples, for pointing me to your program, and for drafting a few test ballots of your own! I admire the drive to create a useful test scenario with a minimal number of ballots. I'll be slower to reply to emails over the holidays, but I look forward to further discussion and collaboration!

Wishing you all the best,

Carl

On Wed, Dec 19, 2018 at 4:07 PM Kristofer Munsterhjelm <[hidden email]> wrote:
On 12/12/2018 21.20, Kristofer Munsterhjelm wrote:

> I'd like to make a test set, but I've recently found myself rather short
> on spare time, so I don't think I could contribute much, at least not at
> the moment.

Here's a test entry that I made while constructing a Smith,Minmax
mono-add-top failure example with as few voters as possible:

Election 1:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C

The Smith set is {A, B, D}. C is the Plurality winner and also the
Minmax winner. Schulze elects A.

Election 2:

8: B>D>A>C
9: C>A>B>D
3: C>D>A>B
5: D>A>B>C
1: A>B>C>D
1: A>C>D>B

The Smith set consists of all four candidates, and the outcomes should
be the same.

This is a Smith,Minmax failure example because C is automatically
disqualified in the first election since C is not in the Smith set; but
adding some A-first ballots gets C into the Smith set, after which it wins.

Incidentally, I haven't been able to find a four-candidate Smith,Minmax
failure example that also fails MAM. That might be a good challenge to
either show impossible or to devise.

Finally, there are example elections where every positional system
except Plurality fails Majority. Could those be good test cases?


--


--

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Kristofer Munsterhjelm-3
On 18/02/2019 23.28, Carl Schroedl wrote:

> Hi Kristofer,
>
> Thanks again for the example election scenarios. I created a repository
> for ranked ballot test scenarios on GitHub and added your examples.
> https://github.com/pivot-libre/ranked-ballot-scenarios/
>
> I've been thinking about this project a bit more broadly. In many
> disciplines it is difficult for engineers to create practical beneficial
> solutions from science's discoveries. Engineers' implementations can be
> incorrect or lag behind the latest science. I'm hoping this ranked
> ballot scenarios repository will make it easy for software engineers to
> faithfully implement the best and latest election science. Viewed
> another way, I'm hoping the repository will make it easy for the work of
> election scientists to be adopted more widely, correctly, and quickly.
>
> Does the structure I proposed support that goal? How could it be improved?

More to come when I have more time, most likely, but I would suggest
that property failure examples should have a specific directory or file
structure.

There are relative and absolute criteria. Absolute criteria go like "in
any election of this type, that should happen" (e.g. majority: in every
election where A is ranked top by more than a majority, A should win).

Relative criteria go like "if A wins in this election, and then you
modify it like this, then A should/shouldn't win in that election". E.g.
mono-add-top (if A wins, then after adding some ballots ranking A top, A
should still win) or cloning (crowding: if A wins and you clone B, then
A should still win; vote-splitting: if A wins and you clone A, then A
should still win; teaming: if A doesn't win and you clone A, then A
still shouldn't win).

For absolute criteria, the directory structure you've detailed in the
readme is probably good enough (e.g.
"scenarios/borda-majority-failure/"). But for relative criteria
failures, I would suggest that the file/directory structure makes it
clear which ballot set is before and which ballot set is after.

E.g.
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/before/
(the ballot with the three-candidate Smith set) and
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/after/
(after some A-top ballots push C into the Smith set).

The names don't necessarily have to be "before" and "after", but that's
what first came to mind.

You could possibly further categorize the examples, e.g.
criterion-failures/mono-add-top/smith-minmax/before/ or
criterion-failures/smith-minmax/mono-add-top/before/ depending. But
you'd have to judge how much that obscures the point of the repository.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Carl Schroedl
Thanks Kristofer! I hadn't considered developing distinct structures for relative and absolute scenarios. I have updated the GitHub repo to attempt to match your proposed structure. How does it look to you?

Since I'm a programmer, and not a social choice theory expert, I'm confident I'll get something about this wrong, if not now then later :) I'm happy to continue hashing it out over email. If you or other list members would like to be a little more hands-on about it, GitHub is a great platform to collaborate, and not just for code -- people even collaborate on Washington DC's laws via GitHub. If you sign up for a free account, you can make a copy of the existing repository, and make changes to match what you are thinking. Once you are happy with it, you can propose merging the changes back into the Pivot Libre organization's repository.

There's a couple of good tutorials here:

Let me know what you think!


On Mon, Feb 18, 2019 at 5:02 PM Kristofer Munsterhjelm <[hidden email]> wrote:
On 18/02/2019 23.28, Carl Schroedl wrote:
> Hi Kristofer,
>
> Thanks again for the example election scenarios. I created a repository
> for ranked ballot test scenarios on GitHub and added your examples.
> https://github.com/pivot-libre/ranked-ballot-scenarios/
>
> I've been thinking about this project a bit more broadly. In many
> disciplines it is difficult for engineers to create practical beneficial
> solutions from science's discoveries. Engineers' implementations can be
> incorrect or lag behind the latest science. I'm hoping this ranked
> ballot scenarios repository will make it easy for software engineers to
> faithfully implement the best and latest election science. Viewed
> another way, I'm hoping the repository will make it easy for the work of
> election scientists to be adopted more widely, correctly, and quickly.
>
> Does the structure I proposed support that goal? How could it be improved?

More to come when I have more time, most likely, but I would suggest
that property failure examples should have a specific directory or file
structure.

There are relative and absolute criteria. Absolute criteria go like "in
any election of this type, that should happen" (e.g. majority: in every
election where A is ranked top by more than a majority, A should win).

Relative criteria go like "if A wins in this election, and then you
modify it like this, then A should/shouldn't win in that election". E.g.
mono-add-top (if A wins, then after adding some ballots ranking A top, A
should still win) or cloning (crowding: if A wins and you clone B, then
A should still win; vote-splitting: if A wins and you clone A, then A
should still win; teaming: if A doesn't win and you clone A, then A
still shouldn't win).

For absolute criteria, the directory structure you've detailed in the
readme is probably good enough (e.g.
"scenarios/borda-majority-failure/"). But for relative criteria
failures, I would suggest that the file/directory structure makes it
clear which ballot set is before and which ballot set is after.

E.g.
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/before/
(the ballot with the three-candidate Smith set) and
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/after/
(after some A-top ballots push C into the Smith set).

The names don't necessarily have to be "before" and "after", but that's
what first came to mind.

You could possibly further categorize the examples, e.g.
criterion-failures/mono-add-top/smith-minmax/before/ or
criterion-failures/smith-minmax/mono-add-top/before/ depending. But
you'd have to judge how much that obscures the point of the repository.


--

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Carl Schroedl
Ah! I re-read an earlier message and saw that you already have a GitHub account (https://github.com/kristomu). Cool! I'm happy to collaborate either way.

Cheers!

On Thu, Feb 28, 2019, 6:10 PM Carl Schroedl <[hidden email]> wrote:
Thanks Kristofer! I hadn't considered developing distinct structures for relative and absolute scenarios. I have updated the GitHub repo to attempt to match your proposed structure. How does it look to you?

Since I'm a programmer, and not a social choice theory expert, I'm confident I'll get something about this wrong, if not now then later :) I'm happy to continue hashing it out over email. If you or other list members would like to be a little more hands-on about it, GitHub is a great platform to collaborate, and not just for code -- people even collaborate on Washington DC's laws via GitHub. If you sign up for a free account, you can make a copy of the existing repository, and make changes to match what you are thinking. Once you are happy with it, you can propose merging the changes back into the Pivot Libre organization's repository.

There's a couple of good tutorials here:

Let me know what you think!


On Mon, Feb 18, 2019 at 5:02 PM Kristofer Munsterhjelm <[hidden email]> wrote:
On 18/02/2019 23.28, Carl Schroedl wrote:
> Hi Kristofer,
>
> Thanks again for the example election scenarios. I created a repository
> for ranked ballot test scenarios on GitHub and added your examples.
> https://github.com/pivot-libre/ranked-ballot-scenarios/
>
> I've been thinking about this project a bit more broadly. In many
> disciplines it is difficult for engineers to create practical beneficial
> solutions from science's discoveries. Engineers' implementations can be
> incorrect or lag behind the latest science. I'm hoping this ranked
> ballot scenarios repository will make it easy for software engineers to
> faithfully implement the best and latest election science. Viewed
> another way, I'm hoping the repository will make it easy for the work of
> election scientists to be adopted more widely, correctly, and quickly.
>
> Does the structure I proposed support that goal? How could it be improved?

More to come when I have more time, most likely, but I would suggest
that property failure examples should have a specific directory or file
structure.

There are relative and absolute criteria. Absolute criteria go like "in
any election of this type, that should happen" (e.g. majority: in every
election where A is ranked top by more than a majority, A should win).

Relative criteria go like "if A wins in this election, and then you
modify it like this, then A should/shouldn't win in that election". E.g.
mono-add-top (if A wins, then after adding some ballots ranking A top, A
should still win) or cloning (crowding: if A wins and you clone B, then
A should still win; vote-splitting: if A wins and you clone A, then A
should still win; teaming: if A doesn't win and you clone A, then A
still shouldn't win).

For absolute criteria, the directory structure you've detailed in the
readme is probably good enough (e.g.
"scenarios/borda-majority-failure/"). But for relative criteria
failures, I would suggest that the file/directory structure makes it
clear which ballot set is before and which ballot set is after.

E.g.
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/before/
(the ballot with the three-candidate Smith set) and
ranked-ballot-scenarios/scenarios/smith-minmax-mono-add-top-failure/after/
(after some A-top ballots push C into the Smith set).

The names don't necessarily have to be "before" and "after", but that's
what first came to mind.

You could possibly further categorize the examples, e.g.
criterion-failures/mono-add-top/smith-minmax/before/ or
criterion-failures/smith-minmax/mono-add-top/before/ depending. But
you'd have to judge how much that obscures the point of the repository.


--

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Introducing Pivot

Kristofer Munsterhjelm-3
In reply to this post by Carl Schroedl
On 01/03/2019 01.10, Carl Schroedl wrote:
> Thanks Kristofer! I hadn't considered developing distinct structures for
> relative and absolute scenarios. I have updated the GitHub repo to
> attempt to match your proposed structure. How does it look to you?

In
https://github.com/pivot-libre/ranked-ballot-scenarios/tree/master/scenarios/relative
you have the directories

https://github.com/pivot-libre/ranked-ballot-scenarios/tree/master/scenarios/relative/smith-minmax-failure

and

https://github.com/pivot-libre/ranked-ballot-scenarios/tree/master/scenarios/relative/smith-minmax-mono-add-top-failure

The former has before/ and after/ but doesn't say what the criterion
being failed *is*. (I assume it's mono-add-top.) The latter says what
criterion it is, but has only one set of ballots. So something is wrong
with the ballots.

I unfortunately haven't had the time to look at it more closely to find
out what; you might have copied my examples incorrecly, I'm guessing.

I've been more occupied with bugfixing my own program. As part of doing
so, I created the following ballot sets:

1:A>B>C>D
1:B>A>C>D
1:B>C>A>D
2:C>B>D>A
1:C>D>B>A
1:D>B>C>A

with Condorcet matrix

- 1 2 3
6 - 4 5
5 3 - 6
4 2 1 -

i.e. the upper right half of the matrix is "1 2 3 4 5 6" from left to
right, and the lower right half, reading from top to bottom and left to
right, is "6 5 4 3 2 1".

This is in row beats column form, i.e. one voter ranks A over B, two
rank A over C and so on.

A related example:

2:B>A>C>D
2:B>C>D>A
1:C>B>A>D
1:C>D>A>B

has Condorcet matrix

- 1 2 3
5 - 4 5
4 2 - 6
3 1 0 -

Pretty much every method elects B in both of these cases. They can be
used to test ballot-parsing and pairwise matrix functions.

In case I mistyped, you can verify these examples with LeGrand's rbvote:
https://www.cse.wustl.edu/~legrand/rbvote/calc.html. Select "calculate
all winners" to get the Condorcet matrix.
----
Election-Methods mailing list - see https://electorama.com/em for list info