You are currently browsing rvohra’s articles.
Starr’s ’69 paper considered Walrasian equilibria in exchange economies with non-convex preferences i.e., upper contour sets of utility functions are non-convex. Suppose agents and goods with . Starr identified a price vector and a feasible allocation with the property that at most agents did not receiving a utility maximizing bundle at the price vector .
A poetic interlude. Arrow and Hahn’s book has a chapter that describes Starr’s work and closes with a couple of lines of Milton:
A gulf profound as that Serbonian Bog
Betwixt Damiata and Mount Casius old,
Where Armies whole have sunk.
Milton uses the word concave a couple of times in Paradise Lost to refer to the vault of heaven. Indeed the OED lists this as one of the poetic uses of concavity.
Now, back to brass tacks. Suppose is agent ‘s utility function. Replace the upper contour sets associated with for each by its convex hull. Let be the concave utility function associated with the convex hulls. Let be the Walrasian equilibrium prices wrt . Let be the allocation to agent in the associated Walrasian equilibrium.
For each agent let
where is agent ‘s endowment. Denote by the vector of total endowments and let .
Let be the excess demand with respect to and . Notice that is in the convex hull of the Minkowski sum of . By the Shapley-Folkman-Starr lemma we can find for , such that and .
When one recalls, that Walrasian equilibria can also be determined by maximizing a suitable weighted (the Negishi weights) sum of utilities over the set of feasible allocations, Starr’s result can be interpreted as a statement about approximating an optimization problem. I believe this was first articulated by Aubin and Elkeland (see their ’76 paper in Math of OR). As an illustration, consider the following problem :
Call this problem . Here is an matrix with .
For each let be the smallest concave function such that for all (probably quasi-concave will do). Instead of solving problem , solve problem instead:
The obvious question to be answered is how good an approximation is the solution to to problem . To answer it, let (where I leave you, the reader, to fill in the blanks about the appropriate domain). Each measures how close is to . Sort the ‘s in decreasing orders. If is an optimal solution to , then following the idea in Starr’s ’69 paper we get:
It states that the Minkowski sum of a large number of sets is approximately convex. The clearest statement as well as the nicest proof I am familiar with is due to J. W. S. Cassels. Cassels is a distinguished number theorist who for many years taught the mathematical economics course in the Tripos. The lecture notes are available in a slender book now published by Cambridge University Press.
This central limit like quality of the lemma is well beyond the capacity of a hewer of wood like myself. I prefer the more prosaic version.
Let be a collection of sets in with . Denote by the Minkowski sum of the collection . Then, every can be expressed as where for all and .
How might this be useful? Let be an 0-1 matrix and with . Consider the problem
Let be a solution to the linear relaxation of this problem. Then, the lemma yields the existence of a 0-1 vector such that and . One can get a bound in terms of Euclidean distance as well.
How does one do this? Denote each column of the matrix by and let . Let . Because and it follows that . Thus, by the Lemma,
where each and . In words, has at most fractional components. Now construct a 0-1 vector from as follows. If , set . If is fractional, round upto 1 with probability and down to zero otherwise. Observe that and the . Hence, there must exist a 0-1 vector with the claimed properties.
The error bound of is to large for many applications. This is a consequence of the generality of the lemma. It makes no use of any structure encoded in the matrix. For example, suppose were an extreme point and a totally unimodular matrix. Then, the number of fractional components of $x^*$ are zero. The rounding methods of Kiralyi, Lau and Singh as well as of Kumar, Marathe, Parthasarthy and Srinivasan exploit the structure of the matrix. In fact both use an idea that one can find in Cassel’s paper. I’ll follow the treatment in Kumar et. al.
As before we start with . For convenience suppose for all . As as has more columns then rows, there must be a non-zero vector in the kernel of , i.e., . Consider and . For and sufficiently small, for all . Increase and until the first time at least one component of and is in . Next select the vector with probability or the vector with probability . Call the vector selected .
Now . Furthermore, has at least one more integer component than . Let . Let be the matrix consisting only of the columns in and consist only of the components of in . Consider the system . As long as has more columns then rows we can repeat the same argument as above. This iterative procedure gives us the same rounding result as the Lemma. However, one can do better, because it may be that even when the number of columns of the matrix is less than the number of rows, the system may be under-determined and therefore the null space is non-empty.
In a sequel, I’ll describe an optimization version of the Lemma that was implicit in Starr’s 1969 Econometrica paper on equilibria in economies with non-convexities.
Economists, I told my class, are the most empathetic and tolerant of people. Empathetic, as they learnt from game theory, because they strive to see the world through the eyes of others. Tolerant, because they never question anyone’s preferences. If I had the talent I’d have broken into song with a version of `Why Can’t a Woman be More Like a Man’ :
Psychologists are irrational, that’s all there is to that!
Their heads are full of cotton, hay, and rags!
They’re nothing but exasperating, irritating,
vacillating, calculating, agitating,
Maddening and infuriating lags!
Why can’t a psychologist be more like an economist?
Back to earth with preference orderings. Avoided the word rational to describe the restrictions placed on preference orderings, used `consistency’ instead. More neutral and conveys the idea that inconsistency makes prediction hard rather that suggesting a Wooster like IQ. Emphasized that utility functions were simply a succinct representation of consistent preferences and had no meaning beyond that.
In a bow to tradition went over the equi-marginal principle, a holdover from the days when economics students were ignorant of multivariable calculus. Won’t do that again. Should be banished from the textbooks.
Now for some meat: the income and substitution (I&S) effect. Had been warned this was tricky. `No shirt Sherlock,’ my students might say. One has to be careful about the set up.
Suppose price vector and income . Before I actually purchase anything, I contemplate what I might purchase to maximize my utility. Call that .
Again, before I purchase , the price of good 1 rises. Again, I contemplate what I might consume. Call it . The textbook discussion of the income and substitution effect is about the difference between and .
As described, the agent has not purchased or . Why this petty foggery? Suppose I actually purchase $x$ before the price increase. If the price of good 1 goes up, I can resell it. This is both a change in price and income, something not covered by the I&S effect.
The issue is resale of good 1. Thus, an example of an I&S effect using housing should distinguish between owning vs. renting. To be safe one might want to stick to consumables. To observe the income effect, we would need a consumable that sucks up a `largish’ fraction of income. A possibility is low income consumer who spends a large fraction on food.
Bertrand, Cournot and Hotelling was on the menu. In addition to covering the mechanics of computing equilibria, spent time trying to motivate each model. Cournot is, I think, the hardest. The short version of the story I gave was this. Firms choose their capacities/quantities, then go to a middleman (should have said platform, so much sexier these days) who auctions of their joint output via a uniform price auction. Wholesale electricity markets come close to this story, which allows one to use Cournot to convey the idea of supply (demand) reduction and the scandal of the California power markets.
Hotelling is easier to motivate, and is a useful vehicle to illustrate why they should always `break’ a model to learn something about it. In the standard Hotelling setup, no reservation price is specified for the buyers. Now, allow the two firms to merge and act like a monopolist. The monopolist’s profit function is unbounded! However, you can still write down a first order condition and solve it. Thus, it is also a useful reminder of the dangers of blindly differentiating and setting to zero.
Contrasted Cournot with Hotelling, for example, the effect on consumer surplus when a merger results in a cost reduction for the merged firm. Also provided an opportunity to remind the class about monopoly and evaluating consumer surplus.
Concluded the module on imperfect competition by applying what had been discussed to Amazon vs. Apple vs the publishers. Another opportunity to walk down memory lane with double marginalization and then add a wrinkle involving competition in the downstream market.
Uber posts a price per ride and keeps a commission on the price. Suppose Uber is the only ride matching service in town. If is the demand function for rides at per ride price and is the supply curve for drivers at wage per ride, Uber must choose and to solve the following:
The last constraint comes from the assumption that Uber is committed to ensuring that every rider seeking a ride at the posted price gets one.
Suppose, Uber did not link the payment to driver to the price charged to rider in this particular way. Then, Uber would solve
The first optimization problem is clearly more restrictive than the second. Hence, the claim that Uber is not profit maximizing. Which raises the obvious puzzle, why is Uber using a revenue sharing scheme?
Sydney Afriat arrived in Purdue in the late 60’s with a Bentley in tow. Mort Kamien described him as having walked out of the pages of an Ian Flemming novel. Why he brought the Bentley was a puzzle, as there were no qualified mechanics as far as the eye could see. In Indiana, that is a long way. Afriat would take his Bentley on long drives only to be interrupted by mechanical difficulties that necessitated the Bentley being towed to wait for parts or specialized help.
I came upon Afriat when I learnt about the problem of rationalizability. One has a model of choice and a collection of observations about what an agent selected. Can one rationalize the observed choices by the given model of choice? In Afriat’s seminal paper on the subject, the observations consisted of price-quantity pairs for a vector of goods and a budget. The goal was to determine if the observed choices were consistent with an agent maximizing a concave utility function subject to the budget constraint. Afriat’s paper has prompted many other papers asking the same question for different models of choice. There is an aspect of these papers, including Afriat’s, that I find puzzling.
To illustrate, consider rationalizing expected utility (Eran Shmaya suggested that `expected consumption’ might be more accurate). Let be the set of possible states. We are given a sequence of observations and a single budget . Here represents consumption in state and is the unit price of consumption in state in observation . We want to know if there is a probability distribution over states, , such that each maximizes expected utility. In other words, solves
The solution to the above program is obvious. Identify the variable with the largest objective coefficient to constraint ratio and make it as large as possible. It is immediate that a collection of observations can be rationalized by a suitable set of non-zero and nonnegative ‘s if the following system has a feasible solution:
This completes the task as formulated by Afriat. A system of inequalities has been identified, that if feasible means the given observations can be rationalized. How hard is this to do in other cases? As long as the model of choice involves optimization and the optimization problem is well behaved in that first order conditions, say, suffice to characterize optimality, its a homework exercise. One can do this all day, thanks to Afriat; concave, additively separable concave, etc. etc.
Interestingly, no rationalizability paper stops at the point of identifying the inequalities. Even Afriat’s paper goes a step farther and proceeds to `characterize’ when the observations can be rationalized. But, feasibility of the inequalities themselves is just such a characterization. What more is needed?
Perhaps, the characterization involving inequalities lacks `interpretation’. Or, if the given system for a set of observations was infeasible, we may be interested in the obstacle to feasibility. Afriat’s paper gave a characterization in terms of the strong axiom of revealed preference, i.e., an absence of cycles of certain kinds. But that is precisely the Farkas alternative to the system of inequalities identified in Afriat. The absence of cycles condition follows from the fact that the initial set of inequalities is associated with the problem of finding a shortest path (see the chapter on rationalizability in my mechanism design book). Let me illustrate with the example above. It is equivalent to finding a non-negative and non trivial solution to
This is exactly the dual to the problem of finding a shortest path in a suitable network (I believe that Afriat has a paper, that I’ve not found, which focuses on systems of the form ).The cycle characterization would involve products of terms like being less than 1 (or greater than 1 depending on convention). So, what would this add?
Completed what I wanted about monopoly and launched into imperfect competition and introduced the nash equilibrium. I follow the set up in the chapter of pricing from my pricing book with Lakshman Krishnamurthi. The novelty, if any, is to start with Bertrand competition, add capacity and then differentiation. I do this to highlight the different forces at play so that they are not obscured by the algebra of identifying reaction functions and finding where they cross. We’ll get to those later on. Midterm Day, 12. I am, as Enoch Powell once remarked in another, unattractive context,
…. filled with foreboding. Like the Roman, I seem to see “the River Tiber foaming with much blood”.
Much of my energy has been taken up with designing homework problems and a midterm exam on monopoly. Interesting questions are hard to come by. Those lying around make me want to make gnaw my feet off. I started with the assumption, which I may live to regret, that my students are capable of the mechanical and have good memories. The goal, instead, is to get them to put what they have learnt in class to use. Here is an example. Two upstream suppliers, A and B, who each supply an input to a Retailer. The Retailer is characterized by a production function that tells you how much output it generates from the inputs supplied by A and B as well as a demand curve for the final product. Fix the price set by B to, w, say. Now compute the price that A should charge to maximize profit. Its double marginalization with a twist. Suppose the inputs are substitutes for each other. If B raises its price above w what effect will that have on A’s profits? There are two effects. The retailers costs will go up of course, so reducing its output. However, A will retain a larger share of the smaller output. Which will be bigger? Its a question that requires them to put various pieces together. I’ve had them work up to it by solving the various pieces under different guises in different problems. Am I expecting too much? I’ll find out after the midterm. Yet, I cannot see anyway around having questions like this. What is the point of the mathematics we require them to use and know if we don’t ask them to apply it when blah-blah alone is insufficient?
I now have a modest store of such problems, but coming up with them has been devilish hard. Working out the solutions is painful, because it involves actual algebra and one cannot afford errors (on that account I’m behind the curve). To compound matters, one is unable to recycle the exam and homework problems given various sharing sites. I begin to regret not making them do just algebra.
Its all the rage. I’m not immune to jumping on a bandwagon, but by the time I get there the dogs have barked and the caravan has moved on. Is there anything new to be said on the subject? Perhaps we can get by with relabeling things we already know? Useful, but not exciting. To think about this I tried to come with questions about privacy that struck me as important. Here is my list, in hopes that it will prompt others to improve upon it.
1) Is the concern for privacy intrinsic or instrumental?
The question matters because an answer would have a profound impact on how one evaluates the welfare consequences of various policies.
2) Property rights over information.
Much of the information about us that is of interest is the result of interactions with others. When I purchase a book from Amazon, who `owns’ the record of that transaction? It could be argued that the record of the transaction is as much Amazon’s as it is mine. The question is not new. It arises, for example, when one writes a biography.
What about when a transaction takes place via an intermediary? What rights does the intermediary have to the record of the transaction?
3) A full specification of property rights would spell out who has the right to disclose what and to whom and under what conditions.
Some of this will involve a balance between the public good and individual harm. Out of court settlements regarding commercial matters whose terms are secret, prevent learning about systemic problems (Akerlof and his lemons, seems like a likely candidate for relabeling).
When is and under what conditions is mandated disclosure warranted? One can also imagine settings where one might wish to prohibit the voluntary disclosure of confidential information. Some professional schools, for example prohibit the disclosure of grades to potential employers (Grossman and Milgrom, anyone?).
4) Compliance. How might one monitor and verify that the specification of property rights have been adhered to?
For example, a promise not to disclose to a third party. In a given setting, are some kinds of promises even feasible? One may promise not to use certain identifying characteristics in the allocation of resources but those characteristics may have good proxies in other `allowed’ characteristics.
Who should bear the costs of such monitoring? (Coase?)As much information of interest is collected by devices, one might think about the `regulation’ of devices as a part of compliance. What standards, if any should devices that collect and transmit information adhere to? Is managing privacy best done through device standards or contracts?
I spent these two classes going over two-part tariffs. Were this just the algebra, it would be overkill. The novelty, if any, was to tie the whole business to how one should price in a razor & blade business (engines and spare parts, kindle and ebooks etc). The basic 2-part model sets a high fixed fee (which one can associate with the durable) and sells each unit of the consumable at marginal cost. The analysis offers an opportunity to remind them of the problem of regulating the monopolist charging a uniform price.
The conclusion of the basic 2-part model suggests charging a high price for razors and a low price for blades. This seems to run counter to the prevailing wisdom. Its an opportunity to solicit reasons for why the conclusion of the model might be wrong headed. We ran through a litany of possibilities: heterogenous preferences (opportunity to do a heavy vs light user calculation), hold up (one student observed that we can trust Amazon to keep the price of ebooks low otherwise we would switch to pirated versions!), liquidity constraints, competition. Tied this to Gillete’s history expounded in a paper by Randall Pick (see an earlier post ) and then onto Amazon’s pricing of the kindle and ebooks (see this post). This allowed for a discussion of the wholesale model vs agency model of pricing which the students had been asked to work out in the homework’s (nice application of basic monopoly pricing exercises!).
The `take-away’ I tried to emphasize was how models help us formulate questions (rather than simply provide prescriptions), which in turn gives us greater insight into what might be going on.