Quantifying Algorithmic Improvements over Time
Quantifying Algorithmic Improvements over Time
Lars Kotthoff, Alexandre Fréchette, Tomasz Michalak, Talal Rahwan, Holger H. Hoos, Kevin Leyton-Brown
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Evolution of the contours of AI. Pages 5165-5171.
https://doi.org/10.24963/ijcai.2018/716
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.
Keywords:
Heuristic Search and Game Playing: Evaluation and Analysis
Heuristic Search and Game Playing: Meta-Reasoning and Meta-heuristics