A Game Theoretic Approach to Measure Contributions in Algorithm Portfolios

Abstract

Algorithm Portfolios [6, 5] have attracted signi cant attention in Arti - cial Intelligence research, due to their ability to exploit the complemen- tary strengths that often exist among di erent algorithms. In this arti- cle, we address the following natural question: How do we measure the contribution that an algorithm makes to a portfolio of algorithms? We show that the solution proposed in the literature to answer this question is inadequate. We then propose the use of the Shapley value|a well- known concept in cooperative game theory|and show that it provides the correct answer. We discuss the potential impact and insights that the use of this measure could bring to the community.