I've been thinking again about a classic allocation problem: we have n agents, each of which has preferences over n items, and we wish to assign one of the items to each agent. An allocation is ex post efficient if and only if it can result from random serial dictatorship, which is probably the way you've solved any such problem you've encountered in real life: the people draw straws (at some level of metaphorical remove), and one person gets his first choice, the next gets his first choice among those remaining, etc. It is fairly obvious that this will result in an allocation that is Pareto efficient (as long as agents have strict preferences), i.e. that there is no trade available after the fact that would make both parties to the trade better off (whichever agent went before the other would not want to trade); it is only slightly less involved to show that any Pareto efficient outcome can be generated by giving the agents the opportunity to pick in some order. (Lemma: at least one agent will get its first choice, or else a mutually beneficial trade would in fact exist. Make that person the first one to choose, then consider the remaining assignment problem with n-1 agents and n-1 items. The result follows from induction.)
What's left to say? Well, it turns out that there are situations in which random serial dictatorship is not "ex ante" efficient: once the mechanism has run, there is always one person who would object if you said, "hey, let's do this assignment differently," but if the people are mathematically adept and know each others' preferences, there are situations in which all agents would prefer some other mechanism from the get-go. From Bogomolnaia and Moulin's 2001 paper in JET, with items a, b, c, and d, suppose two agents prefer a>b>c>d and the other two agents prefer b>a>d>c. If the first two agents get a and c (they toss a coin to decide who gets which), and the other two get b and d, then each agent has a 1/2 chance of getting its top choice and will always get at least its third choice, while random serial dictatorship gives each agent only a 5/12 chance of getting its top choice and 11/12 chance of getting at least its third choice (i.e. a 1/12 chance of getting its last choice). An AER paper from 2011 (I think) offers an even simpler example if one is willing to use von-Neumann–Morgenstern utilities instead of the (stronger) concept of first order stochastic dominance: given 3 items, if three agents assign u(A)=3 and u(B)=0 but two of them assign u(C)=1 and one assigns u(C)=2, random serial dictatorship gives each agent each item with a probability of 1/3, but all agents get a higher ex ante expected utility from giving item C to the third agent and letting the other two toss a coin for A and B.
Generically, suppose I have expected utility maximizing agents, and I want to investigate what kinds of mechanisms I could use to assign them (randomly) objects in this fashion. If I know the agents' utility functions, and I'm a benevolent mechanism designer, I can calculate Pareto optimal mixtures of assignments. It turns out that (I'm reasonably sure) the resulting assignment can always be expressed in the following fashion: there is some positive affine transformation applied to the utility of each agent (possibly different transformations for different agents) such that the ex post utility obtained by each agent will be at least as high as the utility any other agent would have obtained from the object that agent is assigned. For example, if there is a positive probability that you will get item A, then your utility (after the necessary affine transformation) for item A is at least as high as anyone else's utility (after the necessary affine transformation) for item A. In the example of the previous paragraph, in fact, I don't have to do any affine transformations from the form in which I gave the utility functions; the agent who ends up with A assigns it utility 3, the agent who ends up with B assigns it 0, and the agent who ends up with C assigns it 2, regardless of how the coin toss turns out.
Usually, however, I want to work in an environment in which I, as the mechanism designer, don't know their utilities, so my mechanism will have to elicit their preferences in some fashion, and assign random outcomes with a probability that depends on what they indicate. Whatever mechanism I use, however weird, it will ultimately result in some mapping from sets of utility functions to some probability distribution over assignments. These probability distributions then generate expected utilities for each agent. In considering all possible mechanisms, it becomes convenient to ignore the details of the mechanisms (at least for a while), and simply consider the properties of the induced map that takes a utility function from each agent and produces an expected utility for each agent. If the agents know how the mechanism works, though, they may lie; I can only use mechanisms where no agent would prefer the outcome he could obtain by claiming to have a different utility than what he really does. If I consider the mechanisms that are "incentive compatible", and just consider the problem from the standpoint of a single agent, given whatever that agent knows about other agents' actions, the expected utility as a function of what that agent does must be "incentive compatible". It turns out that this imposes relatively few constraints, and they include a constraint we might prefer to have anyway: the expected utility must transform under positive affine transformations in the same way as the utility function does. That is to say, if reporting "u" gets you an expected utility of 5, then reporting "2u+3" must get you 13. Both functions represent the same preferences, and it is necessary that they give the same actual outcome, however it's parameterized. The only other constraint that incentive compatibility imposes is convexity. Since the function is necessarily homogeneous of degree 1 and is convex, it is the support function of some set; that is to say, whatever the mechanism is, given other agent's actions (to the extent this agent knows them), there is some set of lotteries over assignments such that this agent's expected utility from the mechanism will be the expected utility that the agent would derive from its favorite element of the set. [Update: this is actually obvious for a simpler reason. Consider the set of lotteries consisting of any lottery that would be assigned to some utility function; then if the agent, for any utility function, is assigned a lottery to which he prefers some other element of the set, that agent will lie, claiming to have the utility of an agent who is assigned the element he prefers.]
This is appealing in some ways, though unappealing in others. In a large n environment with symmetry among the agents, I might imagine that I can announce the effective set of lotteries, and that each agent is choosing among the same such set. Now, in fact, the set of options an agent has will generally depend on the choices other agents make; the announcement, therefore, would have to be made after everyone's action is taken, so this "announcement" would not be "here's your choice of lotteries, which do you prefer?", since I need your action in order to find out other agents' sets of options. It could be a useful good-faith auditing mechanism, though, to say "this is the set of options that were generated, and thus this is the lottery you chose by way of your action that implied that it was your preference, and the result of the lottery is that you get object H". However, while the effective set of choices will generally depend on other agents' actions, incentive compatibility requires that the set cannot depend on this given agent's action; in a large n environment with a normal amount of information, it might be that we can produce a set that depends only slightly on each agent's action, and thus is practically incentive compatible. It is not, however, strictly incentive compatible.
Suppose we're looking for "Nash equilibrium" type settings, in which everyone knows what everyone else will do but still chooses to do what they were going to do anyway, and we want to spell out a full mechanism. The actions of every set of n-1 agents determine the choices available to the final agent, who is free to choose among them; on the other hand, if the agent gets a real choice, the other n-1 agents will have to, by their actions, be selecting "whatever's left". "Nash equilibrium" type settings, though, may not make practical sense; the mechanism design literature includes implementation in Nash equilibrium by taking advantage of the idea that everyone knows everyone else's preferences, so that you can ask agents for each other's information. (I've assumed this away, implicitly, by suggesting that one's action is only a function of one's own preferences.)
It seems likely to me that, in situations with large numbers of individuals, I can generate shadow prices for the options such that each agent, in a pretty good Pareto efficient equilibrium, has (at least approximately) its preferred lottery among those with expected shadow price of 0 or less. I'm not quite sure of that, though. In a particular small case, suppose three individuals have preferences B>C>A, A>C>B, and A>B>C, with each indifferent between its second choice and a coin toss between the first and third choices; a coin toss between allocations BCA and CAB is, I believe, Pareto efficient, and seems in some ways like the logical lottery to hold, but it can't fit the preceding description, since 50/50 lotteries between each pair must be part of the choice set (and thus have non-positive expected shadow price) but no single item may be part of the choice set (and thus presumably each of them has a positive shadow price). Perhaps the next questions for me to answer would be 1) is there a different Pareto efficient outcome here that can be generated in the proposed fashion, 2) are these indeed part of an incentive compatible mechanism, and 3) can I characterize under what conditions this becomes a good scheme?
Update: Oh, well, I suppose I've well established that the choice sets depend on what the other agents are doing, so all that's really necessary here is that agent 1 have a 50/50 B/C option, agent 2 have a 50/50 A/C option, and agent 3 having a 50/50 A/B option, all as the respective best options. B, A, and A must respectively not be available in higher probabilities with these mixtures, so if agent 1 sees shadow prices of B>0>C, agent 2 sees A>0>C, and agent 3 sees A>0>B with equal absolute values, we could get choice sets of these sorts. In particular, B has a positive shadow price for agent 1 and a negative shadow price for agent 3; agents 1 and 2 together in some sense overdemand B, while agents 2 and 3 in some sense underdemand it. It seems reasonable to think that any option that is the first choice of one agent would have a positive shadow price for other agents in a reasonable symmetric mechanism. More generally, if there are m other agents whose first m choices are the same, then they and I can't all be allowed to choose a lottery that guarantees us an element of that set, so it seems likely that in a symmetric mechanism that, any time m agents' top m choices are the same, all other agents face a positive shadow price for each of the m items. Note, though, that the "Boston mechanism" violates this principle; if two agents have A as their first choice and B as their second, the Boston mechanism would allow other agents to simply take choice B.
Update: Suppose agents are restricted to a set U of possible utility vectors such that 1) if two elements of U are distinct, they indicate different preferences -- i.e. if u is in U, then 2*u+3 is not, and 2) U is convex. Now consider the following program: On the space Un×Rn find the graph of the correspondence from utility function profiles to feasible expected utility profiles, find a way to define and construct the closure of the convex hull of the upper contour set, and hope that its boundary represents the graph of a function from Un→Rn. That thing should be convex, and "optimal" in some sense. Can it be constructed intelligibly, and, if so, can it be done in a computationally efficient manner?
I suppose another angle is in fact to start from serial random dictatorship as a benchmark; what mechanisms might pareto-dominate it, or (in some sense) nearly do so? In the special case where the other agents all have the same preferences (preferring 1>2>3>...>n), I can choose a lottery that gives me each item with probability 1/n, or I can shift some probability from more preferred to less preferred (by other agents) items, but the constraint I face can't be fully "linearized"; for n=3, I can go from (1/3,1/3,1/3) to (0,2/3,1/3), but I can't go to (0,0.67,0.33), which I might imagine if I'm thinking in terms of trading 100/300 of the most popular item and 1/300 of the least popular in exchange for 101/300 of the second-most-popular; allowing this sort of exchange is precisely where I might expect to be able to offer gains from trade between agents with the same ordering but different vN-M preferences.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment