Reference no: EM132295600

Every day at noon exactly, people submit orders of positive integer numbers of paninis at your panini store. It takes you 1 minute to make 1 panini.

When Alice orders 2 paninis and Bob orders 100 paninis, you decide to make Alice's paninis first, because it results in less total customer wait time (104 vs. 202 minutes).

When the town gets wind of your scheme, they hatch devious plans. Instead of ordering 100 paninis, Bob decides to submit 100 orders of 1 panini each under different names, so he gets processed first. Oh no.

Call a panini-making scheme strategy-free if no customer, in any scenario, can strictly decrease their average wait time just by splitting their order up into several smaller (integer-size) orders.

Assume your customers are aware of your scheme and will not split up their orders if the scheme is strategy-free.

1. Show that the scheme "choose the sequence of orders uniformly at random" is strategy-free.

2. Give an example of a strategy-free scheme that has a lower average wait time than the above scheme whenever the orders are not all the same size.

3. Suppose you know that, on any given day, you will either receive (1) three orders for one panini each, or (2) one order for one panini and one order for two paninis. Give a strategy-free panini-making scheme such that in either scenario (1) or (2), the average total wait time is at most 25/24 the optimal total wait time.