In a traditional charity slave auction, the participants are first divided into slaves and buyers. Could this distinction be eliminated? Here's one possibility...
The participants are all in one group. Each participant bids on several others; the bids are collected and a combination calculated so that everyone is involved in at most one successful bid (whether as master or slave), while the total donation is maximised. The solution is displayed, and participants can up their bids until some pre-determined deadline or total.
Google suggests that a computer can calculate such a combination easily - here's the code, complexity O(n³) so it should run reasonably quickly. It's for undirected graphs, but that's OK - mutual bids are resolved in favour of the higher amount, which leaves a plain graph to work with.
Program:
Implemented! (new 19.10.2006) Download the code.
(You need both this and the weighted matching code.)
Notes:
- One might display the whole current solution to all participants, or only tell each participant which bid they're involved in is currently winning, if any.
- Alternately, one might run a Charity Dating Game, where only mutual bids count, valued at the sum (Yankee-auction style) or at twice the smaller bid (Dutch-auction style).
- The above method doesn't allow one master to have two slaves; that would be much more difficult, because (a) the bids probably aren't independent, so one would have to specify a separate bid amount for each combination, and (b) the known algorithm wouldn't be directly applicable any more.
- Similarly, it doesn't really support consortia ("we'll buy our housemate together and make him do the dishes when it's not his turn")
- Be careful googling for "charity slave auction" - it brings up a lot of slash.
- (update 7.2.2005) One might favour earlier bids by adding a small bias to them, for instance the time remaining in tens of megaseconds. This would eliminate ties, but might produce some counter-intuitive effects given the way bids are added together.
- (update 16.8.2005) One list of the other rules (ie, apart from the mechanics of the auction itself) would be the recent Second Floor Slave Auction. That's what I was googling for before, and coming up mostly blank, with the exception of phrasings like "evening of general social amiability" - which may well be better, I guess...
- (update 22.5.2006) I guess you could run it as "Charity Seven Minutes in Heaven", though given the amount of logistics involved, it might feel wasted if it's then all over in seven minutes. Maybe Heinlein's "Seven Hours of Ecstasy" :-)
- (update 20.10.2006) Self-bids (bidding on oneself) is easily supported.
⇦ Blog as a Pensieve | ⇨ The map and the territory in the world of The SCO Group |
