TY - GEN
T1 - Quantifying algorithmic improvements over time
AU - Kotthoff, Lars
AU - Fréchette, Alexandre
AU - Michalak, Tomasz
AU - Rahwan, Talal
AU - Hoos, Holger H.
AU - Leyton-Brown, Kevin
N1 - Funding Information:
We thank Andreas Schutt for kindly providing the virtual machines of the MiniZinc challenge solvers and helping to set up the experiments. Kevin Leyton-Brown, Alexandre Fréchette and Lars Kotthoff were supported by an NSERC E.W.R. Stea-cie Fellowship; in addition, all of these, along with Holger Hoos, were supported under the NSERC Discovery Grant Program and Compute Canada's Research Allocation Competition. Tomasz P. Michalak was supported by by the Polish National Science Centre grant 2015/19/D/ST6/03113.
Funding Information:
We thank Andreas Schutt for kindly providing the virtual machines of the MiniZinc challenge solvers and helping to set up the experiments. Kevin Leyton-Brown, Alexandre Fréchette and Lars Kotthoff were supported by an NSERC E.W.R. Stea-cie Fellowship; in addition, all of these, along with Holger Hoos, were supported under the NSERC Discovery Grant Program and Compute Canada’s Research Allocation Competition. Tomasz P. Michalak was supported by by the Polish National Science Centre grant 2015/19/D/ST6/03113.
Publisher Copyright:
© 2018 International Joint Conferences on Artificial Intelligence.All right reserved.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85055691610&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85055691610&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2018/716
DO - 10.24963/ijcai.2018/716
M3 - Conference contribution
AN - SCOPUS:85055691610
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 5165
EP - 5171
BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
A2 - Lang, Jerome
PB - International Joint Conferences on Artificial Intelligence
T2 - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Y2 - 13 July 2018 through 19 July 2018
ER -