You are currently browsing the category archive for the ‘market design’ category.

Apparently, it is quite the rage to festoon one’s slides with company logos, particularly of the  frightful five. At present this is done for free. It suggests a new business. A platform that matches advertisers to faculty. Faculty can offer up their slides and advertisers can bid for the right to place their logos on the slides.

Platooning, driverless cars and ride hailing services have all been suggested as ways to reduce congestion. In this post I want to examine the use of coordination via ride hailing services as a way to reduce congestion. Assume that large numbers of riders decide to rely on ride hailing services. Because the services use Google Maps or Waze for route selection, it would be possible to coordinate their choices to reduce congestion.

To think thorough the implications of this, its useful to revisit an example of Arthur Pigou. There is a measure 1 of travelers all of whom wish to leave the same origin (${s}$) for the same destination (${t}$). There are two possible paths from ${s}$ to ${t}$. The top’ one has a travel time of 1 unit independent of the measure of travelers who use it. The bottom’ one has a travel time that grows linearly with the measure of travelers who employ it. Thus, if fraction ${x}$ of travelers take the bottom path, each incurs a travel time of ${x}$ units.

A central planner, say, Uber, interested in minimizing total travel time will route half of all travelers through the top and the remainder through the bottom. Total travel time will be ${0.5 \times 1 + 0.5 \times 0.5 = 0.75}$. The only Nash equilibrium of the path selection game is for all travelers to choose the bottom path yielding a total travel time of ${1}$. Thus, if the only choice is to delegate my route selection to Uber or make it myself, there is no equilibrium where all travelers delegate to Uber.

Now suppose, there are two competing ride hailing services. Assume fraction ${\alpha}$ of travelers are signed up with Uber and fraction ${1-\alpha}$ are signed up with Lyft. To avoid annoying corner cases, ${\alpha \in [1/3, 2/3]}$. Each firm routes its users so as to minimize the total travel time that their users incur. Uber will choose fraction ${\lambda_1}$ of its subscribers to use the top path and the remaining fraction will use the bottom path. Lyft will choose a fraction ${\lambda_2}$ of its subscribers to use the top path and the remaining fraction will use the bottom path.

A straight forward calculation reveals that the only Nash equilibrium of the Uber vs. Lyft game is ${\lambda_1 = 1 - \frac{1}{3 \alpha}}$ and ${\lambda_2 = 1 - \frac{1}{3(1-\alpha)}}$. An interesting case is when ${\alpha = 2/3}$, i.e., Uber has a dominant market share. In this case ${\lambda_2 = 0}$, i.e., Lyft sends none of its users through the top path. Uber on the hand will send half its users via the top and the remainder by the bottom path. Assuming Uber randomly assigns its users to top and bottom with equal probability, the average travel time for a Uber user will be

$\displaystyle 0.5 \times 1 + 0.5 \times [0.5 \times (2/3) + 1/3] = 5/6.$

The travel time for a Lyft user will be

$\displaystyle [0.5 \times (2/3) + 1/3] = 2/3.$

Total travel time will be ${7/9}$, less than in the Nash equilibrium outcome. However, Lyft would offer travelers a lower travel time than Uber. This is because, Uber which has the bulk of travelers, must use the top path to reduce total travel times. If this were the case, travelers would switch from Uber to Lyft. This conclusion ignores prices, which at present are not part of the model.

Suppose we include prices and assume that travelers now evaluate a ride hailing service based on delivered price, that is price plus travel time. Thus, we are assuming that all travelers value time at $1 a unit of time. The volume of customers served by Uber and Lyft is no longer fixed and they will focus on minimizing average travel time per customer. A plausible guess is that there will be an equal price equilibrium where travelers divide evenly between the two services, i.e., ${\alpha = 0.5}$. Each service will route ${1/3}$ of its customers through the top and the remainder through the bottom. Average travel time per customer will be ${5/3}$. However, total travel time on the bottom will be ${2/3}$, giving every customer an incentive to opt out and drive their own car on the bottom path. What this simple minded analysis highlights is that the benefits of coordination may be hard to achieve if travelers can opt out and drive themselves. To minimize congestion, the ride hailing services must limit traffic on the bottom path. This is the one that is congestible. However, doing so makes its attractive in terms of travel time encouraging travelers to opt out. Colleagues outside of Economics often marvel at the coordinated nature of the Economics job market. The job market is so efficient, that the profession no longer wastes resources by having everyone read each candidate’s job market paper. That task is assigned to one person (Tyler Cowen) who reports back to the rest of us. In case you missed the report, here it is Economics is not alone in having a coordinated job market. Philosophy has one, but it has begun to show signs of unraveling. The ability to interview via Skype, for example, has reduced the value in the eyes of many, for a preliminary interview at their annual meeting. In response, the American Philosophy Association posted the following statement regarding the job market calendar: For tenure-track/continuing positions advertised in the second half of the calendar year, we recommend an application deadline of November 1 or later. It is further recommended that positions be advertised at least 30 days prior to the application deadline to ensure that candidates have ample time to apply. In normal circumstances a prospective employee should have at least two weeks for consideration of a written offer from the hiring institution, and responses to offers of a position whose duties begin in the succeeding fall should not be required before February 1. When advertising in PhilJobs: Jobs for Philosophers, advertisers will be asked to confirm that the hiring institution will follow the above guidelines. If an advertiser does not do so, the advertisement will include a notice to that effect. Its natural to wonder if the Economics market is not far behind. Skype interviews are already taking place. The current set up requires a department to evaluate and select candidates for preliminary interviews within a month (roughly the middle of November to mid December) which is hardly conducive to mature reflection (and argument). Because I have white hair and that so sparse as to resemble the Soviet harvest of 1963, I am asked for advice. Just recently I was asked about hot’ research topics in the sharing economy. You mean a pure exchange economy?, said I in reply. Because I have white hair etc, I sometimes forget to bite my tongue. Returning to topic, the Economist piece I linked to above, gets it about right. With a fall in certain transaction costs, trades that were otherwise infeasible, are realized. At a high level there is nothing more to be said beyond what we know already about exchange economies. A closer looks suggests something of interest in the role of the mediator (eBay, Uber) responsible for the reduction in transaction costs. They are not indifferent Walrasian auctioneers but self interested ones. eBay and Uber provide an interesting contrast in intrusiveness’. The first reduces the costs with respect to search, alleviates the lemons problem and moral hazard by providing information and managing payments. It does not, however, set prices. These are left to participants to decide. In sum, eBay it appears, tries to eliminate the textbook obstacles to a perfectly competitive market. Uber, also does these things but more. It chooses prices and the supplier who will meet the reported demand. One might think eBay does not because of the multitude of products it would have to track. The same is true for Uber. A product on Uber is a triple of origin, destination and time of day. The rider and driver may not be thinking about things in this way, but Uber certainly must in deciding prices and which supplier will be chosen to meet the demand. Why doesn’t Uber allow riders to post bids and drivers to post asks? Fox News and CNN have been in knots recently about how to allocate scarce debate slots to the many Republican pretenders to the oval office. Should Poll numbers be the criteria? What about gender, race, state office etc. etc. There is a simple and transparent way to allocate the slots: an auction. Neither CNN or Fox are charities. If the debates are a public good, there is no reason why Fox and CNN alone should forgo profits to host them. They should, instead auction off the rights to participate in the debates. What design questions would have to be answered? First, how much time to allocate to the debate, i.e., what is the supply of the resource to be allocated? Second, should one auction slots or time. For example, should it be 10 slots of equal time lengths in a 2 hour time period? Or, should one allow the bidders to bid on the actual amount of time they would get in the 2 hour period? Are candidates the only ones allowed to bid, or can anyone submit bids on their behalf? Can one bid to deny time to the candidates? Actually, as these are not debates at all, but parallel news conference, perhaps one should auction off the right to answer questions. In real time. That would be entertainment! Having caught your eye, I direct you to an article in the April 9, 2015 edition of the Grey Lady. It discusses attempts by various countries to boost domestic birthrates. The same issue had been considered earlier by Noah Smith. There are two questions lurking here. First, what is the optimal population size for a country? If the goal was to shrink the population then a declining birth rate is not a bad thing. Suppose the goal is keep the population fixed, because, say of pension obligations. Then, one wants a replacement birth rate of roughly 2 per couple. If the birth rate is below the target, what should one do? Interestingly, I cannot recall anyone I have asked or read who does not turn to Government interventions of various kinds. Noah Smith, for example, only discusses Government interventions before concluding one should imitate the French. If the birth rate is below what is optimal for society, why doesn’t the market take care of it? Do we have a missing market? Is this a public goods problem? (If so, then, Mankiw who is often castigated for being a selfish beast, is, in this case, an unstinting provider of public goods, see here.) Analogies are sometimes helpful (if biology is the study of bios, life; geology is the study of geos, earth, what does that make analogy?). Farmers plant crops and after a period, the fruits of their labor are harvested and sent to market. The Farmer must anticipate what will be demanded in the future to decide what to plant now. What if she plants turnips when what is desired are parsnips? This problem is solved with a futures market for parsnips (or turnips or pork etc). Why not a futures market for babies? Those who want warm bodies in the future to support them in their dotage pay for babies now. Swiftian, I know, but interesting to consider. Once one thinks about how to implement the idea, difficulties emerge. One might, for example, be concerned with moral hazard on the part of parents. However, these same difficulties are present even with various Government subsidies. General equilibrium! Crown jewel of micro-economic theory. Arrow and Hahn give the best justification: “There is by now a long and fairly imposing line of economists from Adam Smith to the present who have sought to show that a decentralized economy motivated by self-interest and guided by price signals would be compatible with a coherent disposition of economic resources that could be regarded, in a well defined sense, as superior to a large class of possible alternative dispositions. Moreover the price signals would operate in a way to establish this degree of coherence. It is important to understand how surprising this claim must be to anyone not exposed to the tradition. The immediate common sense’ answer to the question What will an economy motivated by individual greed and controlled by a very large number of different agents look like?’ is probably: There will be chaos. That quite a different answer has long been claimed true and has permeated the economic thinking of a large number of people who are in no way economists is itself sufficient ground for investigating it seriously. The proposition having been put forward and very seriously entertained, it is important to know not only whether it is true, but whether it could be true.” But how to make it come alive for my students? When first I came to this subject it was in furious debates over central planning vs. the market. Gosplan, the commanding heights, indicative planning were as familiar in our mouths as Harry the King, Bedford and Exeter, Warwick and Talbot, Salisbury and Gloucester….England, on the eve of a general election was poised to leave all this behind. The question, as posed by Arrow and Hahn, captured the essence of the matter. Those times have passed, and I chose instead to motivate the simple exchange economy by posing the question of how a sharing economy might work. Starting with two agents endowed with a positive quantity of each of two goods, and given their utility functions, I asked for trades that would leave each of them better off. Not only did such trades exist, there were more than one. Which one to pick? What if there were many agents and many goods? Would bilateral trades suffice to find mutually beneficial trading opportunities? Tri-lateral? The point of this thought experiment was to show how in the absence of prices, mutually improving trades might be very hard to find. Next, introduce prices, and compute demands. Observed that demands in this world could increase with prices and offered an explanation. Suggested that this put existence of market clearing prices in doubt. Somehow, in the context of example this all works out. Hand waved about intermediate value theorem before asserting existence in general. On to the so what. Why should one prefer the outcomes obtained under a Walrasian equilibrium to other outcomes? Notion of Pareto optimality and first welfare theorem. Highlighted weakness of Pareto notion, but emphasized how little information each agent needed other than price, own preferences and endowment to determine what they would sell and consume. Amazingly, prices coordinate everyone’s actions. Yes, but how do we arrive at them? Noted and swept under the rug, why spoil a good story just yet? Gasp! Did not cover Edgeworth boxes. Went on to introduce production. Spent some time explaining why the factories had to be owned by the consumers. Owners must eat as well. However it also sets up an interesting circularity in that in small models, the employee of the factory is also the major consumer of its output! Its not often that a firm’s employers are also a major fraction of their consumers. Closed with, how in Walrasian equilibrium, output is produced at minimum total cost. Snuck in the central planner, who solves the problem of finding the minimum cost production levels to meet a specified demand. Point out that we can implement the same solution using prices that come from the Lagrange multiplier of the central planners demand constraint. Ended by coming back full circle, why bother with prices, why not just let the central planner have his way? 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 ${\{S^j\}_{j=1}^n}$ be a collection of sets in ${\Re ^m}$ with ${n > m}$. Denote by ${S}$ the Minkowski sum of the collection ${\{S^i\}_{i=1}^n}$. Then, every ${x \in conv(S)}$ can be expressed as ${\sum_{j=1}^nx^j}$ where ${x^j \in conv(S^j)}$ for all ${j = 1,\ldots, n}$ and ${|\{j: x^j \not \in S^j| \leq m}$. How might this be useful? Let ${A}$ be an ${m \times n}$ 0-1 matrix and ${b \in \Re^m}$ with ${n > m}$. Consider the problem $\displaystyle \max \{cx: Ax = b, x_j \in \{0,1\}\ \forall \,\, j = 1, \ldots, n\}.$ Let ${x^*}$ be a solution to the linear relaxation of this problem. Then, the lemma yields the existence of a 0-1 vector ${x}$ such that ${cx \geq cx^* = z}$ and ${||Ax - b||_{\infty} \leq m}$. One can get a bound in terms of Euclidean distance as well. How does one do this? Denote each column ${j}$ of the ${A}$ matrix by ${a^j}$ and let ${d^j = (c_j, a^j)}$. Let ${S^j = \{d^j, 0\}}$. Because ${z = cx^*}$ and ${b = Ax^*}$ it follows that ${(z,b) \in conv(S)}$. Thus, by the Lemma, $\displaystyle (z, b) = \sum_{j=1}^n(c_j, a^j)y_j$ where each ${y_j \in [0,1]}$ and ${|\{j: y_j \in (0,1) \}| \leq m }$. In words, ${y}$ has at most ${m}$ fractional components. Now construct a 0-1 vector ${y^*}$ from ${y}$ as follows. If ${y_j \in \{0,1\}}$, set ${y^*_j = y_j}$. If ${y_j }$ is fractional, round ${y^*_j}$ upto 1 with probability ${y_j}$ and down to zero otherwise. Observe that ${||Ay - b||_{\infty} \leq m}$ and the ${E(cy) = cx^*}$. Hence, there must exist a 0-1 vector ${x}$ with the claimed properties. The error bound of ${m}$ 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 ${A}$ matrix. For example, suppose $x^*$ were an extreme point and $A$ 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 ${x^*}$. For convenience suppose ${0 < x^*_j < 1}$ for all ${j = 1, \ldots, n}$. As ${A}$ as has more columns then rows, there must be a non-zero vector ${r}$ in the kernel of ${A}$, i.e., ${Ar = 0}$. Consider ${x + \alpha r}$ and ${x -\beta r}$. For ${\alpha > 0}$ and ${\beta > 0}$ sufficiently small, ${x_j + \alpha r_j, x_j - \beta r_j \in [0,1]}$ for all ${j}$. Increase ${\alpha}$ and ${\beta}$ until the first time at least one component of ${x +\alpha r}$ and ${x- \beta r}$ is in ${\{0,1\}}$. Next select the vector ${x + \alpha r}$ with probability ${\frac{\beta}{\alpha + \beta}}$ or the vector ${x- \beta r}$ with probability ${\frac{\alpha}{\alpha + \beta}}$. Call the vector selected ${x^1}$.

Now ${Ax^1 = b}$. Furthermore, ${x^1}$ has at least one more integer component than ${x^*}$. Let ${J = \{j: x^1_j \in (0,1)\}}$. Let ${A^J}$ be the matrix consisting only of the columns in ${J}$ and ${x^1(J)}$ consist only of the components of ${x^1}$ in ${J}$. Consider the system ${A^Jx^1(J) = b - \sum_{j \not \in J}x^1_j}$. As long as ${A^J}$ 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.

Something funny happened when I started watching Al Roth’s lecture and looked at the paper: I realized that what I always assumed is the meaning of repugnant transactions’ is not exactly the phenomena that Roth talks about. What I thought repugnant transaction’ means is a situation of two rights makes a wrong’: it’s totally awesome that Xanders is willing to donate his extra kidney to Zordiac, and it’s really nice of Zordiac to donate money to Xanders, but these two nobles acts done together in exchange for each other is imoral and should be outlawed. Roth however defines repugnant transaction’ more broadly as any transaction that some people want to engage in and others don’t think they should.

Consider the opening example of his paper: laws against selling horse meat in restaurants. Here what is repugnant is not the exchange but the good itself. It’s not two rights makes wrong. It’s just wrong. We outlaw the exchange simply because of constitutional reasons or because it’s impossible to enforce a ban on eating — people will simply order take away and perform the crime of eating at their homes.

So let me offer a distinction between repugnant exchanges’, where the good itself is fine but buying and selling it is repugnant and repugnant good/services’ where the good or service are what is repugnant, even if for whatever reason what we actually outlaw is the transaction. Most of the examples that Roth gives fall into the repugnant good/service’ category rather than repugnant exchange’. Such is the case of buying and selling recreational drugs, endangered species, imported cultural property.

Are there any examples for repugnant exchanges’ in addition to selling human organs ? Well, there is renting’ organs, as in surrogate motherhood. Anything else ? An interesting example is lending money with interest, which used to be repugnant in the West (we got over it already): The very idea of lending money was never considered repugnant. What was repugnant is doing it for payment in terms of interest.

Finally, there is prostitution, which is illegal in the US. Repugnant service or repugnant exchange ? depends on your reasoning. Anti-prostitution laws have an unlikely coalition of supporters. There are the religious moralists, for whom the service (extra-marriage sexual intercourse) is what makes the transaction repugnant. They go for prostitution just because that’s what they can outlaw in the US. (They go further in Iran.) But there are also feminists and liberals who view prostitution as exploitation, as I view selling human organs. They find the exchange repugnant even if they have no problem with the service itself.

Note that the example of prostitution shows the difficulty in the distinction I make between repugnant good/service’ and repugnant exchange’: It relies on unobservable reasoning. Just by knowing the laws and customs of a society you don’t know to which category a forbidden transaction belongs. Moreover, since different people may have different reasoning, the category is sometimes not uniquely defined. But I still think it’s a useful distinction.

In my salad days, school masters would assign boys returning from the summer hols an essay: What I did during the summer’. Yes, masters and boys. I served a portion of my youth in a misbegotten penal colony upon a wind blasted heath’. The only females present were master’s wives, matrons and the French mistress. No, not that kind, the kind that offers instruction in French. As you can see, to the lascivious minds of boys, there was no end to the double entendres. However, I digress.

Over the summer Thanh Nguyen and myself completed a paper about stable matchings. The abstract is reproduced below.

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a nearby’ instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity $k_h$ for each hospital $h$, we find a redistribution of the slot capacities $k'_h$ satisfying $|k_h-k'_h|\le 4$ for all hospitals $h$ and $\sum_h k_h\le \sum k'_h \le \sum_h k_h+9$, such that a stable matching exists with respect to $k'$. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.

In other words, with the addition of at most 9 additional slots, one can guarantee the existence of a stable matchings. This is independent of the size of the market or doctors preferences (it does assume responsive preferences on the part of hospitals). The key tool  is Scarf’s lemma which is a wonderful device for converting results about cardinal matching problems into results about ordinal matching problems. For more on this, consult the paper by Kiralyi and Pap, who should be credited with a formulation of Scarf’s lemma that makes its usefulness evident.