Expert Advice and the Newsvendor Problem

The multi-period newsvendor problem describes the newspaper salesman's dilemma---how many papers should he purchase each day to resell, when he doesn't know the demand? We describe approaches for solving this problem based on algorithms for the Expert Advice problem. We give bounds on the regret of our algorithms in terms of the regret of the static offline optimal algorithm, which chooses a single order quantity for all periods which maximizes the profit. Bounds of this type show that the approach will perform well in 'easy' distributional demand situations while simultaneously giving guarantees for all situations. Testing the algorithms via simulation we find that the method works well in a variety of circumstances despite the minimal assumptions made. Finally, in a separate problem related to distributed computing, we discuss a new model and theoretical results for minimizing the time to distribute a file throughout a network using simple tools.