Huntington Hill Method

[rwd1981]

Hello,

I hope that I can find some help here. I would like to build a utility using Excel that will allocate representatives among several states using the Huntington Hill Method. I have already done so, in fact, but it is cumbersome and I would like scalability. I believe that both problems can be solved using the byrow and Lambda tools.

The most important part of the HH method is that it applies a recursive quotient to each state, evaluating the impact of adding an additional representative to that state's delegation. The state with the highest quotient gets that representative, which changes that state's total delegates, so that the calculation must be run all over again before the next representative can be assigned.

My current build of the utility has each state assigned a row and each representative assigned a column. The first columns, equal in number to the number of states, are given over to assigning each state a representative, since every state gets at least one. I then paste the quotient formula in all of the subsequent cells of the array. Each column has a cell at the top which finds the maximum quotient value among the states below it, and adds another representative to that state's total.

I don't like how many cells it takes up. I have 64 states and over 1,000 representatives. I also don't like how I will have to alter the array itself when I want to change the number of states or of representatives. I believe I should be able to create a list which expands or contracts to an input number of states -- that part I think I can handle. But I believe that I should also be able to set one cell as an input for the number of representatives total to be assigned, and another cell with a formula that uses byrow and Lambda to do all the heavy lifting. I think that formula can be made to 1) assign one representative to each state, 2) evaluate each state's need to be assigned an additional representative, 3) assign that representative to the state's total delegation, and 4) run that process again and again until the total number of delegates assigned between all the states matches the input.

Am I wrong? If it can be done, could someone help me with the syntax?

Thanks for reading. Thanks in advance for any help you can provide.

 

[KRice]

Based on my understanding of the Huntington-Hill method, I'm not sure you need recursion. You can do that, but since only one representative is assigned during each iteration, only one State's Constituency Priority Quotient (CPQ) will change during each iteration...the CPQ being the State's population or votes divided by the "Modified Divisor", D, where D is the geometric mean of the upper and lower representative quotas...with the lower quota representing the current allocation, n, and the upper quota representing the allocation should the State receive a representative, so n+1. Therefore D = sqrt(n * (n+1)). And the CPQ = (population or votes) / D. And since the decision regarding which State should be allocated the next representative is based on the maximum CPQ, you really only need to examine a sorted list of CPQ's after the initial allocation of representatives to determine the order of the States that will be allocated more representatives. All of this hinges on being able to make the initial allocation, which I believe is typically done by taking the total population (or votes) over all States and dividing by the number of representatives that are to be allocated over all States, thus establishing a baseline equi-representation ratio...some population (or votes) per representative that should approximately be applied to each State. Then each State's population (or votes) is divided by this equi-representation ratio and we take the FLOOR of that quotient (i.e., round down to an integer). The only exception is if the result of the FLOOR operation produces 0, we instead award 1 representative to that State since each State must have at least one rep.

All of this is done in columns A:F in this example, and by the time the calculations lead to column F, we know how many representatives' seats remain to be allocated (let's say that is y) and we can simply sort the CPQ's to determine the y-largest CPQ's and award each of them 1 more representative, at which point, all of the allocations are complete. The sorting and final allocations are shown in columns AB:AC.

To begin, I created a notional list of States and Populations:

Book1
	AE	AF	AG
1		Min Pop or Votes	100,000
2		Max Pop or Votes	80,000,000
3
4
5		Notional Data	1311009370
6	State Idx	State Name	State Population
7	1	State1	58,522,682
8	2	State2	15,114,666
9	3	State3	66,845,002
10	4	State4	54,756,201
11	5	State5	13,850,711
12	6	State6	53,928,483
13	7	State7	60,537,641
14	8	State8	29,265,417
15	9	State9	35,142,314
16	10	State10	30,775,540
17	11	State11	4,395,702
18	12	State12	71,288,307
19	13	State13	11,381,141
20	14	State14	50,349,182
21	15	State15	56,806,024
22	16	State16	77096835
23	17	State17	41639551
24	18	State18	73688829
25	19	State19	38656445
26	20	State20	76790150
27	21	State21	50691883
28	22	State22	7305114
29	23	State23	26393599
30	24	State24	53553618
31	25	State25	2091902
32	26	State26	54507457
33	27	State27	36267332
34	28	State28	70904785
35	29	State29	17162762
36	30	State30	71300095
Sheet1

Cell Formulas
Range	Formula
AG5	AG5	=SUM(AG7#)
AE7:AE36	AE7	=SEQUENCE(C1)
AF7:AF36	AF7	="State"&AE7#
AG7:AG36	AG7	=RANDARRAY(C1,1,$AG$1,$AG$2,TRUE)
Dynamic array formulas.

And then these data are fed into the Allocation computation, where we see that after the initial allocation, 985 of 1000 representatives have already been allocated based in the equi-representation rules. Then based on the sorted order of CPQ's (see AB), we know that States in list positions 1, 4, 3, 11, etc. will receive representatives in that order until all allocations have been made. The green computation block is shown for the 1st allocation (after the initial Allocation 0). That computation block (all three columns) can be copied and pasted to extend the iterations, but that is not really necessary. I've shown two more computation blocks for information purposes, but we know after column F which States will receive more representatives, and we can jump over to columns AB:AC for the final result.

Book1
	A	B	C	D	E	F	G	H	I	J	K	L	M														AA	AB	AC
1		Number of States	30
2		Total Representatives to Assign	1000
3		Equal Representation ((pop or votes)/rep)	1,311,009.37
4
5			1,311,009,370	985	Max Idx->	1	986	Max Idx->	4	987	Max Idx->	3	988																1000
6	Idx	States	Population or Votes	Num Reps: Allocation 0	Modified Divisor, D	Constituency Priority Quotient	Num Reps Aft Alloc 1	D	CPQ	Alloc	D	CPQ	Alloc															Known After Allocation 0	Final Rep Allocations
7	1	State25	2,091,902	1	1.414	1,479,198	2	2.449	854,015	2	2.449	854,015	2															1	2
8	2	State11	4,395,702	3	3.464	1,268,930	3	3.464	1,268,930	3	3.464	1,268,930	3															4	4
9	3	State22	7,305,114	5	5.477	1,333,725	5	5.477	1,333,725	5	5.477	1,333,725	6															3	6
10	4	State13	11,381,141	8	8.485	1,341,280	8	8.485	1,341,280	9	9.487	1,199,678	9															11	9
11	5	State5	13,850,711	10	10.488	1,320,613	10	10.488	1,320,613	10	10.488	1,320,613	10															24	11
12	6	State2	15,114,666	11	11.489	1,315,563	11	11.489	1,315,563	11	11.489	1,315,563	11															17	12
13	7	State29	17,162,762	13	13.491	1,272,189	13	13.491	1,272,189	13	13.491	1,272,189	13															14	14
14	8	State23	26,393,599	20	20.494	1,287,876	20	20.494	1,287,876	20	20.494	1,287,876	20															5	21
15	9	State8	29,265,417	22	22.494	1,301,006	22	22.494	1,301,006	22	22.494	1,301,006	22															20	23
16	10	State10	30,775,540	23	23.495	1,309,894	23	23.495	1,309,894	23	23.495	1,309,894	23															12	24
17	11	State9	35,142,314	26	26.495	1,326,361	26	26.495	1,326,361	26	26.495	1,326,361	26															30	27
18	12	State27	36,267,332	27	27.495	1,319,030	27	27.495	1,319,030	27	27.495	1,319,030	27															16	28
19	13	State19	38,656,445	29	29.496	1,310,576	29	29.496	1,310,576	29	29.496	1,310,576	29															6	30
20	14	State17	41,639,551	31	31.496	1,322,057	31	31.496	1,322,057	31	31.496	1,322,057	31															22	32
21	15	State14	50,349,182	38	38.497	1,307,881	38	38.497	1,307,881	38	38.497	1,307,881	38															19	39
22	16	State21	50,691,883	38	38.497	1,316,783	38	38.497	1,316,783	38	38.497	1,316,783	38															29	38
23	17	State24	53,553,618	40	40.497	1,322,412	40	40.497	1,322,412	40	40.497	1,322,412	40															13	40
24	18	State6	53,928,483	41	41.497	1,299,576	41	41.497	1,299,576	41	41.497	1,299,576	41															10	41
25	19	State26	54,507,457	41	41.497	1,313,528	41	41.497	1,313,528	41	41.497	1,313,528	41															27	41
26	20	State4	54,756,201	41	41.497	1,319,522	41	41.497	1,319,522	41	41.497	1,319,522	41															26	41
27	21	State15	56,806,024	43	43.497	1,305,972	43	43.497	1,305,972	43	43.497	1,305,972	43															15	43
28	22	State1	58,522,682	44	44.497	1,315,199	44	44.497	1,315,199	44	44.497	1,315,199	44															21	44
29	23	State7	60,537,641	46	46.497	1,301,960	46	46.497	1,301,960	46	46.497	1,301,960	46															28	46
30	24	State3	66,845,002	50	50.498	1,323,728	50	50.498	1,323,728	50	50.498	1,323,728	50															23	50
31	25	State28	70,904,785	54	54.498	1,301,060	54	54.498	1,301,060	54	54.498	1,301,060	54															25	54
32	26	State12	71,288,307	54	54.498	1,308,097	54	54.498	1,308,097	54	54.498	1,308,097	54															9	54
33	27	State30	71,300,095	54	54.498	1,308,314	54	54.498	1,308,314	54	54.498	1,308,314	54															18	54
34	28	State18	73,688,829	56	56.498	1,304,278	56	56.498	1,304,278	56	56.498	1,304,278	56															8	56
35	29	State20	76,790,150	58	58.498	1,312,700	58	58.498	1,312,700	58	58.498	1,312,700	58															7	58
36	30	State16	77,096,835	58	58.498	1,317,943	58	58.498	1,317,943	58	58.498	1,317,943	58															2	58
Sheet1

Cell Formulas
Range	Formula
C3	C3	=$C$5/$C$2
C5	C5	=SUM(INDEX(B7#,,2))
D5,AC5,M5,J5,G5	D5	=SUM(D7#)
F5,L5,I5	F5	=MATCH(MAX(F7#),F7#,0)
A7:A36	A7	=SEQUENCE(C1)
B7:C36	B7	=SORT(AF7#:AG7#,2)
D7:D36	D7	=IF(FLOOR(INDEX(B7#,,2)/$C$3,1)>1,FLOOR(INDEX(B7#,,2)/$C$3,1),1)
E7:E36,K7:K36,H7:H36	E7	=SQRT(D7#*(D7#+1))
F7:F36,L7:L36,I7:I36	F7	=INDEX($B7#,,2)/E7#
G7:G36,M7:M36,J7:J36	G7	=IF(F5=$A7#,D7#+1,D7#)
AB7:AB36	AB7	=INDEX(SORT(A7#:F7#,6,-1),,1)
AC7:AC36	AC7	=(SEQUENCE($C$1)<=$C$2-$D$5)+D7#
Dynamic array formulas.

If this approach is consistent with your allocation scheme, then it can be consolidated further and reduced to fewer columns of formulas.

 

[KRice]

I think my understanding of the HH method was incorrect, so my previous post is probably not what you want. I assumed the initial allocation was based on applying the average population/representative to all states' populations, which results in a large number of initial allocations. That appears to be incorrect. Instead, every qualifying State is initially awarded one representative (I've assumed there are no exclusionary thresholds that would prevent a State from receiving at least the initial allocation of one). So if we begin with "S" States (in $C$1) and "T" Representatives to be allocated in total (in $C$2), a notional set of data are generated using random values for the populations of states (column O). To avoid issues with volatile random numbers affecting subsequent computations, I copied the list of random numbers and pasted them as values into an adjacent column (column N). Then to convert this range of population values into a spilling array, I multiplied the range by a SEQUENCE of 1's (in $L$8#). These populations are associated with States whose names are formed from another SEQUENCE of {1;2;3;...} (in $J$8# and $K$8#). The reason for doing this is to be able to bring the States and their corresponding populations over into the computation table in a sorted order with a simple spilling reference (in $B$8#). You should be able to replace this notional data in columns K:L with your actual data and revise the formula in $B$8# to specify the correct range for the actual data.

The initial allocations (round 0) result in n0=S allocations (in $D$8#), where n0 represents the sum of all allocations occurring during iteration 0, the initial seeding. This leaves the number of representatives to be allocated as T-n0=T-S (in $D$4). We construct a sequenced array whose maximum is the maximum number of iterations that could possibly be needed for the allocation of T-S representatives. This array is called N:

SEQUENCE(1,$D$4)

The modified divisors that apply to all States are unique to each iteration (or each element in N), and the array of divisors is called D:

SQRT(N*(N+1))

The Constituency Priority Quotient generated during each iteration is the State population divided by D for that iteration...so the array of CPQ values is:

INDEX($B$8#,,2)/D

Note that the state population cannot be referenced directly by the column where it is found because it is part of a two-column array, so INDEX($B$8#,,2) returns just the population column.
Finally, and similar to the point I made in my previous post, we know which States will be awarded representatives because those with the largest CPQ's are given priority, so to return the T-S largest CPQ's, we use the LARGE function with an internal SEQUENCE function that indicates whether the 1st largest, 2nd largest, etc. value in the CPQ array is to be returned. In order to convert this range of values into a spilling array, it is multiplied by a SEQUENCE of 1's.

SEQUENCE($D$4,1,1,0)*LARGE(CPQ,SEQUENCE($D$4,1))

All of these are assembled in a LET function to return just a single spilling array of the largest CPQ's associated with some State that is to be allocated a representative because of that CPQ (in $G$8#).

LET(N,SEQUENCE(1,$D$4),D,SQRT(N*(N+1)),CPQ,INDEX($B$8#,,2)/D,SEQUENCE($D$4,1,1,0)*LARGE(CPQ,SEQUENCE($D$4,1)))

Next, we need to find these largest CPQ values in the 2-dimensional CPQ array in order to determine which row (i.e., State) it is associated with. I've done this with a MATCH and BYROW function, where --(G8=CPQ) is the array passed to BYROW and the LAMBDA in that function simply sums any matches (so if there is a match on a given row, the sum will be 1, otherwise 0), and then feeding this array of 1's and 0's to the MATCH function and looking for where the "1" occurs, the MATCH function returns the row index...which corresponds to the State Index...the State Index is a helper column set up in $A$8#. I am not entirely happy with this approach, as this formula does not spill due the requirement to search the entire CPQ array for each element in G8# individually. There may be a better way to handle this. For now, the implication is that the row-finding step is not a spilling array, but a formula that needs to be pulled down beside the array of the largest CPQ's so that the formula can adjust to consider the CPQ to its left. This row-finding formula is:

MATCH(1,BYROW(--(G8=CPQ),LAMBDA(a,SUM(a))),0)

I've left this MATCH/BYROW construction inside a LET function that creates the CPQ array for convenience in case you or someone else devises a better way to determine which row in the CPQ array the column G values are found. Ideally, this would result in a spilling array. Alternatively, leave the formula as is and ensure that it is copied down far enough to cover the CPQ values...or copy it even further than necessary and ignore the errors.

=LET(N,SEQUENCE(1,$D$4),D,SQRT(N*(N+1)),CPQ,INDEX($B$8#,,2)/D,MATCH(1,BYROW(--(G8=CPQ),LAMBDA(a,SUM(a))),0))

I successfully tested this sheet with S=60 and T=1000 with no issues. Here is a small working example with S=6 and T=25:

MrExcel_20220522_Huntington-Hill.xlsx
	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
1		Number of States	6								Min Pop or Votes	50,000
2		Total Representatives to Assign	25								Max Pop or Votes	100,000,000
3
4		Remainder to Allocate		19
5		Reps Allocated		6	25
6											Notional Data	254,198,148
7	State Idx	States	Population or Votes	Num Reps: Allocation 0	Total Representatives		CPQ's Known After Allocation 0	Add Rep to State with Idx		Input Data Idx	State Name	State Population		Values Only	Random
8	1	State 5	89,577,971	1	9		63,341,191	1		1	State 1	78,822,091		78,822,091	87,197,160
9	2	State 1	78,822,091	1	7		55,735,635	2		2	State 2	40,241,369		40,241,369	74,315,188
10	3	State 2	40,241,369	1	4		36,570,054	1		3	State 3	2,634,333		2,634,333	94,833,998
11	4	State 4	32,428,539	1	3		32,178,984	2		4	State 4	32,428,539		32,428,539	46,942,250
12	5	State 6	10,493,845	1	1		28,454,945	3		5	State 5	89,577,971		89,577,971	87,517,235
13	6	State 3	2,634,333	1	1		25,858,933	1		6	State 6	10,493,845		10,493,845	85,340,256
14							22,930,440	4						49,744,352	95,603,104
15							22,753,978	2						43,224,993	2,550,264
16							20,030,243	1						9,404,955	50,259,142
17							17,625,155	2						55,830,094	13,470,636
18							16,428,470	3						68,858,595	96,782,215
19							16,354,625	1						42,665,726	65,069,508
20							14,390,879	2						2,942,795	53,260,538
21							13,822,181	1						41,051,467	57,259,518
22							13,238,896	4						95,990,596	54,167,782
23							12,162,513	2						26,002,519	63,787,825
24							11,970,360	1						36,631,255	55,790,582
25							11,616,683	3						653,464	67,520,267
26							10,556,865	1						22,692,006	16,236,269
27								#N/A						91,884,529	27,997,841
HH_example

Cell Formulas
Range	Formula
D4	D4	=$C$2-$D$5
D5	D5	=SUM(D8#)
E5	E5	=SUM(OFFSET($E$8,,,$C$1,1))
L6	L6	=SUM(L8#)
A8:A13	A8	=SEQUENCE($C$1)
B8:C13	B8	=SORT(K8#:L8#,2,-1)
D8:D13	D8	=SEQUENCE($C$1,,1,0)
G8:G26	G8	=LET(N,SEQUENCE(1,$D$4),D,SQRT(N*(N+1)),CPQ,INDEX($B$8#,,2)/D,SEQUENCE($D$4,1,1,0)*LARGE(CPQ,SEQUENCE($D$4,1)))
J8:J13	J8	=SEQUENCE(C1)
K8:K13	K8	="State "&J8#
L8:L13	L8	=SEQUENCE($C$1,,1,0)*OFFSET($N$8,,,$C$1,1)
E8:E27	E8	=IF(A8<>"",SUM(D8,COUNTIF(OFFSET($H$8,,,$D$4,1),A8)),"")
H8:H27	H8	=LET(N,SEQUENCE(1,$D$4),D,SQRT(N*(N+1)),CPQ,INDEX($B$8#,,2)/D,MATCH(1,BYROW(--(G8=CPQ),LAMBDA(a,SUM(a))),0))
O8:O27	O8	=RANDBETWEEN($L$1,$L$2)
Dynamic array formulas.