I am looking for an algorithm that is implemented in C, C++, Python or Java that calculates the set of winning coalitions for n agents where each agent has a different amount of votes. I would appreciate any hints. Thanks!
Arrange the number of votes for each of the agents into an array, and compute the partial sums from the right, so that you can find out SUM_i = k to n Votes[i] just by looking up the partial sum.
Then do a backtrack search over all possible subsets of {1, 2, ...n}. At any point in the backtrack you have accepted some subset of agents 0..i - 1, and you know from the partial sum the maximum possible number of votes available from other agents. So you can look to see if the current subset could be extended with agents number >= i to form a winning coalition, and discard it if not.
This gives you a backtrack search where you consider a subset only if it is already a winning coalition, or you will extend it to become a winning coalition. So I think the cost of the backtrack search is the sum of the sizes of the winning coalitions you discover, which seems close to optimal. I would be tempted to rearrange the agents before running this so that you deal with the agents with most votes first, but at the moment I don't see an argument that says you gain much from that.
Actually - taking a tip from Alf's answer - life is a lot easier if you start from the full set of agents, and then use backtrack search to decide which agents to discard. Then you don't need an array of partial sums, and you only generate subsets you want anyway. And yes, there is no need to order agents in advance.
Coalition Search Algorithm