Efficient Auction Design for Multi-Item Allocation Models
Explore the concept of efficient auction design for multi-item allocations through models like Shubik & Shapley assignment and connection to matching models. Understand the significance of Pareto efficiency in achieving optimal outcomes and examine examples to grasp the concept better.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Multi-Item Auctions Many auctions involve sale of different types of items Spectrum licenses in different regions, seats for a concert or event, advertising spots in different locations, assets of a company being liquidated, pieces of a procurement contract. Today s class: Shubik & Shapley assignment model. Focus on simultaneous sale of multiple items Assume each bidder can win just one item. Define appropriate notion of efficiency. Auction design to achieve efficient allocation. Next week: different applications. 2
Connection to Matching Assignment model: goal is to allocate different indivisible items to people with different preferences, with each person getting at most one item. This sounds like a matching problem Before we tried to assign the items without payments. Now, we are assuming items can be priced. We will see that auctions can function similarly to matching algorithms they are mechanisms that find efficient allocations, ideally with good incentives. 3
Example: Cubicle Assignment Problem: assign cubes to economics graduate students. Efficient assignment without prices or money. Assign random numbers, choose in order of numbers. Assignment will be Pareto efficient for any random order of students => may be many Pareto efficient assignments. Suppose that students can trade offices for money Will the outcome of an office draw still be Pareto efficient? What does a Pareto efficient outcome look like? What sort of approach might lead to an efficient allocation? 4
Assignment Model N individuals, K items. Each individual wants at most one item. Let vikdenote individual i s value for item k. If i gets item k and pays pk, utility is vik pk An assignment is a matching of items to individuals, so that each individual gets at most one item. Connection to matching: in matching model, each individual can rank-order items, now each person has a clear monetary value for each item, and cares about value minus price. 5
Pareto Efficiency An assignment is Pareto dominated if it is possible to move to a new assignment and make cash payments between individuals so that everyone is better off. An assignment is Pareto efficient if it is not Pareto dominated. The total value (or surplus) of an assignment that gives item k(i) to each i is v1k(1) + v2k(2)+ + vNk(N). What s the relationship between efficiency & total value? 6
Example Three bidders A, B, C. Two items: X and Y. X 30 20 10 Y 60 40 20 A B C Is it efficient to assign (A,X) and (B,Y)? What is the Pareto efficient allocation? 7
Efficient Assignments Theorem. An assignment is Pareto efficient if and only if it maximizes total value. Proof. Suppose an assignment doesn t achieve maximum value. Then there is another assignment of items that will lead to strictly greater total value, and it will be possible to move to this assignment and find payments between individuals so that everyone is strictly better off. Suppose an assignment does achieve maximum bidder value. Then any change in the assignment reduces the total value, so someone must lose from this change. 8
How to Allocate Efficiently? Suppose items are initially owned by a seller that has zero value for all of the items. Suppose the seller wants to allocate the items efficiently. Seller might also care about selling for high prices, but we won t focus on revenue-maximization today. Let s consider different mechanisms the seller might use. 9
Ascending (Clock) Auction Seller has a price clock for each item. Price of each item starts at $0. At each point, buyers demand at most a single item. Prices advance for goods in excess demand Auction ends when no items are in excess demand. Assumptions At any given moment, each buyer bids for the item it wants most at the current clock prices ( truthful bidding ). Prices rise continuously rather than jumping discretely. 10
Example Three bidders A, B, C. Two items: X and Y. X 30 20 10 Y 60 40 20 A B C Efficient assignment is (A,Y) and (B,X) 11
Ascending Auction Price X Price Y A B C Bidder Values X 30 20 10 Y 60 40 20 A B C 0 0 Y Y Y 0 1 Y Y Y 0 2 Y Y Y 0 3 Y Y Y
Ascending Auction Price X Price Y A B C Bidder Values X 30 20 10 Y 60 40 20 A B C 0 10 Y Y X/Y 0 11 Y Y X When pX=0, pY=10, C is indifferent. Excess demand for Y means pY continues to increase, with C now favoring X. 0 Y Y X 12 0 20 Y X/Y X When pX=0, pY=20, B is indifferent. Now both prices must increase together.
Ascending Auction Price X Price Y A B C Bidder Values X 30 20 10 Y 60 40 20 A B C 1 20 Y Y X 1 21 Y X/Y X 2 21 Y Y X Prices rise together, maintaining pX = pY 20. 2 22 Y X/Y X
Ascending Auction Price X Price Y A B C Bidder Values X 30 20 10 Y 60 40 20 A B C Y X X 2 22 9 29 Y X X 10 29 Y Y -- Auction ends at pX=10, pY=30 10 30 Y X --
Summary: Ascending Auction PX 0 0 0 0 0 1 1 2 10 10 PY 0 5 10 15 20 20 21 21 29 30 A Y Y Y Y Y Y Y Y Y Y B Y Y Y Y X Y X Y Y X C Y Y X X X X X X -- -- Bidder Values X 30 20 10 Y 60 40 20 A B C With continuous price increases When pX=0, pY=20, B is indifferent between X,Y. If pX increases, B chooses Y. If pY increases, B chooses X. So pX, pY increase together with pY - pX = 20, until auction ends at pX=10, pY=30
Example Auction outcome: (B,X) and (A,Y) efficient! X 30 20 10 Y 60 40 20 A B C Auction ends at prices: pX=10, pY=30. A demands Y, B demands X, C demands nothing So demand = supply at final auction prices. Are there other prices at which market clears? 17
Example: market-clearing prices X 30 20 10 Y 60 40 20 A B C Market also clears at pX=10, pY=35. A demands Y B demands X C demands nothing. More alternatives: pX=10, pY=40, or pX=20, pY=50. Can we find all the market clearing prices? 18
Example: market-clearing prices X 30 20 10 Y 60 40 20 A B C There is only one assignment consistent with market clearing Why? To clear the market we need the following to happen C demands nothing: if C demands an item, then A,B with higher values will demand items and there is excess demand. A, B demand an item: or else demand < supply. B demands X: if B wants Y, then pY pX < 20, and A also wants Y. Therefore A must demand Y to get demand = supply. 19
Example: mkt-clearing prices X 30 20 10 Y 60 40 20 A B C Find complete set of market clearing prices for X and Y. pX 10. (C prefers nothing to X) pX 20. (B prefers X to nothing) pY pX + 20 (B prefers X to Y) pY pX + 30 (A prefers Y to X) Range of mkt-clearing prices typical with discrete goods. 20
Example: mkt-clearing prices py 50 40 30 Auction finds lowest market-clearing prices, pX = 10 and pY = 30 20 10 px 10 20 21
Example Three bidders A, B, C. Two items: X and Y. X 35 40 70 Y 40 60 80 A B C What is the efficient (value-maximizing) allocation? 22
Ascending Auction pX 0 0 0 1 1 2 2 3 35 35 pY 0 5 10 10 11 11 12 12 44 45 A Y X X X X X X X B Y Y Y Y Y Y Y Y Y Y C Y Y X Y X Y X Y Y X Bidder Values X 35 40 70 Y 40 60 80 A B C With continuous price increases When pX=0, pY=10, C is indifferent between X,Y. If pX increases, C chooses Y. If pY increases, C chooses X. So pX, pY increase together with pY - pX = 10, until auction ends at pX=35, pY=45 23
Example: mkt-clearing prices X 35 40 70 Y 40 60 80 A B C As above, we can argue that for market clearing, need A to demand nothing, B to demand Y, C to demand X. Lowest market-clearing prices: pX =35, pY = 45. Characterize the full set of market clearing prices Set pX 35 and pY 60. Set pY pX + 10 and pY pX + 20 24
Example: mkt-clearing prices py 60 50 40 Auction finds lowest market-clearing prices. 30 20 10 px 10 40 20 30 50 25
The Magic of the Market Theorem.In the assignment market setting, a simultaneous ascending auction with truthful bidding will Finish at the lowest market clearing prices! Result in an efficient (value-maximizing) assignment Implication: auction works as an algorithm to find market clearing prices, i.e. to find a competitive equilibrium (which is efficient). Proof. Will show this result in two steps. 26
Magic of market, cont. Proof: auction ends at market clearing prices. At start, some items have zero demand (excess supply), some have positive demand. Prices rise for items with demand > 1. Demand for an item with demand > 1 can fall as its price rises, or increase as other prices rise. Demand for an item with demand 1 can increase but cannot fall because the price of the item does not go up. If an item has demand = 0, its price must still be equal to zero. No bidder exits the market if there is an item with demand =0. At the end, no item has demand > 1. If N>K, then also no items have demand = 0, so all have demand = 1. If N<K, then some there is demand = 1 for N items, and demand =0 for K-N items. Note: proof is a little loose about possibility of ties ... a subtle issue. 27
Market Clearing Prices Theorem. Suppose we find market clearing prices (so demand equals supply), and assign the goods as they are demanded. The assignment maximizes total value. Proof Suppose market clearing prices are p1, ,pK Suppose at those prices each bidder i demands item k(i) Pick some alternative assignment in which i gets item z(i) We know that for each bidder i, vik(i) pk(i) viz(i) pz(i) Sum these inequalities: i vik(i) - i pk(i) i viz(i) - i pz(i) But i pk(i) = i pz(i) = p1+ +pK, so i vik(i) i viz(i). 28
Example: how auction works To the right of this line C prefers nothing to X py Above this line, B prefers X to Y. 50 Above this line, C prefers X to Y. 40 (Y,X,-) X 30 20 10 Y 60 40 20 (Y,X,X) 30 (Y,Y,-) A B C 20 (Y,Y,X) (Y,Y,Y) 10 (Y,Y,Y) px 10 20 29
Summary of Results Assignment model: N bidders, K items Each bidder wants at most one item. Bidder i s utility if pays pk for item k: vik pk The Key Results There is an assignment that maximizes total value and is efficient; typically this assignment is unique. There are always market clearing prices for the items, and (item-by-item) minimal market clearing prices. These market clearing prices can be reached using an ascending auction assuming truthful bidding. 1. 2. 3. 30
Connection to Matching At the beginning we noted a possible connection to matching theory b/c of the one-to-one assignment. Think of each bidder as forming a preference list that factors in both item and money preferences (think of prices as being in discrete dollar increments) Example: first choice is to pay zero for item 1, second choice is to pay $1 for item 1, third choice is to pay $0 for item 2, fourth choice is to pay $2 for item 1, etc.. Items prefer more money, but don t care who offers it. 31
Deferred acceptance? Each bidder submits a preference list Seller runs deferred acceptance algorithm Bidders propose to the items. Items accept highest offer, reject others. Bidders continue down their preference list, raising their bids as the algorithm proceeds. Algorithm will eventually terminate. 32
Auctions & Matching Matching algorithm (Gale & Shapley, 1962) Offers made by computer. 1. Men make offers to most preferred remaining acceptable woman. 2. Women hold best man, reject others. 3. Rejected man strikes the woman from his/her list. 4. Process continues until no new offers or rejections. 5. Implement last held allocation. Ascending auction (Kelso & Crawford, 1982) Bids made by computer. Bidders offer most preferred remaining acceptable purchase. Items hold best bid, reject others. Rejected bidder strikes offer from his/her list. Process continues until no new offers or rejections. Implement last held allocation. 1. 2. 3. 4. 5. 33
Deferred acceptance auction What we know from matching theory DA algorithm will converge to a stable allocation. Bidder-offering DA gives stable allocation preferred by bidders, and is strategy-proof for the bidders. Stability: each bidder prefers the item they get, at the price they pay, to any other item at the price it receives. So at the final item prices, demand = supply! Completing the auction/matching link A stable allocation is a competitive equilibrium Bidder-proposing DA gives the lowest mkt-clearing prices. 34
Summary Assignment model captures settings where bidders with diverse preferences must be assigned to a diverse set of goods, and pricing is allowed. Competitive equilibrium is a natural candidate for a good outcome, especially with lowest market-clearing prices. A well-designed auction can elicit willingness-to-pay from bidders and identify market clearing prices. Simultaneous ascending auction Sealed bid assignment auction There is a close connection to matching theory, and a version of the DA can work as an ascending auction. 35
