?

Log in

No account? Create an account
wRog
Something I probably won't present to the state Rules Committee in 2012 
18th-Jan-2008 11:04 pm
party politics
You may not have been aware of this, but III.F.1 of the WSDCC's 2008 Delegate Selection Plan reads as follows:
Alternates shall be listed and seated in the order in which they were elected,
and must be of the same presidential preference, and, to the extent possible,
of the same gender and from the same electing jurisdiction as the delegate being
replaced.
This rule applies at all levels of caucus starting with the LD caucus, where the (bottom-level) precinct delegates go to elect the (2nd-level) delegates to the CD caucus and state convention.

Now, the interesting thing about this is that, unlike at the higher levels, where male and female delegates/alternates are strictly segregated (i.e., you get so many delegates of each gender for a given jurisdiction and there are are likewise separate alternate lists for each gender), the delegation from the precinct caucus to the LD caucus is co-ed; and for each precinct for each candidate there's likewise just a single ordered list of alternates where the M-F pattern can be anything.


So now try to imagine a precinct where you've got some number of female delegates for a given precinct+candidate that are missing on the morning of the LD caucus, the first alternate is male and perhaps there are a bunch of female alternates following him in the sequence. What do you do? You have to seat the male before you can seat any of the females, because respecting the order is the very first requirement.

It is clear from the wording that there are at least some circumstances where it is permissible to seat alternates in other precincts and/or in opposite-gendered slots. Does that mean it's permissible to whisk the male alternate away to be seated in some other precinct (where there are, say, no alternates) in order that one may then seat the female alternates in their home precinct?

Depends. As I see it, everything hinges on what "to the extent possible" is supposed to mean. Could it be
  1. an individual requirement on each single vacant delegate slot (i.e., you try to match both gender and precinct and if you can't, then one of those is enough, and if you can't even do that, then you can give up and plug any old alternate in there...)? Or is it

  2. a collective requirement? I.e., maybe what it means is that you're required to find the seating that maximizes the overall number of same-gender-same-precinct seatings of alternates. It could even be argued that this is more in keeping with the intent of the rule (since the overall gender balance is what people tend to care about,... one might object that there isn't actually any balance in the original election of precinct delegates, though there could be, i.e., it could have been intended that in any case where precinct participants have taken the trouble to choose to send a gender-balanced delegation even if the rules don't require it, that this should nevertheless be respected in the alternate seating... [that's about the best I can do, though it's not bad as arguments go]). It could also be

  3. a combination of the two, in which, say, one is required to maximize some function of the overall (separate) numbers of same-gender seatings and same-precinct seatings -- thus encouraging matching both where you can but still putting a value on matching one or the other? This might be even more in keeping with the intent of the rule.

Anyway, to cut to the chase, (2) is NP-Complete.

I haven't quite come to a verdict on (3), which is not fully specified anyway, though right now I wouldn't be at all surprised to find various similar results there as well.

(aside for the non-CS-geeks:
NP-Complete refers to a class of problems that are, as far as we can tell, Very Annoying -- not the most annoying problems imaginable -- complexity theorists have whole hierarchies of annoyingness, and, believe me, you do not want to know what the upper end of that looks like -- but the NP-Complete ones are rather time-consuming to solve. And they also come up sufficiently often that it really would be nice if we could solve them quickly. Unfortunately, the best-known algorithms tend to take time exponential in the size of the problem instance, which is not to say that anyone has proven that they have to be this hard, but some very smart people have spent a good 40 years beating their heads against this particular brick wall and have not come up with anything yet.

So, if you've got some problem and you don't know how hard it is, but you can find some fast way of reducing some other NP-Complete problem to it (such that any solution for the one can be quickly translated back to a solution for the other), then you will know that your problem is just as hard as that other (NP-Complete) problem.

How will you know this? Because otherwise if it were to happen that your problem does have a fast solution, then you will necessarily also have a fast solution for that other NP-Complete problem, and then, since every NP-Complete problem has a fast reduction to every other NP-Complete problem, you will also have necessarily come up with a fast solution for every NP-Complete problem in existence.

At which point you will have won the Nobel Prize in Computer Science. Except that there isn't a Nobel Prize in CS. But I'm sure They will come up with Something.

Which should give you an idea of just how unlikely it is that your problem has a nice, fast algorithm...)

(... I've also quietly skipped over where the very first NP-Complete problem came from, but you can go to the textbook for that one...)
So here goes.

We start with an instance of the PARTITION problem, already known to be NP-Complete:
You have a set of numbers {a1,a2,...,ak} whose sum is 2N and the question is, does there exist a subset whose sum is exactly N.
Yes, this one's hard; trust me on this. So far as we know, there isn't anything much better than enumerating each of the 2k possible subsets and, for each one, adding it up and seeing if we win. Again, if you find a fast way to do this one in general, you will be famous.

Now consider the following instance of the Alternate Seating Problem.
On the morning of the LD Caucus, there are k precincts for which some delegates have not shown up. In particular, the ith precinct has ai missing female delegates and its alternate list consists of ai males followed by ai females, all present, and likewise for all i: 1≤ik. Just to make life easy, everybody is for the same candidate. Overall, there are 2N delegates missing, 4N alternates available, and the question is, does there exist a valid seating that seats at least N of the female alternates?
It should be noted that because each group of females is behind a similar-sized group of males in the various alternate orderings, it will never be possible to seat more than N females. Moreover, if there's any precinct for which you seat some but not all of the alternates, you'll be getting strictly more males from that precinct, thus strictly more males overall, and therefore less than N females seated.

So if an N-female seating exists, it will seat all of the alternates from a subset of the precincts and nobody else. That would be a subset of precincts whose alternate contingents add up to 2N and whose corresponding missing-delegate counts add up to N. That particular subset of the {a1,a2,...,ak} is then a solution to the previous instance of the PARTITION problem. It should also be clear that wherever we know of a solution to the PARTITION problem we have a solution to the seating problem via seating just that subset of precincts.

So this is an if-and-only-if situation. That is, an answer (yes or no) to the seating problem immediately gives us a definitive answer to the corresponding PARTITION problem. So if there is indeed a fast optimal alternate seating algorithm, then we have a fast algorithm for PARTITION and we're famous.

Or, as is more likely, the alternate seating problem (at least version (2) of it above) is a Seething Pit of Hell and I shouldn't spend any more time on it. Not that I was planning to spend a huge amount of time on it to begin with, but it's always nice to be vindicated in these decisions.

I suppose if any of the CS researchers back in 1973 were watching carefully when the DNC or the Iowa party or whoever was writing the original version of the modern caucus rules, someone could have gotten a paper out of this. Nowadays, this stuff is way too routine... Oh, well...

Coincidentally enough, Cook's original paper on NP-Completeness dates from 1971.

(hm... anyway... not bad for my first NP-Completeness proof in about 10 years. Guess I haven't totally lost it. Or maybe I have...)

(well all right, strictly speaking, I've only shown that it's NP-Hard, though the rest of it, i.e., that the alternate seating problem is not actually massively worse than NP-Complete, is actually pretty easy...)
Comments 
19th-Jan-2008 03:20 pm (UTC)
Thank god there's someone else who posts random proofs to their livejournal; I was beginning to feel like a freak.

(Yes, I had an algorithms course as a grad student, so I could follow this.)
This page was loaded Oct 19th 2017, 8:58 am GMT.