Introduction¶

The Product-Mix Auction is a single-round sealed-bid auction for multiple units of multiple distinct goods. This package contains the following:

an implementation of the core Product-Mix Auction algorithm and various extensions as a Haskell library;
a command-line program pma, which reads a complete specification of an auction from the command line and input files, runs the auction and outputs the results (see Running auctions via the command-line interface);
a web application pma-server, which provides a single-user interface allowing an auction specification to be constructed in a web browser form, sent to the server, solved and the results presented back in the web browser (see Running auctions via the web app).

The remainder of this section gives a high-level overview of the Product-Mix Auction algorithm and the key concepts involved. Subsequent sections explain how to make use of the programs to run auctions. For further background information, see The Product-Mix Auction: a New Auction Design for Differentiated Goods. For a more precise description of the linear programmes being solved, see the accompanying document Specification for Implementing the Product-Mix Auction Solver.

The core Product-Mix Auction algorithm takes as input a supply specification and a set of bids (possibly from multiple bidders). It converts these into a linear programme, and solves it to produce a price for each distinct good and an allocation of goods to bids. (Multiple runs of linear programmes may be necessary for some features.) The number of (distinct) goods is fixed throughout.

Supply¶

The supply specification describes the quantities available of each (distinct) good, and the sequence of reserve prices that the auction price must exceed for the corresponding quantity to be available. Typically the supply specification will be chosen by the auctioneer in advance of the auction. It consists of a supply curve for each good, and a supply ordering across the goods.

A supply curve is a generalisation of the concept of a reserve price for a good: it gives multiple reserve prices depending on the number of units allocated. The price of the good will be at least the reserve price given by the supply curve for the quantity of the good that has been allocated. Supply curves are given as step functions, specifying the width of each step (number of units available) and the price at which they are available. The simplest case is a supply curve with a single step, which corresponds to there being a fixed number of units available for the good at a single reserve price.

A supply ordering gives the relationship between different goods:

Vertical supply ordering means that each good is more valuable than its predecessor. Prices in the supply curve are given relative to the predecessor’s price (or to zero, for the first good). Quantities in the supply curve represent the total amount available for the good and any successive goods. Thus the supply curve for the first good gives the total quantity available of all goods. For example, with two goods, the supply curve for good 1 has absolute prices for good 1 based on the total quantity of both goods, while the supply curve for good 2 has prices relative to good 1 for the quantity of good 2.
Horizontal supply ordering means that goods are independent. All prices are given relative to zero. Quantities in the supply curve represent the amount available for that good alone. For example, with two goods, the supply curve for good j has absolute prices for the quantity of good j.
More general tabular orderings are possible, with goods organised into multiple columns (having related prices and quantities as with a vertical ordering), but horizontal relationships between the columns. A tabular ordering may also have a special good below all the columns, whose supply curve gives the total quantity available of all goods.

A base good for a supply ordering is one whose supply curve prices are given relative to zero, and whose quantities include the amounts allocated to successive goods. Thus a vertical ordering has the first good as its sole base good, while for a horizontal ordering, all goods are base goods.

The auction size is the total width of all supply curves for base goods. Thus a vertical ordering has auction size equal to the total width of the first good’s supply curve, while a horizontal ordering has auction size equal to the total of the widths for all the supply curves.

See Input format for supply and Supply specification in the web app.

Bids¶

A bidder is represented to the program as a list of their bids. The bidder who made a bid is not relevant to the basic functioning of the algorithm, but makes a difference to the presentation of the output and to Additional constraints.

In the simplest case, a bid consists of a single quantity, and a non-negative per-unit price offered for each good. A bid is said to be paired if it offers a non-zero price for two or more goods, or single if it offers a non-zero price for only one good.

If the auction prices are strictly above the bid prices for all goods, the bid is unsuccessful. Otherwise, the bid receives an allocation of its preferred good(s) (i.e. the good(s) for which the bid price minus the auction price is maximised), up to the quantity requested. If there are multiple preferred goods, the bid may receive any combination of them. If the bid price exactly equals the auction price for the preferred good(s), the bid is rationed and may receive fewer units than it requested.

For example, suppose the auction determines prices of 5 for good A and 6 for good B. A bid for 10 units of (good A at price 5) or (good B at price 8) will receive 10 units of B. A bid for 1 unit of good A at price 5 (only), may receive no units, a whole unit, or some intermediate fraction. A bid for 1 unit of (good A at price 3) or (good B at price 5) will receive no units.

An asymmetric bid allows bidders to express more general trade-offs than 1-1 between goods. For example, an asymmetric bid might demand (12/2 units of good A at price 5) or (12/3 units of good B at price 8). If this bid wins, depending on the auction prices, it might receive 6 units of good A, 4 units of good B, or some linear combination in those proportions (i.e. any x units of A and y units of B such that 2x + 3y = 12).

A generalised bid includes a maximum quantity for each good, as well as the overall quantity. For example, a generalised bid might demand 10 units of (up to 7 units of good A at price 80) or (up to 8 units of good B at price 50). If the auction prices were zero, this bid would receive all 7 units of good A (because it prefers A to B as expressed by the higher bid price) and the remaining 3 units of B (to exhaust the overall quantity).

If enabled in the auction configuration, bids may optionally be both asymmetric and generalised.

See Input format for bids and Bids in the web app.

Total Quantity Supply Schedule¶

A Total Quantity Supply Schedule (TQSS) is a function from prices to the total number of units (of all goods) that should be made available at those prices. This allows the auctioneer flexibility in deciding how many units to make available depending on demand. Typically the TQSS function is specified as a list of steps, where the width represents the quantity and the height represents the price. “Solving” the TQSS means finding the intersection between the supply function specified by the user and the demand function calculated from the bids.

Prices used in the TQSS may be normalised (i.e. expressed relative to the applicable supply curve step) or absolute. This affects the algorithm used for solving the TQSS, and the options that are available for use with it, as described in the following subsections. See also Input format for TQSS and TQSS in the web app.

TQSS with absolute prices¶

With absolute prices, a measure on prices must be specified by the auctioneer, converting the prices of all the goods into a single price for use in the TQSS. Typically this will be the mean price of all the goods, or the price of a single nominated good. To solve the TQSS, the software will solve the basic linear programme repeatedly, adjusting the total quantity available each time and calculating the resulting price measure, to produce a demand curve. The (approximate) point where the TQSS function intersects the demand curve will give the total quantity and price measure, and the auction prices and allocations will be presented for this total quantity.

There are two possible approaches to limiting the total quantity available:

Option “Scale supply”: Scaling the supply curves so that the auction size is changed to the desired limit. (This increases the quantities sold to more than the quantities offered by the originally-specified supply curves, if demand is sufficiently high.)

A parameter λ between 0 and 1 must be specified. Supply curve quantities for base goods are scaled in proportion to the new total auction size. Quantities for non-base goods (i.e. goods 2 and up for a vertical auction) are scaled similarly if λ = 0, not scaled at all if λ = 1, or partially scaled for intermediate values of λ. The cumulative totals of the supply curve step widths are rounded upwards; this may introduce rounding errors. The original auction size will be the minimum bound of the search (unless explicitly overridden by the user), so supply curves will typically be scaled upwards, not downwards. The given TQSS function must have a first step of height zero and width equal to the auction size.
Option “Constrain supply”: Adding a constraint to the linear programme requiring that the total quantity actually supplied to all goods does not exceed the limit. (This decreases the quantities sold to less than the quantities offered by the originally-specified supply curves, if demand is sufficiently low.)

The original supply curves are not changed, so the maximum possible quantity available will be limited by the original auction size. The parameter λ is not relevant.

When scaling the supply curves with a non-zero value for the parameter λ, the supply ordering must be vertical. Otherwise, any supply ordering may be used for a TQSS with absolute prices.

TQSS with normalised prices¶

With normalised prices, the TQSS is solved using a single run of a modified linear programme (encoding the structure of the TQSS in the constraints). The supply ordering must be horizontal, and the TQSS constrains the total supply available (the original supply curves are not scaled).

Additional constraints¶

The auctioneer may specify additional constraints on the quantities received by bids. These are directly implemented as constraints in the linear programme.

The form of additional constraint that is currently supported is a maximum quantity that may be allocated (across all goods) to any one bidder. This may be an absolute maximum, or expressed as a fraction of the auction size.

See Additional constraint options for how to specify additional constraints in the command-line interface. It is not currently possible to specify additional constraints in the web interface.

Rationing and rounding¶

Rationing is the process of adjusting the results of the basic Product-Mix Auction to “fairly” share between bidders. Multiple rationing schemes are supported by the software.

The standard approach to rationing is to run the basic auction twice. The first run makes it possible to identify multiply-marginal paired bids (those that are indifferent between receiving multiple goods). On the second run, such bids are “smeared out” by replacing the bid with a collection of bids approximating a linear demand decreasing from the bid quantity to zero as the price increases. This means that the auction will allocate rationed goods (approximately) fairly to multiply-marginal bids. Subsequently, goods are fairly shared between singly-marginal bids (those that are indifferent between receiving or not receiving a single good). This approach may slightly favour paired bids, in the sense that a paired bid at the auction prices may receive an allocation in preference to a single bid at the auction prices.

Optionally, this “smearing out” process can be applied to all marginal bids, not only those that are multiply-marginal. This does not favour paired bids, but it may require more computational time.

Alternatively, rationing can be disabled, in which case rationed goods will be allocated arbitrarily to marginal bids, and identical bids may not receive identical allocations. Of course, the constraints of the auction will be satisfied, so non-marginal bids will always receive the correct allocation. In addition, we have the facility to randomly reorder bids before constructing the linear programme, thereby ensuring a kind of equity even without rationing (as favoured bids will be determined by chance rather than by the structure of the LP or implementation details of the LP solver).

Regardless of the rationing scheme in use, allocated quantities are calculated and reported to a limited number of decimal places, controlled by the user. Increasing the number of decimal places yields more precise results but may require more computational time. Since floating-point arithmetic is used internally, very large numbers of decimal places may lead to inaccurate results. In any case, as a result of rounding there may be a small over- or-under-allocation in the total quantity allocated by the auction (e.g. if the exact solution results in allocations of 0.25 and 0.75 with a total of 1 unit, rounding to 1 decimal place yields 0.3 and 0.8 with a total of 1.1 units).

See Rationing and rounding options for how to control rationing in the command-line interface, and Rationing in the web app for the controls provided by the web app.

Maximisation strategies¶

The basic Product-Mix Auction supports a choice of objectives: maximising efficiency (the combination of the bidders’ surplus and the seller’s profit) or maximising profitability (for the seller alone).

Maximising efficiency determines auction prices and allocations that give the most efficient outcome for the auctioneer and all bidders, following the standard approach described in Specification for Implementing the Product-Mix Auction Solver. All the options described above are supported.

Maximising profitability determines auction prices and allocations that respect the bidder’s constraints and maximise the auctioneer’s profit. This uses an experimental brute-force algorithm based on that used for budget-constrained bids (see Budget constraints). In this case, the supply ordering must be horizontal, bids must be simple (not generalised or asymmetric), a TQSS or additional constraints may not be used, and rationing will not be performed. The prices and allocations that maximise profitability may not be unique, and in this case an arbitrary solution will be reported.