You are currently browsing rvohra’s articles.
There is a debate underway about how effective Israel’s iron dome system is in protecting populated areas from missile attacks. On the pro side it is argued that somewhere between 85% to 90% of incoming missiles are destroyed. The con side argues that the proportion is much smaller, 40% or less. A large part of the difference comes from how one defines `destroy’. Perhaps a better term would be intercept. It is possible that about 90% of incoming missiles are intercepted. However, a missile once intercepted may not have its warhead disabled, making at least one of the fragments that falls to ground (in a populated area) dangerous.
While nailing down the actual numbers may be interesting, it strikes me as irrelevant. Suppose that any incoming missile has a 90% chance of being intercepted and destroyed (which is the claim of the builder of the iron dome technology). If the attacker launches N missiles and iron dome is deployed, the probability (assuming independence) not a single one making it through is (0.9)^N. Thus, the probability of at least one missile making it through the `dome’ is 1 – (0.9)^N. If N is large, this is large. For example, for N = 10, the probability that at least one missile makes its way through is at least 60% (thanks to anonymous below for correction). Thus, as long as the attacker has access to large quantities of missiles, it can be sure to get missiles through the dome.
In the course of a pleasant dinner, conversation turned to dictatorship and the organization of markets. At this point, Roger Myerson, remarked upon the absence of inter-species trade. He was not, of course, referring to trade with alien beings from another planet (who would have discovered correlated equilibrium before Nash equilibrium). Rather, the absence of trade with, say, monkeys. Adam Smith, went further and denied the possibility of trade between animals.
Nobody ever saw a dog make a fair and deliberate exchange of one bone for another with another dog. Nobody ever saw one animal by its gestures and natural cries signify to another, this is mine, that yours………
There is a long history of interactions between men and monkeys of various kinds. Monkeys have been marauders of crops, domestic companions, religious symbols and commodities (meat). The interactions between the species seems to fall into one of three categories: pure conflict (keeping out marauders), long run relationships (pets) or exploitation (used in labs and as entertainment). However, no examples of what one might call trade in the sense of voluntary arms length transactions involving barter. For example, why don’t villagers `pay’ bands of roving monkeys to not pillage?
There is evidence to indicating they would be capable of understanding such transactions. Gomes and Boesch, for example, suggest that monkeys trade meat for sex. Then, there is Keith Chen’s monkey study which suggests that one could teach (some) monkeys about money. From the Jesuit traveller Jose de Acosta in the 1500′s we have the following charming account:
I sawe one [monkey] in Carthagene [Cartagena] in the Governour’s house, so taught, as the things he did seemed incredible: they sent him to the Taverne for wine, putting the pot in one hand, and the money in the other; and they could not possibly gette the money out of his hand, before he had his pot full of wine.
A little known fact about Canada is that it is the world’s largest producer of famous Americans. Recall, for example, John Kenneth Galbraith, Wayne Gretzky, William Shatner, Michael J. Fox, Malcolm Gladwell, Shirley Tilghman and Keanu Reeves. Some have suggested that Obama is a Canadian, leading to a split in the birther movement between the original birthers and the neo-birthers. Originalists believe that Obama was sired in a Kenyan village, imbued with an anti-colonial mindset, leavened by Saul Alinsky radicalism and smuggled into the US with the intent of turning the US into an Islamic caliphate. The neo-birthers believe that this beggars belief. It is simpler, they say, to believe that Obama is Canadian.
Nate Silver, needs no introduction. While I should have read his book by now, I have not. From my student Kane Sweeney, I learn I should have. Kane, if I may ape Alvin Roth, is a student on the job market paper this year with a nice paper on the design of healthcare exchanges. Given the imminent roll out of these things I would have expected a deluge of market design papers on the subject. Kane’s is the only one I’m aware of. But, I digress (in a good cause).
Returning to Silver, he writes in his book:
One of the most important tests of a forecast — I would argue that it is the single most important one — is called calibration. Out of all the times you said there was a 40 percent chance of rain, how often did rain actually occur? If over the long run, it really did rain about 40 percent of the time, that means your forecasts were well calibrated
Many years ago, Dean Foster and myself wrote a paper called Asymptotic Calibration. In another plug for a student, see this post. An aside to Kevin: the `algebraically tedious’ bit will come back to haunt you! I digress again. Returning to the point I want to make; one interpretation of our paper is that calibration is perhaps not such a good test. This is because, as we show, given sufficient time, anyone can generate probability forecasts that are close to calibrated. We do mean anyone, including those who know nothing about the weather. See Eran Shmaya’s earlier posts on the literature around this.
One of the differences, often commented upon, between economists and computer scientists is the publication culture. Economists publish far fewer and longer papers for journals. Computer scientists publish many, smaller papers for conference proceedings. The journals (the top ones anyway) are heavily refereed while, the top conference proceedings are less so. Economics papers have long introductions that justify the importance of what is to come as well as (usually) carefully laying out the differences between the current paper and what has come before. It is not unusual for some readers to cry: don’t bore us get to the chorus. Computer science papers have short introductions with modest attempts at justifying what is to come. It is not unusual to hear that an economics paper is well written. Rarely, have I heard that of a computer science paper. Economists sometimes sneer at the lack of heft in CS papers, while Computer Scientists refer caustically to the bloat of ECON papers. CS papers are sometimes just wrong, etc. etc.
If one accepts these differences as more than caricature, but true, do they matter? We have two different ways for organizing the incentives for knowledge production. One rewards large contributions written up for journals with exacting (some would say idiosyncratic) standards and tastes. The other rewards the accumulation of many smaller contributions that appear in competitive proceedings that are, perhaps, more `democratic’ in their tastes. Is there any reason to suppose that one produces fewer important advances than the other? In the CS model, for example, ideas, even small ones, are disseminated quickly, publicly and evaluated by the community. Good ideas, even ones that appear in papers with mistakes, are identified and developed rapidly by the `collective’. An example is Broder’s paper on approximating the permanent. On the ECON side, much of this effort is borne by a smaller set of individuals and some of it in private in the sense of folk results and intuitions. Is there a model out there that would shed light on this?
It was a pleasure to awaken to the news that this years Nobel (memorial) in Economics went to Shapley and Roth (Schwartz lecture series hits bullseye again). Even more had it gone to me…..but, have yet to see pigs in the sky.
Pleasure turned to amusement as I heard and read the attempts of journalists to summarize the contributions honored. NPR suggested that it was about applying statistics. Forbes had a piece that among Indians would be described as putting shit in milk. This always makes me wonder about the other things they get wrong in the subjects I have no knowledge of. Nevertheless, I will plug one outlet for reasons that will become obvious upon reading it.
In this post, I set myself the task of seeing if I can do a better job than the fourth estate of conveying the nature of the contribution that was honored, Oct 15th, 2012. Here goes.
The fictional decentralized markets of the textbook, like the frictionless plane in a vacuum used in physics, are a useful device for establishing a benchmark. Real markets, however, must deal with frictions and the imperfections of their participants. One such market is for College Admissions in the US that is largely decentralized This decentralization increases uncertainty and raises costs. Students, for example, must forecast which colleges are likely to accept them. The greater the uncertainty in these forecasts the more `insurance’ is purchased either by applying to a large set of colleges or aiming `low’. On the college side, this insurance makes yields difficult to forecast. Increasing acceptance rates to increase yields has the effect of driving application numbers in the future down, so, waiting lists grow. These problems could be eliminated were one to switch to a centralized admissions market. How would one design such a centralized process? This is the question that the work of Shapley (and the late David Gale) and Alvin Roth addresses.
A major hurdle that a centralized market for college admissions must overcome is that it must match students with colleges in a way that respects the preferences and incentives of both parties. A centralized market cannot force a student to attend a college she does not want to, or require a college to accept a particular student. There is always the threat that the participants can pick up their marbles and walk away. If enough do, the incentives for the students and colleges that participate in the centralized market decline. Would a student participate in an centralized market if certain brand name colleges opted out? The work of (Gale &) Shapley was the first to formalize this concern with designing centralized markets that would be immune defections on the part of participants, i.e., stable. Their seminal paper articulated a model and a mechanism for matching students to colleges that would be stable in this sense. Alvin Roth’s own work builds on this in a number of ways. The first is to use the notion of stability to explain why some centralized markets fail. Second, to highlight the importance of other sources of instability associated with, say timing. Participants may wish to `jump the clock’. Colleges, for example, offering admission to high school students in their junior year when there might be less competition for that student. The third, is to use the ideas developed in other contexts to allocate scarce resources where money as a medium of exchange is ruled out, most notably kidneys.
The work honored this year has its roots in a specialty of game theory, long considered unfashionable but one Shapley made deep contributions to: co-operative game theory. One can trace an unbroken line between the concern for stability in the design for markets and the abstract notions of stability discussed, for example, in the first book on game theory by von-Neuman and Morgenstern. It proves, once again, Keynes’ dictum:
“The power of vested interests is vastly exaggerated compared with the gradual encroachment of ideas.’’
One reason given for the value of an MBA degree is the relationships that one develops with other students as well as the connection to the larger alumni network. Such relationships can eventually be used to open doors, secure a place at `the table’ and traded with others. While I’ve long since replaced the belief in `res ipsa loquitur‘ for `who you know matters’, I’m still not convinced by the relationship story.
Suppose introductions to gatekeepers and decision makers are scarce resources. When handing them out, why should I favor someone just because we attended the same institution? Presumably what matters is what good turn the other might do for me. Surely, this will depend on the position held rather than the school attended. Furthermore, why should the other’s academic pedigree suggest anything about the likelihood of the other returning the favor in the future? I know of no B-school that claims that it is selecting a class of future Cato’s.
True, favors are not requested or granted until a bond is established between the parties. Having something in common assists the formation of such bonds. But, why should having attended the same school be any more useful in this regard than a common interest in wine, golf or stamps?
Finally, if the alumni network is valuable, then merging two small networks should increase value for members of either network. Thus, in much the same way that some airlines share their frequent flyer programs (eg star alliance), we should see certain schools merging their networks. Haas and Anderson? Johnson School and Olin? One sees something like this at the executive masters level but not at the full time MBA level.
A paper by Azevdo, Weyl and White in a recent issue of Theoretical Economics caught my eye. It establishes existence of Walrasian prices in an economy with indivisible goods, a continuum of agents and quasilinear utility. The proof uses Kakutani’s theorem. Here is an argument based on an observation about extreme points of linear programs. It shows that there is a way to scale up the number of agents and goods, so that in the scaled up economy a Walrasian equilibrium exists.
First, the observation. Consider . The matrix and the RHS vector are all rational. Let be an optimal extreme point solution and the absolute value of the determinant of the optimal basis. Then, must be an integral vector. Equivalently, if in our original linear program we scale the constraints by , the new linear program has an optimal solution that is integral.
Now, apply this to the existence question. Let be a set of agents, a set of distinct goods and the utility that agent enjoys from consuming the bundle . Note, no restrictions on beyond non-negativity and quasi-linearity.
As utilities are quasi-linear we can formulate the problem of finding the efficient allocation of goods to agents as an integer program. Let if the bundle is assigned to agent and 0 otherwise. The program is
If we drop the integer constraints we have an LP. Let be an optimal solution to that LP. Complementary slackness allows us to interpret the dual variables associated with the second constraint as Walrasian prices for the goods. Also, any bundle such that must be in agent ‘s demand correspondence.
Let be the absolute value of the determinant of the optimal basis. We can write for all and where is an integer. Now construct an enlarged economy as follows.
Scale up the supply of each by a factor of . Replace each agent by clones. It should be clear now where this is going, but lets dot the i’s. To formulate the problem of finding an efficient allocation in this enlarged economy let if bundle is allocated the clone of agent and zero otherwise. Let be the utility function of the clone of agent . Here is the corresponding integer program.
Its easy to see a feasible solution is to give for each and such that , the clones in a bundle . The optimal dual variables from the relaxation of the first program complements this solution which verifies optimality. Thus, Walrasian prices that support the efficient allocation in the augmented economy exist.
In this post I describe an alternative proof of a nifty result that appears in a forthcoming paper by Goeree, Kushnir, Moldovanu and Xi. They show (under private values) given any Bayesian incentive compatible mechanism, M, there is a dominant strategy mechanism that gives each agent the same expected surplus as M provides.
For economy of exposition only, suppose 2 agents and a finite set of possible outcomes, . Suppose, also the same type space, for both. Let be the density function over types. To avoid clutter, assume the uniform distribution, i.e., . Nothing in the subsequent analysis relies on this.
When agent 1 reports type and agent 2 reports type , denote by the probability that outcome is selected. The ‘s must be non-negative and satisfy
Associated with each agent is a vector that determines, along with her type, the utility she enjoys from a given allocation. In particular, given the allocation rule , the utility that agent of type enjoys when the other agent reports type is A similar expression holds agent 2.
Let Interpret the ‘s as the `quantity’ of goods that each agent receives. Dominant strategy implies that should be monotone increasing in for each fixed and should be monotone increasing in for each fixed . The interim `quantities will be: Bayesian incentive compatibility (BIC) implies that the ‘s should be monotone. To determine if given BIC interim `quantities’ ‘s can be implemented via dominant strategies, we need to know if the following system is feasible
System (1-6) is feasible iff the optimal objective function value of the following program is zero:
Let be an optimal solution to this program.
Suppose, for a contradiction there is a pair such that . I will argue that there must exist an such that . Suppose not, then for each , either or and (at optimality, it cannot be that and are both non-zero). In this case
. This last term is negative, a contradiction. Therefore, there is a such that but .
Let , and denote by the point . Observe that is in the convex hull, of for all . Thus choosing ‘s amounts to choosing a point . Equivalently, choosing a point gives rise to a set of ‘s. For convenience assume that is in the strict interior of for all and that is full dimensional. This avoids having to deal with secondary arguments that obscure the main idea.
Recall, implies implies that . Take all points and shift them horizontally to the right by . Call these new points . Observe that for all . Next, take all points and shift them horizontally to the left by to form new points . These points are also in . Leave all other points unchanged.
Because the vertical coordinates of all points were left unchanged, (8) and (10) are satisfied by this choice of points. Because and were shifted in opposite directions along the horizontal, (9) is still true. Finally, because all points in and were shifted by the same amount, (7) continues to hold.
The shift leftwards of reduces while the rightward shift of reduces . Thus, we get a new solution with higher objective function value, a contradiction.
If and are not the interior of but on the boundary, then horizontal shifts alone may place them outside of . In the case of this can only happen if . In this case, shift across and to the right by as well and then downwards by the same amount. This would have to be matched by a corresponding upward shift by some point . Similarly with .
Thanks to Alexey Kushnir and Ahmad Peivandi for comments.
is the title of an engaging management book by Thurston P. Howell a prof at Harvard Business School. Howell may be known to some of you from his presentation at TED on the social networks of members of drug cartels where he uses the Bonacich measure of centrality to identify drug kingpins.
Howell has been running a well received executive development program for cartel members in Colombia and other Latin American countries. The students are exposed to the basics of finance, accounting, marketing and courses on the public-private interface, media relations and crisis management. That experience has allowed him to interview, at length, some of the major figures and ask about the leadership challenges they face as well as how they deal with them. The findings from this fieldwork have been distilled into the present volume.
The book makes a welcome addition to anyones library of airport business books. It complements very nicely `The leadership secrets of Attila the Hun’, `The leadership secrets of Hilary Clinton’, `The leadership secrets of Colin Powell’, `The leadership secrets of Genghis Khan’, `The leadership secrets of Billy Graham’, `The leadership secrets of Jesus Christ’, `The leadership secrets of Elizabeth I’, `The leadership secrets of squirrels, priates, Navy Seals, Bismarck, Santa Claus, King David, Dumbledore, Hornblower, Gandalf and the Trigan Empire’.