Fill the vacancy

[BMAD]

The premature retirement of the beloved leader Aldan has left a vacancy on the ruling triumvirate of the Malthusian city of Zocor. There are two political parties, The Meat Lovers Party (MLP)and the Vegetarian Party of the People (VPP). At present each party has one representative in the triumvirate, with the MLP representative Arctan being the most senior.The other ruling member being Arcsin.

The arcane voting rules for replacing Aldan are as follows. There is a large Praesidium with n people in it. At the moment all the members are in the VPP. Each member has an integer valued priority. The selection process will now go in rounds: At the beginning of a round Arcsin will propose some subset S of the remaining candidates C of the Praesidium. (Initially C will be the whole Praesidium). Arctan then has two choices. He can devour S, but then he is forced to decrease the priority value of each member of C \ S by one. Alternatively, he can devour C \ S and decrease the priority values of the members of S by one.

The process continues until one of two things happen: The whole Praesidium has been eaten and then Arctan can choose any member of his party to fill the vacancy. The other possibility is that someone will reach priority zero and then Arcsin can choose any zero priority person to fill the vacancy. Given that the initial priorities are a₁, a₂, .... a_n, which party will get to fill the vacancy?

[plasmid]

I don't have a full solution, but this might help get things started.

Spoiler

 

Describe the Praesidium as a vector (n₁, n₂, n₃, …) where n_m is the number of people in the Praesidium of priority m. So a Praesidium of (2, 5, 0, 1) would have eight people: 2 of priority one, 5 of priority two, and 1 of priority four.

First note that Arcsin can win if there are at least 2^m people of priority m for any value of m. Just put 2^m-1 people in S so there are also at least 2^m-1 people in not(S), and Arctan will have to leave at least 2^m-1 of them who will be priority m-1 in the next round. Keep repeating that, and you'll get 2¹ people of priority 1 and one of them will get through the next round to reach priority zero. Conversely, if the Praesidium is filled only with people of one priority level (call it m) and there are fewer than 2^m people, then Arctan can just keep eating whichever of S or not(S) has the most people and will eat them all before any reach priority zero.

The interesting stuff happens when there are people at multiple different priority levels, but there are fewer than 2^m people at any given priority level. As a simple example of that, consider the Praesidium (0, 2, 5). If Arcsin just split people into S and not(S) evenly [like making (0, 1, 2) and (0, 1, 3)] then Arctan would just eat the larger one and the next round would be (1, 2), then Arctan would eat whichever of S or not(S) holds the priority one person to make it (1) in the next round, and then Arctan would win. But instead if Arcsin started off by making S and not(S) be (0, 2, 0) and (0, 0, 5), then the next round would either be (2) or (0, 5), and either of those situations would be an easy win for Arcsin because they have n_m > 2^m.

Let's try to generalize that. Suppose there is some priority level m with at least 2^m-1 people. Then Arcsin could make one group S with 2^m-1 people of priority m and the other group not(S) containing the rest of the Praesidium; Arctan would have to eat S or else he would be in a losing situation, and proceeding to the next round would have converted everyone in not(S) to one lower priority level. So if there are two priority levels with n_m at least 2^m-1 (call them ma and mb) then Arcsin can win: put 2^ma-1 priority ma people in S and pub 2^mb-1 priority mb people in not(S). Or if there's a priority level m with at least 2^m-1 people and two different priority levels mc and md with 2^mc-2 and 2^md-2 people, then Arcsin could make S be 2^m-1 people of priority m so Arctan has to eat them with everyone else in not(S) and then could with because mc-1 and md-1 now both hold 2^m-1 people. In general terms, you can calculate the vector where each term is given by (m - log₂ n_m), and if there is any series of terms with at least one value less than or equal to 1, at least one value less than or equal to 2, at least one value less than or equal to 3, etc eventually reaching some point where there are two or more values less than or equal to that number, then Arcsin could win.

That vector can come in handy, so I'll define it as a term for the next paragraph. Since using "l" or "o" from "log" could get confusing: g_m = m – log₂ n_m, and call g_m undefined if n_m = 0 and omit such terms from the vector.

Now consider cases where there's not a series of g_m terms going 1, 2, 3, …, x, x to give Arcsin a win with that approach. Suppose the g_m vector looks like (3, 2, 3, 2, 3, 3). Arcsin could put everyone from both priority levels with g_m = 2 into S and put everyone from the four priority levels with g_m = 3 into not(S). If Arctan doesn't eat S, then there would be two priority levels with g_m = 1 in the next round so Arctan would lose, so Arctan must eat S. Then the next round would have four priority levels with g_m = 2. Arcsin could put everyone from two priority levels in S and everyone from two other priority levels in not(S), so no matter what Arctan does there will be two priority levels with g_m = 1 in the next round and Arcsin could win.

Stated in more general terms, you can take the g_m vector and calculate a new vector ng_m which is a count of all g_m terms over the range (m-1 to m] (excluding m-1 but including m), and if ng_m is at least m, or if there is a series of terms ng_m – m incrementing from 1 upward until there are two terms of the same value, then Arcsin could win.

 

After that point, it gets too abstract for me to continue comprehending.

[CaptainEd]

Plasmid, In what sense is this not a total solution?

Edited December 13, 2018 by CaptainEd

[plasmid]

On 12/13/2018 at 2:16 PM, CaptainEd said:

Plasmid, In what sense is this not a total solution?

Well, I've shown a lot of ways where Arcsin could win, but I don't actually prove that Arctan can win in cases that aren't covered in the above ramblings. An ideal solution would be along the lines of: "If the composition of the Praesidium meets these criteria then Arcsin has a strategy that's guaranteed to win, and if it doesn't fit those criteria then Arctan has a strategy that's guaranteed to win."