{"id":384,"date":"2012-08-22T20:09:11","date_gmt":"2012-08-22T18:09:11","guid":{"rendered":"http:\/\/pit-claudel.fr\/clement\/blog\/?p=384"},"modified":"2013-12-19T01:23:33","modified_gmt":"2013-12-19T00:23:33","slug":"the-cafeteria-paradox","status":"publish","type":"post","link":"https:\/\/pit-claudel.fr\/clement\/blog\/the-cafeteria-paradox\/","title":{"rendered":"The cafeteria paradox: stop using the water dispenser while someone else does!"},"content":{"rendered":"


\n\"A Most cafeteria water dispensers will let two (sometimes more) people fill a jug at the same time. This article uses simple maths to prove that it’s a waste of time. In other words, two people should never use the same water dispenser at the same time: I call this the cafeteria paradox<\/i>.<\/p>\n

An intuitive presentation<\/h2>\n

Let’s start with a little brain teaser:<\/p>\n

\nAlice and Bob are at the cafeteria, seating at different tables. Alice stands up to refill her table’s water jug. Little after, Bob stands up with his own table’s jug, heading to the same water dispenser. That water dispenser is a perfectly standard one, with two taps, and Bob finds himself standing near Alice. After a small hesitation, Bob starts using the second tap to fill his own jug, thereby diverting part of the output previously devoted to Alice.<\/p>\n

This grants him an exasperated and somewhat puzzled look from Alice. Why?\n<\/p><\/blockquote>\n

<\/p>\n

The reason is quite simple: though most people will act just like Bob, using the water dispenser while someone else does is — in most of the cases — a useless waste of time. Indeed, starting to fill his own jug before Alice is done will not save Bob any time, but it will waste some of Alice’s time. That’s the cafeteria paradox<\/em>.<\/p>\n

Fortunately, this paradox is readily explained: assuming both Alice and Bob are using similar jugs, and both start with an empty jug, Alice will finish before Bob does; when Bob leaves, therefore, the water dispenser will have dispatched precisely the countenance of two caferetia jugs.
Now, Since the combined output of the two taps equals that of only one, dispatching this amount of water will take a constant time (precisely twice the time that it would take to fill a single jug). Hence Bob will gain no time at all by starting to fill his jug right away, while some of Alice’s time will be wasted.<\/p>\n

Not convinced? Imagine Bob and Alice are waiting for some pizza at a take-away restaurant. Given that Bob and Alice won’t start eating before they get to their respective homes, should Bob accaparate half of Alice’s pizza when it arrives, or let Alice get the full pizza first and wait for his own pizza? If Bob asks for half of Alice’s, both will wait for two pizzas to be ready; on the other hand, if Bob lets Alice go first, Alice will have only waited for one, while Bob will have waited for two. Clearly the second solution is better for Alice, and neutral for Bob; and the situation is exactly similar to that of the water dispenser.<\/p>\n

Still not convinced? Read on for a full mathematical description of this situation. Otherwise, skip to the conclusion<\/a> (and the sticker!).<\/span><\/p>\n

A mathematically accurate description<\/h2>\n

Let \\(t_A\\) and \\(t_B\\) be the respective times when Alice and Bob reach the water dispenser, and \\(t_A’, t_B’\\) the respective times when they leave. Let \\(t^*\\) be the time when Bob starts using the water dispenser. The water dispenser has a flow rate \\(f\\), and each jug has a capacity \\(c\\).<\/p>\n

From \\(t_A\\) to \\(t^*\\), Alice’s jug is filling at rate \\(f\\); from \\(t^*\\) to \\(t_A’\\), at rate \\(f\/2\\). Hence Alice’s departure time \\(t_A’\\) satisfies the following equation: $$ (t^* – t_A) ⋅ f + (t_A’ – t^*) ⋅ (f\/2) = c$$
\nwhich yields \\(t_A’ = t^* + \\frac{c}{f\/2} – 2 ⋅ (t^* – t_A)\\), so $$ t_A’ = 2 t_A – t^* + \\frac{c}{f\/2} $$<\/p>\n

Similarly, Bob’s departure time \\(t_B’\\) satisfies the following equation: $$ (t_A’ – t^*) ⋅ (f\/2) + (t_B’ – t_A’) ⋅ f = c$$
\nwhich yields \\(t_B’ = t_A’ + \\frac{c}{f} – (1\/2) ⋅ (t_A’ – t^*) \\), so $$ t_B’ = (1 \/ 2) ⋅ (t_A’ + t^*) + \\frac{c}{f} $$<\/p>\n

Finally, subtituting \\(2 t_A – t^* + \\frac{c}{f\/2}\\) for \\(t_A’\\) yields \\(t_B’ = t_A + (1 \/ 2) \\cdot \\frac{c}{f\/2} + \\frac{c}{f}\\); that is $$ t_B’ = t_A + 2 ⋅ \\frac{c}{f} $$<\/p>\n

To summarize, Alice will leave at \\(t_A’ = 2 t_A – t^* + \\frac{c}{f\/2}\\) (the later Bob starts, the earlier Alice will leave), while Bob will leave at \\(t_B’ = t_A + 2 ⋅ \\frac{c}{f}\\), which does not depend on \\(t_B\\) or \\(t^*\\)<\/em>.<\/p>\n

Conclusion<\/h2>\n

The socially optimal solution is that Bob waits until Alice is done before starting to use the water dispenser; otherwise, some of Alice’s time will be wasted, though Bob will not benefit from it. The key to understanding this is that Bob will not leave the water dispenser before both jugs are full, and filling both jugs takes a constant time (the time needed for the water dispenser to deliver twice the volume of a jug, spanning from Alice’s arrival to Bob’s departure). Thus using the water dispenser while someone else does is not only selfish: it’s downright stupid.<\/p>\n

Shocked? Leave a message in the comments! Otherwise join our campaing to stop multi-threading in water dispensers: stick the following message on your cafeteria’s water dispenser and post a picture of your sticker in the comments!<\/p>\n

\"Cafeteria<\/a><\/p>\n

Title image © Cosmetal.<\/p>\n","protected":false},"excerpt":{"rendered":"

Most cafeteria water dispensers will let two (sometimes more) people fill a jug at the same time. This article uses simple maths to prove that it’s a waste of time. In other words, two people should never use the same water dispenser at the same time: I call this the cafeteria paradox.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56,55,33,57],"tags":[58,62,59,61,60],"_links":{"self":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/384"}],"collection":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/comments?post=384"}],"version-history":[{"count":5,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/384\/revisions"}],"predecessor-version":[{"id":760,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/384\/revisions\/760"}],"wp:attachment":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/media?parent=384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/categories?post=384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/tags?post=384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}