Category Archives: Mechanisms

“Learning About the Future and Dynamic Efficiency,” A. Gershkov & B. Moldovanu (2009)

How am I to set a price when buyers arrive over time and I have a good that will expire, such as a baseball ticket or an airplane seat?  “Yield management” pricing is widespread in industries like these, but the standard methods tend to involve nonstrategic agents.  But a lack of myopia can sometimes be very profitable.  Consider a home sale.  Buyers arrive slowly, and the seller doesn’t know the distribution of potential buyer values.  It’s possible that if I report a high value when I arrive first, the seller will Bayesian update about the future and will not sell me the house, since they believe that other buyers also value the house highly. If I report a low value, however, I may get the house.

Consider the following numerical example from Gershkov and Moldovanu.  There are two agents, one arriving now and one arriving tomorrow.  The seller doesn’t know whether the agent values are IID in [0,1] or IID in [1,2], but puts 50 percent weight on each possibility.  With complete information, the dynamically efficient thing to do would be to sell to the first agent if she reports a value in [.5,1]U[1.5,2]. With incomplete information, however, there is no transfer than can simultaneously get the first agent to tell the truth when her value is in [.5,1] and tell the truth when her value is in [1,1.5].  By the revelation principle, then, there can be no dynamically efficient pricing mechanism.

Consider a more general problem, with N goods with qualities q1,q2..qN, and one buyer arriving each period.  The buyer has a value x(i) drawn from a distribution F, and he gets utility x(i)*q(j) if he receives good j.   Incomplete information by itself turns out not to be a major problem, as long as the seller knows the distribution: just find the optimal history-dependent cutoffs using a well-known result from Operations Research, then choose VCG style payments to ensure each agent reports truthfully.  If the distribution from which buyer values is unknown, as in the example above, then seller’s learn about what the optimal cutoffs should be from the buyer’s reports. Unsurprisingly, we will need something like the following: since cutoffs depend on my report, implementation depends on the maximal amount the cutoff can change having a derivative less than one in my type.   If the derivative is less than one, then the multiplicative nature of buyer utilities means that there will be no incentive to lie about your valuation in order to alter the seller’s beliefs about the buyer value distribution.

http://www.econ2.uni-bonn.de/moldovanu/pdf/learning-about-the-future-and-dynamic-efficiency.pdf (IDEAS version).  Final version published in the September 2009 AER. I previously wrote about a followup by the same authors for the case where the seller does not observe the arrival time of potential buyers, in addition to not knowing the buyer’s values.  

“Decentralization, Hierarchies and Incentives: A Mechanism Design Perspective,” D. Mookherjee (2006)

Lerner, Hayek, Lange and many others in the middle of the 20th century wrote exhaustively about the possibility for centralized systems like communism to perform better than decentralized systems like capitalism. The basic tradeoff is straightforward: in a centralized system, we can account for distributional concerns, negative externalities, etc., while a decentralized system can more effectively use local information. This type of abstract discussion about ideal worlds actually has great applications even to the noncommunist world: we often have to decide between centralization or decentralization within the firm, or within the set of regulators. I am continually amazed by how often the important Hayekian argument is misunderstood. The benefit of capitalism can’t have much to do with profit incentives per se, since (almost) every employee of a modern firm is a not an owner, and hence is incentivized to work hard only by her labor contract. A government agency could conceivably use precisely the same set of contracts and get precisely the same outcome as the private firm (the principle-agent problem is identical in the two cases). The big difference is thus not profit incentive but the use of dispersed information.

Mookherjee, in a recent JEL survey, considers decentralization from the perspective of mechanism design. What is interesting here is that, if the revelation principle applies, there is no reason to use any decentralized decisionmaking system over a centralized one where the boss tells everyone exactly what they should do. That is, any contract where I could subcontract to A who then subsubcontracts to B is weakly dominated by a contract where I get both A and B to truthfully reveal their types and then contract with each myself. The same logic applies, for example, to whether a firm should have middle management or not. This suggests that if we want to explain decentralization in firms, we have only two roads to go down: first, show conditions where decentralization is equally good to centralization, or second, investigate cases where the revelation principle does not apply. In the context of recent discussions on this site of what “good theory” is, I would suggest that this is a great example of a totally nonpredictive theorem (revelation) being quite useful (in narrowing down potential explanations of decentralization) to a specific set of users (applied economic theorists).

(I am assuming most readers of a site like this are familiar with the revelation principle, but if not, it is just a couple lines of math to prove. Assume agents have information or types a in a set A. If I write them a contract F, they will tell me their type is G(a)=a’ where G is just a function that, for all a in A, chooses a’ to maximize u(F(a’)), where u is the utility the agent gets from the contract F by reporting a’. The contract given to an agent of type a, then, leads to outcome F(G(a)). If this contract exists, then just let H be “the function concatenating F(G(.))”. H is now a “truthful” contract, since it is in each agent’s interest just to reveal their true type. That is, the revelation principle guarantees that any outcome from a mechanism, no matter how complicated or involving how many side payments or whatever, can be replicated by a contract where each agent just states what they know truthfully to the principal.)

First, when can we do just as well with decentralization and centralization even when the revelation principle applies? Consider choosing whether to (case 1) hire A who also subcontracts some work to B, or (case 2) just hiring both A and B directly. If A is the only one who knows B’s production costs, then A will need to get informational rents in case 1 unless A and B produce perfectly complementary goods: without such rents, A has an incentive to produce a larger share of production by reporting that B is a high cost producer. Indeed, A is essentially “extracting” information rents both from B and from the principal by virtue of holding information that the principal cannot access. A number of papers have shown that this problem can be eliminated if A is risk-neutral and has an absence of limited liability (so I can tax away ex-ante information rents), contracting is top-down (I contract with A before she learns B’s costs), and A’s production quantity is known (so I can optimally subsidize or tax this production).

More interesting is to consider when revelation fails. Mookherjee notes that the proof of the revelation principle requires 1) noncollusion among agents, 2) absence of communication costs, information processing costs, or contract complexity costs, and 3) no possibility of ex-post contract renegotiation by the principal. I note here that both the present paper, and the hierarchy literature in general, tends to shy away from ongoing relationships, but these are obviously relevant in many cases, and we know that in dynamic mechanism design, the revelation principle will not hold. The restricted message space literature is still rather limited, mainly because mechanism design theory at this point does not give any simple results like the revelation principle when the message space is restricted. It’s impossible to go over every result Mookherjee describes – this is a survey paper after all – but here is a brief summary. Limited message spaces are not a panacea since the restrictions required for limited message space to motivate decentralization, and particularly middle management, are quite strong. Collusion among agents does offer some promise, though. Imagine A and B are next to each other on an assembly line, and B can see A’s effort. The principal just sees whether the joint production is successful or not. For a large number of parameters, Baliga and Sjostrom (1998) proved that delegation is optimal: for example, pay B a wage conditional on output, and let him and A negotiate on the side how to divvy up that payment.

Much more work on the design of organizations is needed, that is for sure.

http://people.bu.edu/dilipm/publications/jeldecsurvrev.pdf (Final working paper – published in June 2006 JEL)

“Dynamic Costs and Moral Hazard,” G. Arie (2011)

(A quick note: it’s almost job market time here in the world of economics. Today’s paper is a job market paper by Guy Arie, a theorist here in MEDS who I saw present a really interest model the other day. If your department is looking for a micro theorist this year, definitely give a skim through the Northwestern candidates’ papers; we have 8-10 students in theory, and the job market talks I’ve been to have been very nice overall. OK, on to Arie’s paper…)

All but the simplest dynamic mechanism design problems prove difficult, particularly because the intuition of the revelation principle fails. In a dynamic problem, I can not only lie about my type, but I can also lie about my type conditional on the history generated by the mechanism. A particular worry among agents is that if, in a truthful mechanism, the principle can elicit my type in period 1, he will then use that information to punish me in future periods (so-called “ratcheting”). The constraints in dynamic mechanism design, then, are much larger: I am going to need to worry about history-dependent deviations, and I am going to need to be sure that ratcheting is not a concern.

Arie studies what looks like a straightforward contracting problem. Imagine a risk-neutral salesman selling over a year (a technical note: the salesman have limited liability so I can’t just sell them the firm right away). They have N potential buyers which they can try to sell to. If they try to sell to one in a given period, a sale is made with probability p. Under any sensible contract, the salesmen will try to sell to the easiest clients first, so that the effort needed to make a sales attempt is increasing in the number of sales attempts I’ve made previously. The salesmen’s boss can only observe the number of sales made, but does not know how many sales have been attempted. A successful sale is worth V to the boss.

Now hopefully you see the problem: if I knew how may sales had been attempted, I would pay the salesmen just enough to cover his cost of effort at any given time, and I would ask him to keep making sales until the wage payment, adjusted for the probability of success, was higher than the value of the additional sale. The salesman will make exactly zero profits after accounting for his cost of effort. But when the boss does not know how many sales are attempted, the salesman has a nice deviation: just sit on his laurels in period 1, and only then start trying to make sales. The payment for each successful sale is now higher than the cost to the salesman of attempting the sale because the salesman has “delayed” making the easy sales until later in the year when the “bonus” is higher. Worse, if I try to condition payments on past sales, a salesmen who is unlucky with his first few “easy” sale attempts will just stop working altogether because he will be getting paid for “easy” sales but will in fact be trying to make relatively hard sales. Evidently these problems actually comes up empirically.

So what can the boss do? The standard dynamic moral hazard solution without increasing costs but with limited liability would be something like the following: have the salesman try to sell, giving him “credit” for each sale. Once he has enough credit, give him the firm (meaning give him the profits from each future sale). The promise of this big bonus in the future is incentive enough for the employee to work hard now. If he gets unlucky and does not make early sales, fire him, because no matter how lucky he gets in the future, he’ll never make back enough credit to get the firm.

With increasing costs, things are not so simple. Arie manages to write the problem as a linear program – binary effort and risk neutrality are quite important here – and then notes that it is not obvious that we can apply a one-stage deviation principle; indeed, a simple example shows that checking one-stage deviations is not equivalent to checking incentive compatibility here. But, the problem can be transformed, as all linear programs (as well as many other mathematical programs!) into a dual. The dual has nice properties. Essentially, the choice variables of the dual will be the shadow prices on the ex-ante probability I will ask the salesman to try to sell after a given public history. If that shadow price is strictly positive, then asking the salesman to try harder after a given history increases the principle’s profits, even accounting for the dynamic effects such a request has on incentives to shirk in the past. The dual formulation offers a number of other nice interpretations which make the potential solution easier to see – the usefulness of shadow prices should come as no surprise to economists, given that it has been the critical element in results going back at least to Ramsey’s taxation paper and Hotelling’s resource extraction model, both in the early part of the 20th century.

So what is the optimal contract? Don’t pay the agent anything except “credit”. When this credit gets too low, fire the agent. When credit is sufficiently high, pay the agent a fixed rate per success over the next N periods, where the pay each period is just high enough to incentivize the agent to exert effort N periods in the future. Essentially, the agent is paid a very high piece rate at the end of the contract. Until that point, successful sales are rewarded only by conditions making it easier for the agent to begin getting his bonuses; e.g., “if you make a sale today, then after two more consecutive sales, I’ll put you on the bonus schedule for a month, but if you don’t make a sale today, you’ll need four more sales, and will only get the bonuses for two weeks”. And why do I tell the employee only to work for N more periods rather than just give him the firm and let him work until the moment it is too costly to exert any more effort? Essentially, I am destroying the “value” of the future firm after every failed sale in order to keep the agent from shirking; by reducing the future value of the firm after a failure, I can still give the agent who was unlucky some reason to keep working, but in such a way that the destroyed future value of the firm makes shirking unprofitable.

http://www.kellogg.northwestern.edu/faculty/arie/GuyArie_DynamicCosts.pdf (Job market working paper)

“Collaborating,” A. Bonatti & J. Horner (2011)

(Apologies for the long delay since the last post. I’ve been in that tiniest of Southeast Asian backwaters, East Timor, talking to UN and NGO folks about how the new democracy is coming along. The old rule of thumb is that you need 25 years of free and fair elections before society consolidates a democracy, but we still have a lot to learn about how that process takes place. I have some theoretical ideas about how to avoid cozy/corrupt links between government ministers and the private sector in these unconsolidated democracies, and I wanted to get some anecdotes which might guide that theory. And in case you’re wondering: I would give pretty high odds that, for a variety of reasons, the Timorese economy is going absolutely nowhere fast. Now back to the usual new research summaries…)

Teamwork is essential, you’re told from kindergarten on. But teamwork presents a massive moral hazard problem: how do I make sure the other guy does his share? In the static setting, Alchain-Demsetz (1972) and a series of papers by Holmstrom (May He Win His Deserved Nobel) have long ago discussed why people will free ride when their effort is hidden, and what contracts can be written to avoid this problem. Bonatti and Horner make the problem dynamic, and with a few pretty standard tricks from optimal control develop some truly counterintuitive results.

The problem is the following. N agents are engaged in working on a project which is “good” with probability p. Agents exert costly effort continuously over time. Depending on the effort exerted by agents at any given time, a breakthrough occurs with some probability if the project is good, but never occurs if the project is bad. Over time, given effort along the equilibrium path, agents become more and more pessimistic about the project being good if no breakthrough occurs. The future is discounted. Agents only observe their own effort choice (but have correct beliefs about the effort of others in equilibrium). This means that off-path, beliefs of effort exertion are not common knowledge: if I deviate and work harder now, and no breakthrough occurs, then I am more pessimistic than others about the goodness of the project since I know, and they don’t, that a higher level of effort was put in.

In this setting, not only do agents shirk (hoping the other agents will pick up the slack), but they also procrastinate. Imagine a two-period world. In a two period world, I can shift some effort to period 2, in the hope that the other agent’s period 1 effort will lead to a success. I don’t want to work extremely hard in period 1 when all that this leads to is wasted effort because my teammate has already solved the problem in that period. Note that this procrastination motive is not optimal when the team is of size 1: you need a coauthor to justify your slacking! Better monitoring here does not help, surprisingly. If I can see how much effort my opponent puts in each period, then what happens? If I decrease my period 1 effort, and this is observable by both agents, then my teammate will not be so pessimistic about the success of the project in period 2. Hence, she will work harder in period 2. Hence, each agent has an incentive to work less in period 1 vis-a-vis the hidden action case. (Of course, you may wonder why this is an equilibrium; that is, why doesn’t the teammate play grim trigger and punish me for shirking? It turns out there are a number of reasonable equilibria in the case with observable actions, some of which give higher welfare and some of which give lower welfare than under hidden action. The point is just that allowing observability doesn’t necessarily help things.)

So what have we learned? Three things in particular. First, work in teams gives extra incentive to procrastinate compared to solo work. Second, this means that setting binding deadlines can be welfare improving; the authors further show that the larger the team, the tighter the deadline necessary. Third, letting teams observe how hard the other is working is not necessarily optimal. Surely observability by a principal would be welfare-enhancing – the contract could be designed to look like dynamic Holmstrom – but observability between the agents is not necessarily so. Interesting stuff.

http://cowles.econ.yale.edu/P/cd/d16b/d1695.pdf (Final Cowles Foundation WP – paper published in April 2011 AER)

“Contracting with Repeated Moral Hazard and Private Evaluations,” W. Fuchs (2007)

Firms often want to evaluate employees subjectively or using private information – feedback from an employee’s clients, for instance – not available to the agent. Solving repeated games with private monitoring and no verification is difficult. Using some clever mathematics, William Fuchs merges the results of MacLeod (2003), where in a one-shot game firms must burn money sometimes if they are to incentivize workers, and Levin (2003), where optimal infinite reputational contracts are considered. Fuchs is different from MacLeod in that he considers a finite repeated game, rather than a one-shot game, and different from Levin in that he shows that the “full review” property Levin uses to solve for a pseudo-optimal contract is actually restrictive: a firm can do better by bundling reviews and termination periods such that reviews are only held every T periods.

Under risk neutrality, the usual tradeoff will guide any solution: firms need to punish workers for bad realizations of output, but firms must not have an incentive to lie to the employee, since otherwise they will report output is low when it is actually high, and the proposed contract will not be an equilibrium.

In either the finite or the infinite period case, the intuition above suggests that after any realization, the agent’s continuation value must be higher if the output was higher (to incentivize him to work) and the principle’s continuation value must be the same no matter the output (to incentivize her not to lie). In the finite case, this requires money to be burned at some point if the agent is going to be incentivized to always put in effort, since sometimes that effort will result in low output, and the principle can’t earn surplus by reporting low surplus: rather, he just has to burn the money. A footnote in this paper notes that this type of money burning actually does sometimes occur: in professional baseball, when players are fined by their teams, the team gives the money to charity rather than keeping it.

It is also straightforward to show that for any finite-period relational contract in the Fuchs setting, there is a payoff-equivalent contract that just pays efficiency wages to the agent each period (i.e., pays the agent his expected production given full effort) until he is fired. No bonuses are necessary. Essentially, the principle’s full value from the original contract in period 0 is paid to her by the agent; the relational contract thereafter makes the principle indifferent between firing and not firing the agent in every period. That is, the principle has no incentive problem. Let the agent collect the remaining surplus in every period. The agent will not want to quit because he collects all of the surplus after period 0. Making the agent work with full effort until termination just requires setting the termination date such that the appropriate amount of money burning occurs.

The previous results lead immediately to the following link between unlimited money-burning in dynamic games and equilibrium results in static games: if I can burn as much value in the last period as I want, and I can also just pay the agent (accounting for discounting) his wage in the final period, then in this equilibrium there is no need to give the agent updates about how he is doing (since I expect full effort in every period anyway), and the whole problem just collapses to a static game.

In the infinite-period game, the finite results suggest that as the length of the game goes to infinity, an optimal contract burns an arbitrarily large amount of money arbitrarily far in the future. This isn’t satisfying; for one, we only release information to the agent “at the end” whch is infinitely far away. Fuchs instead endogenizes money burning by capping the amount of money burned at the total surplus of the game. He then extends Levin by considering T-period review contracts, where the principal reveals her evaluation of the agent every T periods, rather than every period as in Levin. The results above that termination contracts can be found which are payoff-equivalent to contracts involving complicated wage and bonus schemes still hold, so let a T-period review contract fire the agent with probability B if performance is “unsatisfactory” after T periods. If the employee passes evaluation, a new T-period review starts with a clean slate. Linking as many periods as possible together is optimal because the amount of money the principle needs to burn in each evaluation period is independent of the length of the period; the intuition here is that if get effort from the agent if the principle pledges to burn money far in the future, then that same pledge will be even stronger in future periods since the future where money is burned is not as far away.

There are two simple notes at the end of the paper on how to avoid money burning. If there are two agents, as in Lazaer and Rosen tournaments, the principle can credibly commit to just pay whichever agent produces higher output, so no burning is necessary. Alternatively,the principle can hire a manager, pay her a fixed wage, and have the manager report publicly whether output was good or not; since the manager’s wage is independent of the report, there are no longer any incentive problems.

Even with these nice results, the general problem of optimal relational contracting is still open; dynamic mechanisms with imperfect monitoring are hard.

ftp://ftp.cemfi.es/pdf/papers/wshop/paper%20W.Fuchs.pdf (Working paper – Final version published in AER 2007)

“Perfect Implementation,” S. Izmalkov, M. Lepinski and S. Micali (2010)

Let’s continue on the theme of secrecy from the last post with a recent GEB by a group of computer scientists. In standard mechanism design, there is either a lot of information revealed or there is a lot of trust placed in some mediator (which we call “the mechanism”). Consider a second-price auction. Either the auctioneer reveals everyone’s bids after bidding or the bidders must trust the auctioneer is not “making up” a second bid arbitrarily close to the highest bid, which the auctioneer certainly has an incentive to do. Revelation ex-post is worrying, though. If bidders are revealing their types, they may wish to shade or randomize their bids so that their competitors in the same industry do not learn what value they place on an object.

Micali, one of the coauthors of this paper, has a series of papers in the 1980s about “zero-knowledge” proofs, which essentially show a method for proving a statement to a verifier with high probability, but not giving the verifier details of how to do the proof. This new paper is a similar idea, applied to mechanism design. We want to find a mechanism that is strategically equivalent to the original mechanism, that preserves the privacy of the players (to the level of the original game – in the second-price auction, there is no way around revealing the “private” information that the ex-post winner had the highest private value), and that is not too computationally complex.

Let’s ignore complexity and focus on the first two criteria. A “private” deterministic mechanism is surprisingly simple. Let the action consist of reports of length k-bits; that is, if the action space is the integers 0 to 100, these numbers can be represented in binary using 7 bits. Let g(m1,m2) be the deterministic outcome function mapping messages (from 2 players, in this case) to outcomes. The mechanism creates a matrix of sealed envelopes containing g(m(i),m(j)), where the matrix is of size IxJ where I is the number of action available to player 1, and J for player 2. Player 1 is then given this matrix of envelopes and is allowed to permute the row however she wishes, but ensuring that the row containing m(i) is on top. Player 2 is then given this permuted matrix and is allowed to secretly permute the columns, but ensuring that m(j) is on the left. The mechanism then opens only the envelope on the top left. This gives away only information that would be known in the non-“private” mechanism (i.e., in a second-price auction, it would give away the value submitted by the loser and the fact that the winner submitted a higher value) and does not require anyone to trust a secret mediator.

Izmalkov et al do not particularly like this mechanism because it involves 2^(2k) envelopes, so as the action space grows, the “number of envelopes” gets very large very quickly. The authors use some well-known results in complexity theory to show that since the outcome function can be represented using only a fixed number of elementary operations on secret enveloped which encode each player’s action, there is a “not-too-complex” way to privately and verifiably implement any mechanism.

A nice result, then. My remaining comments have solely to do with style. I’m all for cross-disciplinary work, but I consider customs and traditions within a field to be a critical part of paradigmatic science. That is, economics and law and computer science and literary criticism all have certain styles in how research is presented, and those styles exist so that novel results can be efficiently transmitted to members of a given field. The results in this paper are simply presented in the style of a computer science conference paper. Sections of essay-like paragraphs, common in economics, are instead replaced with oddly mechanistic notes and side-comments. The action space is represented in terms of bit complexity instead of in the standard economic manner, and I don’t see anything that couldn’t have easily been “translated” into usual econ-talk. The majority of the paper discusses results in computational complexity that, frankly, are going to be much less interesting to the average GEB reader than the initial result on private-mechanism existence; these results on complexity are presented at the expense of the type of results an economic theorist would be most interested in. For instance, if the action space is a continuum, is there a “private” mechanism satisfying strategic equivalence? Who knows – it is never discussed. These types of issues really need to be hashed out before papers are published in the top journals in our field.

http://dspace-test.mit.edu/handle/1721.1/50634 (Final WP version published at MIT’s lovely repository of research. The published version is in GEB 2010.

“Relational Incentive Contracts,” J. Levin (2003)

In the real world, there is a lot of information that simply can’t be contracted on, whether for legal reasons, for information verification reasons, or for cost of contracting reasons. Nonetheless, we still see attempts to maintain incentive structures even without contracts when a relationship in repeated: consider a worker in a long-term relationship with a firm who expects a bonus, given at the firm’s discretion, each year. Jon Levin – fair bet for this year’s Clark? – calls these “relational contracts,” where the incentive to not break the implicit equilibrium contract comes from a desire to not get minmax punished for the rest of the game. What might an optimal repeated relational contract look like if this is the only incentive agents have not to deviate ex-post, under various informational assumptions?

In general, this will be a very difficult problem; even today, fully specifying general optimal mechanisms has made little progress since Tirole and Laffont (1988). Levin has a clever trick, though, that shows some intuition from the auction theory literature. If every actor in the game has quasilinear utility and is risk-neutral, then there is no scope for risk-offloading in the optimal contract, and further simple money transfers in any period can be used, in one shot, to stand in for potentially complicated multi-period reward and punishment strategies. In particular, if any self-enforcing contract can achieve total average surplus per period s, then any outcome given each player at least her minmax with total surplus below s is achievable in equilibrium. This is not just a variation of Fudenberg-Levine-Maskin’s 1994 folk theorem for repeated games (since the discount rate is arbitrary here), but rather just comes from making one of the actors pay the other a lump sum in period one: incentives at all future times do not change and each actor still gets at least the minmax, so the equilibrium remains. But now note that the maximum social surplus that can be achieved is achievable with a stationary incentive structure, meaning incentives that depend only on current period variables. The reason is that if I’m going to maintain some incentive with a complicated string of rewards and punishments in the future, those rewards and punishments have an equilibrium expected value to the actor. By risk-neutrality and quasilinearity, I can just transfer the expected sum of that string to (or from) the actor in the current period. There is a brief argument ensuring that in equilibrium, since the principle’s action is perfectly observed by both agents, there is no reason the principle would destroy or create social surplus in the future, so the total social surplus is just a fixed value to be moved shifted among the two players.

With these nice properties in hand, it turns out that optimal relational contracts have a relatively simple form. With perfect information, the relevant constraints are that neither the principle nor the agent wants to walk away from the promised continuation utility, which is just the discounted difference of all future stage game payoffs higher that the outside option. The IC constraint inducing optimal effort for the agent is the normal one, but there is also a dynamic constraint which requires the largest total payment in any period to the agent minus the smallest total contingent payment to be bounded, since if not, one of the actors has an incentive to walk away and take their outside option forever at the end of the current contract instead of paying the specified bonus transfer. This limitation on incentives is essentially the cost of not being able to contract.

What about the limited information cases, moral hazard and adverse selection? Let the agent have a cost of production that is unobservable by the principle, and let that agent choose a level of effort which is observable. Make the standard assumptions on the cost function that allow full separation of types in the static hidden information problem. The lack of contracts in the dynamic problem give an highest-total-surplus equilibrium where equilibrium effort for all types is lower than the first-best. By self-selection arguments, getting more effort from a higher cost type means raising the slope of the bonus schedule in effort. But the total variance in incentives is bounded as described above. So sometimes, relatively high cost types are all pooled at a suboptimal level of effort.

If there is moral hazard rather than hidden information (agent’s cost is observed by everyone, but not agent’s effort), assuming normal Rogerson conditions so the first-order approach can be used to solve the program, risk-neutrality allows us to use a “one step” incentive system: if output is high enough, pay the maximal bonus, else pay the minimal one.

A couple final notes. In the case of subjective performance measures (only the principal observes final output which has some stochastic component), the optimal contract is a termination contract: if output is sufficiently low, terminate the job, else pay a bonus. The reason termination is necessary is that the principal must be punished for trying to cheat the agent by reporting low output, and terminating the job punishes the principal by giving him only his outside option forever. Second, there’s no worry here about unrealistically using an infinite game, since we discount: you can let some exogenous chance of the contract ending at any time enter the problem through the discount rate and by risk-neutrality this interpretation is not worrisome.

http://www.stanford.edu/~jdlevin/Papers/RIC.pdf (Final version, AER 2003)

“Nash Implementation with Partially Honest Individuals,” B. Dutta & A. Sen (2009)

Sometimes a lovely, unintuitive result seems a too simple once you see the proof. Here’s one, from Dutta and Sen, that I bet you didn’t expect.

Consider Nash implementability of social choice functions; that is, we want to know if, for some social choice correspondence (a mapping from preferences R to outcomes), there exists a game form whose only Nash equilibrium outcomes given preferences is in the social choice correspondence (scc). Maskin famously showed that, with three or more players, any social choice correspondence satisfying No Veto Power (if (n-1) of the players top-rank an outcome A, then the scc must select it) and Maskin Monotonicity (roughly, if the scc selects outcome A under preferences R, but not under R’, then at least one agent must reverse their ranking of a and some other outcome b). It turns out that Maskin Monotonicity is a super-strong assumption, actually: the scc must be dictatorial (Muller-Satterthwaite), and if it is a function, then the scc must be constant regardless of preferences (Saijo 1987, JET).

Dutta and Sen say, fine, but what if a single agent, whose identity is not known to the mechanism designer, has lexicographic preferences for honesty. That is, the agent maximizes her preferences while playing the designer’s chosen game form, but when two actions (here, the relevant action space is just revelation of the preference ordering) give the same outcome, and one of those actions is truthful, then the agent takes the truthful action. It turns out that this simple assumption allows any scc with three or more agents to be implemented!

The proof is simple if you know Maskin’s result. The game is the same as in Maskin: each agent’s strategy is to reveal the preference ordering of all agents, a recommended action, and an integer. As in Maskin, this is a game of complete information, so every agent but the designer knows other agent’s preference ordering; Matt Jackson has a paper on Bayesian implementability if you don’t like this assumption. If at least (n-1) reveals the same thing, and if the action A recommended is such that f(R)=A in the specified social choice correspondence, then that action is chosen. Otherwise, the action announced by the agent who chose the highest integer is implemented.

No veto power alone gets us everything except ensuring that there is no equilibrium where every agent deviates to some false preference orderings R’ and action a’. To show there is no such equilibrium, we can use Maskin Monotonicity. Alternatively, just note that with lexicographic honesty, such a deviation cannot be an equilibrium. By the (n-1) part of the game outcome above, the honest agent can deviate to (R,a) and not change the outcome. In that case, he prefers the honest revelation (R,a). So everyone revealing (R’,a’) is not an equilibrium. This is literally the whole proof. Basically, Maskin’s proof involved a snitch who is incentivized by monotonicity to deviate and entire the integer subgame when everyone reveals (R’,a’). Here, lexicographic honesty does the same job.

A few final notes: Dutta and Sen, of course, prove many more results, particularly for the more difficult problem of two-agent implementability; the general difficulty there is that one person deviates, since there are only two agents, you don’t know who deviated as the designer. They also show, with some reasonable restrictions on mechanism types, that if even there is an epsilon chance that a single agent may have lexicographic honesty, that is enough to allow existence of a mechanism implementing any scc. This paper does not get around a well-known objection to the Maskin mechanism, however: the strategy space is not compact. In particular, the integers are unbounded. Lombardi and Yoshihara (2011) show that some reductions in the strategy space far weaker than requiring compactness and requiring that agents know only their own preferences nonetheless drastically change what is Nash implementable with lexicographically honest players.

http://www2.warwick.ac.uk/fac/soc/economics/research/papers_2009/twerp_920.pdf (2009 Working Paper; hat tip to Dimitrios Diamantaras for the reference)

“Optimal Auction Design Under Non-Commitment,” V. Skreta (2011)

Consider a government selling an oil or timber tract (and pretend for a second that the relevant uncertainty is over how effectively the buyers can exploit the resource, not over some underlying correlated value of the tract; don’t blame me, I’m just using the example from the paper!). If buyers have independent private values, the revenue-maximizing auction is the Myerson auction, which you can think of as a second-price auction with a reserve price. But if a reserve price is set, then sometimes the auction will end with all bids below the reserve and the government still holding the resource. Can the government really commit not to rehold the auction in that case? Empirical evidence suggests not.

But without this type of commitment, what does the optimal sequence of auction mechanisms look like for the government? There is a literature beginning in the 80s about this problem. In any dynamic mechanism, the real difficulty comes down to the fact that, in any given stage, buyers do not want to reveal their actual type (where type, in our example, is their private value for the good). If they reveal in period 1, then the seller can fully extract their surplus in period 2 because private values are now public information. So there is a tradeoff often called the “ratchet effect”: mechanism designers can try to learn information in early stages of the dynamic mechanism to separate types, but will probably have to compensate agents in equilibrium for giving up this information. On a technical level, the big problem is that this effect means the revelation principle will not apply. This, you won’t be surprised, is a huge problem, since finding an “optimal” mechanism without the revelation principle means searching over any way to use messages that imply something about types revealed in some sequence, whereas a direct truthful mechanism means searching only over the class of mechanisms where every agent states his type and does not want to mimic some other type.

In a clever new paper, Vasiliki Skreta uses some tricks to actually solve for the optimal sequential auction mechanism. McAfee and Vincent (GEB 1997) proved that if an auctioneer is using a first price or second price sequence of auctions, revenue equivalence between the two still hold even without commitment, and if the discount rate goes to 1, seller revenue and optimal reserve prices converge to the static case. This result doesn’t tell us what the optimal mechanism is when discount rates matter, however; oil tract or cellular auctions may be years apart. Skreta shows that the highest perfect Bayesian equilibrium payoff is achieved with Myerson style reserve prices in each period and shows how to solve for these (often numerically due to their formula complexity). In the case of symmetric bidders, the optimal mechanism can be written as a series of first price or second price auctions, with reserve prices varying by period.

The actual result is probably less interesting than how we reach it. Two particular tricks are worth noting. First, Skreta lets the seller have total flexibility in how much information to reveal to buyers. That is, after period 1, if there is no sale the auctioneer can reveal everyone’s bids to each bidder, or not, or do so partially. Using a result from a great 2009 paper, also by Skreta, it turns out that with independent private values, it does not matter what information the seller reveals to the buyers in each period. That is, when looking for optimal mechanisms, we can just assume either than every bidder knows the full history of bids by every other bidder, or assume that every bidder knows only their own full history of bids. The proof is difficult, but the intuition is very much along the lines of Milgrom-Stokey no-trade: all agents have common priors about other agents’ types, and auctioneers can lie in their information disclosure, so if a seller is willing to offer some disclosure, it must be that this disclosure has negative expected value for bidders. For buyers to be willing to “offer their type” in an early stage to the auctioneer, they must be compensated positively. Since disclosure can’t be good for both buyer and seller by a type of Milgrom-Stokey result, any information disclosure rule that is able to gather good information has expected value zero for the seller. Obviously, I’m eliding the difficulties in the proof, but this is the basic idea.

The second useful result is about when you might want to separate types as the auctioneer. Imagine you are committing to holding the auction no more than 6 times. Should you separate early or late? It turns out you want to separate types as late as possible. That is, the optimal auction will, in period 1, sell to the highest bidder above some cutoff. The auction does want to separate types above that cutoff. But below that cutoff, buyers know that by not pooling their types, they are giving the auctioneer information about their private values which will be used in period 2 to extract rents. In equilibrium in period 1, then, the low-value buyers will need to be compensated to not choose actions that pool their types. This compensation turns out to be so expensive that the informational gains to the seller in period 2’s auction are not valuable enough to make it worth the cost.

A few comments: really what we care about here is what happens as the number of auctions which may occur goes to infinity. The principle is proven to be the same – cutoff rules are optimal – but how do those cutoff rules as the lack of commitment gets arbitrarily bad? What revenue properties are there? For instance, for various discount rates in the 2-bidder, uniform [0,1] private value auction, does seller revenue approach zero? Or does it asymptote to some fraction of the revenue in the auction with commitment? I think these types of applied theory questions are quite important, and should be answered here. My hunch is that even in simple cases the mathematics becomes too difficult as the number of periods grows large, and this is why Skreta didn’t include it. If the loss to the auctioneer from non-commitment turns out to be really large, we already know the “optimal” auction without commitment is to assign the rights to the auction to some second seller who, perhaps for contractual reasons, actually can commit not to resell. If the loss in some simple numerical examples is no more than 10%, then no big deal.

http://sites.google.com/site/vskreta/research/auctions_rev_3.pdf (WP version, Jan 2011)

“Multiple Referrals and Multidimensional Cheap Talk,” M. Battaglini (2002)

Mechanism design and game theory is often radically different when the state is multidimensional instead of unidimensional: finding the differences has been one of the most productive parts of economic theory over the past decade. This classic paper by Battaglini is the one to read when it comes to multidimensional cheap talk.

Consider a president listening to two expert advisors, or a median voter in Congress listening to two members of a committee. Everyone is biased. The experts know exactly the results of some policy, but the receiver does not: that is, the outcome x=y+a, where y is the policy chosen, and a is some noise whose realization is known only to experts. When the policy and state are unidimensional, a number of classic results (Gilligan & Krehbiel 1989, for example) note that cheap talk from the experts can only be influential in equilibrium if the biases of the expert are small. Even then, equilibrium existence relies on out-of-equilibrium beliefs (the solution concept is Perfect Bayesian Nash) that are in some sense crazy.

This turns out not to be true in a multidimensional world. Consider potential policies which will affect both global warming and unemployment, where these are mapped into utilities in two-dimensional Euclidean space. The two experts know exactly how these policies will affect the environment and the economy, while the receiver only knows the effect of policy y, and knows that the signal a has expected value of zero. In this case, it turns out full revelation is almost always possible, no matter what the biases are; this result does not rely on crazy out-of-equilibrium beliefs and it is robust to a specific form of collusion among the experts.

What magic is being used? The basic idea is to find dimensions upon which each agent has preferences that are aligned with those of the receiver, and ask agents only about those preferences. Intuitively, ask the environmentally-conscious guy about which policy is best given that the economy is affected in the optimal way, and ask the economically-minded guy about which policy is best for the environment given that the economy is affected in the optimal way. Mathematically, let the optimal outcome of the receiver be represented at the origin, and consider the vectors tangent to each expert’s indifference curves at the origin. Ask each expert only to reveal a dimension of the state he prefers along this line in two-dimensional space. By construction, if an expert has to choose from only that line, he will choose the origin. This intuition will always work as long as utility is quasiconcave and the gradients of each agent’s utilities are linearly independent at the origin.

This clears up some puzzles in political economy. For instance, the unidimensional result suggested that biased committees are uninformative, but committee members in Congress tend to be made up of Congressmen with the strongest biases. So why do such committees persist if they aren’t influential? Battaglini’s result shows that on multidimensional problems, committees are indeed useful, even when made up of very biased members, because they still transmit information to Congress at large in equilibrium.

A quick mathematical caveat: Ambrus and Takahashi note in a 2008 Theoretical Economics that Battaglini’s result is not just a dimensionality of state space argument, but also one that relies on the state space being the entire Euclidean space. When the state space is compact (say, the policy is spending on education and military, and there is a fixed budget), it is not true, under some robustness conditions, that information is always fully revealed. The trick is dealing with out-of-equilibrium cases that are “impossible”, such as when the strategies of the experts imply that the optimal spending is strictly greater than the budget. If you like Battaglini’s paper, it’s probably worth taking a look at Ambrus & Takahashi.

http://www.princeton.edu/~mbattagl/cheaptalk.pdf (Final WP – published in Econometrica 2002)

%d bloggers like this: