|
INFORMATION Revelation why Honesty is not ALWAYS the best policy Think of a community that has to choose from a number of alternatives. In a democratic setting, the alternative that is chosen by the community (the social choice) should depend on the preferences of the individuals. It is unlikely that the individuals in the community are unanimous in their ranking of these alternatives. Can procedures be devised for social decision-making that respect individual preferences in the presence of diversity of opinion? It is well known that some procedures lead to difficulties. As long ago as 1785, the French thinker Marquis de Condorcet had noted the inconsistencies that majority voting can lead to. Suppose our community consists of three individuals 1, 2 and 3, who have to decide between three alternatives x, y and z. Let the preferences of the individuals be as below:
Then, in a vote between x and y, x defeats y; likewise y defeats z, but paradoxically z defeats x. Manipulating the order of voting can make any of the alternatives emerge as the "socially chosen" one. This fact has long been exploited by people who set the agenda for meetings. For instance, if you want to make y win, set the agenda so that first a vote is taken between x and z: z wins and x is eliminated. Then take a vote between z and y. Obviously y will be the ultimate winner. Problems of this kind are not peculiar to majority voting. Mathematical reasoning shows that some inconsistency or the other arises in all procedures for making social choices. This fact is far from apparent. Most people would find it difficult to believe that it is even possible to use mathematics to think about such social and political questions. And yet, not only is a mathematical formulation possible, but it actually provides completely unexpected insights. The level of mathematics used is elementary. What is exemplified is the way the use of mathematics as a language forces clear and logical thinking about a problem.
Arrow's Impossibility Theorem Suppose there is a set X of social alternatives under consideration by a community of N individuals, each of whom can order these alternatives according to his preferences. The individuals are assumed to have what are called rational preferences, that is each individual can rank any two alternatives, and if alternative x is better than y, and y is better than z, then x must be regarded as better than z. A social choice function is a procedure for choosing one alternative from the set X, given the preferences of all the individuals. We assume that the social choice function has unrestricted domain, that is the procedure should work for any possible configuration of rational individual preferences. Ideally this social choice function should satisfy some minimal conditions corresponding to our notions of a "good" procedure. The first of these is what is called the Pareto condition: if for a pair of alternatives x and y, everybody strictly prefers x to y, then y should not be chosen. The second condition is monotonicity. Suppose an alternative x is the social choice under a particular profile of preferences. Consider a different profile where for all individuals any alternative y, which was inferior to x under the original profile, continues to remain inferior to x. Then x should be the social choice under the new preference profile also, because its desirability has not decreased for any individual. An individual is said to be a dictator for a given social choice function if, whenever he prefers alternative x to y, then y is not chosen, no matter what the preferences of the other individuals are. That is, the alternative chosen "socially" is always the one that this individual wants. A social choice function that admits a dictator is called dictatorial. Evidently we would like our social choice function to be non-dictatorial.
Arrow proved a theorem that is equivalent to the following:
Remarkable though this result is, the Arrow framework ignores an important aspect of the problems involved in making social choices. An individual's preferences are private information, and known only to himself. If the social choice is to depend on individual preferences, we will have to rely on the reports that individuals themselves make about their preferences. An individual may then find it possible to manipulate the social choice by deliberately misrepresenting his preferences. Manipulation: Public Works Suppose the government is considering building a new road through a town. The cost of construction is known, say Rs.50 crores. Building the road is justified if the monetary values of the benefits to all the residents of the town add up to at least Rs.50 crores. To ascertain whether this is indeed the case, the government asks residents to report their valuations. This procedure will be successful only if all the people surveyed tell the truth. Respondents will, however, almost always find it to their advantage to misrepresent their valuation. The nature of misrepresentation will depend on the method used for financing the building of the road. Suppose, first, that if the road is built every resident will have to pay an equal share of the cost of construction. If a person's valuation is less than the flat tax, then he will try to prevent the road from being built. He can do so by drastically understating the benefits that he will derive (perhaps even to the extent of claiming that the road will be a nuisance and that hence his valuation is a large negative sum). On the other hand, if his valuation is more than his share of the cost, he will overstate it because the chances of the road being built are then greater, while the cost to him does not change. Charging residents in proportion to their stated benefits (as opposed to a flat tax) will not elicit truthful revelation either. It is now in each person's interest to understate his benefit in the hope that others will state their benefits truthfully, pay up, and get the road built. He himself would then be able to use the road while paying less for it. This is the classic free rider problem. If everybody reasons this way, the road may never get built because the sum of stated benefits falls short of the cost. Finally, if no specific taxes are to be levied on the residents of the town, and the road is to be financed out of national tax revenues, a local resident will tend to exaggerate the usefulness of the road, so as to ensure the road gets built. Again, the revealed information on which the decision has to be based, will not be the truth.
Bidding for contracts Another example is provided by the system of tendering for contracts. Suppose the government wants to auction licenses for providing a cellular phone service in a state. The license will be awarded to the highest bidder. The winning firm pays the government an amount equal to its bid. One might at first think that each firm would bid the actual amount that the license is worth to it (i.e. the net profit it expects to earn from providing the service), so as to maximise its chances of winning. However, it is easy to see that the firms will underbid, and that consequently the expected government revenues will be lower. Each firm will bid an amount that maximises its expected profit. If Firm k does not get the license, its profit is zero. In the other possible 'state' in which it does get the license, its net gain is equal to its profit from operating the network (P k) minus what it has bid for the license (Bk). The expected net gain is, therefore, the probability pk of winning the license times (P k - Bk). The probability pk will depend on all the bids; it will increase as Bk increases, other things remaining equal. If in its sealed tender the firm bids its true valuation (Bk = P k), the net gain in either state will be zero, and hence its expected net gain will also be zero. If the firm bids less than P k (understating its true valuation), the probability that it will win the contract decreases, but when it does win the firm makes a positive net profit. Hence the expected net gain if the firm does not report its valuation truthfully is strictly greater than zero (the net gain from reporting truthfully). A bidding system of this kind is called a first-price sealed bid auction. In a second-price sealed bid auction, the highest bidder gets the license but only has to pay the second-highest bid as the license fee. This might seem an odd procedure because it appears that the government will get less revenue. However, all the bids will now be higher than in the first-price auction. In fact, for each firm bidding its true valuation will be the dominant strategy, that is, the strategy that is best for the firm irrespective of what the other firms are doing. In the example above, let b be the highest bid among firms other than k. If b is less than P k, Firm k makes a positive profit by bidding P k. Changing the bid to an amount higher than b does not change the net gain to the firm (it still gets the license, and pays the same license fee). On the other hand, if Firm k bids less than b it loses the license and has a zero net gain. Similarly, one can show that if b > P k, then bidding P k is still its best strategy.
One can in fact further show that (if bidders' valuations are independent of each other) the expected revenue of the government is the same in all the following forms of auction: the second-price, the first-price, the English, and the Dutch auctions. In the familiar English (ascending-price) auction, used in the sale of paintings or antiques, bidders keep on increasing their offers starting from a reserve price, till only one bidder is left and the hammer comes down. In a Dutch (descending-price) auction, used in the sale of cut flowers in Holland, the price starts at a high level, and is successively decreased by the auctioneer till a bidder claims the article by shouting "Mine!" The first-price auction is used in India and many other countries for awarding government contracts. The second-price auction has been used in recent years in the United States for the sale of Treasury Bills.
THE GIBBARD - SATTERTHWAITE THEOREM Constructing an appropriate auction system is a typical mechanism design problem. Suppose there are many individuals ('agents') with private information. Agents take some actions (which we can think of as sending messages). The message an agent sends will typically depend on his private information. A social choice is then made on the basis of the messages received from all the agents. Hence the message sent by an agent is influenced by considerations of strategy. Sending a particular message is a dominant strategy for an agent if sending this message is optimal for him irrespective of what other agents are doing. In the general mechanism problem the set of all possible messages can be very 'rich' and complex. A simplified case is that of a direct mechanism in which agents simply report their private information in their messages. Of course, they do not have to be truthful in their reports. In our framework the private information that agents have is what their true preferences are over the social alternatives. A mechanism is manipulable if by lying about his true type an agent can change the social choice to one that he desires more. We would like to have a mechanism in which lying cannot be beneficially employed and telling the truth is the dominant strategy for every agent. We call such a mechanism non-manipulable or strategy-proof since the social choice will not be vulnerable to strategic lying by any agent. Mathematical analysis shows, however, that any social choice function that is strategy-proof must be monotonic and also has to satisfy the Pareto condition. But this takes us back to the Arrow Impossibility Theorem. We already have seen that the only social choice function that satisfies these conditions is the dictatorial one. Hence we have the following striking theorem, first proved by Alan Gibbard and Mark Satterthwaite:
That dictatorial choice functions are strategy-proof is obvious. The dictator himself discloses his true preferences so that his best alternative is chosen. Others have no incentive to lie, since in any case their preferences are inconsequential. It is the converse that is the unexpected and deep result. It is reported that, when it was pointed out to Jean-Charles de Borda in the eighteenth century how easily his method of rank-order voting could be manipulated by sophisticated strategies, Borda retorted in vexation: "My scheme is only intended for honest men!" We now know that there are no non-dictatorial schemes for dishonest men! Related Projects : Axiomatic Social Choice Theory
Copyright © 2022 ICICI Centre for Mathematical Sciences |
