Using the Shapley Value to Analyze Algorithm Portfolios

Authors

  • Alexandre Fréchette University of British Columbia
  • Lars Kotthoff University of British Columbia
  • Tomasz Michalak University of Oxford and University of Warsaw
  • Talal Rahwan Masdar Institute of Science and Technology
  • Holger Hoos University of British Columbia
  • Kevin Leyton-Brown University of British Columbia

DOI:

https://doi.org/10.1609/aaai.v30i1.10440

Keywords:

algorithm portfolios, Shapley value, contribution analysis, SAT competition

Abstract

Algorithms for NP-complete problems often have different strengths andweaknesses, and thus algorithm portfolios often outperform individualalgorithms. It is surprisingly difficult to quantify a component algorithm's contributionto such a portfolio. Reporting a component's standalone performance wronglyrewards near-clones while penalizing algorithms that have small but distinctareas of strength. Measuring a component's marginal contribution to an existingportfolio is better, but penalizes sets of strongly correlated algorithms,thereby obscuring situations in which it is essential to have at least onealgorithm from such a set. This paper argues for analyzing component algorithmcontributions via a measure drawn from coalitional game theory---the Shapleyvalue---and yields insight into a research community's progress over time. Weconclude with an application of the analysis we advocate to SAT competitions,yielding novel insights into the behaviour of algorithm portfolios, theircomponents, and the state of SAT solving technology.

Downloads

Published

2016-03-05

How to Cite

Fréchette, A., Kotthoff, L., Michalak, T., Rahwan, T., Hoos, H., & Leyton-Brown, K. (2016). Using the Shapley Value to Analyze Algorithm Portfolios. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10440

Issue

Section

Technical Papers: Search and Constraint Satisfaction