How to draw Congressional districts to mirror the Popular Vote Let me preface this by saying that I'm not sure whether this is fundamentally a mathematical question or not, but I think it is.
In the United States, the House of Representatives is elected roughly as follows.  The country is divided into 435 contiguous congressional districts, drawn in such a way that each district contains approximately the same number of people.  And the people in each district elect one person to represent them in the House of Representatives.  
Suppose for simplicity that there are only two political parties, the Democrats and the Republicans.  Now an often-criticized fact about congressional elections is that there is a divergence between the House Popular Vote, the percentage of people all across the country who voted for one party over the other in the Congressional election, and the party control of the House of Representatives, i.e. the percentage of members of the House who belong to each party.  This is sometimes due to gerrymandering, or the intentional drawing of districts to benefit one party or the other, but it's often just due to how the districts are naturally drawn.  To take an extreme example, if people voted for Republicans 1 - 0 in 434 out of 435 districts, and they voted 500-66 for Democrats in the last district, then Republicans would win the House of Representatives 434-1, even though the popular vote would be tied 500-500.
Now people often just point to this divergence as a symptom of some other problems that we need to fix, and they propose redrawing district maps to fix those more fundamental problems.  But my question is, what if you made minimizing the divergence your criteria?  That is to say, given only the requirements that the number of districts must stay at 435, that districts must contain equal numbers of people, and that they must be contiguous regions, what is the mathematically optimal way to draw districts such that the the divergence between party control percentages and national popular vote percentages is minimized?
Note that I'm not asking for what the actual optimal districts are for the United States would be, I'm just asking what mathematical methods would allow you to solve this general type of problem?  I assume in practice you would just do a numerical simulation where you try lots of different possible district maps until you found one that approximately optimal, but just at an intuitive level, what sort of district drawing scheme would be at least close to optimal? 
 A: If we assume that districts have the same number of inhabitants, the divergence between party control percentages and national popular vote percentages is substantially dependent on the variable proportion of actual voters in each district. In a theorerical situation where this proportion is constant across districts, divergence would be eliminated. So, to minimize divergence, we have to find a way to minimize the voting proportion variability. This means to redraw districts in such a way that each of them contains approximately not only the same number of people, but also the same number/proportion of actual voters.
To do this, it is necessary that the proportion of voters across the whole Country is somewhat predictable with sufficient geographic definition. If we assume total unpredictability, there is no way to define "fixed" districts prior to the elections and avoiding the risk of divergence. Alternatively, considering the problem only from a mathematical point of view, we could imagine - albeit politically not feasible - to design districts after the elections, when the proportion of voters across the Country is known.
In both cases, the problem reduces to that of drawing $435$ districts in such a way that they are approximately homogeneous in both number of inhabitants and number/proportion of voters. This could be done as follows:

*

*start from a division of the Country in $K$ arbitrary, random subdistricts (with $K>>435$), each with the same number of inhabitants (to optimize the results of the successive algorithm, it is preferrable to choose $K$ among exact multiples of $435$);


*draw, for each subdistrict, the local proportion of actual voters;


*calculate the average proportion (predicted or observed) of actual voters in the whole Country, and call it $p$;


*begin the construction of the first district by randomly choosing an initial subdistrict (say that it has voting proportion $p_1$);


*add a second contiguous subdistrict, to get a larger region with resulting voting proportion $p_2$,  choosing the subdistrict that allows the maximal "nearing" of $p_2$ to $p$ (i.e., the one that minimizes the distance $|p-p_2|$);


*iterate the process, progressively adding new contiguous subdistricts, to get a growing region with evolving overall voting proportion $p_i$, each time choosing the subdistrict that minimizes the distance $|p-p_i|$;


*stop the process when you approximately reach the desired total number of inhabitants of a district: note that, if $K$ has previously been chosen among exact multiples of $435$, stopping the process after $\frac{K}{435}$ steps we have built a district with exactly $\frac{N}{435}$ inhabitants (where $N$ is the total population of the Country);


*repeat the process to create the other districts.
The final result should be a division in $435$ districts with the same number of inhabitants and approximately the same number/proportion of actual voters. In this condition, divergence should be considerably reduced, and probably minimized.
