Math question: Settle-up after poker game with fewest transactions possible (1 Viewer)

[Davism72]

Any math lovers here? I could use some help. Here's the situation:

A group of friends are playing a game of poker. Each player buys chips on debt, not actually paying any money into the bank. When the game is over, they need to settle up -- losers pay out, winners collect. Each player's net balance will be the difference between the amount of chips they borrowed from the bank and the amount they return at the end of the game.

Is there some mathematical way to achieve balance with the fewest possible transactions? If one player owes $50, and another player is owed the same amount, it makes sense that those two should be paired -- one transaction, two accounts closed. But what if the debts are more complex?

Player	Bought In	Cashed Out
Matt	$100	$85
Jake	$80	$200
Danny	$100 + $100	$0
Hank	$50	$145

I understand that it's probably a better idea to just buy the chips up front, then pay everyone from the bank, but humor me.

Thanks in advance!

 

[RocAFella1]

Matt owes $15. Danny owes $200. Pay Jake $120 and pay Hank $95.
Am I missing something here?

Instead of trying to pair +/- transactions. I would just collect money from everyone who’s in the negative and then use that to pay off everyone who’s in the positive.

 

[Davism72]

Matt owes $15. Danny owes $200. Pay Jake $120 and pay Hank $95.
Am I missing something here?

Should have been more clear. The example I gave was trivial, but I'm looking for a repeatable way to solve problems like this quickly and accurately.

 

[Undream]

Anyone who lost puts the amount they lost on the table. The winners divy up the cash on the table relative to how much they were up.

 

[RocAFella1]

I’m assuming you keep a book of buyins and subsequent cashouts. If the numbers in match the numbers out then everything is square and losers pay and winners collect.

 

[pltrgyst]

Tote up the net for each player.

If a loser's and a winner's amount match, they pay directly.

Next, if two losers total the exact amount due one winner, they pay him directly.

Ditto for 3 losers, 4, 5, etc.

Finally, any one of the remaining losers collects from all the other losers, and he in turn pays all the remaining winners.

The maximum number of transactions will be the number of players minus the number of players who broke even for the night.

 

[Mr Winberg]

Since Swedes don't use cash, I always write up everyone's buy-ins and settle directly with each player when he/she cashes out. If they are ahead, I transfer the difference to them, otherwise they transfer it to me. It's faster and simpler than trying to find an optimal sequence of transfers, especially since players cash out at different times through the night, only a handful are left at the end. If all is correct, I will end up with exactly my poker win/loss.

Regarding the math question, I don't have anything better than @pltrgyst

 

[markleteenie]

Fewest transactions, I assume we're doing something like poker on credit, and then venmo to settle up? Even though it seems like more transactions to all pay and then some cash, I think it is comparable and more secure/less confusing.
In your scenario, Matt owes 15, Jake is owed 120, Danny owes 200, and Hank is owed 95. The fewest transactions I see is maybe everyone who lost pays the big winner, and that person redistributes. So Matt and Danny pay Jake 215 and Jake pays Hank 95. 3 transactions.

Although in some scenarios, there might be one person just paying out direct transactions....I think a good argument can be made for someone to just be the bank, and everyone sends money to that one person, and then that person sends out money to the winners.

In your scenario - 5 people "deposit" and then 3 "withdraw." If one of the players is also the bank, then that eliminates one transaction for buying in and cashing out. So in your scenario, if Matt is also the bank, then there are 6 transactions, not too bad. Plus no one can renege, unless it is the bank.

Player	Bought In	Cashed Out
Matt	$100	$85
Jake	$80	$200
Danny	$100 + $100	$0
Hank	$50	$145

 

[Mr Winberg]

In your scenario [...] there are 6 transactions, not too bad.

Using the patented Mr W approach in post #7 it would be just 3 transactions...not to bad either

If Matt is the bank he would transfer 120 to Jake and 95 to Hank, and receive 200 from Danny, leaving him with a result of -$15.

 

[markleteenie]

Using the patented Mr W approach in post #7 it would be just 3 transactions...not to bad either

3 transactions.

Yep, that's because you are the bank and everyone is playing on credit, so you will always have one transaction per player, unless they break even. It sounds like in the OPs scenario, no one is stepping up to be the bank.

 

[Mr Winberg]

Yep, that's because you are the bank and everyone is playing on credit, so you will always have one transaction per player, unless they break even. It sounds like in the OPs scenario, no one is stepping up to be the bank.

Yeah, I see now that that's the same as your version where the big winner effectively acts like the bank.

 

[markleteenie]

Yeah, I see now that that's the same as your version where the big winner effectively acts like the bank.

I assume you're used to being the big winner, so it's an understandable oversight.

 

[pltrgyst]

Using the patented Mr W approach in post #7 it would be just 3 transactions...not to bad either

That would actually be at least six transactions -- just virtual, instead of cash.

 

[WedgeRock]

We're all friends here, right? No risk of getting left holding the bag?

If so, and if any profit/win for one player = any loss by one or more players exactly, handle those first. That is a no brainer.

Then, have the biggest loser xfer to the biggest winner. Adjust the biggest loser's amount (or if the biggest winner isn't completely paid off, adjust the biggest winner's amount). Danny (-$200) is the biggest loser, he transfers $120 to the biggest winner, Jake (+$120). After the transfer, adjust Danny from -$200 to -$80.

Now back to step one. Guess what, Danny (adjusted to -$80) and Matt (-$15) now equal the amount owed to Hank +$95.

EZPZ.

Each time the biggest loser transfers to the biggest winner, you're retiring 1 debt. Check and see if you have even amounts and if not, have the biggest remaining loser pay the biggest remaining winner and retire one more debt. Check for balance. Wash and repeat as many times as necessary.

 

[Mr Winberg]

That would actually be at least six transactions -- just virtual, instead of cash.

I think the OP is intrested in the number of money transfers to balance the books. If not, then that's at least what I am referring to, and that is 3 in this case.

The maximum number of transactions will be the number of players minus the number of players who broke even for the night.

I could be mistaken, but wouldn't it be nr of players minus players who broke even minus one?

 

[Mr Winberg]

We're all friends here, right? No risk of getting left holding the bag?

If so, and if any profit/win for one player = any loss by one or more players exactly, handle those first. That is a no brainer.

Then, have the biggest loser xfer to the biggest winner. Adjust the biggest loser's amount (or if the biggest winner isn't completely paid off, adjust the biggest winner's amount). Danny (-$200) is the biggest loser, he transfers $120 to the biggest winner, Jake (+$120). After the transfer, adjust Danny from -$200 to -$80.

Now back to step one. Guess what, Danny (adjusted to -$80) and Matt (-$15) now equal the amount owed to Hank +$95.

EZPZ.

Each time the biggest loser transfers to the biggest winner, you're retiring 1 debt. Check and see if you have even amounts and if not, have the biggest remaining loser pay the biggest remaining winner and retire one more debt. Check for balance. Wash and repeat as many times as necessary.

I know I'm far from the smartest person alive and would probably mess up even the simplest approach, but that is exactly what I used to do, and when the player count approaches two tables it becomes a real pain in the ass. Especially when players are leaving at different hours. The books get cluttered and if mistakes are made (due to alcohol or my stupidity) it's harder to retrace.

Having one person (me) act as the bank is sooooo much less effort. Each row in the book (i.e., each player) is independent and clean with total buy-ins, chip count, the difference, and a checkbox for "Settled".

The transaction count will always be the nr of players minus players breaking even minus 1.

Just my experience though, YMWV.

 

[WedgeRock]

Agreed, a bank is preferred. Period.

But if you're going to settle up this way, I wouldn't do it until the next day, when clearer minds prevail.

When someone cashes out, have them tell you the amount they have, then you verify that amount and write it down.

 

[dkersey]

An assumption with all this is the losers are still around at the end of the night to pay the winners. The reality of cash games is that many losers leave early.

 

[Mr Winberg]

Agreed, a bank is preferred. Period.

But if you're going to settle up this way, I wouldn't do it until the next day, when clearer minds prevail.

When someone cashes out, have them tell you the amount they have, then you verify that amount and write it down.

I actually settle directly when they cash out, but yes, I definitely write everything down in case I got unlucky when performing my arithmetic.

 

[waddadonk]

Intuition said to try this, not sure if optimal:

1. Calculate net (Cashed out - Cashed in) for each player.

2. Create two lists sorted:
a) Most to least negative.
b) Most to least positive.

3. Exhaust the negatives to pay off the positives Take the max of either column to pay the other column, resort and continue.

For your example specifically:

M : -15
J : +120
D : -200
H : +95

Lists:
-200D +120J
-15M +95H

Transfer D > J

Lists:
-80D
-15M +95H

Transfer D >H

Lists:
-15M +15H

Transfer M > H

...


Seems like there should be some smart optimization algorithm, but I can't find a clear one on StackOverflow. Found this https://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/ which I think supports the above method...



Another example

1)
-1000 +900
-800 +800
-700 +700
-600 +600
-500 +600

2)
-800 +800
-700 +700
-600 +600
-500 +600
-100

After 3/4/5)

-500 +600
-100

 

[Davism72]

Okay, I'll try to clear up some confusion by being a little more transparent. I'm working on an online poker app as a personal project. The idea would be that no money actually passes through the app -- it just makes the whole thing much harder -- but I'd still like to help with cashouts. One obvious way is to venmo all buy ins to a central bank, then redistribute from there. But what if nobody wants to act as the bank? I'd like to find the simplest way possible for all parties to get paid while reducing the work everyone has to do. The idea would be that everyone would basically get an invoice at the end of the night saying how much they owed and to whom.

I totally realize that this is suboptimal. The idea is to try to make a shitty situation a little less shitty.

 

[Davism72]

Intuition said to try this, not sure if optimal:

1. Calculate net (Cashed out - Cashed in) for each player.

2. Create two lists sorted:
a) Most to least negative.
b) Most to least positive.

3. Exhaust the negatives to pay off the positives

For your example specifically:

M : -15
J : +120
D : -200
H : +95

Lists:
-200D +120J
-15M +95H

Transfer D > J

Lists:
-80D
-15M +95H

Transfer D >H

Lists:
-15M +15H

Transfer M > H

...


Seems like there should be some smart optimization algorithm, but I can't find a clear one on StackOverflow. Found this https://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/ which I think supports the above method...

Quality link. Thanks, dude. I'll look through.

 

[markleteenie]

Okay, I'll try to clear up some confusion by being a little more transparent. I'm working on an online poker app as a personal project. The idea would be that no money actually passes through the app -- it just makes the whole thing much harder -- but I'd still like to help with cashouts. One obvious way is to venmo all buy ins to a central bank, then redistribute from there. But what if nobody wants to act as the bank? I'd like to find the simplest way possible for all parties to get paid while reducing the work everyone has to do. The idea would be that everyone would basically get an invoice at the end of the night saying how much they owed and to whom.

I totally realize that this is suboptimal. The idea is to try to make a shitty situation a little less shitty.

I thought someone already did something similar to this, and a lot of people got ripped off.

 

[Davism72]

We're all friends here, right? No risk of getting left holding the bag?

If so, and if any profit/win for one player = any loss by one or more players exactly, handle those first. That is a no brainer.

Then, have the biggest loser xfer to the biggest winner. Adjust the biggest loser's amount (or if the biggest winner isn't completely paid off, adjust the biggest winner's amount). Danny (-$200) is the biggest loser, he transfers $120 to the biggest winner, Jake (+$120). After the transfer, adjust Danny from -$200 to -$80.

Now back to step one. Guess what, Danny (adjusted to -$80) and Matt (-$15) now equal the amount owed to Hank +$95.

EZPZ.

Each time the biggest loser transfers to the biggest winner, you're retiring 1 debt. Check and see if you have even amounts and if not, have the biggest remaining loser pay the biggest remaining winner and retire one more debt. Check for balance. Wash and repeat as many times as necessary.

Yes, I think this is right. Seems like the same algo @pltrgyst was outlining: optimize for single-transaction closeouts. Then slowly increase complexity until everyone is paid.

I guess I was just hoping there was some off-the-shelf mathy way to do this. Honestly don't know what I'm looking for. Just seemed like it should be a solved problem.

I thought someone already did something similar to this, and a lot of people got ripped off.

Could be. It's not a novel idea. PokerStars Home Games are an obvious competitor, but I'm sure there are others, and some of them may be less than savory. Regardless, it's a fun personal project and I'm learning a lot. Onward!

 

[pltrgyst]

I could be mistaken, but wouldn't it be nr of players minus players who broke even minus one?

It depends on whether or not you count as a transaction the contribution from the person who pays off the last winner. It's a semantic distinction, really. That last loser processes his loss into the pooled loser money, and then transfers that money to the winner. So does he conduct one or two transactions?

 

[Mr Winberg]

It depends on whether or not you count as a transaction the contribution from the person who pays off the last winner. It's a semantic distinction, really. That last loser processes his loss into the pooled loser money, and then transfers that money to the winner. So does he conduct one or two transactions?

I agree, it depends on the semantics of "transaction". What I an referring to is physically opening my Swish app, entering the phone number of the receiver, clicking Send, and finally identifying myself with my BankID app to complete the transfer. I.e., the actual wiring of money. In that case, it's 3 in the example above and in general N - E - 1 (N = Nr of players, E = Nr of Even-breakingeners).

 

[waddadonk]

Quality link. Thanks, dude. I'll look through.

Thing I got wrong was keeping the same person paying off the top. Gotta re-sort after a transaction. Added example where it becomes really obvious why

-edit- Didn't read through thread. Looks like others have come up with the same method!

 

[Frogzilla]

Wedge Rock's solution is pretty close to optimal (but not 100%).

Waddadonk is going to run a lot quicker though.

The real issue though which dkersey alludes too....losses and wins usually don't happen at the same time. Your losers are going to want to know who they owe when they bust.

 

[WedgeRock]

I thought someone already did something similar to this, and a lot of people got ripped off.

Are you talking about Full Tilt?

 

[Davism72]

Are you talking about Full Tilt?

Interested also.