Budget constraints

A Product-Mix Auction with budget constraints is a variant of the basic problem (see Introduction), where instead of bids specifying a quantity of goods they wish to receive, each bid specifies a budget available to spend. As usual, the auction calculates prices for each good and each bid receives the goods it prefers at those prices.

For example, a bidder might ask to spend 10 on either (good A at price 5) or (good B at price 2). If the auction determines prices of 2 for good A and 2 for good B, the bid will receive 5 units of good A (exhausting its budget). If the auction determines prices of 5 for good A and 2 for good B, the bid may receive any combination of units of A and B that costs no more than 10 in total.

The following sections outline the algorithm. For a more detailed specification, see the accompanying document Specification for Implementing the Budget-Constrained Product-Mix Auction Solver.

The algorithm

The algorithm takes as input:

• a cost curve (step function) for each good available in the auction, giving the auctioneer’s costs as a function of the number of units sold;
• a list of budget-constrained bids, which consist of a label, a budget (maximal amount that can be spent) and a vector of prices that the bidder offers for each good.

The goal of the algorithm is to find the (per-good) unit price vector that maximises the auctioneer’s profit. The outputs of the algorithm are the price at which the auctioneer should sell each good, the total quantity of each type of goods sold, the profit made by the auctioneer and an assignment of quantities of goods to each bid.

Interpreting bids’ demand

Given some candidate price vector (the auction prices) for the goods, the rules for deciding whether a bid wins, and the quantity of goods it may receive, are determined based on the ratios of the bid price to auction price for the different goods, as follows:

• A bid is a winning bid for a good if it offers a price greater than or equal to the candidate unit price for that good (equivalently, if the bid_price / auction_price ratio is at least 1).
• A winning bid is non-marginal if there is a unique highest bid_price / auction_price ratio that is strictly greater than 1 and is achieved by a single good. Such a bid will necessarily get all of its budget worth of that single good.
• A winning bid is marginal in a set of goods if the highest bid_price / auction_price ratio is strictly greater than 1, and is achieved by more than one good. Such a bid may receive any linear combination of the goods in which it is marginal, but the combined value of the goods will necessarily equal the bid’s budget.
• A winning bid is marginal in its budget and a set of goods if there is at least one good (but possibly more) for which the bid_price / auction_price ratio is 1, and that it is the highest ratio for the given bid and candidate unit prices. Such a bid may receive any linear combination of the goods in which it is marginal, with a combined value anywhere between 0 and the bid’s budget.
• If a bid is not a winning bid for a good, it receives no units of that good.

Note that a bid’s demand is not well defined if the price for any good is zero. Thus we reject any candidate price vector containing a zero price. Correspondingly, we require that for each good, the set of bids contains at least one bid with a non-zero price for that good.

Search for optimal prices

Since unit prices and quantities are arbitrarily divisible, we cannot just enumerate their possible values. Instead, we calculate a set of candidate price vectors (vertices of the unique demand regions generated by the bids) amongst which the optimal prices must lie. We then search for the most profitable bid-to-quantity assignment for each candidate price vector in this set, and return the prices that yield the greatest profit.

Two strategies are supported for choosing the set of candidate price vectors to search:

• Finding every intersection of the demand hyperplanes generated by the bids, which is potentially slow due to the large number of intersections (especially in auctions with more than a few goods), but should ensure the optimal value is found.
• A more refined algorithm for identifying a smaller set of candidate price vectors, which is likely to be faster but has not been proved correct.

For a single candidate price vector, we cannot consider all possible assignments of quantities to bids that satisfy the bids’ demands, because marginal bids may receive arbitrary combinations of goods on which they are marginal. However, the structure of the cost curves means that it is enough to consider a finite set of possible assignments, amongst which the maximum profit must lie:

• Non-marginal winning bids always get their budget worth of a single good. If there is not enough supply to meet their demands, we can immediately reject the candidate price vector (knowing that there will be higher candidate prices at which there are fewer non-marginal winning bids).
• For marginal bids, we keep track of the current quantity sold of each good, and try all possible orders of assigning quantities of goods to bids.
• Bids that are marginal in the budget and some goods force us to explore several options for assigning some quantity of a good (on which the bid is marginal):
  • no units of the good;
  • enough units of the good to exhaust the remainder of the budget;
  • any positive quantity (whose value is less than the remaining budget) that, when added to the current quantity sold for that good, adds up to the quantity at the upper endpoint of a line of the cost curve for the good.
• Bids that are marginal in some goods (but not marginal in the budget) are similar, but once we have finished assigning goods to a bid, we make sure the assignments for that bid end up being worth the entire budget of that bid.

By exploring all the possible combinations of decisions that come out of this process, and only keeping the decisions that abide by the rules, we get all the candidate quantities and allocations. All that’s left to do at this point is to look at the allocation that maximises the objective function (computing the auctioneer’s profit). This gives us the best allocations for a given price vector. We have several candidate price vectors, so we just repeat this process for each price vector and keep the one that maximises the auctioneer’s profit.

We return an arbitrary allocation of goods to bids that results in the maximum profit. There may well be multiple possible allocations that result in the same profit, and in this case we do not attempt any kind of fairness between bids.

Budget constraints in the command-line interface

The budget constrained bids functionality is available in the command-line interface under pma bc (see Running auctions via the command-line interface). To run a budget-constrained auction, the following options must be specified:

--supply-file CSV-FILE

Specify the file containing the cost curve information.

--bids-file CSV-FILE

Specify a file containing bids.

The following output file locations may optionally be specified, otherwise they will be written to standard output by default:

--prices-file CSV-FILE

For each good, the price determined by the auction and the total quantity allocated.

--allocs-file CSV-FILE

For each bidder, the quantities of each good it is allocated.

--results-file TXT-FILE

A text file containing the auctioneer’s profit.

The set of candidate price vectors to search can be chosen using the --all-prices or --filter-prices option. By default, --all-prices will be used.

--all-prices

Explore all hyperplane intersections when determining candidate auction prices.

--filter-prices

Use the smarter heuristic for decreasing the number of candidate auction prices - NOT proved correct.

The cost curve data is specified using the --supply-file option to specify a CSV file in the same format as for the standard Product-Mix Auction, described in Input format for supply. The supply ordering is always horizontal. For example, here are cost curves for 3 goods, each with 2 steps, with a price of 1 for the first 10 units and a price of 2 for the next 30 units:

--supply-file example (source)

Quantity of good 1	Price for good 1	Quantity of good 2	Price for good 2	Quantity of good 3	Price for good 3
10	1	10	1	10	1
30	2	30	2	30	2

The --bids-file option is used to specify the bid data in a CSV file with columns for the bid label and total budget, then one column per good giving the bid price. This is rather like the standard format described in Input format for bids, except that the second column is a budget rather than a maximum quantity.

--bids-file example (source)

Bid	Budget	Price for good 1	Price for good 2	Price for good 3
A	20	2	3	5
B	31.2	2.2	2.8	4

The --prices-file, --allocs-file and --results-file options are used to output results to the named files. If not specified, results will be written to standard output (printed out to the console).

For example, running pma bc with the above cost curves and bids produces the following output files:

--prices-file example (source)

	Good 1	Good 2	Good 3
Auction price	2.2	2.8	4.0
Allocation	0.0	4.0	10.0

--allocs-file example (source)

Bid	Quantity of good 1	Quantity of good 2	Quantity of good 3
A	0.0	0.0	5.0
B	0.0	4.0	5.0

In the command-line application, input quantities and prices may be specified as decimals (internally they are represented as double-precision floating-point numbers). Output prices will not be rounded, but should not be assumed to be arbitrarily precise. Output quantities will be rounded based on the --scale-factor option.

--scale-factor INT

Specifies the precision with which quantity results should be reported, as a number of decimal places. The default is 1 decimal place.

As in LP auctions, the --arbitrary-bids and --arbitrary-supply options can be used to generate random data instead of providing input files (see Generating test data for further discussion).

--arbitrary-supply

Generate an arbitrary supply function

--arbitrary-bids

Generate an arbitrary list of bids

--num-goods INT

Number of goods for random data generation

--arbitrary-supply-min-units INT

Minimum amount of units used to draw random supply steps

--arbitrary-supply-max-units INT

Maximum amount of units used to draw random supply steps

--arbitrary-supply-min-price INT

Minimum price used to draw random supply steps

--arbitrary-supply-max-price INT

Maximum price used to draw random supply steps

--arbitrary-supply-min-steps INT

Minimum number of steps used to draw a random supply

--arbitrary-supply-max-steps INT

Maximum number of steps used to draw a random supply

--arbitrary-min-price INT

Minimum price used to draw random bids

--arbitrary-max-price INT

Maximum price used to draw random bids

--arbitrary-bid-min-budget INT

Minimum budget used to draw random bids

--arbitrary-bid-max-budget INT

Maximum budget used to draw random bids

--num-bids INT

Number of bids to generate

--num-j-paired-bids J INT

Number of j-paired bids to generate

--dump-bids CSV-FILE [OUTPUT]

Dump input bids to a CSV file (useful with --arbitrary-bids). Pass - to dump to standard output.

--dump-supply CSV-FILE [OUTPUT]

Dump input supply to a CSV file (useful with --arbitrary-supply). Pass - to dump to standard output.

--no-run

Do not actually run an auction, only read / generate inputs. Useful in combination with --arbitrary-bids, --arbitrary-supply, --dump-bids and/or --dump-supply.

Budget constraints in the web application

The web application (see Running auctions via the web app) supports a “Budget constrained” input mode. This provides a graphical interface for specifying cost curves and budget-constrained bids. Running a budget-constrained auction will report the auctioneer’s profit (the optimal value of the objective function) and display prices and allocations of goods to bids that yield the optimal value.

The web application requires prices to be entered as integers, and rounds output prices to the nearest integer (except the auctioneer’s profit, which may be displayed more precisely). Calculated allocations are always rounded to at most 1 decimal place.

It is not currently possible to choose the set of candidate price vectors to search using the web application. The --filter-prices option, which uses a smaller set of candidates, is always used.

3D graph of budget constraints

For help visualising budget constraints in three dimensions, an interactive 3D plot of budget constraints is available. This renders the planes separating the unique demand regions arising from bids.

The parameters of the graph can be changed by opening the page in a web browser, then extending the URL query string with key-value pairs, for example replacing budget-constraints-3d.html with budget-constraints-3d.html?x=10&y=20&z=30. The following parameters can be changed:

• mx, my, mz: dimensions of the graph (maximum x, maximum y, maximum z);
• x, y, z: coordinates of the first bid;
• x1, y1, z1 .. x9, y9, z9: optional coordinates of additional bid points;
• opacity: controls the transparency of the planes: a value between 0 and 1, where 0 is transparent and 1 is opaque;
• budget: the value no renders unique demand regions for bids in the standard Product-Mix Auction, rather than budget-constrained bids.

Coordinates of bids can be set to a number between 0 and the corresponding maximum value, or to the special value r, which will cause the coordinate to be chosen at random.

Here is an example with 10 points aligned and here is an example with 10 random points.

Note that in some web browsers, it may be necessary to access the page from a http[s]: URL (i.e. a web server) rather than a file: URL (i.e. a file stored on the local disk).