Represents a price supplied by or presented to the user.

In dot-bids auctions, quantities are always integers (discrete rather than continuous) but may be negative.

Goods are numbered from 0 to N-1, where N is the dimension of the auction.

A bundle of goods (i.e. a quantity for each good).

A vector in price space (i.e. a price for each good).

The bundle containing no goods.

Test whether the first bundle is a sub-bundle of the second (i.e. it contains less of each good).

Find the price of a single good.

Increment the price of a single good.

Modify the i-th component of a vector.

generate n f generates a list-like data structure containing n items, such that item n equals f n.

Prepend a 0th element of value 0 to a vector. This is effectively an implementation of the ι function described in Algorithm 1, step 2.

Dual to extend: removes the first element from a vector.

Explicitly set the 0th element of a vector to 0. Several algorithms require this step

Get the dimension of a vector. Right now, it is just an alias for length.

Get the n-th element from a vector, 0-based. This used to be important when the codebase still had 1-based vectors with implicit 0th elements, but now that this distinction has been removed, this is just an alias for !.

The opt function frequently used in the validityAllocation paper: given vectors p and v, find the goods on which p - v is maximal, and return the maximal value and a vector representing the set of goods on which the difference is maximal.

Informally, this gets us the best price relative to the target price.

unitWhereLower a b gets a vector v such that v[n] = 1 if a[n] < b[n], else 0.

Find the powerset of a set, implemented using lists.

Find the powerset of a set.

Create a unit vector from a set of coordinates.

Find the powerset of the set of N goods, represented as a list of vectors such that for each good in the set, the corresponding vector's coordinate is set to 1, while for each good not in the set, the vector's coordinate is set to 0.

eX, from section 3 of "LP for dot-bids, and usage of the Ellipsoid Method", used in several of the algorithms described there.

For X ⊂ [N] write eX for the vector defined by (eX)i = 1 iff i ∈ X, (eX)i = 0 otherwise.

For efficiency reasons, instead of calculating individual eX for a given subset X of [N], and considering the use cases, we implement instead a function eXs, that enumerates *all* the possible eX for a given N.

A variation of eXs that does not include the zero vector.

Identifies a bid agent. A bid agent can be either a real Bidder, or the Auctioneer, who will buy all the unsold goods in the auction back at any price.

A dot-bid is represented by a number of units (which may be positive or negative) and a vector of prices for each good.

Calculate the maximum price bid on each good.

Sort a list of bids into a Map indexed by bid agent. We will be using this in algorithms that require us to only look at the set of bids from one specific bid agent.

replaceAgentBids agentID bidsToKeep bids removes all bids for agent agentID from the list of bids, and then inserts all the bids in bidsToKeep. The bids in bidsToKeep should all be from the bidder indicated by agentID, however this is not enforced.

Algorithm 2 from validityAllocation: Separate bids across goods at p, minimizing demand.

Algorithm 3 from validityAllocation: Separate bids across goods at p, maximizing demand.

Algorithm 4 from validityAllocation: Calculate a bundle demanded at p, minimizing demand (via Algorithm 2 / separateBidsAcrossGoodsMin)

Algorithm 4 from validityAllocation: Calculate a bundle demanded at p, maximizing demand (via Algorithm 2 / separateBidsAcrossGoodsMax)

Calculates an overestimation of bundles demanded at a given price point.

Not all bundles returned are guaranteed to be actually demanded at the price point, but any bundle that is actually demanded is guaranteed to be in the returned set.

The approximation is calculated based on marginality: - bids that are non-marginally accepted at the price point are always selected on the good that they are accepted on - for each bid that is marginal on any goods (including REJECT), bundles are explored that select the bid on each of the goods that it is marginal on - any other bid (neither non-marginally accepted nor marginal) is ignored

Add auctioneer bids to an auction, replacing any existing auctioneer bids. Needed for Algorithm 1.

Calculate auctioneer bids for a bundle. Needed for Algorithm 1.

Calculate the auctioneer bid for a given good and bundle. Needed for Algorithm 1.

Checks if the price vector has no marginal bids.

Get all bids marginal on a given good at a given price vector. See Algorithm 5 in validityAllocation.pdf.

Get all bids marginal on any good at the given price vector.

Check if a bid is marginal on a given good at a given price vector. See Algorithm 5 in validityAllocation.pdf.

Algorithm 10 from validityAllocation.pdf: Identify bids non-marginally accepted on each good (including REJECT)

Identify bids non-marginally accepted on a given good.

Check if a bid is non-marginally accepted on a given good.

Check if any bids are marginal on the given good.

List all unique bidders that are marginal on a given good at a given price point.

Calculate u and g, as shown in Lemma 3 in section 3.3 of "LP for dot-bits, and usage of the Ellipsoid Method".

For a given set of bids and a target bundle, minimising g gives the price vector at which the target bundle is demanded.

Returns the value of u in the first component, and the value of g in the second component.

Calculate u only.

Calculate g only.

Given a good j and a price vector prices, this computes the set V_j(prices) from Definition 5 in Section 3.3 from a list of dot bids.

A dot bid will end up in (at most) one of the V_j sets, where j indicates the good which is demanded by this bid. If multiple goods are equally close to the bid, then we put the bid in the set for the good with the lowest index.

Check that the given target bundle is a sub-bundle of the bundle demanded at the origin. If this is not the case, the search algorithms may return an invalid result or fail to terminate.

Find prices that cause the given bundle to be demanded.

This uses a brute-force search for the minimum of g across all prices.

Find prices that cause the given bundle to be demanded. The validTarget predicate should be satisfied to make sure this doesn't loop.

Find prices that cause the given bundle to be demanded.

This implementation uses the GreedyUpMinimal algorithm described in section 3 of "LP for dot-bids, and usage of the Ellipsoid Method", also described as Algorithm 8 in validityAllocation.

Flavor of findBundle_GreedyUpMinimal with tracing, in an arbitrary Monad.

Find prices that cause the given bundle to be demanded.

This implementation uses the TwoPhaseMinMin algorithm described in section 3 of "LP for dot-bids, and usage of the Ellipsoid Method". The same algorithm is also described in validityAllocation as Algorithm 9.

Flavor of findBundle_TwoPhaseMinMin with tracing, in an arbitrary Monad.

Flavor of findBundle_TwoPhaseMinMin with tracing, in an arbitrary Monad.

Base implementation of the TwoPhase algorithms, with tracing.

minimalMinimizer p xs finds the smallest x in xs for which p x is minimal.

minimalMinimizerBy f p xs finds x' in xs' such that xs' is the set of x for which p x is minimal, and f x' is minimal in xs'.

maximalMinimizer p xs finds the smallest x in xs for which p x is maximal.

maximalMinimizerBy f p xs finds x' in xs' such that xs' is the set of x for which p x is minimal, and f x' is maximal in xs'.

List all the prices contained in the hyperrectangle with given bottom-left and top-right corners.

Get the upper limit of bid prices per dimension, like upperPriceBounds, but for DotBids, not PriceVectors.

Get the upper limit of prices per dimension. E.g., for bids [ (1, 10), (5, 5), (9, 2) ], the upper limit is (9, 10).

Empty input returns Nothing.

Algorithm 11 from validityAllocation.pdf: Identify I and K as in Proposition 4.4. Needed for Algorithms 12 and 13 (optimized minimal/maximal minimizers)

Algorithm 12 from the validityAllocation.pdf document. This doesn't implement all of Algorithm 12, rather it just filters a given list of candidates according to the conditions outlined in the last section (such that...). Finding the actual minimal minimizer is already handled in the crawler algorithm itself, and other filters are applied there already, so we do not duplicate this here.

Algorithm 13 from the validityAllocation.pdf document. This doesn't implement all of Algorithm 13, rather it just filters a given list of candidates according to the conditions outlined in the last section (such that...). Finding the actual minimal minimizer is already handled in the crawler algorithm itself, and other filters are applied there already, so we do not duplicate this here.

λ p x from the validityAllocation.pdf paper, used in Algorithm 14.

ν p x from the validityAllocation.pdf paper, used in Algorithm 15.

Brute-force way of finding a minimal neighbour.

Find minimal neighbour via Fujishige-Wolfe algorithm.

This implements the previous version of the valid bids generation procedure as shown in section 3.1 in "Valid Combinations of Bids", where all bid weights are 1. For a generalized version as described in a newer version of the same paper, which produces randomly weighted bids, see generateValidBidsW.

This implements the valid bids generation procedure as shown in section 3.1 in "Valid Combinations of Bids". This flavor produces randomly weighted bids; set maxWeight to 1 to disable this behavior, or use generateValidBids instead.

A variation on the generateValidBidsW function that intentionally generates bids sets that "line up with each other in a horrible way".

An allocation problem is defined as:

1. An equilibrium price vector, found using one of the findBundle functions (named p in the paper).
2. Bids, including auctioneer bids (named V in the paper).
3. Bid weights (implemented as the _dotBidQuantity field of the DotBidOf data structure; named w in the paper).
4. Such that for each bidder (j ∈ J in the paper), the set of bids for that bidder is P-valid.
5. An endowment map, associating each bidder with a bundle allocated to that bidder (m in the paper).
6. A residual supply (r in the paper), initialized to the target bundle (t in the paper) but, over the course of resolving the problem, to be reduced to all-zero if possible.
7. Additionally, we track a set of active goods, that is, all the goods that haven't been resolved fully.

Allocation problems are polymorphic on a bidder ID type, b, and a price type, a. The latter is necessary because some parts of the algorithm require fractional prices (specifically, half-unit prices).

An allocation problem is considered vacuous if any of the following hold true:

1. there are no more bids to consider
2. there is no residual supply left to allocate
3. there are no more active goods in the active goods set

When an allocation problem is vacuous, we can assume that no further processing is desired.

The total number of units per good in a given allocation problem, i.e., the sum of all allocated goods plus the residual supply.

Create an initial allocation problem from a set of bids and a target bundle (initial supply).

Fully configurable preparation of an allocation problem.

Generate a valid allocation problem with multiple bidders.

Generate a "horrible" (but valid) allocation problem with multiple bidders.

Apply the Obvious Refinement defined in section 6.2 of the validityAllocation paper.

Loosely following Algorithm 16.

Flavor of allocateObvious with monadic trace logging.

Find a key list within a set of bids, starting at a given good that is assumed to be marginal for at least one bid at the given price vector p.

The given bids are assumed to all belong to the same bidder.

A key list is a set of at least two goods and exactly one bidder, such that the goods form the nodes of a maximally connected subgraph of the marginal bids graph for the given bids and price vector.

Unlike Algorithm 18 described in validityAllocation, we return only the goods that make up a key list, not the bidder, which is implicitly assumed to be the only bidder in the list of given bids.

Also unlike Algorithm 18, we return a singleton set if the given good is not part of a key list; consumers who wish to treat this case specially will have to perform the relevant checks themselves.

Determine whether a good is a link good at the specified price point, as per Definition 6.6 and Algorithm 17 in the validityAllocation paper.

A good is considered a link good iff the number of distinct bidders marginal on this good at the given price point exceeds 1, or, in terms of the Marginal Goods Graph, iff it has edges labelled by more than one bidder.

Allocate to key list goods, if possible, as described in Algorithm 19 in validityAllocation.

allocateByKeyList with tracing in an arbitrary Monad.

A jiggle, as per definition 7.2 in the validityAllocation paper.

Jiggle an individual bid.

A single (i*, j*) jiggle, as described in Algorithm 20 in validityAllocation.

jiggle with tracing in an arbitrary Monad.

The Projection Preserving Marginality as described in Algorithm 21 of the validityAllocation paper, applied to all bids in an allocation problem.

The Projection Preserving Marginality as described in Algorithm 21 of the validityAllocation paper, applied to a list of bids.

The Projection Preserving Marginality as described in Algorithm 21 of the validityAllocation paper, applied to a single bid.

The Projection Preserving Marginality as described in Algorithm 21 of the validityAllocation paper, applied to a price vector.

Algorithm 23 from the validityAllocation paper. Unravel all the unambiguous allocations in an allocation problem.

Flavor of unravelUnambiguous with monadic trace logging.

Algorithm 24 from the validityAllocation paper: priority-based procedure to solve an allocation problem.

Flavor of allocatePriorityBased with monadic trace logging.

An auction, as provided by the user. Before the algorithms can process this, preprocessing as defined in Algorithm 1 is required, which is provided by prepareAP

A raw bid, as provided by the user.

Run a full auction, using the priority-based algorithm (Algorithm 24 in validityAllocation).

Flavor of runAuction with monadic trace logging.

Convert a solved allocation problem to an auction result. This covers the following:

• Reverting reserve price normalization
• Removing auctioneer endowments
• Removing REJECT coordinates from all endowments, prices, and bundles
• Collecting all remaining supply as well as supply allocated to the auctioneer into a single rejected bundle
• Carrying over good labels from the original auction

Prepare an auction for processing, creating an allocation problem. This includes:

• Adding a 0th element to every price and bundle (the REJECT good)
• Applying reserve price normalization
• Adding an auctioneer bidder and auctioneer bids
• Finding an equilibrium price

Prepare a list of bids for processing.

Prepare a list of bids from one agent for processing.

Prepare one agent + bid pair for processing.

Generate a valid auction with multiple bidders.