Our local networks went down this morning and I started thinking about cake-cutting. Didn't get very far, but on the way, came up with the following question.
Given n players, and a binary game tree, each of whose leaves is labelled with one of the players, who is deemed to be the winner if that leaf is the outcome of the game. Each node of the tree is also labelled with a player, with the understanding that if that node is reached during the game, the that player gets to choose one of the two subtrees.
Question: how hard is it to find the smallest coalition that has the property that they can ensure that one of their members ends up winning? (There are two versions of this question: you can require them to nominate a winner in advance, or you could just require that the winner is one of them, but precisely who, depends on the behaviour of the non-members of the coalition.)
Comment: Let's focus on the second of the above versions. In that case, there are many winning coalitions of size n/2. Why? You can partition the players into 2 subsets (opposing teams that play against each other), then treat each subset as a single player, resulting in a 2-player version. You can find out which of those two "players" can win, in a bottom-up fashion. So, if the subsets are the same size, you end up finding a subset consisting of half the players, that can win.
Another question: leaving aside computational issues, should it always be possible to find winning coalitions of size less than n/2? Probably not.
Disclaimer: I don't know if this is a new problem, it could may have been worked on already.
Best paper awards at ICALP 2016
11 hours ago