Need to pick a winner and your crystal ball is broken? An MIT mathematics professor and his colleagues have come up with a method to help schedule computer jobs on a network or choose a movie that will please the most viewers in a pay-per-view cable TV service. In short, the method helps solve any problem in which you have to choose an option with the best future performance.
Surprisingly, Professor F. Thomson Leighton found that with some knowledge of past performance, even someone who has no way to predict the future performance of any of his or her options can still guarantee himself a high probability of success in picking a winner. But investors beware: although he has used the method in an imaginary investment scenario, the theory has not yet been proven to work in the stock market and cannot be used to guide investing.
The algorithm itself, which relies partly on flipping a coin, is considered simple by mathematicians but isn't for those who have trouble balancing a checkbook. But it may someday be embedded in easy-to-use software and applied to investment planning, strategic planning and other areas where it's important to predict the future moves of an adversary or a market.
"Even if the past is not correlated with the future, the past can be combined with randomness to provide a very good prediction of future performance," Professor Leighton said. "The intuition that past winners are likely to be future winners can be used as the basis for a successful strategy, even though the intuition is not precisely correct."
The scheduling algorithm, for instance, tends to schedule jobs on machines that have been available in the past. The investment scenario tends to call for buying stocks that have paid dividends in the past. "This should not be confused with the dangerous strategy of jumping on the bandwagon, although picking a random time to jump on the bandwagon can turn out well," he said.
Although it might seem that coin-tossing would add an unpredictable element, this actually "takes the guesswork out and can prevent the worst-case scenario," said Professor Leighton, who also is affiliated with the Laboratory for Computer Science.
Here's a scheduling scenario. Bob has a job requiring a certain amount of computer time. His goal is to schedule his job on a workstation that will be free to complete the job within a reasonable time frame. But the workstations could be assigned higher-priority jobs at any time, leaving Bob's job unfinished.
Which workstation should Bob choose? The problem assumes that if Bob chooses wrong and switches to another workstation, he would have to pay for the change.
To use Professor Leighton's formula, Bob would check to see which of the three workstations on the network (there can be any number of workstations) is available. If workstation 2 is available, Bob flips a coin to decide whether to assign the job to it.
This is not a random coin toss. It is more heavily weighted toward a workstation that has been available that day. The more often workstation 2 was available, the better the chance it would be chosen now. If workstation 2 is not chosen, Bob continues to flip a coin.
If the job is assigned, Bob stops flipping coins and waits for the job to be completed. He now has a good shot at having his job done, as long as there was at least one workstation that had the time -- plus some extra time to make up for time lost in the choosing process -- available to complete the job. If no workstation was ever available, Bob couldn't have hoped to get his job done anyway.
Likewise, to win in the investment scenario, you would have to assume that at least one stock in 1,000 will pay a lot of dividends in a given period. If none of the stocks paid any dividends, then it doesn't matter what you do -- you're not going to make money. (This is not about buying and selling shares of stock. The model does not yet address entities that can go down in price. The model addresses choosing a stock that pays good dividends over one that pays none.)
Investors want to pick a stock that will come as close to a best-case scenario as possible, acting as if they know the future even though they don't. "People believe they are at the whim of the stock market," Professor Leighton said. "Using this method, you can do better than you might think without knowing the future."
Assume there are six stocks available (again, any number will work). In each fiscal quarter, the one you own may or may not pay a dividend of $1; you only collect if you own the stock when it pays out the dividend. The objective is to choose the stock that pays the most over time. The goal is to maximize profit while minimizing the number of changes, which may have a cost.
Every day, check which stock paid a dividend. Each time a company pays a dividend, look at its past record. The more dividends the company has paid in the past, the better the chance that it will come up heads in your coin toss. If it comes up heads, pick it on that day. If you want to switch to a different company, keep flipping coins to decide when to change.
"We can prove mathematically that this is the best you can ever do," Professor Leighton said. The proof assumes that you are comparing your results against a worst-case scenario. In the real world, you might have information that would allow you to do better.
The formula also works when the goal is to choose which movie will garner the most customers on a pay-per-view channel. As customers request movies during the day, the channel must choose which movie it will show that night. Each customer's request is immediately acccepted or rejected, and if a request is accepted, the movie must be shown. Rejected customers are lost.
Compared with the options scenario, the movies are the options, the customers are the days the option is held, the requests are dividends paid and profit is the number of accepted requests.
Professor Leighton, with colleagues Baruch Awerbach at Johns Hopkins University and Yossi Azar and Amos Fiat at Tel Aviv University's computer science department, are looking at applying his method to a new pricing model for stocks' call options. However, he said it's too early to tell whether it will have practical applications in that field.
The research is supported in part by ARPA.
A version of this article appeared in MIT Tech Talk on May 20, 1998.
