Research Downloads

Show only:
 Empirical Algorithmics 
 Computational Game Theory 
 Combinatorial Auction Winner Determination 

 

Empirical Algorithmics

Computational Game Theory

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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. 
  • 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: HTMLLeyton-Brown & Tennenholtz, 2003.
    • Java JAR file: ZIPJAR  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. 
  • CASS (Combinatorial Auctions Structured Search).  An algorithm for solving the winner determination problem for single-unit combinatorial auctions. 
  • CAMUS (Combinatorial Auction Multi-Unit Search). An algorithm for solving the winner determination problem for multi-unit combinatorial auctions. 
  • 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 HTMLLeyton-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: ZIPTAR.GZ  256 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
      • Archive: ZIPTAR.GZ  144 goods, 1000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
      • Archive: ZIPTAR.GZ  64 goods, 2000 non-dominated bids, 10 distributions, 500 instances per distribution. 550 Mhz Xeon, CPLEX 7.1.
    • Variable problem size:
      • Archive: ZIPTAR.GZ  40-400 goods, 50-2000 non-dominated bids, 10 distributions, 800 instances per distribution. 2.4 Ghz Xeon, CPLEX 8.0.
    • Archive: ZIPZIP  Objective function values, feature values and CPLEX, CASS and GL runtimes for all the instances listed above.
    • Code for generating our features: ZIPTAR.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: ZIPZIP

Last updated October 1, 2021