-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
2763 lines (2426 loc) · 97.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html>
<meta charset="utf-8">
<meta name="viewport" content="initial-scale=1">
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$', '$'], ['\\(','\\)']]},
TeX: { equationNumbers: {autoNumber: "AMS"} },
"HTML-CSS": { showMathMenu: false,
scale: 90 }
});
</script>
<link rel="stylesheet" href="base.css">
<style>
#nav {
position: static;
}
a:hover.screenshot {
opacity: .7;
}
.site {
fill: white;
stroke: black;
stroke-width: 1;
}
.client {
fill: black;
opacity: .5;
}
.repclass{
}
.voterclass{
}
.place,
.place-label {
fill: black;
opacity: 1;
stroke: none;
}
</style>
<script>
// "lightblue","lightgreen","tomato","yellow","orange"
var color_fill = ["#add8e6","#90ee90","#ff6347","#ffff00","#ffa500","#65C1A5","#8D9EC9","#E68AC2","#D4BDDC","#DDCFAF","#6EA0C8","#D90015","#DE9B13","#6EA0C8","#A4D959","#198E64","#DD0076","#936219","#525252","#615AA2"];
var color_stroke = ["#000099","#006600","#990000","#999900","#994400","black","black","black","black","black","black","black","black","black","black","black","black","black","black","black"];
</script>
<body>
<ul id="nav">
<li class="current"><a href="#intro">Intro</a></li>
<li><a href="#problem">Problem</a></li>
<li><a href="#model">Model</a></li>
<li><a href="#implementation">Implementation</a></li>
<li><a href="#demo">Live Demo</a></li>
</ul>
<div id="example_container">
<div class="example_section" id="intro">
<h1>Searching for Parliament</h1>
<subtitle>(the computer science kind of search)</subtitle>
</div>
<p>
Selecting a group of people to represent a nation is an example of what computer science calls a search problem, an assignment problem, and a load balancing problem. Distributing goods in an economy is a problem of supply and demand. These problems have something in common. We would like to sell to the highest bidder. Representatives should be the candidates who got the most votes.
</p>
<p>
Also, there is a moral problem. There is demand for representation that is not being met. Because we have single winner districts, the winner doesn't even need 50% of the vote to win the right to represent all the voters. Some voters are able to get a great deal on their politicians, while other voters could have pooled their votes across districts and elected a more valuable representative.
</p>
<p>
Let's get started on the computer science. We'll construct a mathematical model of the load balancing problem, implement this model in the Python programming language with an optimization package called Gurobi, and compute and visualize an optimal solution.
</p>
<p>
The implementation of the model and the structure of this explanation is forked from the work of Emilien Dupont (on <a href="https://github.com/EmilienDupont/facilityLocation">github</a> and hosted as <a href="http://examples.gurobi.com/facility-location/"> a featured example on Gurobi's website</a>). The code for <a href="https://github.com/paretoman/searchingforparliament">this website is on github</a>.
</p>
<h3>
Click the screenshot to skip directly to the Live Demo!
</h3>
<p>
Note: The live demo is only partly-functional because I have to work out the Gurobi license.
</p>
<p>
<a href="#demo" class="screenshot">
<img src="screenshot.png" alt="Live Demo" style="vertical-align: middle;">
</a>
</p>
<div class="example_section" id="problem">
<h2><a href="#problem" name="problem">Problem Description</a></h2>
<div style="float:right;">
<a href="https://en.wikipedia.org">
<img src="Sir_Gerald_Kaufman.jpg" alt="Sir_Gerald_Kaufman" style="width:200px;">
</a>
</div>
<p>Northern England gets rid of district boundaries because there was too much debate about where the boundaries should go. It wants to pick 5 reps (representatives). And it wants to space them out instead of having them all from the middle. It wants regional interests to be represented and it doesn't want all the seats to be taken by people from the same neighborhood in the middle of Northern England.</p>
<p>Several good candidates have decided to run, but it remains to decide which should win.</p>
<aside> A typical rep.<span style="font-size: 10px"></span>
</aside>
<p>Selecting reps from the middle of Northern England would be advantageous as they would have the most votes overall. However, voters from the middle of Northern England would be overrepresented and voters from the coast would be very far from their from their reps.</p>
<p>We will find the optimal tradeoff between reps being near all the voters and voters having reps nearby.</p>
<h3> Search Trees </h3>
<p>
Our problem is related to a very famous problem in computer science called the knapsack problem. It differs in many ways. It is similar in how it can be solved. Both are kinds of binary search. A search problem tries to find a combination of variables that is in some way the best combination. One way to approach such a problem is the branch and bound method. Here is a video on the <a href="https://www.coursera.org/learn/discrete-optimization/lecture/66OlO/knapsack-5-relaxation-branch-and-bound">branch and bound method</a> from a fantastic Coursera course in the field of <a href="https://www.coursera.org/learn/discrete-optimization/">discrete optimization</a>. From this video, just understand that <b>there is a large number of possible choices to make and that they can all be organized in a tree structure</b>. (The actual algorithm for searching through the tree will be taken care of by Gurobi, and we don't talk about it below.) We still haven't said what the score is for each choice (or path) in the tree, so let's do that. Most of the writing below is about that. Each choice in the tree represents whether a candidate wins. The first split is for the first candidate, the second split is for the second candidate, etc.
</p>
<p>
<div style="text-align: center">
<p>
<img src = "./tree.png"/>
</p>
</div>
</p>
<p>
This tree is not for the problem at hand, but our problem is similar because it has the same binary variables $x_i$.
</p>
</div>
<div class="example_section" id="model">
<h2><a href="#model" name="model">Mathematical Model</a></h2>
<p>
Let us now formulate a mathematical model for our problem.
</p>
<p>
We need to say when a candidate wins. Let's list all the candidates as can #1, can #2, can #3, etc, and let's make variables for each one. If can #1 wins, then $x_1=1$ and if can #2 loses, then $x_2=0$. Basically, $x_j$ is binary.
\[
x_j = \left\{\begin{array}{ll}
1 & \text{if we choose can #j, }\\
0 & \mathrm{otherwise.}
\end{array}\right.
\]
We set a constraint on the $x_j$ variables because there are only a limited number of seats in the legislature. We set the sum of all $x_j$ to this number of seats.
\[
\sum_{j \in Reps} x_j = \text{number of seats}
\]
</p>
<h3> Map Data </h3>
<p>
We need to say how close a voter is to a candidate. Let's list all the voters as voter #1, voter #2, etc, and let's make measurements for each voter and candidate combination. If the distance between voter #1 and can #3 is 100 km, then $d_{13}=100$.
\[
d_{ij} = \text{distance between voter i and rep j}
\]
</p>
<p>
What does a ballot look like? We want to make this problem easy to show on a map so we're going to make a simplification of the problem. We're going to let the voters give scores. This is actually nicer for the voters because they get to say what they think of every candidate. Also, voters will base their score entirely on how far away the candidate is. Basically, the score will be the inverse of distance.
\[
\begin{array}{ll}
a_{ij} & = {\displaystyle \frac{1}{d_{ij}/10 + 1} } & \text{Inverting distance}\nonumber \\
b_{ij} & = {\displaystyle a_{ij} * \frac{1}{\max_{m \in Voters}{a_{mj}}}} &\text{Ballot normalized} \nonumber
\end{array}
\]
</p>
<p>
The 10 is here for scaling distance. The extra 1 is here to avoid dividing by 0. Really, there are many choices for this function. One more modification we make is to allow voters who don't have a candidate nearby to vote with their full vote for their closest candidate. This is normalization.
</p>
<div style="text-align: center">
<p><img src="./tally.png" style="text-align: center" /></p>
</div>
<p>
We need a way to count the ballots. The easiest way is to add them together to get the tallies for each candidate.
\[
tally_j = \sum_{i \in Voters} b_{ij}
\]
</p>
<h3> Motivation </h3>
<div class="spacer" id="triggerjefftop"></div>
<p>
If we stop here then we just end up picking the candidates in the middle because they have the highest tallies.
</p>
<p>
We want to avoid overrepresenting the middle voters because they would be getting representation for cheap. <b>Think of the price of a seat in parliament as the number of voters represented by it.</b> We want as much representation as possible. We also want to avoid overrepresentation. Think of the value of a vote as a fraction of a seat in parliament. We want to spread vote value evenly so that each voter has fair representation.
</p>
<p>
Our solution is to let the reps keep a fraction of their voters' ballots. Voters have reps, so it makes sense that the reps get to keep the voters, too. Each rep must keep the same amount of votes. The idea of the rep keeping some votes is not new. The election method called Single Transferable Vote (STV) does the same thing. It is different because it doesn't use scores. It uses ranking. Still, it is very similar. When a candidate is declared a winner, he keeps a "quota" of votes and the rest of the votes go to the voters' second choices.
\[
\text{STV quota} = \frac{\text{voters}}{\text{seats} + 1}
\]
The quota is set as the number of voters divided by the number of seats to fill with reps. An additional 1 is added to the number of seats because of the iterative nature of STV (a longer explanation is needed). Basically, this quota is the price of a seat in parliament, and only those candidates with enough cash (votes) can pay this price.
</p>
<h3> Jefferson's method, Phragmen's method, and Load Balancing</h3>
<p>
Something similar also happens when deciding how many seats each state gets in the US House of Representatives. Think of it like an auction. The price starts off low and there are too many bidders and not enough seats. In an auction the price goes up until there are exactly the number of bidders left to buy all the items. It's basically the same with seats except the seats are "paid" for by population numbers.
</p>
<p style="text-align:center">
<span id="bid3"></span>
</p>
<p>
We can flip that around so that the auction house gets a higher price. We can start at a high price and then lower it until we have enough buyers. Likewise, for the House, we can start at a high number of voters required for a seat. As we lower the requirement, we assign seats to the states that can pay until all the seats are filled. It's easy to grasp because we are filling the seats one by one. Note that this method assings the seats proportionally, so a state with twice the population will have twice as many seats:
</p>
<p style="text-align:center">
<span id="bid"></span>
</p>
<p>
Also, instead of price or voters-per-seat, <b>think of the amount of representation a voter gets, the vote value</b>. Vote value starts low and is increased until one representative can be bought. The process goes one representative at a time until we fill all 435 seats.
</p>
<p style="text-align:center">
<span id="jeff"></span>
</p>
<p>
This is Jefferson's method, and it was the first method used by the US House of Representatives. It lasted for 50 years until being replaced by Webster's method, a slight variation. Jefferson's method ensured that no state got a special deal on representation when another state would have deserved it more. In this way, the states each had representation in proportion to their population.
</p>
<div class="spacer" id="triggerliquidtop"></div>
<p>
This method can be represented as an election. In this election, the ballots are pretty simple since every voter approves all the candidates from their state.
\[
b_{ij} =1 \ \ \ \ \ \forall \ j \in Reps \ , \ i\in Voters \ \ \text{in the same state.} \\
\]
Also, the candidates (or seats) are all identical and a state just gets a number of seats instead of individual representatives.
</p>
<p>
Now we have a different way to look at Jefferson's method of apportionment.
We can make a graphical representation of vote value. Let's call it y. Each vote will be represented with a box of height y and width 1. We combine many boxes together into a block, a bigger box. The block's width is the number of voters:
</p>
<p style="text-align:center">
<span id="splitrectangle"></span>
</p>
<p>
The area is what you get when you multiply the vote value (seats per vote) by the number of voters. So the area is 1 seat. Every candidate's block has an area of 1. We can write this mathematically, with v for voters, as
\[
v_j * y_j=1 \ \forall \ j \in Reps
\]
We can also restate this for every individual voter with the constraint that votes are by state.
\[
\begin{array}{rl}
b_{ij} &=1 \ \ &\forall \ j \in Reps \ , \ i\in Voters \ \ \text{in the same state.} \\
\sum_{i \in Voters} b_{ij} * y_{ij}&=1 \ &\forall \ j \in Reps \\
y_{ij} &= 1/v_j \ \ &\forall \ j \in Reps\ \text{who win} \\
\end{array}
\]
</p>
<p>
The constraint above means each representative has the same amount of representation to give to his voters. So a thinner block (less voters) will need to be taller (give more value to each vote). Let's apply this to the apportionment example from above.
</p>
<p style="text-align:center">
<span id="liquidjeff"></span> $ \approx $ <span id="liquidjeffagain"></span>
</p>
<p>
It is clear in this graph that the reason there are less green representatives is that there are less green voters. The vote value of green voters is the total height of the green blocks (since they each get 2 reps).
</p>
<p>
<b>Is this proportional? Yes. Approximately. </b> Because we have to have whole numbers of representatives, we can't represent each kind of voter exactly equally. Blue voters get a higher vote value. The best we can do is to make sure that nobody is getting a special deal on representation. There is nobody who has the votes needed for a seat that doesn't already have a seat. Every representative deserves his seat. There is no better way to stack the blocks.
</p>
<p>
What was our method of getting to this solution? Well, we stacked the blocks evenly so that no stack would be too tall. This is the shortest we can stack this number of blocks. In doing so, we kept the value of each vote nearly the same. We can state this stacking principle in math terms:
\[
\text{Minimize} \max_{i \in Voters} \sum_{j \in Reps} y_{ij}
\]
This is a load balancing problem. The idea of elections as a load balancing problem was developed by Lars Edvard Phragmén, a Swedish professor of mathematics and editor of Acta Mathematica feared for his ability to point out flaws in other people's work. This particular method is called max-Phragmen. There is another method called var-Phragmen, and he advocated for a sequential method able to be calculated by hand, seq-Phragmen. My point, and Phragmen's point, is that Jefferson's method is a specific example of a general problem of load balancing.
</p>
<h3> Pooled Votes </h3>
<p>
How can we adopt Jefferson's method with individual voters' ballots? Using parties to replace states is not a good idea because voters don't exactly fall into parties and not all party candidates are equal. Also, this gives too much power to political parties. We have a set of ballots with important information about who a voter would feel represented by. So let's try to use it.
</p>
<p style="text-align:center">
<span id="liquid12"></span>
</p>
<p>
How do we deal with this situation? The two candidates above are very similar and share some supporters. The voters who like both have a high vote value while the voters on one side or the other don't have as much vote value. Actually, the voters who like both could solve this by each deciding to pick one or the other. And that is an interesting idea. What would happen?
</p>
<p style="text-align:center">
<span id="liquid13"></span>
</p>
<p>
So the problem is solved. We just need to split this middle group of voters. We can also split them a different and equivalent way that makes more geometric sense. It just looks like the two blocks are being smushed together:
</p>
<p style="text-align:center">
<span id="liquid14"></span>
</p>
<p>
(This looks like Phragmen Tetris.)
</p>
<p>
Mathematically, we allow the blocks to smush together by removing some constraints on this vote value.
\[
y_{ij} \stackrel{?}{=} 1/v_j
\]
We let this vote value be a variable. Not every vote value should be the same. Some voters will vote for two representatives. We need to allow a voter's value to add up from all the candidates his vote helped elect. We still want this total vote value to be the same for all voters. The optimizing force ensures that will happen and that there will be an "even build" of these liquid blocks.
</p>
<p>
Since we are relaxing some constraints on y, we want to make sure it still is constrained in some ways that make sense. Let's restate everything about our new liquid block model:
\[
\begin{array}{rll}
0 \leq y_{ij} \leq 1 & \text{Vote value. Voter i bought this fraction of a seat for rep j.} \\
\\
y_{ij} \leq x_j & \text{Candidate j cannot represent anyone if he is not elected.} \\ \\
{\displaystyle \sum_{i \in Voters}y_{ij}*b_{ij}=1} \ & \text{The price of each seat is the same.} \ \ \ \forall j \in \text{Reps who win.} \\
\\
{\displaystyle \text{Minimize} \max_{i \in Voters} \sum_{j \in Reps} y_{ij}} & \text{The representation of each voter is fair.}
\end{array}
\]
</p>
<p>
Basically, what this tries to do is to find groups of voters who can pool their votes to support a representative. This pool is liquid. It can move to get the best representation. The action of minimization is animated here as a smushing force:
</p>
<p style="text-align:center">
<span id="liquid2"></span>
</p>
<p>
In addition to adjusting the distribution of the "representation liquid", we can also change which candidates are selected. Broader candidates will have an easier time smushing into other candidates.
</p>
<p style="text-align:center">
<span id="liquid8" ></span> $ \rightarrow $ <span id="liquid11"></span> $ \approx $ <span id="liquid7"></span>
</p>
<p>
They don't have to be too broad, though. The red example above has 2 candidates and they split the vote evenly. The red-blue combination achieves the same objective score as the yellow-blue combination, which means red doesn't have to be as broad as yellow. And still red is a better option than green because red is broader than green.
</p>
<p>
So a best-combination of candidates could include a set of candidates that are very local, but each have very high ratings among a community of a size at least as big as the number of voters divided by the number of seats. This is the same basic rule that was found in STV.
</p>
<p>
Another big topic is proportionality. Proportionality is important because if a party decides to split, then its voters should still get represented just the same. Actually, we have already seen a party split in an animation above. There need to still be enough members to support a candidate if there is a party split.
</p>
<p>
The big point is this: by enforcing Jefferson's method's principle of "no special deals", the representation is spread out in proportion to population. In the same way, by enforcing the same "no special deals" principle to our pool approach, we can reach a proportional outcome.
</p>
<h3> Scores </h3>
<p>
Now consider scores. Voters will want to rate some candidates in between others. One might be a 10 out of 10 while another is a 6 / 10 and another a 0.
</p>
<p style="text-align:center">
<span id="liquid1b"></span>
</p>
<p>
This is the ballot. To represent score, we use shading. These are 2 voters, left and right. They both like the green and blue candidates. The left voter gave green a 10/10 and blue a 6/10. Vice versa for the right voter. Now imagine the box is 3-D and there is a colored fluid in it. A thicker box will look darker. Thickness is the score, the b term, how much a voter liked a candidate. Another way you could think about drawing this is to spin the containers by 90 degrees so that you can see the thickness, and we will show that for just one drawing.
</p>
<p style="text-align:center">
<span id="liquid1c"></span>
</p>
<p>
Width is not a good representation of score because we are already using this dimension to represent a number of voters. Also, a voter is indivisible, so we can't do the kind of flows we showed above. There is a different kind of smushing going on for a single voter.
</p>
<p>
How do we smush these two candidates together? We can squeeze on the less dense parts to move the representation to the more dense parts. That lets the candidates fit better together.
</p>
<p style="text-align:center">
<span id="liquid1a"></span>
</p>
<p>
A liquid flows between the boxes, which are kind of like balloons because they can stretch and have different pressures. The flow makes sense because voters are being assigned to candidates they rated more highly.
</p>
<p>
Let's look at 3 candidates just for fun:
</p>
<p style="text-align:center">
<span id="liquid3"></span>
</p>
<p>
We can also change which candidates are selected. In the context of scores, a better choice of representatives might have thicker containers.
</p>
<p style="text-align:center">
<span id="liquid5"></span> $ \rightarrow $ <span id="liquid6"></span>
</p>
<p>
This is good for everyone. These are the candidates with the highest ratings.
</p>
<div class="spacer" id="triggerjeffbottom"></div>
<h3>Formal Model</h3>
<p>
Stated in formal math terms, the model minimizes the maximum of a sum of linear terms involving continuous variables $y_{ij}$ and a table of measurements $b_{ij}$. There is a binary variable $x_j$ that indicates wins, and it has a constraint that there are a specified number of winners. Gurobi takes care of the search algorithm to find the maximum among a really large number of combinations (think factorial!).
</p>
<p>
The problem is defined by the following model in the variables $x_j$ and $y_{ij}$ :
\[
\begin{array}{lll}
\text{Minimize} & {\displaystyle \max_{i \in Voters} \sum_{j \in Reps} y_{ij}} & \text{The representation of each voter is fair.} \\
\\
\text{Subject to} & {\displaystyle \sum_{i \in Voters} y_{ij} * b_{ij} =x_j } & \text{The price of each winning seat is the same.} \ \ \ \forall \ j \in Reps \\ \\
& 0 \leq y_{ij} \leq 1 & \text{Vote value. Voter i bought this fraction of a seat for rep j.} \\ \\
& y_{ij} \leq x_j & \text{Candidate j cannot represent anyone if he is not elected.} \\ \\
& x_j \in \{ 0, 1 \} & \text{Candidates either win or lose.} \\ \\
& {\displaystyle \sum_j x_j = N} & \text{Only N candidates win.} \\
\\
\\
\text{Constants } & b_{ij} = {\displaystyle \frac{a_{ij}}{\max_{m \in Voters}{a_{mj}}}} &\text{Voters score the closest candidate a 1.} \\ \\
& a_{ij} = {\displaystyle \frac{1}{d_{ij}/10 + 1} } & \text{The further away, the lower the score.}\\ \\
& d_{ij} & \text{Distance between voter i and candidate j on the map.}
\end{array}
\]
</p>
</div>
<div class="example_section" id="implementation">
<h2><a href="#implementation" name="implementation">Implementation</a></h2>
<p>Below is an example implementation of the model with example data in
Gurobi's Python interface:
</p>
<p>
For the full implementation, see <a href="https://github.com/paretoman/searchingforparliament">https://github.com/paretoman/searchingforparliament</a>.
</p>
<p> Here is a link to Gurobi. I kept it here because I forked this project from Emilien Dupont (on <a href="https://github.com/EmilienDupont/facilityLocation">github</a> and hosted as <a href="http://examples.gurobi.com/facility-location/"> a featured example on Gurobi's website</a>)
</p>
<div class="col_5 column">
<a href="http://www.gurobi.com/downloads/evaluation-request">
<button class="red stack-button">
<i class="fa fa-lg fa-line-chart"></i>
Commercial Users: Free Evaluation Version
</button>
</a>
</div>
<div class="col_5 column">
<a href="http://www.gurobi.com/downloads/download-center">
<button class="red stack-button">
<i class="fa fa-lg fa-line-chart"></i>
Academic Users: Free Academic Version
</button>
</a>
</div>
<p>
I suggest using conda to install it. And then there is a license to download, so you have to make an account on the gurobi website. I used Python 2.
</p>
<div class="spacer" id="triggerliquidbottom"></div>
<examplecode>
from gurobipy import *
import math
import numpy
# Problem data
voters = [[c1,c2] for c1 in range(10) for c2 in range(10)]
reps = [[f1*3+1.5,f2*3+1.7] for f1 in range(3) for f2 in range(3)]
numReps = len(reps)
numVoters = len(voters)
nWinners = 5
# Calculate constants
d = numpy.zeros((numVoters,numReps))
a = numpy.zeros((numVoters,numReps))
b = numpy.zeros((numVoters,numReps))
def distance(a,b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return math.sqrt(dx*dx + dy*dy)
for i in range(numVoters):
for j in range(numReps):
d[i,j] = distance(voters[i], reps[j])
a = 1 /( d/10 + 1 )
for i in range(numVoters):
b[i,:] = a[i,:] / max(a[i,:])
# Add variables
m = Model()
x = {}
for j in range(numReps):
x[j] = m.addVar(vtype=GRB.BINARY, name="x%d" % j)
y = {}
for i in range(numVoters):
for j in range(numReps):
y[(i,j)] = m.addVar(lb=0, ub=1, vtype=GRB.CONTINUOUS, name="t%d,%d" % (i,j))
Z = m.addVar(lb=0, vtype=GRB.CONTINUOUS, name="z")
m.update()
# Add constraints
m.addConstr(quicksum(x[j] for j in range(numReps)) == nWinners)
for j in range(numReps):
m.addConstr( x[j] == quicksum(b[i,j]*y[(i,j)] for i in range(numVoters)) )
for i in range(numVoters):
m.addConstr( Z >= quicksum( y[(i,j)] for j in range(numReps) ) )
# Set objective and optimize
m.setObjective(Z,GRB.MINIMIZE)
m.optimize()
# Output
print(["%d" % x[j1].X for j1 in range(numReps)])
</examplecode>
</div>
<div class="example_section" id="demo">
<h2><a href="#demo" name="demo">Live Demo</a></h2>
<p>
Below is a visualization of our example. We are using the
location data from <a href="#geolytix">GeoLytix</a> for a large
supermarket chain in the UK, and visualizing its outlets in
Northern England. (This is an approximation to population distribution.)
</p>
<p>
The voters are represented by:
<svg height="20" width="20">
<circle cx="10" cy="15" r="3" fill="black" opacity=".5" />
</svg>
</p>
<p>
By clicking the map you can add candidate locations.
These are drawn as:
<svg height="20" width="20">
<circle cx="10" cy="10" r="8" stroke="black" stroke-width="1" fill="white" />
</svg>
</p>
<p>
Click "Compute Winners" to find the winners. These will be drawn as:
<svg height="20" width="100">
<circle class="circlelist" cx="10" cy="10" r="8" stroke="#000099" stroke-width="3" fill="lightblue" />
<circle class="circlelist" cx="30" cy="10" r="8" stroke="#006600" stroke-width="3" fill="lightgreen" />
<circle class="circlelist" cx="50" cy="10" r="8" stroke="#990000" stroke-width="3" fill="tomato" />
<circle class="circlelist" cx="70" cy="10" r="8" stroke="#999900" stroke-width="3" fill="yellow" />
<circle class="circlelist" cx="90" cy="10" r="8" stroke="#404040" stroke-width="3" fill="orange" />
</svg>
<script>
d_circles = document.getElementsByClassName("circlelist")
for (var i=0; i < 5; i+=1) {
d_circles[i].fill = color_fill[i]
d_circles[i].stroke = color_stroke[i];
}
</script>
</p>
<p>
A few candidate locations have already been set up, but
you can add more by clicking the screen.
</p>
<p>
Note: The live demo is only partly-functional because I have to work out the Gurobi license. You can still use beast-mode to run openSTV elections and more. Just not the Phragmen method.. which is the one I described in detail on this page.
</p>
<aside style="width:150px">
<div id="options" style="display:none">
<form>
<fieldset>
<legend>Map:</legend>
<input type="range" min = .1 max = 1 step = .1 id="zoom_id" value="1" oninput="updateZoom(value)" class="slider-width" style="width:60px">Zoom<br />
<input type="range" min = -1 max = 1 step = .1 id="xshift_id" value="0" oninput="updateXshift(value)" class="slider-width" style="width:60px">X<br />
<input type="range" min = -1 max = 1 step = .1 id="yshift_id" value="0" oninput="updateYshift(value)" class="slider-width" style="width:60px">Y<br />
</fieldset>
<fieldset>
<legend>Ballot:</legend>
<input class="op" checked="true" type="checkbox"> Normalize <br />
<input class="op" checked="true" type="radio" name="ballots"> 1 / Distance<br />
<input class="op" type="radio" name="ballots"> Linear <br />
<input class="op" type="radio" name="ballots"> Exponential <br />
<input class="op" type="radio" name="ballots"> Threshold (todo) <br />
</fieldset>
<fieldset>
<legend>Computation:</legend>
<input class="op" type="radio" name="compute" checked="true"> Phragmen<br />
<input class="op" type="radio" name="compute"> Phragmen bid <br />
<input class="op" type="radio" name="compute"> RRV max <br />
<input class="op" type="radio" name="compute"> RRV rep<br />
<input class="op" type="radio" name="compute"> Binary Quadratic Problem <br />
<input class="op" type="radio" name="compute"> STV <br />
<input class="op" type="radio" name="compute"> Meeks STV <br />
<input class="op" type="radio" name="compute"> RRV <br />
<input class="op" type="radio" name="compute"> RRV-TDON <br />
<input class="op" type="radio" name="compute" id="openstv"> OpenSTV
<select id="stvtype" name="stvtype" onclick="selectOpenstv()">
<option value="Approval">Approval (bug?)</option>
<option value="Borda">Borda</option>
<option value="Bucklin">Bucklin</option>
<option value="CambridgeSTV">CambridgeSTV</option>
<option value="Condorcet">Condorcet</option>
<option value="Coombs">Coombs</option>
<option value="ERS97STV">ERS97STV</option>
<option value="FTSTV">FTSTV</option>
<option value="GPCA2000STV">GPCA2000STV</option>
<option value="IRV">IRV</option>
<option value="MeekQXSTV">MeekQXSTV</option>
<option value="MeekSTV">MeekSTV</option>
<option value="NIrelandSTV">NIrelandSTV</option>
<option value="QPQ">QPQ</option>
<option value="RTSTV">RTSTV</option>
<option value="SNTV">SNTV</option>
<option selected="selected" value="ScottishSTV">ScottishSTV</option>
<option value="SuppVote">SuppVote</option>
<option value="WarrenQXSTV">WarrenQXSTV</option>
<option value="WarrenSTV">WarrenSTV</option>
</select> <br />
<input class="op" type="radio" name="compute"> Plurality Multiwinner <br />
<input class="op" id="schulzestv" type="radio" name="compute"> Schulze STV (bug)<br />
<input class="op" id="cluster" type="radio" name="compute"> Load Balancing<br />
<select id="loadType" onclick="selectCluster()">
<option value="min total distance">min total dist</option>
<option value="max total ballot">max total ballot</option>
<option value="max min-total-ballot (jefferson)">jefferson</option>
<option value="min diff-total-ballot (webster)">webster</option>
</select> <br />
<input class="op" type="radio" name="compute"> A new formulation (working on it) <br />
<input class="op" type="radio" name="compute"> RRV Load Balance Fast way?<br />
<input class="op" type="radio" name="compute"> RRV Load Balance Easy way<br />
<input class="op" type="radio" name="compute"> RRV bid <br />
<input class="op" type="radio" name="compute"> RRV max easy<br />
<input class="op" type="radio" name="compute"> var-Phragmen<br />
</fieldset>
<fieldset>
<legend>Output:</legend>
<input id="calcVoterCom" type="checkbox" checked="true"> Calculate Voter Communities <br />
</fieldset>
<fieldset>
<legend>Keeps:</legend>
<input type="range" min = 500000 max = 3000000 step = 500000 id="cost" value="1000000" oninput="outputUpdate(value)" class="slider-width" style="width:100px"> <br />
<output for=cost id=costDisplay>1.0</output> Multiplier <br />
<input class="op" type="radio" name="keeps" checked="true"> Seats Plus Zero <br />
<input class="op" type="radio" name="keeps"> Seats Plus Half <br />
<input class="op" type="radio" name="keeps"> Seats Plus One <br />
</fieldset>
<fieldset>
<legend>Similarity Measure:</legend>
<input class="op" type="radio" name="similarity" checked="true"> Jaccard<br />
<input class="op" type="radio" name="similarity"> Both Out Of One<br />
<input class="op" type="radio" name="similarity"> One From Either<br />
<input class="op" type="radio" name="similarity"> Simultaneous<br />
<input class="op" type="radio" name="similarity"> integrateKeeps<br />
<input class="op" type="radio" name="similarity"> Cosine<br />
<input class="op" type="radio" name="similarity"> L1<br />
<input class="op" type="radio" name="similarity"> multiplySupport<br />
</fieldset>
<input class="op" id="doballotfile" type="checkbox"> Ballot File Input? <br />
<input class="op" id="doballotfile" type="checkbox"> multiply vote factors by score<br />
<input class="op" type="checkbox"> more winners (x5)<br />
<input class="op" id="dohist" type="checkbox"> show proportionality output<br />
<textarea id="ballotfile" rows="4" cols="15">20 3 1 1 0 20 1 3 1 0 20 1 1 3 0 20 0 0 0 3 color 1 2 3 4 times 10 10 10 10</textarea>
</form>
</div>
</aside>
<div id="demoarea">
</div>
<div id="spinnerdiv">
</div>
<div style="float:left;width:800px;">
<div style="float: left; width: 100%;">
<p>
<button class="pure-button" onclick="compute()">Compute Winners</button>
<button onclick="restart()">Restart</button>
<button class="pure-button" onclick="toggle_options()">Beast Mode</button>
<button class="pure-button" onclick="toggle_div()">Gurobi Log</button>
<input type="range" min = 1 max = 20 step = 1 id="numberOfWinners" value="5" oninput="numberOfWinnersUpdate(value)" class="slider-width" style="width:200px">
<output for=numberOfWinners id=numberOfWinnersDisplay>5</output> Winners <br />
</p>
</div>
<div id="divvotertableshow" style="width: 49%; float: left;">
<p>
Voter Communities:
</p>
<canvas id="votertableshow" width="350" height="350"></canvas>
</div>
<div id="divbtable" style="width: 24%; float: left;">
<p>
Ballots:
</p>
<canvas id="btable" width="155" height="350"></canvas>
</div>
<div id="divytable" style="width: 24%; float: left;">
<p>
Voter Assignment (y):
</p>
<canvas id="ytable" width="155" height="350"></canvas>
</div>
<div id="divtableshow" style="width: 50%; float: left; ">
<p>
Election Results (tally and similarity):
</p>
<canvas id="tableshow" width="350" height="300"></canvas>
</div>
<div id="divybtable" style="width: 24%; float: left;">
<p>
Support (y*b):
</p>
<canvas id="ybtable" width="155" height="350"></canvas>
</div>
<div id="divsybtable" style="width: 12%; float: left;">
<p>
Sum y*b:
</p>
<canvas id="sybtable" width="100" height="350"></canvas>
</div>
<div id="divsytable" style="width: 12%; float: left;">
<p>
Sum y:
</p>
<canvas id="sytable" width="100" height="350"></canvas>
</div>
<div style="width: 49%; float: left;">
Vote Value (y):
<p>
<span id="liquid16"></span>
</p>
</div>
<div style="width: 49%; float: left;">
Support for Winners (y*b):
<p>
<span id="liquid17"></span>
</p>
</div>
<div style="width: 49%; float: left;">
Vote Value again (y):
<p>
<span id="liquid15"></span>
</p>
</div>
<div>
<p style="text-align:center">
<span id="download"></span>
</p>
</div>
<div>
<p style="text-align:center">
<span id="texthist"></span>
</p>
</div>
</div>
<script>
var cost;
var numberOfWinners;
function outputUpdate(value) {
document.querySelector('#costDisplay').value = value/1000000;
}
function numberOfWinnersUpdate(value) {
document.querySelector('#numberOfWinnersDisplay').value = value;
}
function updateZoom(value) {
zoomit = value;
draw_map();
}
function updateXshift(value) {
xshift = value;
draw_map();
}
function updateYshift(value) {
yshift = value;
draw_map();
}
function selectOpenstv() {
document.querySelector('#openstv').checked = true;
}
function selectCluster() {
document.querySelector('#cluster').checked = true;
}
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script>
function toggle_div() {
var logfile = d3.select('#logfile');
if (logfile.style("display") === "none") {
logfile.style("display", "block");
} else {
logfile.style("display", "none");
}
}
function toggle_options() {
var optionsdiv = d3.select('#options');
var tableshowdiv = d3.select('#divtableshow');
var votertableshowdiv = d3.select('#divvotertableshow');
optionsdiv.style("display", "block");
tableshowdiv.style("display", "block");
votertableshowdiv.style("display", "block");
//actually we don't want to cause confusion. If you activate beast mode, you can't go back.
// if (optionsdiv.style("display") === "none") {
// optionsdiv.style("display", "block");
// } else {
// optionsdiv.style("display", "none");
// }
}
</script>
<examplecode id=logfile style="float:left; width: 100%;">
</examplecode>
</div>
<div style="float:left">
<p>
<button id="morebutton" class="pure-button" onclick="toggle_readmore()">Read More</button>
</p>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script>
function toggle_readmore() {
var readmorediv = d3.select('#readmore');
if (readmorediv.style("display") === "none") {
readmorediv.style("display", "block");
} else {
readmorediv.style("display", "none");
}
}
</script>
</div>
<div id="readmore" style="display:none; float:left">
<p>
The output is worth explaining. Similarity measures between voters can be put into a table so that more similar pairs are indicated by light grey and distant pairs are represented by dark grey. This is the "voter communities" table. Similarity measures are used for the canidates as well. This is the "election results" table. Also, to the left of the election results table is a bar chart showing the vote totals for each rep. The scale at the bottom has tick marks that indicate a votes/seats. The great thing about this kind of table of election results is that it shows communities of similar people. Each community looks like a big bright square along the diagonal. You can see how big each community of voters is and which reps (colors) are serving each community.
</p>
<p>
Also, the raw ballots are shown (b). Next, Phramgen's method calculates the y data, which indicates vote value. Below these are y*b. This is the amount of representation each representative is giving. Each gives an equal amount (the column sum is the same for all the winners). To the right is voters' total representation and voters' vote value. At the bottom is an animated chart showing how the blocks of candidate votes are spread across the voters by smushing. These are the same blocks we've been talking about, and they are more detailed because we are dealing with a real election.
</p>
<p>
There is also a beast mode where you can see different computations. STV is included. <a href="https://www.opavote.com/methods/single-transferable-vote">OpenSTV's implementations</a> of several voting methods are there. There are other load balancing methods where the weight of each part of a ballot is optimized to give the most support to the winners. In other words, the total distance between voters and reps is minimized. This is similar to the project that this project was forked from. There is a reweighted range voting (RRV) as an option as well. In addition to computations, there are also different ballot types, an option for disabling normalization, an option for adding a +1 to the seats, different similarity measures for the binary quadratic problem, etc. .
</p>
<p>
In beast mode, there is also a text entry area where you can input values separated by whitespace or commas. Each row is for voters. The first number in the row is the number of voters who voted the same way. A special row called "times" says how many candidates are running as clones. A special row called "color" allows assignment of color to the candidates. Integers represent colors.
</p>
<p style="font-size:8px">
<a name="geolytix">Location data:</a>
<a href="http://geolytix.co.uk/downloads/OpenSupermarkets.zip">Supermarket
locations © GeoLytix</a> copyright and database right 2014.
</p>
<div class="example_section" id="thoughts">
<h3> Thoughts </h3>
<p>
The first incarnation of this page is <a href="./bqpr.html">here</a>. It is an approximation to proportionality, and it explains more of what the output charts mean. It has a drawback because it overcounts in the case of a 3-way party split where the split is not complete.
</p>
<h3> Re-weighted Range Voting </h3>
<p>
By the way, we can still think about another way to state this problem that better corresponds to a picture of price:
</p>
<p style="text-align:center">
<span id="price"></span>
</p>
<p>
Compare that to the picture of representation we had used instead:
</p>
<p style="text-align:center">
<span id="rep"></span>
</p>
<p>
Now look at the math form of fair price:
\[
\begin{array}{lll}
\text{Maximize} & \min_{j \in Reps} \sum_{i \in Voters} y_{ij}*b_{ij} & \text{The price of each seat is fair.} \\
\text{Subject to} & \forall \ i \in Voters \ \ \sum_{j \in Reps} y_{ij}=1 & \text{The representation of each voter is the same.} \\
\end{array}
\]
Versus the math form of fair representation:
\[
\begin{array}{lll}
\text{Minimize} & { \max_{i \in Voters} \sum_{j \in Reps} y_{ij}} & \text{The representation of each voter is fair.} \\
\text{Subject to} & {\forall \ j \in Reps} \ \ \sum_{i \in Voters} y_{ij} * b_{ij} =x_j \ \ \ & \text{The value of each winning seat is the same.}
\end{array}
\]
These are actually equivalent statements in some cases. For instance, if voters are partisan, then the statements are the same. Otherwise, I imagine these statements can be different.
</p>
<p>
"Phragmen Bid" in Beast Mode is the price-based formulation. As far as I can tell, it gives the same results as Phragmen.
</p>
<h3> Motivation for RRV</h3>
<p>
The smushing rules might not seem fair. Most voters end up just getting all their vote assigned to one representative when really they like a couple different ones. So it seems like we could add a rule that says your vote gets divided in proportion to how much you like each winning candidate.
</p>
<p style="text-align:center">
<span id="liquid14again"></span>
</p>
<p>
In math terms,
\[
\frac{y_{ij}}{b_{ij}}=f_i \quad \text{Vote value is proportional to score. (for all winning candidates)}
\]
"RRV max" is what I call this method in beast mode. RRV stands for "re-weighted range voting". I think this method has the same goal as RRV. It wants to divide each voter proportional to his scores and pick the candidates with the highest total scores.
</p>
<p>
Right now, this method, as implemented, is kinda slow. Maybe there is a way to speed it up. Try the regular RRV method, which is an approximation to this optimization.
</p>
<p>
For a little more math, maybe we can understand a little more. Using this f term in the price of each seat, we get
\[
\sum_{i \in Voters} y_{ij}*b_{ij} = \sum_{i}
f_i*b_{ij}^2
\]
What is f?
\[
\begin{align}
y_{ij} &=f_i * b_{ij} * x_j \nonumber \\
\sum_j y_{ij} &= 1 \nonumber \\
\text{so} \ \sum_j f_i * b_{ij} * x_j &= 1 \nonumber \\
f_i &= { \displaystyle \frac{1}{\sum_j b_{ij} * x_j }} \nonumber \\
\end{align}
\]
Well, I guess that gives us an expression for f but I need to think a little more about what that expression means. And we could write the problem as
\[
\text{Maximize} \quad { \min_j \sum_i \frac{b_{ij}^2}{\sum_j x_j*b_{ij}}}
\]
This is just what you get when you try to eliminate as many variables as you can, though I have to think about it more to get some insight. What's nice about this is there is no y term.
</p>
<p>
The purpose of writing this was to show how STV and RRV are related. We related STV to Phragmen to RRV. The main difference is the idea of whether individual votes should be divided proportionally among the winning candidates. In STV, you whole vote goes to one candidate while in RRV it gets divided proportional to how much you supported the candidate.
</p>
<p>
Oh yeah, and we can do an RRV method that is similar to phragmen. Call this "RRV rep" becase it does fair representation instead of fair price.
\[
\begin{array}{lll}
\text{Minimize} & { \max_{i \in Voters} \sum_{j \in Reps} f_i * b_{ij} * x_j} & \text{The representation of each voter is fair.} \\
\text{Subject to} & {\forall \ j \in Reps} \ \ \sum_{i \in Voters} f_i * b_{ij}^2 *x_j =x_j \ \ \ & \text{The value of each winning seat is the same.}
\end{array}
\]
</p>
<h3> More thoughts </h3>
<p>
Also, another great topic of consideration is what scores a voter would actually want to give a candidate? How is a 9 different than a 6 or a 2? Well, to answer that, I've been thinking that a really good scoring system would basically have 2 major levels and ranks at each one. So basically, there would be a 10.0, 9.9, 9.8 and then a 0.2 0.1 0.0. Because voters really either like you or they don't. And they might have a preference for someone else but it won't mean they'll not support whoever wins just as much. Voters still want to give the same opportunity to every candidate that they like. They also would rather be represented by a particular person. If that person doesn't find enough support with other people, then they'd like to be represented by a second choice. So really there are 2 lists. The approved list and the bad list. And there are rankings in each list. This is actually something I've seen at rankechoicevote.com but I haven't seen it anywhere else.
</p>
<p>
Also having all the ratings right near 10, like 10.0, 9.9 etc would mean that a vote gets transferred basically in full. This would be like STV. This is how you would make a ranking system out of Phragmen's method.
</p>
<p>
</div>
</div>
</div>
<div style="min-height:100px"></div>
<!--[if gt IE 8]><!--><script src="//ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script><!--<![endif]-->
<script src="jquery.nav.js"></script>
<script>
$(document).ready(function() {
console.log('calling onePageNav');
$('#nav').onePageNav({scrollOffset:120});
});
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="https://d3js.org/topojson.v1.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/spin.js/1.2.7/spin.min.js"></script>
<script>
// Hide Log File intially
d3.select('#logfile').style("display", "none");
//Width and height
var width = 800;
var height = 500;
var padding = 30;
var miles_per_px = 0.19;
var price_per_px = 3*miles_per_px;
var alpha = 5*365*price_per_px; // Consider the cost over 5 years
alpha = alpha * 1754385.964912 * 0.000548 // let's change alpha for "keep"
alpha = 1000100
alpha = 1000000