Thoughtful Thursday, more on Combinatorial Auctions

In an earlier Thoughtful Thursday, I talked about Combinatorial auctions based upon Dr. Conitzer's article in Communications of ACM, March 2010, Volume 53, Number Three, Pages 84 to 94. What are the issues and how do they relate to combinatorial auctions? This allows people to put values on bundles of goods. eBay only allows one to make bids on individual goods. One can put a bid on the tables being sold. One can put a bid on a set of chairs. One can put a bid on both of them, but then one may win the chairs and not the table or vice versa. This Thoughtful Thursday is based upon Combinatorial Auctions by Peter Cramton, Yoav Shohan, Richard Steinberg.

An issue in all auctions is whether to use a single private bid or allow bidding. The first is used in bidding on government contracts, everybody puts in their bid. The one with the lowest bid gets the contract at that price. A stereotypical auction, the auctioneer keeps raising the price by reasonably small increments. But a sealed-bid auction is subject to the winner's curse. The company which wins the auction is probably the person who underestimated how much it would cost to do the work, or the company that is desperate. The Vicrey's auction, the person who has the lowest bid earns the bid. But he is awarded the second lowest price rather than what he bid. This reduces the incentive to underbid. Assume that B would do the contract for $100,000. And A bids to do the contract at $95,000. A gets the contract but gets the price of B. This has a whole bunch of nice properties, described in the first chapter of the book and in Wikipedia. In particular, it allows the parties to get the advantages of learning each other's prices as they go along. One can get the advantages of a stereotypical combinatorial auction by generalizations described in Chapters Four and Chapter Five of the textbook. These have been used in bidding for blocks of radio spectrum, mentioned in Mr. Othman's blog as a "Foundational Paper." That simply means that bid makers get to make slight changes in their package, every couple of hours and react to the others doing the same thing. This continues every few hours or couple of days until things converge.

One concern is how the particpants can express their bids. eBay sells thousands if not millions of item at one time. Clearly, one cannot specify a bid for every possible combination 2^n different bids or prices where n is the number of items. Even if only ten items were available, that would be 1024 different bids to be entered. One for every possible combination of bids. One needs to be able to specify different combinations more succinctly (Noam Nisan's Chapter Nine on Bidding Languages for Combinatorial Auctions). I discussed using ID3 to select via participatory democracy, the gun law. There are many categories in a gun law:

1. (Is this a BB-gun, an antique gun, a non-functional gun, an assault gun, a pistol, etc?)
2. Is the weopon concealed? And there are the characteristics of the owner of the possessor. Are they mentally ill, convicted of a crime, have an order of protection against them, etc.
3. Was the person's life threatened?
4. Does the person job need it, e. g. security guard.
5. And lastly, what is the place: a school, bar, a place where beer is sold such as some supermarkets.

To specify every possibility that is relevant, one would need 360 votes, just for the possibilities that I explicitly listed above--and certainly the above list is not complete. However, some voters might want to specify relations between categories-- if pistols are allowed, then we should allow BB guns. And, we haven't even considered having different categories of offense such as various grades of misdemeanor or felony Dr. Sandholm pointed out that in all but small auctions, nobody will bid on most combinations. For example, at eBay, nobody is going to bid on a combination of thousands of items with everything from vintage hairbrushes to industrial water distillers. However, in developing a penal code or tax code, one needs to allow for every possible combination of factors, and somehow specify them.

In the I proposed, I handle this by allowing people to vote on what categories are most important first. Thus, the voters could together decide to look first at type of gun and then location and decide that pistols are not allowed in bars. In fact, they could just look at the conviction status of the person first. They could then vote to choose status immediately for a felon convicted of a violent crime--they would not be allowed to own any type of gun at any time.

And we may want to allow some kind of horse trading. There are voters who are very concerned about gun rights. There are other voters concerened about abortion or the right to choose. Might there be a way to trade between those who feel passionate about one and have mild feelings about the other? From a satisfaction point of view, this makes sense, but obviously some people feel that such horse trading or log rolling is immoral.

There are two other major concerns. In a combinatorial auction, we have to decide who wins, "Optimal Winner Determination." If one is an auctioneer or auctioning off things sucha s a government auctioning off surplus goods or those seized, one desires to maximize revenue or total bids. However, this is an NP complete problem. (That means the general solution is probably computationally impossible! But often a random solution that works most of the time or an approximation is available. Computer Scientists discovered three main limitations on algorithms that are impossible--Last Century Dr. Webber at Western Illinois University gave a wonderful colliquium here on them. NP-complete, chaotic problems such as weather prediction or simulating what happens on the billiard table, and undecidable problems. Thus, many things we would like to do, such as computing the results of certain voting schemes, bad for us as participatory democrats, or computing how to vote strategically in others, which is good for us as participatory democrats.) And like many other NP-complete problems, Chapter Fourteen and Connitzer's articles describe practical algorithms to find which person wins their bundles, when there are conflicts, someone bids n dollars for A,B and C, someone bids m dollars for A,B and D, and someone bids q dollars for b and D.

But, the budgeting problem and revenue problem are interesting. For example, their may be several proposals for new public works on the ballot on which people can vote. Let's say two of these are bridges, a and b over the Mississippi river about fifty miles part. Each voter will value just bridge a being built, bridge bbeing built and many would like both, but probably not as much as the sum of the values for a and b In participatory budgeting, projects are winnowed down so voters might vote for only one project of a type. For example, a new sports complex, a libary, a street renewal project, or "commercial center regeneration" as they did in one district of Belo Horizonte. But what if there were projects to widen streets that were fairly close to each other and which could form an alternative for some people, or to build two libraries? So our job is to find a way to combine everyone's preference function to decide which government projects will be undertaken. And there is sadly reason to believe this might be difficult.

Christos Papadimitrou and Yaron Singer looked at an auction to purchase goods by a government. The government has a utility for each combination of goods (forget about considering participatory democracy). This is different from the mechanism used where each public contract is bid separately. And it is different when one wants to get the best allocation of goods to achieve a social welfare. They found that standard mechanisms where the "auctioner" hopes to optimize a utility function on subsets of items for many functions. But they do have some good approximation results for submodular functions. (This is defintely on queue for a future Thoughtful Thursday post.)