- Mechanical TA: Partially automated high-stakes peer
grading. A web-based application enabling students to
grade work from randomly selected peers in a class. The key difference
from other peer-grading systems is that it uses TAs to perform selective
spot-checks and thus incentivizes high-quality grading.
- Paper: PDF; ACM Digital Library; DOI
- Web page: Mechanical TA project page.
- HAL: A framework for the automated design and analysis
of high-performance algorithms. An experimental management
and analysis platform for empirical algorithmics, particularly targeting
meta-algorithmics. HAL has been designed to facilitate the easy and
correct use of a broad range of standardized, advanced empirical
analysis and design methods; to design and perform computational
experiments, including large-scale analysis and design tasks involving
substantial amounts of computation on potentially large clusters of
machines; and to support the development and critical assessment of
novel empirical analysis and design techniques.
- Paper: Nell, Fawcett, Hoos & Leyton-Brown, 2011.
- Web page: HAL project page.
- SMAC and ROAR: Sequential model-based optimization for
general algorithm configuration. Model-based active
learning methods for the automatic, black-box configuration of
- Paper: Hutter, Hoos & Leyton-Brown, 2011.
- Web page: Automated Algorithm Configuration Project Pages.
- Hydra: automatically configuring algorithms for
portfolio-based selection. The software automatically
builds an algorithm portfolio out of a single, highly-parameterized
algorithm, targeting a given instance distribution and performance
- Paper: Xu, Hoos & Leyton-Brown, 2010.
- Web page: Hydra project page.
- SATzilla: A portfolio-based solver for SAT problems.
It won 3 gold and 2 silver in the 2009 SAT competition, and 3 gold, 1 silver, 1 bronze in the 2007 SAT competition. Based on
these results, it's arguably the strongest all-around SAT solver in the
- Paper (SATzilla-09): Xu, Hutter, Hoos & Leyton-Brown, 2009.
- Paper (Journal paper): Xu, Hutter, Hoos & Leyton-Brown, 2008.
- Paper (SATzilla-07): Xu, Hutter, Hoos & Leyton-Brown, 2007.
- Paper (SATzilla-04): Nudelman, Devkar, Shoham, Leyton-Brown & Hoos, 2004.
- Web page: SATzilla project page.
- SATenstein: A generalized, highly parameterized solver framework that can be configured to instantiate a broad range of
existing high-performance SLS-based SAT solvers, and also over 1023 novel algorithms. We tuned it with ParamILS
(see below), achieving state-of-the-art
performance on all six of the widely-studied benchmarks we tried.
- Paper: KhudaBukhsh, Xu, Hoos & Leyton-Brown, 2009.
- Web page: SATenstein project page.
- ParamILS: Iterative local search for
algorithm configuration. It can be used as an entirely automated, model-free approach for tuning an algorithm's
parameters to optimize a performance measure such as runtime. We've applied it
in a wide variety of domains, including to
state-of-the-art SAT solvers and to CPLEX.
- Paper: Hutter, Hoos, Leyton-Brown & Stützle, 2009.
- Web page: ParamILS project page.
- Empirical Hardness Models. Code for building models
that predict an algorithm's runtime based on cheaply-computable features
describing a given instance. The papers below describe the construction
of these models for various different classes of algorithms, problem
- Paper: Leyton-Brown, Nudelman & Shoham, 2009.
- Paper: Xu, Hoos & Leyton-Brown, 2007.
- Paper: Hutter, Hamdi, Hoos & Leyton-Brown, 2006.
- Paper: Leyton-Brown, Nudelman, & Shoham, 2005.
- Paper: Nudelman, Leyton-Brown, Hoos, Devkar & Shoham, 2004.
- Paper: Leyton-Brown, Nudelman & Shoham, 2002.
- Web page: Empirical Hardness Models Project Page.
Benchmark Generator for Security Games. This
Java-based generator allows researchers to generate synthetic security
game problems from the computationally hardest region where the
deployment-to-saturation ratio is 0.5, for a variety of different
problem domains. It also provides tools for computing Strong Stackelberg
Equilibria of these games using both GLPK and CPLEX.
- Paper: Jain, Leyton-Brown & Tambe, 2012.
- Web page: Security Games Benchmark Generator page.
Bayesian Action-Graph Games: An extension of the AGG
representation to Bayesian games. The software enables the
efficient computation of expected utility and of Bayes-Nash equilibria.
- Paper: Jiang & Leyton-Brown, 2010.
- Web page: AGG project page.
Computational Analysis of Position Auctions. Software for representing position auctions as AGGs and finding their (possibly mixed-strategy)
equilibria, as well as data from our published experiments.
- Paper: Thompson & Leyton-Brown, 2009
- Web page: Position Auctions project page
Action Graph Games. Code for computing expected utility in
action-graph games, finding their Nash equilibria through GAMUT solvers,
and for generating AGGs for computational experiments.
- Paper: Jiang & Leyton-Brown, 2008
- Web page: AGG project page
- Platform for the Empirical Testing of Multiagent
Reinforcement Learning Algorithms. A Matlab program that
allows large-scale experimentation on multiagent reinforcement learning
algorithm. The platform also supports visualization of the
experimental results, and is easily extensible.
- Paper: Lipson & Leyton-Brown, 2005.
- Web page:
MALT project page
- GAMUT: A test suite for game theoretic algorithms.
An extensible Java package that generates games from one or more classes
described in the game theoretic literature. It is intended to be
used as input for the empirical testing of game theoretic algorithms,
e.g., multiagent reinforcement learning; computation of Nash equilibria.
- Paper: Nudelman, Wortman, Shoham & Leyton-Brown, 2004.
- GAMUT web page:
- Local Effect Game solver. Java program that
allows B-LEGs to be inputted graphically, and that uses myopic best response
dynamics to find a pure-strategy Nash equilibrium for the game, or (upon a
sufficient number of cycles detected) uses exhaustive enumeration to prove that
a PSNE does not exist.
- Paper: Leyton-Brown & Tennenholtz, 2003.
- Java JAR file:
To run it, either
double-click it (works on many operating systems including windows) or
from a console, type "java -jar LEG.jar". JAR files are
actually ZIP files, so if you want to modify or read the source code
just open the file with any UNZIP program.
Combinatorial Auction Winner Determination
- The downloads in this section could also be called Empirical Algorithmics; however, because they all specifically concern combinatorial auctions they're collected separately.
- CATS (Combinatorial Auction Test Suite).
Benchmark instances for combinatorial auction winner determination algorithms.
- Paper: Leyton-Brown & Shoham, 2006. This more recent work describes version 2.0, which contains many substantial enhancements and was released August 2003.
- Paper: Leyton-Brown, Pearson & Shoham, 2000.
- Web page: CATS website. Contains documentation, other downloads, etc.
- Git Repository: GitHub. Updated 2019; use this rather than the original archive!
- CASS (Combinatorial Auctions Structured
Search). An algorithm for solving the winner determination problem
for single-unit combinatorial auctions.
- Paper: Fujishima, Leyton-Brown & Shoham, 1999; explained in more detail in my thesis.
- Archive: ZIP. Source code (ANSI C++).
- CAMUS (Combinatorial Auction Multi-Unit
Search). An algorithm for solving the winner determination problem for
multi-unit combinatorial auctions.
- Paper: Leyton-Brown, Shoham & Tennenholtz, 2000; explained in more detail in my thesis.
Source code (ANSI C++).
- Combinatorial Auction
Code and Data. Instances
generated by CATS 2.0 for every distribution (including "legacy" distributions),
along with optimal revenue for the instance, runtimes for CPLEX 7.1/8.0 (depending on the dataset), CASS and
Gonen-Lehmann. Also included are feature values for the runtime prediction
models described in
Leyton-Brown, Nudelman & Shoham, 2008.
Warning: it appears that occasionally, CPLEX reported that it had run to optimality, but in fact computed a suboptimal value. As far as we know, the CASS and GL numbers are reliable.
Warning: each file represents CPU-years of data, and will take a long time to download!
- Fixed problem size:
- Archive: TAR.GZ 256 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Archive: TAR.GZ 144 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Archive: TAR.GZ 64 goods, 2000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
- Variable problem size:
- Archive: TAR.GZ 40-400 goods, 50-2000 non-dominated bids, 10 distributions, 800 instances per distribution. 2.4 Ghz Xeon, CPLEX 8.0.
- Archive: ZIP Objective function values, feature values and CPLEX, CASS and GL runtimes for all the instances listed above.
- Code for generating our features: TAR.GZ you only need this if you want to generate features for instances that aren't already in the above archives
- Matlab Pipeline used to generate empirical hardness models: ZIP
- Fixed problem size: