Quantifying Algorithmic Improvements over Time

Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Frechette et al. [2016] advocated performing such analysis via the Shapley value, a concept from coalitional game theory. In this paper, we argue that while this general idea is sound, it unfairly penalizes older algorithms that advanced the state of the art when introduced, but were then outperformed by modern counterparts. Driven by this observation, we introduce the temporal Shapley value, a measure that addresses this problem while maintaining the desirable properties of the (classical) Shapley value. We use the tempo- ral Shapley value to analyze the progress made in (i) the different versions of the Quicksort algorithm; (ii) the annual SAT competitions 2007–2014; (iii) an annual competition of Constraint Programming, namely the MiniZinc challenge 2014–2016. Our analysis reveals novel insights into the development made in these important areas of research over time.

Authors

• Lars Kotthoff University of Wyoming, Laramie, WY, USA
• Alexandre Fréchette
• Tomasz Michalak University of Warsaw IDEAS NCBR
• Talal Rahwan
• Holger H. Hoos Chair for AI Methodology, RWTH Aachen University, Germany LIACS, Leiden University, The Netherlands
• Kevin Leyton-Brown University of British Columbia

Keywords

• Heuristic Search and Game Playing: Evaluation and Analysis
• Heuristic Search and Game Playing: Meta-Reasoning and Meta-Heuristics