Agreed;fortunately for the pension systems I used to design (as opposed to chess programs, for example) the number of possibilities is fairly finite. 
I havenât seen this mentioned in the threads on this topic, but I apologize if this has been brought up before and I just missed itâŚ
(emphasis mine)
It seems to me the central problem with this rule is this underlined part â namely, I feel like it should read:
ââŚunless any of the winners or groups of winners would receive more money by winning or dividing only a particular prize for which others in the tie are ineligible.â
The problem in the example from page one shouldnât be that the 2400+ got too much, rather, that the U2400 players received too little: had the three U2400 players scored 3.75 points, they each would have shared 306 + 1379 + 766 = 817. In fact, even if there hadnât been a 4th place prize, they each would have split 1379 + 766 = 715, still more than the 536 third place prize.
(as an aside, on page 1 Kevin said something to the effect barring a player from winning more than he or she would have won had he or she finished above the others in the tie; I think my change above is equivalent to this if it read âbarring a player or group of playersâŚâ Including the âgroupâ qualifier is important; if there were 10 other 2400+ tied at 4.0âŚ)
Unfortunately, this problem looks like it could easily be very hard. One way to model it: assume that there are n prizes tied for by m >= n players, with C1, C2, âŚ, Ck the class quantifiers (not necessarily the number of prizes, but rather a set of all the prize-winners eligible for that âclassâ), with another âquantifierâ being the âopenâ category, O.
Case 1: Strict classes, i.e., 2400-2200, 2199-2000, etc â then the intersection of Ci and Cj is always empty, while the intersection of Ci and O is trivially Ci. Then, the only valid subsets to split away for prize purposes are singleton subsets. To prove this, consider a counter-example: suppose that there is some scenario where Ci and Cj split away together, earning strictly more than they would have if they stayed in the group, and earning strictly more than had they split individually.
Case 1.1: The Ci/Cj split uses no prizes from O. Let |Cj| denote the prize values given to players in Cj if Cj split away itself; define similarly |Ci| for Ci, and |Ci, Cj| for Ci,Cj. If |Cj| > |Ci|, it should stand to reason that |Cj| > |Ci,Cj|, and since the players in Ci have no valid claim towards the prizes in Cj, it stands to reason that Cj should be able to break away from Ci, making itself a singleton split.
Case 1.2: The Ci/Cj split uses at least one prize from O. This feels fuzzy, though: let D denote the complement of the Ci/Cj split; D has just as much of a claim to the prizes in O as the split does, but doesnât stake a claim to it. This, I believe, inevitably leads to the conclusion that the inclusion of the Ci/Cj split in D would decrease Dâs payout, therefore implying that the split is in fact bad for Ci and Cj, causing a contradiction.
Admittedly, this isnât a particularly rigorous proof, but it seems like it matches the intuition. The algorithm to solve this would work as follows: look at the case with no splits and compare that to each singleton split: take the highest valid singleton split, break it away as completed, and then run again with everything else. If no valid singleton split exists, terminate.
Case 2: Under/subset classes, i.e., U2400, U2200, etc â here, the quantifiers are all subsets of each other: O<=Ck<=âŚ<=C2<=C1. It seems to me that there are only k possible splits here; each split can occur at Ci and must include Cj with j < i. To prove against this, consider x < y < z, with Cx,Cz in one split and Cy in another. Since Cy isnât with Cx, it stands to reason that Cy decreases Cxâs payout, and similarly, since Cz is with Cx, it stands to reason that Cz increases Cxâs payout. Similarly, since Cz isnât with Cy, Cz must be decreasing Cyâs payout. This, however, causes a contradiction, as Cy decreases Cxâs payout, but Cz increases Cxâs payout while simultaneously decreasing Cyâs payout.
Working this should be simple: see what happens by breaking away C1, then C1,C2, etc.
Case 3: Abstract classes and non-structured classes, i.e, U2200, 155-698, wearing glasses, from Alaska, etc. Iâve been trying to solve this case, but I canât figure out a good way to do it. My belief, after looking at it for a while, is that this problem is at least NP-hard â without any structure on the quantifiers, I think there can be an exponential (or even factorial!) number of possible valid splits, without there being any reasonable heuristics or proofs to eliminate some of them.
Thank you, Andy. I didnât go back and catch that part of the rule, and that is certainly what I was after. Your suggestion is spot on (per my second example.) So this is simpler than I thought. I think several of us missed that.