This is a real life game theory problem.
I have to organize an auction.
There is a finite number of lots, which are not equivalent.
There is a finite number of bidders; the number of bidders is larger than the number of lots.
Each bidder has a different set of preferences for the lots and a different willingness to pay.
The goal is to maximize the total proceeds of the auction under the following constraints:
First, each bidder cannot win more than one lot.
Secondly, at the end of the auction no bidder should feel he would have preferred winning another lot for a price greater than it was adjudicated for, over whatever this bidder came out with (assume preferences are constant throughout the process).
What is the best way to organize the auction (or can someone prove it is not feasible!).
Thanks the questions/comments. Here is additional information.
First let me give the real life background of the problem for color (just for illustration). We are a condo association managing a building complex with several hundred units and owners. We are building a roof garden with a public space and a number of private spaces. The question is about the best way to auction the private spaces among existing owners.
We don’t know much about the preferences of the potential bidders. However you can assume that for any pair (lot, price) any bidder is either open to transact or not and that he can order any two pairs {(lot1, price1), (lot2,price2)} by preference. We should also assume preferences don’t change over the course of the auction.
The single lot restriction is purely arbitrary and stems from the real life situation. As Marconius points out, it does create a timing issue if the lots are auctioned in a sequential manner. It forces the bidders to design a strategy to deal with the multiple lots/single win rule. The goal of the second constraint is to eliminate need to strategize in that way.
I am open to modifications to the second rule; I am really struggling with the best formulation. Its purpose is to eliminate regrets but not with the outcome of the auction per se but with any impact of the one lot per bidder rule. For example if the lots are auctioned sequentially, an early winner might realize later that a lot is adjudicated at a price lower than what she would have been ready to pay for it and would have preferred that outcome over her early win.
I don’t think it is necessary for the formulation of the problem but I would suggest we can assume the following:
- Each bidder has a hidden utility function that assigns a scalar value (a number) to any combination of (lot,price).
- The goal is to assign a bidder and a price to each lot so that at the end no bidder would be ready to trade his (lot,price) outcome for another lot at a higher price than it has been attributed to another bidder (in other words among all the (lot,price) combinations that constitute the result of the auction the one he has been assigned had the highest utility for him).
- Finally we want to maximize the sum of all prices in the final outcome of the auction
(to make the formulation complete you can also assume there exists zero-lots corresponding to not winning. They necessarily sell at price zero, and are all equivalent in the eyes of any bidder).
.