Written 19 October 2005. Disclaimer. I've written these pretty hastily. Apologies for the mistakes. Please send me requests for clarifications as well as corrections.
In class, we'll discuss the idea of bagging from the neural networks literature, and the concept of utilitarian voting from the robotics literature. These two concepts successfully use voting mechanisms in computer science applications.
If we really want honesty to be "the best policy" in a multi-agent decision problem, then we have to design a mechanism that encourages honesty. Since this is not possible for the general class of problems without also implying that the mechanism is dictatorial, we will need to find ways around this. (BTW, I've been studying the Gibbard Satterthwaite theorem, but I still don't understand it well enough to include it in these notes. Consequently, I am forced to wave my hands about the impossibility of having a truth-dominant, fair social choice mechanism.) In this section of the class, we will discuss the use of incentives to induce honesty. More precisely, we will use auctions as the tool for inducing honesty and we will find that there are auctions which produce a truth dominant equilibrium of the strategy game. The cost of using one of these auctions is the difference between the true value of the highest bid and the true value of the second highest bid.
Recall from the discussion of voting that it is possible for agents to misrepresent their true preferences. In a social choice setting where it is possible for agents to do this, we say that an agent reveals its type, meaning the type of agent it is or the type of agent that it is pretending to be. The number of possible types that can be revealed equals the number of possible preference orderings available to an agent.
Given a particular social choice mechanism, there is a formal game that emerges as agents try and decide what they want to reveal (or which type of agent they want to pretend to be). Let Θ = {θ} denote the set of all types that each agent in society can be. Let θi denote the type of agent i. A social choice function is defined in Microeconomic Theory (by Mas-Colell and Whinston, Oxford University Press, 1995, page 859) as
... a function f: Θ1× Θ2× ... × Θn → X that, for each profile of the agents' types (θ1,θ2, ... θn) assigns a collective choice f((θ1,θ2, ... θn) in X.
The set X in this definition is the set of possible alternatives from which the agents make a collective choice. This set of alternatives could be a winning candidate, the distribution of a good to an agent along with the exchange of money between the agent and a seller, an ordering among possible candidates, etc. In words, a social choice function takes the true types of the agents and returns the social choice (or social ordering) from the agents types.
Given the agent's type and the outcome of the collective choice (as dictated by the social choice function), each agent can evaluate their utility ui(θi,x) denote the utility to player i when its type is θi and society's choice is x.
The problem faced by the agents is that the types are not known to everyone, so it is possible for an agent to use a strategy si(θi) where it reveals something about itself; it may be the true type of the agent, si(θi)=θi, or a type that differs from the true type, si(θi)≠θi. A mechanism is like a social choice function, except that the mechanism is supposed to work when agents can play strategies that differ from their true type. Mas-Colell and Whinston say it this way: "We need to consider not only the possibility of directly implementing social choice functions by asking agents to reveal their types but also their indirect implementation through the design in which the agents interact. The formal representation of such an institution is known as a mechanism" (page 856). In other words, the mechanism is an institutional device that selects some outcome given the possible strategies of the agents. Again, quoting from Mas-Colwell and Whinston,
A mechanism Γ = (S1, ... Sn, g()) is a collection of n strategy sets (S1, ... Sn) and an outcome function g: S1 × ... × Sn→ X.
A mechanism designer can use incentives or punishments (like taxes or fines) to shape the kinds of strategies that the agents will play. If we have selected a desirable social choice function, one that implements our favorite subcollection of Arrow's fairness axioms, then our next task is to design a mechanism that induces people to play strategies that produce the same outcome.
There are two criterion for what it means for a mechanism to induce people to select the same outcome as the one that would have been chosen had everyone honestly revealed their true type. The first criterion is that an equilibrium of the "mechanism game" produces the same outcome as the social choice function given honest agents. The second criterion is that the strategically dominant choice for each agent in the "mechanism game" produces the same outcome as the social choice function given honest agents. When an equilibrium of the mechanism game produces the same outcome as the social choice function given honest agents, we say that the mechanism implements the social choice function. When a strategically dominant set of solutions exists that produces the same outcome as the social choice function given honest agents, we say that the mechanism implements the social choice function in dominant strategies. Clearly, the second flavor is stronger than the first flavor.
I think that the Gibbard-Satterthwaite theorem says that when X is finite and has at least three agents, and when we are considering all possible preference patterns, and when any possible outcome X can be reached by the social choice function (i.e., citizen's sovereignty), then any mechanism that truthfully implements the social choice function in dominant strategies is dictatorial. Thus, there is no fair way to eliminate strategies in the game.
The goal of the seller is to have agents reveal their true preferences in the form of a money-based utility representation of the value to the agent of the item being sold. If the auctioneer can get buyers to do this, then the seller gets the highest price possible for the item. Unfortunately, the buyer who values the item the most has an incentive to reveal something other than the truth about his or her true value. After all, this buyer can always use a strategy where he or she values the item just a bit more than the second highest bidder.
Thus, the seller is left in an inescapable predicament: either give an incentive to the buyers to reveal their true utilities, or have sellers that lie about their true values. Intuitively, the cost to the seller to induce buyers to reveal their true utilities is the difference between the highest true bid and the second highest true bid.
In class, we will discuss four types of auctions. We will discuss the mechanism and whether they induce truth dominant strategies from the buyers.
We will prove that the Vickrey auction is truth dominant in class..
Find examples from the current literature on how auctions are used in Computer Science applications.