Positive and negative dot-bids¶

A Product-Mix Auction with positive and negative dot-bids is a variant of the basic problem (see Introduction), where quantities are indivisible (i.e. a bid for 1 unit must receive exactly 1 unit, not 0.5 units) and bids may request negative quantities.

Format of the Problem¶

An auction consists of:

A set of goods; these can be anything, but the quantity auctioned, demanded, and sold on each of them will be integral (see above).
A set of bidders; each bidder is identified by a string label. Any label is valid, the only constraint is that no two bidders may have the same label.
A reserve price for each good. The algorithm will never sell any goods below the reserve price for that good; bids will not be considered for goods on which they fall below the reserve price.
A target bundle, which is a set of available supply per good. For many types of auctions, the auctioneer has exactly one unit of each good available, so that is the default.
For each bidder, a set of bids.

The combination of reserve price and target bundle is equivalent to a supply curve with exactly one step.

A bid consists of:

one desired integral quantity; and
the maximum price the bidder is willing to pay for each good.

This format allows a bid to express an alternative choice: a bidder can bid on a fixed quantity of any of a range of goods, specifying the minimum price they are willing to pay for each.

For example, let’s assume we’re auctioning off FM radio frequencies, and we have three of those on offer, let’s call them A, B, and C. Now a bidder can put in a bid that says “I want to buy one frequency, I am willing to pay up to 6000 for frequency A, up to 3000 for frequency B, or up to 2000 for frequency C”:

Bids example (`source`)¶
Bidder	Weight	A	B	C
AcmeCorp	1	6000	3000	2000

If a bidder is interested only in some of the goods, but not others, then this can be expressed by setting the prices on the uninteresting goods to some value below the reserve price. The algorithm will never sell below reserve price, so such bids will never be accepted on these goods.

It is also possible to use negative weights for bids. These bids are used to cancel positive bids, and enable us to depict any strong substitute preferences in our language. Negative bids can only be placed on price combinations for which the same bidder is guaranteed to accept sufficient goods from other, positively weighted, bids. (Note that a negative bid cannot be interpreted as a “bid to sell”: a negative bid is accepted on a good only if the price of that good is below the bid for that good, whereas a seller would wish to sell a good only if its price were above a certain level.)

In order for this to work, negative bids can only be placed on price combinations for which the same bidder is guaranteed to accept sufficient goods from other, positively weighted, bids. For example, the following combination would be valid:

Bids example (`source`)¶
Bidder	Weight	A	B
AcmeCorp	1	6000	3000
AcmeCorp	-1	5000	2000
AcmeCorp	1	5000	0
AcmeCorp	1	0	2000

The Working Of The Algorithm¶

The auction algorithm is a two-step process.

Step 1: Finding equilibrium prices¶

In order to find equilibrium prices, the algorithm performs a series of Submodular Function Minimisation steps.

Informally, this process finds the lowest possible prices for which the total demand is less than or equal to the target bundle on every good. In other words, we find the lowest possible prices at which there is no excess demand.

The algorithm is designed so that such prices will always exist: at the reserve price of each good, the seller has placed bids to “buy back” more than the entire supply of this good. So each price may drop to its reserve price, but if it drops lower, there will be excess demand.

Step 2: Allocating¶

The allocation algorithm is somewhat complex, but essentially, it consists of three steps that are applied iteratively until either all bids have been dealt with, or the entire supply has been sold.

The first step is the obvious step, in which all bids are dealt with that are unambiguous:

If a bid is higher than the equilibrium price by a larger amount on one good than on all the others (i.e., it is non-marginally accepted), then the algorithm allocates on that good.
If a bid is lower than the equilibrium price on all goods (non-marginally rejected), then the algorithm rejects it.

The second step is the unravel step, in which we look at groups of bids that are ambiguous (marginal), but such that there is no more than one good among them for which more than one bidder needs to be considered. For such a group, we can unambiguously figure out how much to allocate:

On the goods for which only one bidder has any marginal bids, we can allocate the entire remaining supply of that good on that bidder.
On the one good for which multiple bidders have marginal bids, we can calculate the maximum possible allocation based on what we’ve allocated on the other goods, and the remaining supply.

The third step is the jiggle step, in which we resolve ambiguous situations by picking a combination of bidder and good, and giving it a slight advantage by temporarily moving all the bids of this bidder up by half a unit on that good. We then find the new equilibrium prices as above. This may cause bids to either become non-marginal, or it will break ambiguous groups such that the unravel part can resolve them. So we perform the obvious and unravel steps again, and then move bids back to where they were before. This step, thus, acts as a tie breaker, and our choice of bidder and good determines who gets priority.

Using the CLI¶

The dot-bids auction functionality is available under the subcommand pma dot-bids. Available options are:

--bids-file CSV-FILE¶

Specify a CSV file containing the bids. The first column is the bidder name, the second column is the bid weight, subsequent columns are interpreted as bid prices per good.

The first row (CSV header row) should contain good labels in columns 3 and up, referring to the goods in that column. Columns 1 and 2 in the header row are ignored, but should, by convention, contain the labels “Bidder” and “Weight”.

Without this option, CSV data is read from standard input instead.

--supply QUANTITIES¶

Available supply: space-separated list of quantities, one per good, in double quotes. If not specified, defaults to one unit of every good.

The number of quantities in the list must match the number of goods in the auction, as determined by the number of columns in the bids file (see --bids-file), or --num-goods for the arbitrary-bids generator (see --arbitrary-bids).

--reserve-price PRICES¶

Reserve prices: space-separated list of prices, one per good, in double quotes. If not specified, defaults to a reserve price of zero for every good. The auction algorithm will never sell anything below this price.

The number of prices in the list must match the number of goods in the auction, as determined by the number of columns in the bids file (see --bids-file), or --num-goods for the arbitrary-bids generator (see --arbitrary-bids).

--supply-file CSV-FILE¶

Supply of goods available in the auction, and their reserve prices, represented as a CSV file with a header row and exactly one data row. This may be used instead of both the --supply and --reserve-price options. (This is to match the format of other auction types, where multiple rows are used to represent multiple supply curve steps.)

The number of goods in the file must match the number of goods in the auction, as determined by the number of columns in the bids file (see --bids-file), or --num-goods for the arbitrary-bids generator (see --arbitrary-bids).

--allocs-file CSV-FILE¶: Output the resulting allocations to the given CSV file. The output format consists of a column for the bidder name, followed by one column per good giving the allocated quantities. The last row lists unsold supplies under the bidder name “UNSOLD”.

--prices-file CSV-FILE¶: Output the resulting equilibrium prices to the given CSV file. The output format consists of a header column and one column per good: the two data rows give the price for the good and the total quantity sold.

--log [FILE]¶: Log the internal steps of the allocation algorithm to FILE, or to standard error if no file is specified.

--arbitrary-bids¶: Generate a random set of arbitrary bids. Normally, this is fed to the auction resolver directly and silently; in order to view the generated auction, use --dump-bids, and to bypass the auction resolver and just run the auction generator, use --no-run.

--num-goods N¶: Number of goods in an auction. This is mostly useful when using --arbitrary-bids (the n parameter), but can be specified as a sanity check in other cases. The default, 2 goods, is used only if the number of goods is not determined by any other inputs.

--max-weight WEIGHT¶: Maximum weight (bid quantity) to generate. The default, 1, generates only unit bids. (default: 1)

--complexity B¶: The b parameter. Higher values for b create more complex auctions. At b = n, bids are likely to collide a lot. (default: 3)

--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. Pass - to dump to standard output.

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