A combinatorial auction allows one to say that they value a set of objects that are being offered for auction. Imagine that Ms. Smith was browsing on eBay and saw a set of chairs and a table that she liked and she wanted to buy together for her dining room. However, she doesn't want the table without the chairs or the chairs without the table. There is no way she could do this now. If eBay would implement a combinatorial auction, then Ms. Smith could say or bid that she would pay $150 for both the table and chairs. Assume that Mr. Johnston bids $75.00 for just the table and Mr. Nixon bids $59.00 for just the set of chairs. The combinatorial auction system would realize that the best use (and the most money for the auction company) would happen if the pair of items were given to Ms. Smith. Had Mr. Johnston bid $75.00 and Mr. Nixon bid $76.00 for the set of chairs, the auction system would give each of these to the individual bidders and Ms. Smith would not win anything.
A lot of time in public choice is spent on dealing with multi-candidate elections. How do we deal with an election involving N, B and G and we want to allow people to say I really like N, but if it is a choice between B and G, then give me G? How do people specify their preferences. How does the election system computer decide who won? And how can we make the system strategy-proof? That is, we don't want a person who really prefers N to feel that if they rank N belong B or G, they are more likely to get N elected. One of the impressive things in Dr. Conitzer's article is the Kemeny Rule for elections. Let each person simply give each ranking. The election computer would compute a complete set of ranks that minimizes the total number of disagreements. One "disagreement" occurs when one voter ranking candidate i above candidate j and the election system ranks candidate j above candidate i. It would be great if we could do this for all kinds of things, like which bridge design do the members of the region prefer or what tax code do we prefer. Computing this is NP-complete. That means (I won't go into all the provisos here) any computer algorithm purporting to solve it for all possible sets of rankings will take time proportional to some power of the number of alternatives. In other words, for modest size problems, it is impossible to solve this generally even with computers much faster than the impressive ones that are available today. However, getting a problem proved NP-complete does not mean that an algorithm might not solve it efficiently most of the time or for most practical cases. And Dr. Conitzer reported they use CPLEX for ranking one hundred Ph.D. candidates to their Computer Science department by the Kemeny method. Dr. Conitzer analyzed many voting systems in a masterful Journal of the ACM article. In particular, although he showed that many schemes are NP-compatible to manipulate, that does not mean that one could not find an algorithm that will manipulate most practical elections as he demonstrated with an algorithm at the end of the article.
However, there are many who advocate for simply having each voter assigning a score within a range. say -1 to 1 or 0 to 100, to each candidate and the one with the highest average wins. (I will do a Thoughtful Thursday Post on Wally Smith's simulation and theorems.)
And I was impressed by the work on kidney exchanges. Assume A wants to donate a kidney to B and C wants to donate a kidney to D. Unfortunately A is not compatible with B, C is not compatable with D, but A is compatible with D and C is compatible with B. The computer system at Carnegie Mellon finds the proper matching and constructs a chain out of a set of all the people who would like to exchange kidneys with each other. However, it tries to minimize the chains.
These are examples of choice problems that don't use money. I sometimes wonder, and I will talk about this in another posting, whether this kind of technique could be used to minimize the necessity of money. As a poster on The Oil Drum put it, "Money is the lubricant in the economic engine and without enough of it that engine will seize up as it did in the 1930's when farmers dumped milk they couldn't sell into ditches while others were starving for want of the money to buy food." Could a program such this find the chains between the person working at Intel building parts for computers and the farmer without using a currencies or a numeraire?
Personal Note
Dr. Conitzer is a personal hero of mine since I read his dissertation. Last century, I read Robert Tilove's Disertation on Constructive Solid Geometry that was impressed me for being extremely clear and building up a whole research area. This century, I was amazed at the breadth in Dr. Conitzer's dissertation handling a whole area of combinatorial auctions and the remarkable clarity of his writing. I see the same quality of writing in the Communications of the ACM article on which I reported and his Journal of ACM(2) article!
Reference
- Combinatorial Auctions edited by Peter Cramton, Yoav Shoham and Richard Steinberg, 2006 Massachusetts Institute of Technology Press
- Conitzer, Vincent, Sandholm, Tuomas and Lang, Jerome, "When are Elections Hard to Manipulate" Journal of the ACM Volume 54, Number Three, Article 14, June 2007, 1 to 33.
No comments:
Post a Comment