Skip to main content

Computing prices in a generalisation of the Product-Mix Auction


Suitable for

MSc in Computer Science
Mathematics and Computer Science, Part C
Computer Science and Philosophy, Part C
Computer Science, Part C


The Product-Mix Auction was devised by Klemperer in 2008 for the purpose of providing liquidity to commercial banks during the financial crisis; it was used for a number of years by the Bank of England. See the following link:

It uses bids that represent the amounts a buyer is willing to pay for certain bundles of goods, and the "correct" prices (causing the available supply of goods to be released to the buyers) can be found by solving a linear program. The project investigates an extension to the original auction that allows buyers more flexibility to express their requirements. This extension, allowing "negative bids" to be made, allows a buyer to express any "strong substitutes" demand function. In this extension, the search for prices has the form of a sub modular minimisation problem, and the project envisages applying algorithms such as Fugishige-Wolfe to this challenge. We envisage applying algorithms to simulated data, and obtaining experimental results about their runtime complexity. We also envisage testing local-search heuristics.