Stochastic, Nerdtastic Restaurant Bill Splitting

by scottkrager • 14 years ago

33 47 14 years ago

dreeves10• 14 years ago

Excerpt that describes the actual mechanism:

Start with any item on the bill. The person who ordered that item pays the bill with probability equal to the cost of that item divided by the subtotal. Flip the appropriately biased coin; if that person is it, then you're done. If not, then subtract that item from the subtotal and repeat, recursively, with another arbitrary item. If you start with expensive items then you'll probably find the person who's paying after a handful of items, but it doesn't matter for fairness what order you pick things in. You won't have to figure out all the confusing drinks and appetizers (yet the outcome is as fair as if you had!).

dy• 14 years ago

I've tried this with a group. It's good for generating endless conversation on principles of economic fairness. It completely fails to be a time-saving mechanism.

There is the completely rational mind and then there are humans - this represents a separation point :)

dreeves10• 14 years ago

Ha! Touche! Yes, this has never actually saved time. Well, among me and Bethany Soule (coauthor of the Android app described in the article) and Sharad Goel (co-blogger at Messy Matters) I think it's now routine enough that it saves time.

But it's so the Right Way to do it! I guess it's like trying to get Americans to use the metric system. It would be worth it if it actually worked...

mseebach2• 14 years ago

Since one person ends up paying the whole thing, it's only fair if the same group of people goes out together frequently, such that there is a reasonable expectation that everyone will end up paying their fair share eventually.

Another downside is the liquidity requirement. To adequately participate, you need to be able to pay for a fairly large number of meals.

dreeves10• 14 years ago

From the article: http://messymatters.com/expectorant/#EXP

"A common complaint about stochastic schemes is that they’re “only fair if you do it repeatedly with the same group of people”. That’s true if you insist on ex post fairness. We’re usually happy with ex ante fairness. Consider selling me a (perfectly fairly priced) lottery ticket for a dollar. That’s guaranteed to be unfair, ex post. Either you sold me a worthless piece of paper for a dollar, or I got a million dollars and only paid a dollar for it. But the fact that none of us knew which would happen made the one dollar price fair. Same story with venture capital investment, for example. You may need a gambling mentality to be down with it, but it’s quite fair even if only done once. The fact that it averages out in the long term to be perfectly fair ex post is icing on the cake."

chime• 14 years ago

Why is the bill-splitting problem so much more interesting to techies compared to the tons of other real-life math application problems out there? I see more apps and websites on how to split a bill n-way than I see for predicting cashflows, organizing tables/chairs, and maximizing toothpaste usage combined. I think it is a fun problem as any other, but what makes it more interesting than others?

bsoule• 14 years ago

nerd attempt at social skills. you don't maximize toothpaste usage with friends!

SatvikBeri• 14 years ago

Personally, I split bills almost every day, and it's frequently a headache. But I can't remember the last time I thought about maximizing toothpaste usage.

paulsutter2• 14 years ago

I have an even better idea. How about anyone who thinks this is even marginally interesting just leaves me out of their dinner plans.

There are only two ways to take care of the check. Either one person pays, or n people pay equally like the opening scene in American Psycho. Any sort of bookkeeping at the dinner table is really bad manners.

EDIT, more etiquette hints:

when looking at the check, make at most a quick glance. Ideally don't look at the check at all. If you can't trust them to prepare a check you probably shouldn't trust their cooking either.

How do you figure out who picks up the check?

- if you are dining with the boss, you're the one who pays

- if you're dining with customers, you're the one who pays

- if you're dining with your girlfriend and her female friends, you're the one who pays

- if you're the host in any sense, you're the one who pays

- if you're dining with students and you're the only one who has a job, you're the one who pays

- if you're the one who went deep on the wine list, you're the one who pays

There aren't many times that a check gets split, or any sort of turn-taking applies. For the most part, you're the one who pays.

donall• 14 years ago

The proposed method isn't bookkeeping. It sounds like it's closer to bookmaking!

dreeves10• 14 years ago

Such a debbie downer! Note that in this system one person does pay. Just that you play a little gambling game to determine who it is.

Do you think credit card roulette is bad manners? This is basically a fairer version of that.

redslazer• 14 years ago

Going down the list:

- if you are dining with the boss, you're the one who pays ------ No unless you invited them. - if you're dining with customers, you're the one who pays ----- Yes but hopefully your company reimburses you for that. - if you're dining with your girlfriend and her female friends, you're the one who pays ----- Maybe in 1980's, in my experience most people want to go dutch nowadays. - if you're the host in any sense, you're the one who pays ----- Yes but thats not the kind of situation that this would be used in. - if you're dining with students and you're the only one who has a job, you're the one who pays ---- Only if you invited them. If you made plans for dinner and they couldn't afford it, they should have made it clear before going out. - if you're the one who went deep on the wine list, you're the one who pays ----- If your the only one drinking wine, your doing it wrong.

pyoung• 14 years ago

God damn, I wish my friends/acquaintances were more like you. I would be eating out all the time!!

konstruktor• 14 years ago

Judging from the style of your writing, you seem oblivious to the fact that your list assumes very specific cultural context (hint: you are even assuming the gender and relationship status of the reader, how they call their partner, and very specific gender roles), and may be very debateable even within that context.

paulsutter2• 14 years ago

It's not so much that I'm oblivious, but rather that I think we're better off taking on responsibility than we are obsessively complicating things that can be simple.

When I was in college we had a sink full of dirty dishes until we had a rule to always wash one more dish than you dirtied. It worked even though the math major refused to participate. The problem wasn't an individual free rider, the problem was that humans were involved, humans make mistakes, and the errors accumulated in the sink.

Paying more than your share is a good habit that has good effects elsewhere in your life. Can you fairly split all the little schleps among the founding team of a startup? Best results are obtained when each person does (what feels like) more than their share. Both members of a married couple should make (what feels like) more than their fair share of compromises. As parents we'll make nothing but compromises and be repaid in resentment. But it's one of the most rewarding things we do in life.

Make a game out of finding ways to pay more than your share, sneak it past the anal retentives and militant obsessives. Extra points if they never notice. It's harder than you might think. But it's good practice for the rest of life.

theorique3• 14 years ago

if you're dining with your girlfriend and her female friends, you're the one who pays

"Hmm, why do my date nights get bigger and bigger? Last time we had ten of her friends show up!"

calinet6• 14 years ago

Appropriately, "Expectorant" also refers to a medication which helps produce mucus. This is roughly the social equivalent.

aaronblohowiak• 14 years ago

The (unfair) credit card roulette that they mention is a more "baller" version of this, and a favorite around certain groups of friends.

theorique3• 14 years ago

I love credit card roulette! Great low-stakes bonding experience with friends and co-workers.

lmm2• 14 years ago

I find it hard to believe this would be faster than just adding up what everyone ordered, and then either picking someone with weighted random (absolutely equivalent to the given algorithm), or just everyone paying for their own stuff (perfectly fair).

dreeves10• 14 years ago

I think the real beauty of this method is that you don't have to figure out what everyone ordered (only a few people usually).

lmm2• 14 years ago

The probability you use is the value of that item divided by the total, no? So on average you'll get halfway down the menu, and have to have figured out who ordered half the things, in slow bits and pieces.

Thinking about it, I think I have a faster way to do it: 1. generate a random number between 0 and bill amount. 2. "Count" that much money down the bill. 3. Whoever ordered the item you stop on pays.

fatbat• 14 years ago

All that math just complicates the roulette-ness.

How about just toss all the credit cards in a bag/box/etc and ask your nice waiter to pick one at random.

AlisdairO• 14 years ago

With good friends I generally just split the bill evenly, but that tends to be non-scalable.

One method I found which seems to work quite nicely is each person puts in what they think they owe, and any difference between that and the total bill is split evenly between the group. This tends to work out nearly-equitable and is very fast.

theorique3• 14 years ago

I agree.

I generally offer more if I feel I've consumed more - "hey, I had four drinks and you had two, you don't have to pay for me" - but if they insist on splitting evenly I am OK with that.

Same thing if I'm the underconsumer - I don't want to show up at 2230, have a beer, and split a check that's been open since 1700, but if the differences are small then even split is just fine.

seivan2• 14 years ago

I solved this recursively, but with a different algorithm... will try this out now :) Looks like fun!

dmvaldman2• 14 years ago

What algorithm? I think these problems are fun.

seivan2• 14 years ago

I don't got a name for it, as it wasn't a specific algorithm being followed, I Just "solved it" by coding it. I had to do it recursively because calling it once would not give an accurate number, so it called itself until the numbers matched up :) I can share the Ruby code once I clean it up. I intend to open source the web app anyway.

renwick• 14 years ago

Note the dreadful UI on their app implementation! (You type something like '100:5,25,60' and invite someone to guess a number on each round)

Why wouldn't they do something like:

1. Enter the subtotal (becomes permanently printed at the top) 2. Enter successive item amounts, after each entry the app says 'pay' or 'continue'

dreeves10• 14 years ago

True. The historical reason is that it was (well still is) originally a general biased coin flipper where you could enter any expression that evaluated to a probability. Then we added syntactic sugar for the case of restaurant bill splitting.

UI improvements welcome! Bethany has it on github: https://github.com/bsoule/Expectorant

dmvaldman2• 14 years ago

This makes me start thinking what other problems can be handled more efficiently if everyone agreed to be satisfied with an "expectation" of fairness in the long term.

You gain efficiency, at the loss of acquiring short term risk. Might be a useful exchange in some cases.

One good example: in a traffic jam everyone decides to maintain a minimum of 50ft between them and the car in front of them.

morsch2• 14 years ago

Where I live, it's very widespread and perfectly acceptable to pay exactly what you owe, especially if you're drinking/dining with peers. Waiters typically ask if you want to share a common bill or if you want to pay separately; if it's the latter they'll do the adding up for you.

hellweaver666• 14 years ago

Where do you live?

morsch2• 14 years ago

Germany. Gosh I hope that's not just a German thing.

dfxm122• 14 years ago

Where do you live that this isn't the norm? (sorry if you weren't implying that it isn't)

tonakai• 14 years ago

similar approach in Czech Republic, and you can leave the tip separately.

dfxm122• 14 years ago

Yeah, it is like this where I live too. I will never understand people trying to play a game in order to figure out who pays the whole bill.

brokentone• 14 years ago

TL;DR - This is not splitting the bill, but rather a gamble of paying the entire bill with a probability equal to your share of it.

dreeves10• 14 years ago

Quite right! But I think the cool thing from a mathematical/nerd perspective is that you can have everyone pay with that probability (splitting the bill stochastically) without figuring out what those probabilities are. Ie, without figuring out what everyone ordered.

alttab2• 14 years ago

So the guy who orders more expensive items or more items pays for the whole bill more often then that? Sorry joe, you owe me for your entree whether or not I had 2 beers

meddlepal• 14 years ago

I usually just pay what I owe and a 15 - 20% tip. Occasionally, and it depends on the acquaintances/friends. I am with, I will do equal split (total + tip) / number of people.

Is this really that difficult?

Stochastic, Nerdtastic Restaurant Bill Splitting

Related Stories