Quantifying algorithmic improvements over time

Lars Kotthoff, Alexandre Fréchette, Tomasz Michalak, Talal Rahwan, Holger H. Hoos, Kevin Leyton-Brown

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Fréchette 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 temporal 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
PublisherInternational Joint Conferences on Artificial Intelligence
Number of pages7
ISBN (Electronic)9780999241127
StatePublished - 2018
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: Jul 13 2018Jul 19 2018

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823


Other27th International Joint Conference on Artificial Intelligence, IJCAI 2018

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Quantifying algorithmic improvements over time'. Together they form a unique fingerprint.

Cite this