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.
Subscribe to:
Post Comments (Atom)
4 comments:
Don't the nodes on the shortest path from the root to a leaf form a good enough coalition?
That would give a log n bound (for any tree since non-branching nodes can be ignored) or am I missing something obvious.
The problem with your suggestion is that the label for that leaf (the winner) may be different from the labels of the nodes on the path that reach it. So, log n of the players can indeed choose an outcome, but not necessarily one in which one of those players is the winner.
The winner is always welcome. He doesn't have to do anything but win (and I assume share the winnings at the end).
Uh, that looks suspiciously like a valid observation! So, now the problem is looking easier than I thought it was (although we don't quite have a polynomial-time algorithm.)
(BTW, I originally had in mind a related version in which each leaf of the tree identifies a particular loser, and a successful coalition should consist of a subset of agents that can avoid any of them being the loser. But it's now looking to me as if, in this version also, there should be successful coalitions of size proportional to log n.)
Post a Comment