Stochastic, Nerdtastic Restaurant Bill Splitting | Hacker News Reader

Stochastic, Nerdtastic Restaurant Bill Splitting

messymatters.com

33 pointsscottkrager47 comments

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?

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

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.

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.

Where do you live?

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

In Sweden it is also in many situations acceptable to pay for just your items.

Shit guys I do this in America. Delegate the work to the waiter by telling her you want to split the checks up front. Problem solved.

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

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

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.

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.

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.

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

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

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

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!).

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 :)

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...

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.

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."

Yeah, it says it's gambling. Even if it's mathematically fair gamling, that doesn't make it a "fair" way to spilt a bill.

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.

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.

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

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.

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?

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'

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

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

What algorithm? I think these problems are fun.

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.

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).

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).

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.

Ooh, I like that!

But to clarify, the method in the article is quite a bit better than you think:

"On average you’ll only traverse half the bill — and that’s half in terms of dollar value, not number of items. So much less than half the items if most of the bill is concentrated in a few expensive entrees."

I actually think it's kind of fun, with the multiple trials for who will pay. But I'm eager to try your idea now!

EDIT: You're totally right, this is a faster fair way! It's not as simple as it sounds though: if you land on, say, a $2 drink of which there are multiple such on the bill then you need a protocol to disambiguate. You could randomize again among the people who got one of those items.

What I like most about the method in the article is that you can avoid the confusing smaller items with high probability. Maybe the way to achieve that with your method is to walk down the items in decreasing order of price. That also forces you to identify sets of things that all cost the same, so you can do the second randomization if necessary. (You could also just pick a canonical order of the people, like alphabetical, or where they're seated, since there's enough randomness in the original random number.)

You're even righter than I thought. This is definitively faster than the method in the article. And with your method there's no point in rearranging the items. You're no more likely to have to deal with a confusing small item than with the method in the article.

The only possibly worse aspect is that, when the item is chosen, you have to make sure to identify everyone who got a copy of that item. With the method in the article you always consider items one at a time, in isolation.

Hey lmm, can you get in touch so I can credit you with this idea in an addendum to the article?

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.

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.

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

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.

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.

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

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.

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.

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!"

Reply on news.ycombinator.com