Frege's election method: discrepancy, invariant polygons and Farey geometry

Abstract

We give a comprehensive study of Frege's modified election method as a proportional allocation rule and as a dynamical system. The method was introduced by Harrenstein, Lackner and Lackner (2022) as a modification of Frege's original proposal (1918), and it coincides with the greedy algorithm for the chairman assignment problem studied by Coppersmith et al. (2011). We consider several aspects of this method. First, we prove that the harmonic bound on the discrepancy earlier shown to be sharp for time-dependent vote proportions remains sharp for fixed vote proportions; we further quantify the restrictions on votes needed for the discrepancy to come close to this bound. Secondly, the method defines a dynamical system with a piecewise translation which, for almost every vote vector, has a unique compact attractor made up of finitely many polytopes, and every orbit is equidistributed on it, whatever choices are made at ties. Thirdly, for three parties, the dynamics is two-dimensional. We construct the invariant polygons explicitly and give a complete description of the geometry governing their bifurcations as the votes vary in the two-dimensional parameter space; this space is partitioned into a countably infinite number of ``Farey cells'' indexed by reduced fractions in $(0,\frac{1}{2}]$, and each of them is further partitioned into a finite number of stability domains, separated by stability walls. In an open Farey cell indexed by a reduced fraction $u/v$, the invariant polygon has $4v+3$ vertices inside each stability domain and $4v+2$ on an internal stability wall. We construct the Farey cells explicitly and determine all stability walls and their endpoints; we also show that stability walls in different Farey cells combine to form a pattern of triangles.

arXiv comment96 pages