Shostack + Friends Blog Archive


The Wallet Game

At lunch after Shmoocon, Nick Mathewson said he’d like to pay something between zero and the amount of money in his wallet. I think this suggests a fascinating game, which is that Alice asks Bob for some amount of money. If Bob has that much money in his wallet, he pays. Otherwise, Alice pays him the amount asked for. How much should Alice ask for?

The more she asks for, the more likely she is to pay that amount. [Updated: That used to say ‘less likely.’] The more information Alice has about Bob, the better off she is. (If she has just seen Bob take a fat wad of bills for the ATM, for example.)

R.G., R.D., and noise suggested that if Alice challenges Bob to the game, Bob should be able to choose if he will ask or be asked.

What is Alice’s optimal strategy, absent special information about Bob’s circumstances? Does the non-continuous nature of US currency change things? What if everyone were carrying coins of a single denomination? Does iteration change things?

(Jenlight’s Duct tape wallet is from Flickr.)