About

This is an implementation of the algorithms developed in the paper (BGKL) by Elizabeth Baldwin, Paul Goldberg, Paul Klemperer and Edwin Lock available at https://doi.org/10.1287/moor.2019.0248 and on the ArXiv. The algorithms solve the Strong-Substitutes Product-Mix Auction (originally developed by Paul Klemperer, see original paper) that uses the strong-substitutes product-mix bidding language with positive and negative bids; that is, the algorithms find a competitive (Walrasian) equilibrium.

Installation

The package uses modern Python packaging with automatic Cython compilation:

# Clone and install in development mode
git clone https://github.com/edwinlock/product-mix.git
cd product-mix
python3 -m venv venv

# Activate virtual environment (macOS/Linux: source venv/bin/activate | Windows: venv\Scripts\activate.bat)
source venv/bin/activate

# Install with automatic compilation
pip install -e .

# Install test dependencies
pip install -e ".[test]"

Note: No manual compilation steps are required. The setup.py automatically handles Cython compilation for the disjoint set data structure.

Detailed installation instructions can be found in INSTALL.md.

Requirements

• Python 3.8+ (tested with Python 3.13)
• NumPy 1.24+
• Cython 3.0+
• pytest 7.0+ (for running tests)

Testing

This implementation includes comprehensive unit tests covering all major components:

# Install test dependencies first (if not already installed)
pip install -e ".[test]"

# Run all tests
python -m pytest tests/ -v

# Run specific test modules
python -m pytest tests/test_productmix.py -v    # Main productmix module
python -m pytest tests/test_sfm.py -v          # Submodular function minimization  
python -m pytest tests/test_disjointset.py -v  # Disjoint set data structure

The test suite includes 89 comprehensive tests:

• test_productmix.py: 48 tests covering allocation problems, file I/O, demand functions, algorithms, validation, edge cases, and integration workflows
• test_sfm.py: 27 tests covering the Fujishige-Wolfe algorithm, memoization, and submodular functions
• test_disjointset.py: 14 tests covering the disjoint set data structure used in allocation

Performance Optimizations

This implementation includes several optimizations over the basic algorithms:

• Improved memoization: Uses frozenset for better performance with set-like inputs in SFM
• Optimized demand vector computation: Reduced memory allocations and direct boolean comparisons
• Efficient Cython implementation: Fast disjoint set operations with path compression

As described in BGKL, computing a competitive equilibrium can be separated into two parts:

1. Find the component-wise minimal market-clearing price using a steepest descent approach. Both long-step methods described in the paper are implemented.

2. Find an allocation of the supply (=target) bundle among the various bidders so that each bidder receives a bundle they demand at the market-clearing price. This is implemented according to algorithm described in the BGKL paper.

A note on the encoding of prices and bundles

For an auction with n goods, prices and bundles of goods are represented as (n+1)-dimensional vectors, where the i-th entry corresponds to the i-th good and the 0-th entry corresponds to a notional 'reject' good that is useful for technical reasons (see BGKL). In particular, every price vector has an 0-th entry of value 0. Moreover, an allocation of the target bundle among the bidders consists of a list containing a bundle vector for each bidder, and each vector's 0-th entry denotes how many notional 'reject' goods the bidder receives.

Example Usage

Initial

Activate the virtual environment and launch an interactive Python shell:

$ cd path_to/product-mix
$ source venv/bin/activate
$ python

Import the product-mix package

>>> import productmix as pm

Solving the Product-Mix auction

Load an allocation problem from a file

>>> alloc = pm.load_from_json('examples/example2.json')

Find a market-clearing price using unit step steepest descent

>>> prices = pm.min_up(alloc, long_step_routine="")

Find market-clearing prices using long step steepest descent

>>> prices = pm.min_up(alloc, long_step_routine="demandchange")

or

>>> prices = pm.min_up(alloc, long_step_routine="binarysearch")

Print and set market-clearing prices in allocation problem object

>>> print(prices)
[0. 2. 4.]
>>> alloc.prices = prices

Compute a valid allocation. This outputs a list of bundles.

Note that running the pm.allocate(alloc) method has the side effect that all bids in the allocation problem instance alloc are deleted!

>>> allocation = pm.allocate(alloc)
>>> print(allocation)
[array([3., 3., 0.]), array([2., 4., 1.])]

Hence the first bidder is allocated 3 items of good 1 and no items of good 2, while the second bidder is allocated 4 items of good 1 and one 1 item of good 2.

Miscellaneous methods

Reload the allocation problem from a file

>>> alloc = pm.load_from_json('examples/example2.json')

Check validity of bid lists

>>> pm.is_valid(alloc)
True

Define some price vector p and compute market-clearing vector prices

>>> import numpy as np
>>> p = np.array([0,1,1])
>>> prices = pm.min_up(alloc)  # Uses 'binary search' long step technique by default

Compute the Lyapunov function at price vectors p and prices

>>> pm.lyapunov(alloc, p)
49.0
>>> pm.lyapunov(alloc, prices)
39.0

Get a demanded bundle at p and prices (not necessarily unique!)

>>> pm.demanded_bundle(alloc, p)
array([0., 7., 6.])
>>> pm.demanded_bundle(alloc, prices)
array([5., 7., 1.])