+972 52-548-6969
Giving a job candidate a HARD problem
Every now and then I’ll run into a problem and say, “Oh, that would be a great thing to give in a job interview”. In addition to the Corona issue, Israel has been faced with multiple cases of hung parliament. Therefor, I decided that the next candidate we’ll interview will have to solve that problem. If you are good enough to solve conflicts in politics, you can solve conflicts in a distributed system.
Here is the problem, given the following parliament’s makeup, find all the possible coalitions that has 61 or greater votes.
- Likud – 36 seats
- KahulLavan – 33 seats
- JointList – 15 seats
- Shas – 9 seats
- YahadutHatura – 7 seats
- IsraelBeitenu – 7 seats
- AvodaGesherMeretz – 7 seats
- Yemina – 6 seats
There is a total of 120 seats in the Israeli parliament and you need 61 seats to get a coalition. So far, so good, but now we come to the hard part, not all parties like each other. Here is the make up of the parties’ toleration to one another:
| Likud | KahulLavan | JointList | Shas | YahadutHatora | IsraelBeitenu | AvodaGesherMeretz | Yemina | |
| Likud | -0.5 | -1.0 | 0.95 | 0.95 | -0.2 | -0.8 | 0.95 | |
| KahulLavan | -0.9 | -0.6 | -0.5 | -0.5 | 0.5 | 0.8 | -0.2 | |
| JointList | -0.9 | -0.3 | -0.6 | -0.6 | -1.0 | -0.2 | -1.0 | |
| Shas | 0.96 | -0.7 | -0.6 | 0.9 | -1.0 | -0.7 | 0.8 | |
| YahadutHatora | 0.97 | -0.6 | -0.6 | 0.92 | -1.0 | -0.6 | 0.7 | |
| IsraelBeitenu | -0.4 | -0.1 | -1.0 | -0.99 | -0.99 | -0.6 | 0.1 | |
| AvodaGesherMeretz | -0.95 | 0.98 | 0.3 | -0.89 | -0.89 | -0.01 | -0.75 | |
| Yemina | 0.999 | -0.92 | -1.0 | 0.86 | 0.85 | -0.3 | -0.4 |
As you can see, the parties are ranked based on how probable they are to seat with one another. Note that just this listing of probabilities is probably highly political and in the time since the last election (all of a week ago), the situation has likely changed.
All of that said, I don’t really think that it is fair of a job candidate to actually solve the issue at an interview. I’m pretty sure that would require dynamic programming and a lot of brute force (yes, this is a political joke), but the idea is to get a list of ranked coalition options.
If you want to try it, the initial parameters are here:
And hey, we won’t get a government out of this, but hopefully we’ll get a new employee 
.
Comments
I do not quite understand the effect of the 'tolerances' between the parties. The question is to 'find all the possible coalitions that has 61 or greater votes', however even the two parties who hate each other could be in coalition. Is the additional requirement to sort it by likelihood? Is there a cap/limit or something?
Dalibor,
Okay, here we get to interesting politics and how they work together. I'm not sure where you are from, and what is the governing form in your country.In Israel, we have the notion of a coalition that is composed of multiple parties. In order to form a government, you need 61 votes.However, different parties have different makeup and tolerances for one another. If there are serious worldview differences between parties, they are unlikely to sit together.The tolerances represent how alike those parties are (an arbitrary determination that I made up).
If you try to compose a coalition between the Vegan Party and the Butcher Guild, for example, you might be mathematically successful, but it is not a feasible coalition.The idea is to get the "best" coalition possible. One that has a unified world view. In practice, yes, you are expected to use the tolerances to sort things out.
Ok, but to calculate this 'rank' we just sum up the tolerances between each party or? For example if it takes 4 parties to build up a coalition I could combine the tolerances between each of the parties so we would have some 12 numbers (first with second, first with third, second with third etc). If you only have 2 parties in coalition the number would be smaller because it is only one tolerance. So how do you calculate this rank?
Dalibor,
The tolerance is both ways, mind.
In other words, X likes Y more than Y likes X. You want the maximum compatibility number across the board. So when adding a new member to the coalition, compute the tolerance of each member to all others, and sum them all.
Likud "tolerates" KahuLaval at -0.9 even though KahuLaval "tolerates" Likud at -0.5.
So far I understand it is most probable that the parties {KahuLaval;Likud} sit together than {Likud;KahuLaval} which... doesn't make sense since it is the same coalition in both cases. Except if order matters ? In which case can you explain why ? Or isn't you matrix supposed to be symmetrical in order to solve this problem ?
Cyril,
It means that Likud dislike KahulLvan more than KahulLavan dislike Likud.
In other words, the compatibility of the coalition in this case
{KahuLaval;Likud} = -1.4.The order doesn't matter@Oren Ok, I overlooked that part but my question was more aimed that the algorithm seems to favor multiple parties because sum of tolerances between 4 parties will probably be a larger number then just one tolerance between two parties. I might be wrong.
@Dalibor Čarapić, exactly!
You have the weigh-in the number of votes a party brings to the Delta tolerance it brings to all other coalition members. So a party with more members that have slightly lower scores can still be a better outcome for the coalition.
Dalibor,
That depend on the cohesiveness of the parties, more than anything else.2 parties that don't like each other would be worst than 4 parties that match well
I've created a sample app here: https://repl.it/@Daliborarapi/SmoggyJumpySyntax
I stole some code from StackOverflow from generating combinations (credits in code).
I think its valid. I am not sure how I could test the validity.
Dalibor,
That looks like a valid solution.
A bit another way to brute-force over all combinations, but the result is same as the Dalibor's app gives. So is there a light at the end of the tunnel for Israel parliament :) ?
gist
Are you really asking a hiring candidate to solve an NP-hard problem?
If you find this candidate, you better kill him on sight... half of world's economy and politics is based on the assumption that it cannot be solved (all cryptography, just to name one case). This person would wreak havoc worldwide, so you better make it look like an accident.
😜
I just noticed the CAPS in the post title. I guess you already knew... 👍
Fun problem! It looks like all sufficient solutions (12) require the Likud party and 10 of the 12 (including the most likely) require the Shas party.
gist
Garcha,
You are going to need to add comments to explain this code. Lots of bit manipulation that makes me go... "huh?" Couldn't you use a counter, instead?But yeah, that looks like it would give a solution
Kurbein,
There is a total of 8 parties, the most that ever run to the Knesset is 40. The most parties actually got to the Knesset is 15.
Note that 8! is 40,320, so should be easily solvable even by brute force.
David,
I think you didn't account for the fact that two parties may not like each other in the same manner. This is minor, and the actual code does the work
statevariable in source)stateinteger. Initially lowest bit corresponds Likud (ix=0in source), for the next iteration thestateinteger is shifted right andixincreased (state=state>>1, ix+=1) - now lowest bit corresponds KahulLaval and etc.Comment preview