Poker is a zero-sum game. This means that the amount of money going out of the table is equal to the amount going in. I mentioned poker here because that is what I need the solution for, but the question applies to any zero-sum game.
Let's say that I play poker for money. The format is the cash game. This means that anyone can buy in again after he loses all his money. Anyone can buy in as many times as he wants with any amount of money. I distribute poker chips in amounts corresponding to the amount of buy-in to every player. At any time the chips can be counted to know how much money one owes/is owed.
There are two arbitrary assumptions.
1. We don't use cash for buying in. We just write it down on paper and plan to settle it after the game (when winning/losing amounts are known).
2. No one will act as a bank - keeping all money and redistributing it to winners after a game
Let's see a manual solution on two examples.
Sample game
Let's say that there are 4 players: user A, user B, user C, user D, and User E.
At the end of the game, the balance looks as follows.
User A lost $30
User B lost $5
User C lost $20
User D won $42
User E won $13
Solution .1
The first solution coming to my mind is: User A sends $30 to user D.
User B sends $2 to user D and user B sends $3 to user E.
User C Sends $10 to user D and user C sends $10 to user E.
This solves the settlement using 5 transactions.
Solution .2
User B sends $5 to user A.
User A sends $13 to user E.
User A sends $22 to user D.
User C sends $20 to user D.
This solves the settlement using 4 transactions (better than solution .1).
My question is: How to create a map of settlement for a game of poker algorithmically containing the least number of transactions (optimal)?
Note that the number of players increases and the ratio of the number of winners to losers changes this makes the solutions differ a lot. It may be pretty hard to find an optimal one by hand (subjectively).
What is a generic approach that will always lead me to an optimal number of transactions?
I am sure this problem is generalized and it is named somehow but I never managed to find it.
