Cooperative Competition: A New Way of Solving SAT and other NP-Hard Problems in AI and Beyond
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Argues that competitions should reward contribution to team performance by automatically building per-instance selectors over submitted solvers; implements the SPARCL platform that uses AutoFolio to construct selectors and bootstrap resampling to test stability. Uses relative marginal contribution to split credit. On a 2018 SAT set the selector closes 14.3% of the gap to the virtual best (rises to 55.7% when training per-family); a planning challenge shows similar gains. System works but faces classifier generalization, no solver reconfiguration, and adversarial-submission risks.
AI-written summary · about
chapters (30)
- 0:00Introduction
- 2:13Competition
- 4:20Inconvenient Truths
- 5:04Assessing Competition Outcomes
- 6:14SAT 2014 Results
- 8:18Confidence Bands
- 9:42Strength of solvers
- 10:58Configurable SAT solver competitions
- 13:23Performance complementarity
- 14:28Competitions
- 15:55Cooperative Competition
- 16:37Sparkle Challenges
- 17:59Leaderboard Phase
- 18:24SAT 2018
- 19:00Training Set
- 19:30Testing Set
- 20:38Autofolio
- 21:29Solver Contributions
- 23:15Results
- 25:41Standalone vs relative marginal contribution
- 27:47Official results
- 29:03Training example
- 31:10AI Planning
- 32:19SAT Comparison
- 34:02Summary
- 36:37Benefits
- 37:26Whats next
- 40:49Conclusion
- 43:04Questions
- 46:17Discussion