About vote bubbles¶

This document talks about vote bubbles.

This page contains code snippets (lines starting with >>>), which are being tested during our development workflow. The following snippet initializes the demo project used throughout this page.

>>> from lino_seggi.projects.seggi1.startup import *

>>> obj = seats.Board.objects.get(id=1)
>>> obj
Board #1 ('Riigikogu')

>>> rt.show(seats.VotesByBoard, obj, column_names = "id user user__id delegate delegate__id *")
==== =================================== ==== ======================= ====
 ID   User                                ID   Delegate                ID
---- ----------------------------------- ---- ----------------------- ----
  Hans Altenberg                      5    Andreas Arens           3
  Andreas Arens                       3    Ulrike Charlier         9
  Annette Arens                       4    Berta Ernst             15
  Alfons Ausdemwald                   6    Hildegard Hilgers       23
  Laurent Bastiaensen                 7    Josef Jonas             29
  Marc Chantraine                     10   Laura Laschet           33
  Ulrike Charlier                     9    Annette Arens           4
 Charlotte Collard                   8    Laurent Bastiaensen     7
 Dorothée Demeulenaere               12   Charlotte Collard       8
 Daniel Dericum                      11   Bernd Evertz            16
 Dorothée Dobbelstein                14   Josef Jonas             29
 Dorothée Dobbelstein-Demeulenaere   13   Marc Malmendier         36
 Daniel Emonts                       18   Annette Arens           4
 Edgar Engels                        19   Marc Chantraine         10
 Berta Ernst                         15   Charlotte Collard       8
 Eberhart Evers                      17   Edgar Engels            19
 Bernd Evertz                        16   Luc Faymonville         20
 Luc Faymonville                     20   Irene Ingels            25
 Germaine Gernegroß                  21   Marc Malmendier         36
 Gregory Groteclaes                  22   Laurent Bastiaensen     7
 Henri Hilgers                       24   Edgar Engels            19
 Hildegard Hilgers                   23   Henri Hilgers           24
 Irene Ingels                        25   Karl Kaivers            31
 Jacqueline Jacobs                   27   Melissa Meessen         37
 Jérémy Jansen                       26   Rando Roosi             2
 Johann Johnen                       28   Laurent Bastiaensen     7
 Josef Jonas                         29   Charlotte Collard       8
 Jan Jousten                         30   Daniel Dericum          11
 Karl Kaivers                        31   Henri Hilgers           24
 Guido Lambertz                      32   Laura Laschet           33
 Laura Laschet                       33   Hans Altenberg          5
 Line Lazarus                        34   Dorothée Demeulenaere   12
 Josefine Leffin                     35   Eberhart Evers          17
 Marc Malmendier                     36   Hildegard Hilgers       23
 Melissa Meessen                     37   Josef Jonas             29
 Marie-Louise Meier                  39   Laura Laschet           33
 Michael Mießen                      38   Josefine Leffin         35
==== =================================== ==== ======================= ====

>>> collected, bubbles = obj.detect_bubbles()
>>> for chain in collected:
...     print(chain)
(2 has 1 direct votes:
··(26 has 0 direct votes:

>>> for chain in bubbles:
...     print(chain)
(29 has 3 direct votes:
··(7 has 3 direct votes:
····(8 has 2 direct votes:
······(12 has 1 direct votes:
········(34 has 0 direct votes:
······(15 has 1 direct votes:
········(4 has 2 direct votes:
··········(9 has 1 direct votes:
············(3 has 1 direct votes:
··············(5 has 1 direct votes:
················(33 has 3 direct votes:
··················(10 has 1 direct votes:
····················(19 has 2 direct votes:
······················(17 has 1 direct votes:
························(35 has 1 direct votes:
··························(38 has 0 direct votes:
······················(24 has 2 direct votes:
························(23 has 2 direct votes:
··························(6 has 0 direct votes:
··························(36 has 2 direct votes:
····························(13 has 0 direct votes:
····························(21 has 0 direct votes:
························(31 has 1 direct votes:
··························(25 has 1 direct votes:
····························(20 has 1 direct votes:
······························(16 has 1 direct votes:
································(11 has 1 direct votes:
··································(30 has 0 direct votes:
··················(32 has 0 direct votes:
··················(39 has 0 direct votes:
··········(18 has 0 direct votes:
····(22 has 0 direct votes:
····(28 has 0 direct votes:
··(14 has 0 direct votes:
··(37 has 1 direct votes:
····(27 has 0 direct votes:
(2 has 1 direct votes:
··(26 has 0 direct votes:

id	user	delegate
1	A	E
2	B	C
3	C	D
4	D	E
5	E	F

After 1st loop we have:

Chain(E, [A, D]) Chain(C, [B]) Chain(D, [C]) Chain(F, [E])

After reducing the chains:

Chain(F, [Chain(E, [Chain(A), Chain(D, [Chain(C, [B])])])])

id	user	delegate
1	A	E
2	B	C
3	C	D
4	D	E
5	E	A

After 1st loop we have:

Chain(E, [A, Chain(D, [Chain(C, [B])])]) Chain(A, [E])

After reducing the chains:

Chain(E, [Chain(A), [E]), Chain(D, [Chain(C, [B])])])

Old stuff:

How to detect and resolve vote bubbles.

Let’s say we have the following series of votes:

id	seqno	user	delegate	xyz
1	1	A	E
2	2	A	B
3	1	B	C
4	1	C	D
5	1	D	A
6	1	E	A
7	2	E	F

Users A and E gave 2 votes, i.e. a “first choice” and a “alternative choice”.
Users B, C and D gave only 1 vote.
User F didn’t give any vote at all.

In our example there are four possibilities:

A1-E1 : A gets their first choice, E gets their first choice
A1-E2 : A gets their first choice, E gets their 2nd choice
A2-E1 : A gets their 2nd choice, E gets their first choice
A2-E2 : A gets their 2nd choice, E gets their 2nd choice

The system needs an algorithm that detects the case that causes least bubbling to the whole system.

The algorithm must decide which of the alternative votes to “use” and which ones to “disable”.

Let’s look at the results in each of these four cases. For each permutation, we can build a list of “vote chains”. A vote chain is an ordered sequence of users who voted for each other, without duplicates.

In case A1-E1 we have 3 vote chains:

A -> E
B -> C -> D -> A
E -> A

We can say:

We have a bubble (a circular reference): A votes for E and E for A.
Users B and F have 0 voices (nobody voted for them)
User C has 1 voice (b voted for them)
User D has 2 voices (1 direct and 1 indirect)
User A has 4 voices (2 direct and 2 indirect)
User E has 4 voices (1 direct voice from A, which carries 3 indirect voices)

In case A1-E2 we have one single vote chain:

B -> C -> D -> A -> E -> F

We can say:

User B has 0 voices (nobody voted for them)
User C has 1 voice (b voted for them)
User D has 2 voices (1 direct and 1 indirect)
User A has 3 voices (1 direct and 2 indirect)
User E has 4 voices (1 direct and 3 indirect)
User F has 5 voices (1 direct and 4 indirect)

User F is the favorite, everybody wants him.

In case A2-E1 we get two vote chains:

E -> A -> B -> C -> D

D -> A

In case A2-E2 we get three vote chains:

A -> B -> C -> D
D -> A
E -> F

More observations:

If there are 2 votes with 2 choices, we have 4 possible permutations.

If E would add a third vote, this would add two more permutations (A1-E3 and A2-E3), so we would have 6 possible permutations.

In general, the number of permutations for n users giving r votes each is:

\[P(n,r) = \frac{n!}{(n-r)!}\]

For example if we had 5 users and each of them gave 3 votes, we would have 5! / 2! = 5*4*3 = 60 possible permutations:

Next step: how to evaluate the different possibilities?

Edge case:

If A votes for B and B for A, both without any second choice, then the system should tell them that their vote is void, which means that they must either vote for somebody else or add a second choice.

digraph foo {
5 -> 3;
3 -> 9;
4 -> 15;
6 -> 23;
7 -> 29;
10 -> 33;
9 -> 4;
8 -> 7;
12 -> 8;
11 -> 16;
14 -> 29;
13 -> 36;
18 -> 4;
19 -> 10;
15 -> 8;
17 -> 19;
16 -> 20;
20 -> 25;
21 -> 36;
22 -> 7;
24 -> 19;
23 -> 24;
25 -> 31;
27 -> 37;
26 -> 2;
28 -> 7;
29 -> 8;
30 -> 11;
31 -> 24;
32 -> 33;
33 -> 5;
34 -> 12;
35 -> 17;
36 -> 23;
37 -> 29;
39 -> 33;
38 -> 35;
}