Is It Rational to Be Competitive? On the Decision-Theoretic Foundations of the Competitive Ratio

Authors: 
Ran El-Yaniv
Abstract: 

The competitive ratio, a performance measure for online algorithms, or alternatively, a decision making criterion for strict uncertainty conditions, has become a popular and accepted approach within theoretical computer science. This paper closely examines this criterion, both by characterizing it with respect to a set of axioms and in comparison to other known criteria for strict uncertainty.

Date: 
August, 1996
Published in: 
Number: 
113