occur online, computational considerations in mechanism design are taking on a growing significance. Distributed algorithmic mechanism design, or just algorithmic mechanism design, is emerging as a field in its own right.
“Mechanism design is one of the major intellectual interfaces between computer science and economics, as well as one of the most vibrant areas of economics,” says Christos Papadimitriou, a computer scientist at the University of California, Berkeley.
Broadly speaking, there are two main strands in the literature. The first involves bringing computational considerations to the economics mechanism design literature. The second involves bringing incentive considerations to the computer science literature.
As an example of the first issue, consider the recent spectrum auction by the Federal Communications Commission mentioned earlier. In this auction, the right to use spectrum in various locations was sold to mobile phone companies and other potential users. The valuation that a buyer places on spectrum in a particular location may depend strongly on whether or not it wins spectrum in other locations.
In theory, each buyer could assign a different value to each possible subset of the geographic locations being sold. How does one design an auction that will yield reasonable outcomes in such a “combinatorial auction”? In such auctions, it turns out that the so-called “winner determination problem” is, in general, NP-complete. However, researchers working in algorithmic mechanism design have discovered various approximation algorithms and special cases that allow for reasonably good solutions in practical examples.
As an example of the second issue, consider the famous “stable marriage problem” in which one wants to design an algorithm to match up men and women. Each man has a ranking over the women, and each woman has a ranking over the men. A stable assignment is one such that no couple would prefer to leave their current mates to form a new couple. Although this particular description may sound somewhat frivolous, there are much more serious examples, such as matching
up hospitals and residents or organ donors and recipients.
It turns out that stable assignments always exist, and there are a number of algorithms that compute them. However, these algorithms assume that the participants are truthfully revealing their rankings. Do they actually have the appropriate incentives to do so? It turns out that some algorithms provide such incentives to men, and some provide such incentives to women, but there is no algorithm that provides incentives for both sides of the market to be truthful.
Ideas from economics can shed light on many computer science problems that arise from user interactions, such as computer viruses and spam, says Preston McAfee, a researcher at Yahoo! Research in Burbank, CA. “I think there’s a growing recognition that problems of bad behavior are incentive problems in the realm of game theory, rather than technological problems in the realm of traditional computer science,” he says.
Understanding the effect of incentives on how algorithms perform is “the latest and most momentous twist” on the question of computation’s limits, Papadimitriou says.
“With classical algorithms, you get your inputs and then compute away, and the answer comes out,” he says. “In this new context, you have to get your inputs by peering into the souls of selfish agents trying to promote themselves.”
A good starting point for studying distributed algorithmic mechanism design is a simple auction. A seller has one item to sell and n buyers have values
v1, … , vn for this item. The seller may have a reserve price r, which is the minimum price at which he is willing to sell the item. Typically there will also be a bid increment, the minimum amount by which a bid may be changed.
The goal is to design an online auction that will achieve some desired goals. There are many types of auctions that could be used. They include:
English auction. The seller starts at r and progressively raises the price by the bid increment until all but one of the buyers drops out. This is the most common form of auction.
Dutch auction. The seller starts at a high price and progressively lowers the price by the bid increment until a buyer shouts out “buy.” This sort of auction is used to sell flowers in the Netherlands.
First-price sealed bid. The buyers write down a bid and seal it in an envelope. The envelopes are opened and the item is awarded to the highest bidder at the price he or she bid. This form is commonly used for construction contracts.
Second-price sealed bid. The buyers write down a bid and seal it in an envelope. The envelopes are opened and the item is awarded to the highest bidder at the second-highest price. This auction was used by stamp collectors in the 19th century to sell stamps by mail.
It turns out there are some relationships among these auctions. For example, with fully rational players, the outcome of the English auction is the same, up to the bid increment, as the outcome of the second-price sealed bid auction. This is, perhaps, not so surprising upon reflection, as the English auction ends up awarding the item to the bidder who is willing to go the highest, but he or she only has to pay the bid of the second highest bidder plus a possible bid increment.
To make the argument slightly more precise observe that the payoff to a bidder with value v1 is v1 – b2 where b2 is the bid of the second-highest bidder. There are three cases to consider:
˲ v1 > b2. In this case bidder 1 wants to win. But the bidder can do so by reporting b1 = v1.
˲ v1 < b2. In this case bidder 1 wants to lose. But the bidder can so by reporting b1 = v1.
References:
Archives