COMMENTARY

# The Theory of Mechanism Design: An Overview

Arunava Sen

voters are free to reveal any ranking, they can also misrepresent their true ranking. Clearly their report will depend on how they believe others will vote. A natural question is whether a voting rule can be designed where voters can be induced to reveal their true ranking irrespective of

#### Three US-based economists have been awarded the Nobel Prize for economics for 2007 for laying the foundations of mechanism design theory. A description and discussion of this theory, its importance and the work of the award-winning economists. Mechanism design could help policymaking in a number of areas, one potential area is in drawing up the rules for land acquisition.

I am grateful to Parikshit Ghosh and Debasis Mishra for their comments.

Arunava Sen (asen@isid.ac.in) is at the Indian Statistical Institute, New Delhi.

he Nobel Prize in economics for 2007 was awarded to Leonid Hurwicz (University of Minnesota, US), Eric Maskin (Institute of Advanced Studies, Princeton, US) and Roger Myerson (University of Chicago, US) for “having laid the foundations of mechanism design theory”. What is this theory and why is it important? What are the contributions of the recipients of this year’s prize? This article brieﬂy attempts to address these questions.1 Introduction

Consider the following example on the design of voting rules, which is a particular aspect of the theory of mechanism design. Suppose that there are N voters in a committee who have to choose one of K proposals. Each voter has an opinion on the proposals, which can be expressed in the form of a ranking of the proposals. For instance, voter j may prefer proposal a to proposal b to proposal c and so on. A “voting rule” is a method for aggregating individual opinions into an outcome. It determines the chosen proposal at any given proﬁle of rankings of voters – the chosen proposal can be thought of as the “the optimal” proposal in that situation. An example of a voting rule is the familiar “Plurality Rule” where the proposal selected is the ﬁrstranked candidate for the largest number of voters. Another well known class of voting rules is based on the “Majority Principle” which picks the proposal that beats all other proposals in pairwise majority contests whenever such a proposal exists.1

Revealing Information

A natural assumption in a setting where individuals vote is that each voter’s opinion is known only to the voter. Moreover voting is the act of revealing this information. If voter opinions were commonly known, voting itself would be superﬂuous. Since their beliefs regarding the voting behaviour of others. Unfortunately this does not hold for either the Plurality Rule or rules based on the Majority Principle.

To see this consider (for simplicity) the case where there are are three voters 1, 2 and 3 and exactly three proposals a, b and

As a result, a host of questions arise which are addressed by mechanism design theory. Are there other rules where voters are induced to vote truthfully? Can the truth-telling requirement be weakened sensibly? What happens if monetary compensation or randomisation is permitted? What if voters had better information about the true rankings of other voters? Is there any beneﬁt in designing more complex communication systems than simply requiring voters to reveal their rankings directly?

Devising a Mechanism

In general terms, mechanism design theory is concerned with resource allocation (understood very broadly) in multi-agent

december 8, 2007 Economic & Political Weekly

COMMENTARY

environments. The key feature of the problem is that the determination of an “optimal” allocation depends on information which agents possess privately. In order to achieve an optimal allocation, this private information must therefore be elicited from the agents. However, agents are sophisticated in the sense that they recognise that they may (depending on beliefs that they have about the information revealed by the other agents) be served better by lying rather than by telling the truth. Computing the optimal allocation from incorrect information may entail serious errors; hence the challenge is to devise a mechanism or a procedure for communicating the information of agents such that the outcome is an optimal allocation even when these agents behave strategically. Mechanism design theory can therefore be thought of as a theory of the design of institutions or the design of the rules of interactions amongst fully strategic agents in order to achieve desirable outcomes.

A critical step in the development of a theory is the formulation of a conceptual framework that allows consideration of relevant issues at a high degree of generality. For instance, progress in game theory was possible only after von Neumann and Morgenstern introduced the idea of normal and extensive form representations. This permitted a uniﬁed analysis of all strategic interaction between players including in its ambit for instance, interaction as disparate as that in chess and that in oil cartels. In this respect, the foundations of mechanism design theory were laid by Hurwicz (1960, 1972). The basic model ,which I outline below, is both simple and versatile.

2 The Formal Model

There are N agents, a set of feasible alternatives or outcomes or allocations A and an abstract set of “states of the world” Θ. Every realisation of a state θ∈Θ endows each agent i with a preference ordering Ri(θ) over the elements of A with the following interpretation: for all a,b∈A, aRi(θ)b implies a is “at least as good as b” accord

(θ).2, 3

ing to Ri There is another agent called the “planner” or the “principal” who has the authority to pick an alternative from

A. As we shall see from vatious examples, the planner need not be a “real” person; she can be a ﬁctitious individual who

Economic & Political Weekly december 8, 2007

represents the collective will of all the agents. The goals of the planner are captured by a “Social Choice Correspondence” (SCC) F which is a mapping from the set Θ to the set of non-empty subsets of A. Thus, for any θ∈Θ, F(θ)⊂A are the alternatives which are socially optimal in the state θ.

The crux of the problem is that the planner does not know the realisation of the state of the world, i e, does not know which θ∈Θ has occurred. Agents however have better information about the state and in particular, jointly know the θ. In other words, if their information is pooled, then it identiﬁes θ exactly (I shall try and make these notions more precise very shortly). The planner must induce the agents to reveal their information. She does so by constructing a mechanism G which consists of a message set Mi for each agent i and an outcome function g:M1×M2×...×MN → A.

Each agent i sends a message mi from his message set; the outcome function then speciﬁes an outcome g(m1,..,mN) as a function of the messages received. The mechanism is commonly known to all the agents. A pair (G,θ), θ∈Θ therefore deﬁnes a game. Consider a solution concept E appropriate for this game and let E(G,θ)⊂A denote the set of equilibrium outcomes according to E. We say that the mechanism G implements F (according to E) if there exists a mechanism G such that E(G,θ)=F(θ) for all θ∈Θ.4 Moreover, the SCC F is implementable if there exists a mechanism which implements it. If a SCC is implementable, the planner can put the mechanism which implements it into operation and be completely certain that no matter which state occurs, the outcomes which obtain will be optimal for that state. The primary goal of mechanism design theory is to determine the SCCs that are implementable; in certain cases it is also to identify SCCs within the implementable class that satisfy additional optimality properties.

Structure of Information

Before proceeding further, an important issue regarding the structure of information which also bears on the solution concept E used, must be clariﬁed. In the complete information setting, the state θ is commonly known to all agents. For any mechanism G, the game (G,θ) is therefore, a game of complete information and a solution concept such as Nash equilibrium, is appropriate.5 In the incomplete information setting, each agent has only partial information regarding the state.

Typically, θ comprises an N tuple (θ1,.., θN) where θi is the private information of agent i. In general θ1,.., θN are random variables whose joint distribution is commonly known (by all agents and the planner) but θi is observed only by agent i. In the private values model (to which I shall mainly conﬁne my attention), θi determines i’s preferences Ri(θi). Here, (G,θ) is a game of incomplete information and there are two solution concepts which are natural. The ﬁrst is dominant strategy equilibrium where each agent has an optimal message which gives him a better outcome no matter what messages are sent by the other agents.6

The second is the weaker requirement of Bayes-Nash equilibrium which is a strategy N-tuple from which no agent, regardless of the information he receives, can deviate unilaterally and obtain a higher expected pay-off. A more complicated model is the interdependent values model in the incomplete information setting, where each agent i observes θi but whose preferences depend not just on but also on

the entire vector θ, i e, we have Ri(θi).

θi

I now give a number of applications which illustrate the general framework outlined above and describe some important results.

3 Complete Information

Adjudication Problems: The most celebrated example is the so-called King Solomon problem from the Book of Kings in the Old Testament of the Bible. Two women claim to be the mother of a child. Solomon orders the child to be cut in half and for each woman to be given a piece. One woman then withdraws her claim and asks for the child to be given to the other woman. Solomon gives the child to her on the ground that only the true mother would give up her child than to see it killed.

Consider the following plausible formulation of this situation. The two agents are woman 1 and 2 referred to as W1 and W2 respectively and the planner is King Solomon. The set A={a,b,c} where a is the alternative where the child is given to W1, b the alternative where the child is given to W2 and c the alternative where the child

COMMENTARY

is cut in half. The set Θ={θ,φ} where θ is the state where W1 is the true mother and φ the state where W2 is the true mother. In each state both women most prefer the alternative which gives the child to her but the true mother prefers giving up the child to the other woman than to see it cut in half while the exactly the reverse holds for the impostor. Hence a R1(θ)bR1(θ)c, bR2(θ) cR2(θ)a while aR1(φ)cR1(φ)b and bR2(φ) aR2(φ)c. Solomon’s objective is to give the child to the true mother in each state, i e, by the SCC F(θ)=a and F(φ)=b. This is a complete information problem because in each state both women know exactly who the real mother and the impostor are.

Solomon’s mechanism can be construed as follows: M1 = M2 = Θ and the outcome function g:Θ×Θ→A is deﬁned by g(θ,θ)=a, g(φ,φ)=b, g(θ,φ)=g(φ,θ)=c. In other words, both women are asked to reveal the state; if they agree, the outcome is the F-optimal alternative for that state while if they disagree, the outcome is c.

Does this mechanism implement F? Alas no! In state θ the unique Nash equilibrium is for both W1 and W2 to send the message φ leading to the outcome b. Note that unilateral deviation by either W1 or

leads to c which both W1 and W2 prefer

W2 less than b according to their preferences in state θ. The message pair (θ,θ) leading to outcome a is not a Nash equilibrium because W2 can deviate unilaterally to φ and obtain c which she prefers to a and neither (θ,φ) are equilibria because W1 will deviate. Analogous arguments establish that the unique Nash equilibrium in state φ is the message pair (θ,θ) leading to a. Thus the Solomonic mechanism achieves the exact opposite of what it sets out to do – it always leads to the child being given to the impostor. How then did Solomon achieve the right outcome? By using a trick that mechanism design theory does not approve of. Note that the true state can always be deduced from the equilibrium outcome. If both women send (φ,φ), then the true state is θ while observing (θ,θ) is equivalent to the true state being φ. Solomon thus infered the true state from the equilibrium message pair and changed the g function ex post to make g(θ,θ)=b and g(φ,φ)=a. The two agents in this case were successfully fooled by the planner; however if agents anticipate that the planner may change the g function after receiving their messages, they will change their behaviour accordingly. In general, the failure of the planner to commit to a mechanism can have bad consequences.

The question therefore remains; can the Solomonic SCC be implemented? It turns out that in the form that it has been presented here, it cannot. There is a literature which examines this issue and related adjudication problems in detail.

Resource Allocation Problems: A classic debate in economic theory in the 1930s and 1940s centred on the possibility of “rational economic calculation” in socialist economies. Lange (1936) and Lerner (1944) claimed that socialist economies could replicate market outcomes with the central planning agency (CPA) playing the role of the ﬁctitious Walrasian auctioneer.

This view was disputed for instance, by Hayek (1945) who not only emphasised the computational difﬁculties involved but also pointed out that relevant information would be widely dispersed amongst agents in the economy who would not necessarily have the correct incentives to reveal this information to the CPA.

Consider the following highly simpliﬁed and stylised version of this problem. There are N agents who have endowments ωi of L commodities which are publicly observable. The set of alternatives A is the set of allocations amongst the agents of the aggregate endowment Σωi. A state θ

i

speciﬁes a preference ordering Ri(θ) for each agent over allocations. The Walrasian SCC W associates the set of perfectly competitive allocations to each state θ, i e, for each θ, W(θ)⊂A are the allocations which can be decentralised by a price mechanism when preferences are given by (R1(θ),...,RN(θ)) and endowments by (ωi,..., ωN).7 Can W be implemented? What else can be implemented? How much redistribution is feasible? Answers to these and other questions can be found by applying a very general result of Maskin.

A General Solution: Maskin (1977, 1999) provided a very general solution to the complete information implementation problem. He proved that provided that N≥3, a SCC F is implementable only if F satisﬁes a property which is now known as Maskin Monotonicity (MM). Conversely, if F satisﬁes MM and additionally, a weak requirement called No Veto Power (NVP),8 then it is implementable. Moreover Maskin explicitly constructed a mechanism which implements it.

MM says the following. Suppose that alternative a∈F(θ). Consider another state φ which has the property that for agents i, all alternatives b which are worse than a according to Ri(θ) are also worse than a

december 8, 2007 Economic & Political Weekly

COMMENTARY

according to Ri(φ); then we must have | depends on the solution concept E. If E is |

a∈F(φ). MM is a condition which is gener | dominant strategy equilibrium, then the |

ally easy to verify. For instance, W satisﬁes | incentive compatibility condition is called |

MM and can therefore be implemented. | strategy-proofness and requires each |

Other SCCs which can be implemented are | agent to reveal his information truthfully |

the Pareto-efﬁcient SCC9 and subcorre | irrespective of his beliefs about the reports |

spondences of the envy-free SCC.10 | of other agents. If E is Bayes-Nash equilib |

rium, the incentive compatibility is re | |

4 Incomplete Information | ferred to as Bayes-Nash incentive compat- |

Unlike the complete information case, | ibility and requires an agent to be truthful |

agents have exclusive information in the | if it yields an expected pay-off higher than |

incomplete informaton model. The plan | that obtained by lying, assuming that all |

ner can therefore no longer rely on agents | other agents are telling the truth. |

to verify each other’s reports.11 This intro | |

duces extra constraints on implementa- | Voting: This has already been discussed |

tion as we shall see. | earlier. There are N voters who have to |

An important tool in the analysis of im | elect one of the candidates in the set A. |

plementation in this model is “The Revela- | Voter j’s private information is his ranking |

tion Principle”. Consider the model where | of all the candidates. Voting consists of re |

a state θ is an N-tuple (θ1,...,θN) and θ1 is | vealing his ranking and a voting rule |

agent i’s private information with θi∈Θi. | elects a candidate based on the revealed |

Suppose a social choice function (SCF)12 f | rankings of all voters. Here the planner is |

can be implemented according to the solu | clearly ﬁctitious and a voting rule simply |

tion concept E by a mechanism G. Now | reﬂects a “just” way to aggregate voter |

consider the “direct” mechanism where | opinions. What are the voting rules which |

each agent i’s message space is Θi and the | can be implemented in, say dominant |

outcome function is f itself. In other words, | strategies? A conclusive answer is provid |

each agent reveals his private information | ed by the Gibbard-Satterthwaite Theorem |

θi and outcomes are speciﬁed by the SCF f. | [Gibbard 1973; Satterthwaite 1975] which |

The Revelation Principle says that tell | states that the only strategy-proof voting |

ing the truth (i e, agent i with private in | rules with a range of at least three13 are |

formation θi sending the message θi) is an | dictatorial. A dictatorial voting rule is |

equilibrium according to E provided that | one where the candidate elected is always |

E satisﬁes a mild property. Moreover since | the most preferred candidate of a pre |

the outcome when agents tell the truth is | determined voter called the dictator. |

the optimal outcome according to f it | An interpretation of the Gibbard-Satter |

would appear that the direct mechanism | thwaite Theorem is that it is impossible to |

also implements f. This is not quite correct | design a non-trivial, strategy-proof voting |

because the direct mechanism could also | rule when voter rankings are unrestricted. |

have non-truthtelling equilibria with out- | Voters are permitted to declare any conceiv |

comes that are not optimal according to f. | able ranking of the candidates as their true |

Nevertheless, it has become conventional | ranking. If the set of alternatives has some |

to ignore this multiplicity of equilibria | predetermined structure and rankings are |

issue and to weaken the notion of imple | restricted a priori, then interesting strategy |

mentation to implementation via truth | proof voting rules can be demonstrated to |

telling in the direct mechanism. | exist. Suppose voters have to determine |

The requirement that f must induce a | by voting, the percentage of the national |

truth-telling equilibrium according to E, is | budget to be spent on education. Consider |

called incentive compatibility [Hurwicz | the following class of plausible preferences |

1972]. This is clearly a necessary condition | known as single-peaked preferences. Each |

for implementability in incomplete infor | voter has a “best” percentage called the |

mation models and is an additional re | peak, and preferences “decrease” the far |

quirement over the conditions necessary | ther the percentage is from the peak. For |

for implementation in complete informa | instance, the peak may be 6 per cent in |

tion environments. It is important to note | which case 5 per cent is better than 3 per |

that the incentive compatibility condition | cent and 9 per cent is worse than 8 per |

Economic & Political Weekly december 8, 2007 |

cent. If voter preferences are single-peaked, then median rules are strategy-proof. For instance, suppose that there are ﬁve voters and their declared rankings have the following peaks (in percentages): 2, 2, 5, 7 and

10. Then the chosen outcome is 5 per cent. There is a rich theory of the design of voting rules on restricted preference domains.

Public Good Provision: There are N citizens who have to decide whether or not to undertake a public project (say, building a bridge). The set of alternatives A={0,1} where 0 and 1 represent the alternatives “don’t build” and “build” respectively. Each citizen i has a valuation of the project θi∈Θi which is private information. Assume that the project costs c and that this is shared equally if the project is undertaken.

c

Thus the utility of citizen i is θi – — if 1 is

N selected and 0 otherwise. An efﬁcient decision rule d(θ1,..,θN) is a SCF whose value is 1 if Σ θi>c and 0 if Σ θi<c.14 Is d

ii strategy-proof? No, because an agent for

c

whom θi– —>0 has an incentive to exag-

N

gerate his valuation while the reverse is

c

true for an agent for whom θi– —<0.

N

Can citizens be compensated monetarily in order that they have dominant strategy incentives to reveal their valuations truthfully and simultaneously ensure that the decision is efﬁcient? The answer is yes; moreover there is a unique class of compensation schemes which do this and they are called Vickrey-Clarke-Groves or VCG schemes.15 VCG schemes are central to mechanism design theory in environments where monetary compensation is possible and the utility function is quasilinear.16 These schemes have a signiﬁcant drawback though; the sum of the compensations paid out to the N citizens is not zero. However, if the incentive compatibility is weakened to Bayes-Nash incentive compatibility, then efﬁciency and the aggregate balancedness of the compensations paid out can be simultaneously attained [d’Aspremont and Gerard-Varet 1979].

Bilateral Trade: There is a seller and a prospective buyer of a house. The seller has a valuation ν and the buyer, a valua

s

tion νb which is private information for the seller and buyer respectively. These valuations can be assumed to be independently distributed random variables on the interval

—

[ ν, ν ] whose realisations are observed by the relevant parties. A “Bilateral Trade Rule” consists of bids by both players

11

COMMENTARY

(interpreted as revelation of private information) and two decisions based on these bids. The ﬁrst is the decision whether trade takes place and the second is the price at which trade occurs if it occurs. The question is whether a Bilateral Trade Rule exists which satisﬁes the following requirements: (i) Bayes-Nash incentive compatibility, (ii) ex post efﬁciency, i e, recommends trade only if νb≥ν, (iii) in

s

duces seller and buyer to participate voluntarily, and (iv) balancedness, i e, the seller receives what the buyer pays. Myerson and Satterthwaite (1983) show that such a rule does not exist.

Auction Design: There are N buyers for a single object. Each buyer i has a valuation νi for the object which is private information. Assume that these valuations are random variables distributed independently. There are several well known auctions such as the ﬁrst and second price sealed bid auctions, dynamic auctions such as the English and Dutch auctions and so on. What procedure to sell the object should the seller choose in order to maximise her expected revenue?

Applying the Revelation Principle, it sufﬁces to restrict attention to direct mechanisms where a bid is solicited from each buyer. An auction is a rule which speciﬁes (as a function of the bids received) the bidder who gets the object (the seller is allowed to retain the object) and the price various bidders pay. The problem is therefore of determining an auction which (i) is Bayes Nash incentive compatible, (ii) induces voluntary participation from the bidders, (iii) maximises expected revenue subject to (i) and (ii). This is a problem of considerable mathematical complexity but in a classic paper, Myerson (1981) provided a comprehensive solution to it. The general solution is subtle; however in the special case where the buyers are ex-ante symmetric, i e, the νi ’s are identically distributed and its distribution satisﬁes a certain regularity condition, the optimal auction is a second price auction17 with a reserve price set by the seller.

Regulation and Auditing: There is a single ﬁrm (a monopolist) in the market for a certain product whose costs are private information. The planner is a regulator whose objective is to maximise social welfare. A regulatory mechanism elicits cost information from the monopolist and speciﬁes an output target and a tax/subsidy. Baron and Myerson (1982) derive the optimal mechanism which is the mechanism that maximises expected social welfare subject to incentive compatibility and a participation constraint for the monopolist. The mechanism design approach to regulation thus provides a sound theoretical framework for the investigation of a classical problem in economics.

5 Concluding Remarks

Mechanism design theory is an active area of ongoing research. A particularly interesting set of questions relate to the design of combinatorial auctions. In these models, the seller has multiple objects to sell and buyers have valuations for all subsets of objects. For instance, the government of India is currently engaged in selling spectrum licences for FM radio broadcasting across the country and there may be synergies for buyers in acquiring particular combinations of licenses. Or they may be interested in selling off the rights to modernise various airports. What procedure should they follow? A fundamental theoretical question which remains open is the design of expected revenue maximising auctions in this setting. Important computational issues also arise in the multiple object model. For instance, it is typically computationally difﬁcult to determine efﬁcient allocations. Do procedures exist that are computationally easy but approximately efﬁcient?

A potential application of mechanism design theory of topical interest in India, is the issue of land acquisition for SEZs. Consider a model with N farmers each of whom have exactly one unit of land to sell but whose valuations are private information.18 There is a buyer who has a positive valuation only for all N units of land, i e, only if all farmers sell. Moreover this valuation is also private information for the buyer. What is the “best” trading rule in this situation? An obviously desirabale property is efﬁciency which would require sale to take place only if the buyer’s valuation exceeds the sum of the farmers’ valuations. Another requirement could be voluntary participation which would ensure that farmers are not forced to sell at prices below their valuations. It is possible that efﬁciency, voluntary participation and Bayes-Nash incentive compatibility are mutually incompatible. In that case what is the second-best rule, the one which violates these requirements the “least”? Is there a role for an outside agency such as the government to set reserve prices, force sale in some circumstances and redistribute appropriately?

6 A Brief Guide to the Literature

There is a huge literature on mechanism design straddling several branches of economic theory such as social choice theory, public economics, auction theory, the theory of contracts and so on. A brief survey of the issues as well as an extensive reading list is provided by the Nobel Foundation in connection with the 2007 Economics prize (available at http:// nobelprize.org/nobel−prizes/economics/ laureates/2007/press.html).

Jackson (2001) and Maskin and Sjöström (2002) survey the complete information implementation literature. Accounts of the mechanism design problem in the voting context can be found in Moulin (1983) and Barberá (2001).

An excellent recent book on auctions including its mechanism design aspect is Vijay Krishna’s Auction Theory while Green and Laffont’s 1979 book Incentives in Public Decision Making surveys the classical issues in public good provision quite comprehensively. For “state of the art” accounts on combinatorial auctions and algorithmic mechanism design dealing with computational issues, readers may refer to Crampton et al (eds) (2006) and Nisan et al (eds) (2007).

Notes

1 An example of such a rule is the “Dodgson Rule” devised by Rev Charles Dodgson better known as Lewis Caroll, the author of Alice in Wonderland.

2 An important class of problems arises when θ determines the set A itself but this leads to complications which I wish to avoid here.

3 More formally, Ri(θ) is a binary relation on the elements of A satisfying the properties of completeness, reﬂexivity and transitivity.

4 A weaker requirement would be ∅≠E(G,θ)⊂F(θ) for all θ∈Θ. 5 The message vector (m*1,...m* ) is a Nash equilibrium

N

if g(m*1,...m* ) Ri(θ)g(mi, m* ) for all mi∈ Mi and all i.

N–i

^

6 For each θi, the message mi(θi) is a dominant strategy

^

for i if g(mi(θi),m–i) Ri(θi)g(mi, m–1) for all mi∈Mι and

m–i∈ M–i. 7 Let us assume that such allocations exist for all states. There are of course, well known conditions that ensure this. 8 NVP is trivially satisﬁed in the resource allocation problem provided agents like more of any commodity to less, i e, if Ri(θ) is “increasing”.

december 8, 2007 Economic & Political Weekly

COMMENTARY

9 This is the correspondence which picks the set of all Pareto-efﬁcient allocations in a state.

10 It is possible to implement the SCC which selects Walrasian allocations from an equal division of the aggregate endowment. Such allocations are envyfree in the sense of Foley (1967).

11 In fact this is possible only if N≥3 in the complete information case. If there are two agents 1 and 2 and they send the equilibrium messages for states θ and φ respectively, then it is impossible for the planner to verify whether θ is the true state and 2 is deviating or whether the true state is φ and 1 is deviating.

12 A SCF is a singleton-valued SCC. 13 There are at least three distinct candidates which are elected at different voter rankings. 14 This is the well known Samuelson-Lindahl rule for Pareto efﬁciency. 15 William Vickrey recieved the Nobel Prize for economics in 1995. 16 Suppose y is the level of a public good and xi is the monetary compensation received the agent i. The utility function U(y,xi) is quasi-linear if it is of the form Ui(y,xi)=hi(y)+xi. 17 A second price auction is one where the highest bidder gets the object but pays a price equal to the second highest bid. 18 It is easy to accommodate the case where a farmer does not want to sell his land at any price by assuming that his valuation in this case is inﬁnite.

References

d’Aspremont, C and L-A Gerard-Varet (1979): ‘Incentives and Incomplete Information’, Journal of Public Economics, 11, 25-45.

Barberá, S (2001): ‘An Introduction to Strategy-Proof Social Choice Functions’, Social Choice and Welfare, 18, 619-53.

Baron, D and R Myerson (1982): ‘Regulating a Monopolist with Unknown Costs’, Econometrica, 50, 911-30.

Crampton, P, Y Shoham and R Steinberg (eds) (2006): Combinatorial Auctions, MIT Press.

Foley, D (1967): ‘Resource Allocation and the Public Sector’, Yale Economic Essays, 7, 45-98.

Gibbard, A (1973): ‘Manipulation of Voting Schemes: A General Result’, Econometrica, 41, 587-602.

Green, J and J-J Laffont (1979): Incentives in Public Decision Making, North Holland, Amsterdam.

Hayek, F (1945): ‘The Use of Knowledge in Society’, American Economic Review, 35, 519-30.

Hurwicz, L (1960): ‘Optimality and Informational Efﬁciency in Resource Allocation Processes’ in Arrow, Karlin and Suppes (eds), Mathematical Methods in the Social Sciences, Stanford University Press.

– (1972): ‘On Informationally Decentralised Systems’ in C B McGuire and R Radner (eds), Decentralisation and Organisation, North Holland, Amsterdam.

Jackson, M (2001): ‘A Crash Course in Implementation Theory’, Social Choice and Welfare, 18, 655-708.

Krishna, V (2002): Auction Theory, Academic Press.

Lange, O (1936): ‘On the Economic Theory of Socialism’, Review of Economic Studies, 4.

Lerner, A P (1944): The Economics of Control, MacMillan, New York.

Maskin, E (1977, 1999): ‘Nash Equilibrium and Welfare Optimality’, paper presented at the summer workshop of the Econometric Society in Paris, June 1977, Published in 1999 in Review of Economic Studies, 66, 23-38.

Maskin, E and T Sjöström (2002): ‘Implementation Theory’ in K Arrow, A K Sen and K Suzumura (eds), Handbook of Social Choice and Welfare, Volume 1, Elsevier Science, Amsterdam.

Moulin, H (1983): The Strategy of Social Choice, Advanced Textbooks in Economics (C J Bliss and M D Intrilligator (eds)), North-Holland, Amsterdam.

Myerson, R (1981): ‘Optimal Auction Design’, Mathematics of Operations Research, 6, 58-73.

Myerson, R and M Satterthwaite (1983): ‘Efﬁcient Mechanisms for Bilateral Trade’, Journal of Economic Theory, 28, 265-81.

Nisan, N, T Roughgarden, E Tardos and V Vazirani (eds) (2007): Algorithmic Game Theory, Cambridge University Press.

Satterthwaite, M (1975): ‘Strategyproofness and Arrow’s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions’, Journal of Economic Theory, 10, 187-217.

Hiren Gohain (hiren.gohain@gmail.com) is a well known writer, literary theorist and social critic, who lives in Assam.