| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
ProductMixAuction.BudgetConstraints
Description
Product-Mix Auctions with budget constraints
- data BCAuction b = BCAuction {}
- bca_supply :: forall b. Lens' (BCAuction b) SupplyCurveVector
- bca_kind :: forall b. Lens' (BCAuction b) AuctionKind
- bca_filter_prices :: forall b. Lens' (BCAuction b) FilterPrices
- bca_bids :: forall b b. Lens (BCAuction b) (BCAuction b) [Bid b] [Bid b]
- data BCAuctionResult b = BCAuctionResult {}
- bcar_quantities :: forall b. Lens' (BCAuctionResult b) QuantityVector
- bcar_profit :: forall b. Lens' (BCAuctionResult b) Price
- bcar_prices :: forall b. Lens' (BCAuctionResult b) PriceVector
- bcar_allocations :: forall b b. Lens (BCAuctionResult b) (BCAuctionResult b) (BidAssignments b) (BidAssignments b)
- mapBCAuctionResult :: Ord b' => (b -> b') -> BCAuctionResult b -> BCAuctionResult b'
- objectiveFun :: SupplyCurveVector -> PriceVector -> QuantityVector -> Price
- data WinningBid
- data MarginalBid
- = MarginalGoods [Good] Budget
- | MarginalBudget [Good] Budget
- marginality :: AuctionKind -> PriceVector -> Bid b -> Maybe WinningBid
- computeWinningBids :: AuctionKind -> PriceVector -> [Bid b] -> [(Bid b, WinningBid)]
- initialQuantities :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [(Bid b, WinningBid)] -> Maybe (QuantityVector, BidAssignments b, [([Bid b], MarginalBid)])
- mergeMarginalBids :: [(Bid b, MarginalBid)] -> [([Bid b], MarginalBid)]
- ppAssignments :: Show b => BidAssignments b -> String
- type QuantityTree b = Tree (QuantityVector, BidAssignments b)
- treeLeaves :: Int -> Tree a -> Maybe [a]
- treeLeaves' :: Int -> Tree a -> [a]
- costFor :: Units -> SupplyCurve Units -> Price
- nextStepsDiffs :: AuctionKind -> [Step Units] -> Budget -> Price -> Units -> [Maybe Units]
- maxQuantity :: [Step Units] -> Units
- nextEndpoints :: AuctionKind -> Budget -> PriceVector -> Good -> QuantityVector -> SupplyCurveVector -> [Maybe Units]
- allOf :: AuctionKind -> Budget -> Good -> PriceVector -> QuantityVector -> SupplyCurveVector -> Maybe Units
- budgetToQuantity :: AuctionKind -> Budget -> Price -> Units
- quantityToBudget :: AuctionKind -> Units -> Price -> Budget
- processBids :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [([Bid b], MarginalBid)] -> (QuantityVector, BidAssignments b) -> [QuantityTree b]
- distribute :: AuctionKind -> PriceVector -> QuantityVector -> [Good] -> [Bid b] -> [(b, QuantityVector)]
- processBid :: AuctionKind -> SupplyCurveVector -> PriceVector -> QuantityVector -> ([Good], Budget, Bool) -> [(Good, Units)] -> [QuantityVector]
- updateQuantities :: QuantityVector -> [(Good, Units)] -> QuantityVector
- bidData :: MarginalBid -> ([Good], Budget, Bool)
- bestQuantities :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [Bid b] -> Maybe (QuantityVector, BidAssignments b, Price)
- bestPricesAndQuantities :: Ord b => AuctionKind -> ([Bid b] -> Set PriceVector) -> SupplyCurveVector -> [Bid b] -> Maybe (BCAuctionResult b)
- ppCandidate :: Show b => BCAuctionResult b -> String
- findCandidateRates :: Eq b => AuctionKind -> FilterPrices -> [Bid b] -> Set PriceVector
- runBCAuction :: Ord b => BCAuction b -> Maybe (BCAuctionResult b)
Documentation
Constructors
| BCAuction | |
Fields
| |
bca_supply :: forall b. Lens' (BCAuction b) SupplyCurveVector Source #
bca_kind :: forall b. Lens' (BCAuction b) AuctionKind Source #
bca_filter_prices :: forall b. Lens' (BCAuction b) FilterPrices Source #
data BCAuctionResult b Source #
Constructors
| BCAuctionResult | |
Fields | |
Instances
| Eq b => Eq (BCAuctionResult b) Source # | |
| Show b => Show (BCAuctionResult b) Source # | |
bcar_quantities :: forall b. Lens' (BCAuctionResult b) QuantityVector Source #
bcar_profit :: forall b. Lens' (BCAuctionResult b) Price Source #
bcar_prices :: forall b. Lens' (BCAuctionResult b) PriceVector Source #
bcar_allocations :: forall b b. Lens (BCAuctionResult b) (BCAuctionResult b) (BidAssignments b) (BidAssignments b) Source #
mapBCAuctionResult :: Ord b' => (b -> b') -> BCAuctionResult b -> BCAuctionResult b' Source #
Exploring quantity space
objectiveFun :: SupplyCurveVector -> PriceVector -> QuantityVector -> Price Source #
The simple objective function from the document: sum over i of q_i * p_i - c_i(q_i)
where: - i ranges over goods - q_i is the quantity of good i sold by the auctioneer - p_i is the auction price for good i - c_i is the cost of providing q_i units of good i
data WinningBid Source #
Constructors
| NonMarginal Good Budget | the bid should get the given budget worth of the given good, no flexibility whatsoever. happens when a bid has a unique highest (bid_price / auction price) ratio among the goods that's strictly greater than 1. |
| Marginal MarginalBid | a bid that leaves a choice in the budget and/or goods it should get |
Instances
data MarginalBid Source #
This type describes what kind of choice we have when assigning quantities of goods to each bid, for those bids that by the rules of a budget-constrained PMA, leave us a choice, whether in terms of budget, goods or both.
- The
MarginalGoodsconstructor indicates that the bid has offered strictly more than the auction price for at least two goods. This type of bid will gets its budget worth of goods, but it can get any linear combination of the goods in which it is "marginal". - The
MarginalBudgetconstructor indicates that the bid has offered exactly the auction price for one or more goods and will therefore get any linear combination of those goods that's worth between 0 and the bid's budget.
Constructors
| MarginalGoods [Good] Budget | the bid should get any linear combination of the given goods that's worth the given budget (it must use the entire budget). happens when there is a highest bid_price / auction_price ratio that's strictly greater than 1, but realised by several goods. the list of goods is therefore guaranteed to contain at least two goods, because otherwise the bid would not be marginal and would just spend all its budget on the unique good that realises the highest ratio. |
| MarginalBudget [Good] Budget | the bid should get anywhere between 0 and the given budget worth of any linear combination of given goods. happens when the bid_price equals the auction_price on the given goods (possibly a single one). |
Instances
marginality :: AuctionKind -> PriceVector -> Bid b -> Maybe WinningBid Source #
computeWinningBids :: AuctionKind -> PriceVector -> [Bid b] -> [(Bid b, WinningBid)] Source #
Given auction prices and bids, get all the winning bids
along with their Marginality.
initialQuantities :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [(Bid b, WinningBid)] -> Maybe (QuantityVector, BidAssignments b, [([Bid b], MarginalBid)]) Source #
Given auction prices and winning bids, compute:
- the quantities that necessarily have to be sold because they are
demanded by
NonMarginalbids; - all the bids that _are_ marginal (offer a choice), that will power some quantity space search algorithm.
mergeMarginalBids :: [(Bid b, MarginalBid)] -> [([Bid b], MarginalBid)] Source #
Given a list of bids with their marginality, group together bids that are marginal in the same way, calculating the total budget across them all.
ppAssignments :: Show b => BidAssignments b -> String Source #
type QuantityTree b = Tree (QuantityVector, BidAssignments b) Source #
A tree of quantities that can be sold by fulfilling bid demands in different ways
treeLeaves :: Int -> Tree a -> Maybe [a] Source #
Get all the leaves at the given depth in the tree.
Returns Nothing if there are none.
treeLeaves' :: Int -> Tree a -> [a] Source #
Get all the leaves at the given depth in the tree.
nextStepsDiffs :: AuctionKind -> [Step Units] -> Budget -> Price -> Units -> [Maybe Units] Source #
Find the upper ends of the supply curve lines greater than the given quantity that are within the given budget, for the given price for that good.
maxQuantity :: [Step Units] -> Units Source #
what's the maximum quantity that the given supply curve can provide?
nextEndpoints :: AuctionKind -> Budget -> PriceVector -> Good -> QuantityVector -> SupplyCurveVector -> [Maybe Units] Source #
what are the next thresholds on the supply curve for the given good?
allOf :: AuctionKind -> Budget -> Good -> PriceVector -> QuantityVector -> SupplyCurveVector -> Maybe Units Source #
Returns the given budget's worth of the given good, at
the price given by the price vector, _if there's enough
left_. Returns Nothing otherwise.
Note: the case where everything is not sold yet but there isn't
enough to satisfy the entire given budget is already handled
by nextEndpoints. Indeed, in such a case we would assign the remaining
quantity of the good to the bid and this would necessarily make us land on
the very last "endpoint" of the supply curve, which would in this case be
last Units value returned by nextEndpoints.
budgetToQuantity :: AuctionKind -> Budget -> Price -> Units Source #
quantityToBudget :: AuctionKind -> Units -> Price -> Budget Source #
processBids :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [([Bid b], MarginalBid)] -> (QuantityVector, BidAssignments b) -> [QuantityTree b] Source #
Given supply curves for the goods, a given (auction) price vector and some pre-determined quantities to be sold already for all goods, look at all the potentially optimal ways to satisfy the winning bids in terms of quantities of goods.
distribute :: AuctionKind -> PriceVector -> QuantityVector -> [Good] -> [Bid b] -> [(b, QuantityVector)] Source #
Given a list of bids that are all marginal in the same way on the given list of goods, and a quantity vector to share between them, calculate the quantity assignments to individual bids. This doesn't attempt to be fair between bids. Since the bids are all marginal in the same way, they must have bid the same prices for the goods on which they are marginal.
If the bids are marginal in the goods (but not budget), the quantity vector must be sufficient to satisfy all their demands.
Arguments
| :: AuctionKind | |
| -> SupplyCurveVector | supply curves for our goods |
| -> PriceVector | candidate (auction) prices for our goods |
| -> QuantityVector | quantities of goods sold so far in this branch of the quantity space |
| -> ([Good], Budget, Bool) | (goods wanted by the bid, total budget, spend entire budget) |
| -> [(Good, Units)] | accumulator that stores the quantities of goods assigned to the bid so far |
| -> [QuantityVector] | all the possible quantities that we could sell by satisfying this bid's demands in different ways |
Given supply curves for the goods, an (auction) price vector and the quantities of goods sold so far, find all the potentially optimal (for the seller) ways to satisfy the given marginal bid's demands.
updateQuantities :: QuantityVector -> [(Good, Units)] -> QuantityVector Source #
bidData :: MarginalBid -> ([Good], Budget, Bool) Source #
Summarize the marginality of a good as a list of goods, a total/maximal budget and a boolean that indicates whether the entire budget must be spent or whether it should just be considered as an upper bound.
bestQuantities :: Ord b => AuctionKind -> SupplyCurveVector -> PriceVector -> [Bid b] -> Maybe (QuantityVector, BidAssignments b, Price) Source #
Return the optimal quantities to sell (for the auctioneer) as well as the profit made selling those quantities.
Solution to the entire problem
bestPricesAndQuantities Source #
Arguments
| :: Ord b | |
| => AuctionKind | |
| -> ([Bid b] -> Set PriceVector) | strategy for determining candidate price vectors |
| -> SupplyCurveVector | |
| -> [Bid b] | |
| -> Maybe (BCAuctionResult b) |
Given the supply curves for each good and all the auction's bids, return the optimal auction prices and quantities sold, in terms of the auctioneer's benefits (returned as the 3rd component in the tuple).
ppCandidate :: Show b => BCAuctionResult b -> String Source #
findCandidateRates :: Eq b => AuctionKind -> FilterPrices -> [Bid b] -> Set PriceVector Source #
runBCAuction :: Ord b => BCAuction b -> Maybe (BCAuctionResult b) Source #