Market Design Class (Session 2)

A mathematical detour in this session. Stated and proved some basic results in combinatorial optimization that have applications in matching and auction theory. The first is the max-flow-min-cut theorem. I use it to prove Hall’s marriage theorem as well as derive the Border-Matthews characterization of implementable interim allocation rules. It has other applications. Itai Sher, for example, uses it in the analysis of a special case of the Glazer-Rubinstein model of persuasion. Mobius et al use it in their study of capital flows in social networks (the Peruvian village paper). Olszewski and myself have a forthcoming paper where we use it to talk about team formation.

Then, on to polymatroids which can be used to show the assignment problem retains its integrality property in the presence of additional constraints. These additional constraints arise in, for example, school choice problems. See the paper by Budish, Che, Kojima and Milgrom for a list of examples.

A summary of the session appears here.mktdesign2

Market Design Class (Session 1)

Bit the bullet and started a (reading) course on market design. The plan is to begin with some  lectures that cover some of  the usual stuff that is covered followed by readings. First session was on the Shapley-Shubik (SS) assignment model. A summary can be obtained by clicking on mktdesign1

The readings cover the following topics:

1) Credit Default Swaps

du & zhu

gupta & sundarjan

chernov, gorbenko & makarov

2) Bankruptcy
The Economics of Bankruptcy Reform Author(s): Philippe Aghion, Oliver Hart, John Moore Source: Journal of Law, Economics, & Organization, Vol. 8, No. 3 (Oct., 1992), pp. 523-546

New Approach to Corporate reorganization by Lucien Bebchuk, Harvard Law Review, 1988

Analysis of secured debt, Stultz and johnson, JFE, 1985

3) Healthcare Markets

Ho, Katherine 2009. “Insurer-Provider Networks in the Medical Care Market.” American Economic Review, 99(1): 393–430.

Fong and Schwarz

Arrow & cast of thousands

4)  IPO’s

Jaganathan et al

Jovanovich et al

5)  Affirmative Action
Hickman
Fryer & Loury 
Chung

5) Wages, centralized matching, unraveling
Bulow & Levin
Roth
Halaburda

Life, liberty and intellectual property

So, wikipedia is dark today in protest of an initiative in congress to block sites that link to sites that infringe on copyrighted intellectual property. Ever noticed before how many times a day you use wikipedia ?

Here is what I don’t get about this whole idea of “copyrighted intellectual property”. Is it something advocated on moral grounds or on economic grounds ? I mean, when Bob sneaks into Alice’s vineyard and eats the grapes without permission, we view it as a moral atrocity; It’s just a wicked thing to do; It invokes the wrath of the gods; Moses explicitly forbade it. To be sure, it’s hard to pin down what exactly makes the vineyard belong to Alice without getting into a recursive definition of ownership, and if we try tracing back the vineyard from one legitimate owner to another we arrive to the first man who just fenced a piece of land and said “This is mine”. But here the economic argument kicks in — Most of us don’t begrudge this initial act of illegitimate fencing because the bastard who committed it was the founder of civil society. We like the idea of civil society. We like prosperity and growth. Without protection of private property we will have none of these.

But what about protection of “intellectual property” ? Clearly this is not a necessary condition for a civil society. It’s also not a necessary condition for production of knowledge and culture. We had Plato and Archimedes and Cicero and Shakespeare and Newton before it occurred to anybody that Bob has to gets Alice’s permission to reproduce a code that Alice wrote. Coming to think about it, when did the concept of intellectual property pop up anyway ? Waitaminute let me just check it up on wikipedia. Oops.. What did we ever do before wikipedia ?

The White House thinks that intellectual property is justified on economic grounds

Online piracy is a real problem that harms the American economy, and threatens jobs for significant numbers of middle class workers and hurts some of our nation’s most creative and innovative companies and entrepreneurs. It harms everyone from struggling artists to production crews, and from startup social media companies to large movie studios.

I wonder if this assertion backed by some empirical research ? I realize some people lose their job because of online piracy. Also, Some people lost their jobs following the introduction of ATMs. But we view ATMs as positive development since it made a certain service way cheaper. My guess is that the same is true about intellectual piracy — it makes distribution of culture and knowledge cheaper and therefore makes also the production of culture and knowledge cheaper. True, some companies, particularly the established ones, are damaged by intellectual theft. Other companies, particularly startups, benefit. One may argue that intellectual piracy destroys incentive to produce and therefore no new culture or knowledge will be produced absent some protection for intellectual property. But this is a claim that can be empirically checked no ? We live in a world of file sharing and user generated (often stolen) content sites. Are there less books written ?

The economics job market

Embassy Suite hotel Saturday morning. Photo by Jacob Leshno.

Brouwer implies Nash implies Brouwer

They say that when Alfred Tarski came up with his theorem that the axiom of choice is equivalent to the statement that, for every set , and have the same cardinality, he first tried to publish it in the French PNAS. Both venerable referees rejected the paper: Frechet argued there is no novelty in equivalence between two well known theorems; Lebesgue argued that there is no interest in equivalence between two false statments. I don’t know if this ever happened but it’s a cool story. I like to think about it everytime a paper of mine is rejected and the referees contradict each other.

Back to game theory, one often hears that the existence of Nash Equilibrium is equivalent to Brouwer’s fixed point theorem. Of course we all know that Brouwer implies Nash but the other direction is more tricky less known. I heard a satisfying argument for the first time a couple of months ago from Rida. I don’t know whether this is a folk theorem or somebody’s theorem but it is pretty awesome and should appear in every game theory textbook.

So, assume Nash’s Theorem and let be a compact convex set in and be a continuous function. We claim that has a fixed point. Indeed, consider the two-player normal-form game in which the set of pure strategies of every player is , and the payoffs under strategy profile is for player I and for player II. Since strategy sets are compact and the payoff function is continuous, the game has an equilibrium in mixed strategies. In fact, the equilibrium strategies must be pure. (Indeed, for every mixed strategy of player II, player 1 has a unique best response, the one concentrated on the barycenter of ). But if is a pure equilibrium then it is immediate that .

Update I should add that I believe that the transition from existence of mixed Nash Equilibrium in games with finite strategy sets to existence of mixed Nash Equilibrium in games with compact strategy sets and continuous payoffs is not hard. In the case of the game that I defined above, if is a dense subset of and is a mixed equilibrium profile in the finite game with the same payoff functions and in which both players are restricted to the pure strategy set , then an accumulation point of the sequence in the weak topology is a mixed strategy equilibrium in the original game.

Belief consistency and trade consistency

A short presentation of a new paper by Ehud Lehrer and Dov Samet revisiting the question of characterizing situations in which no agreeable bet exist between players.  The paper answers the question for a countable state space. The case of arbitrary state space is still open.

For more GT papers clips of a different style look at posts of Rakesh and Noam.

Merry christmas !

Is Education a Public Good?

Was a question that came up when Jonathan Weinstein and I dined recently. This post is a summary of that conversation.

Certainly not if one goes by the textbook definition (non-rivalrous and non-excludable). Nevertheless, it is generally accepted that Government should fund primary and secondary education. If there is dissent, it is over whether funding should continue until tertiary education, and over whether government should limit itself to funding rather than furnishing education as well. Why should the Government be in the business of funding education at the primary and secondary level? Three answers come to mind.

1)An educated work force is essential for economic growth and competitiveness (more prosaically, its nicer to live in a world where car mechanics are capable of deduction).
If this were the case there would be sufficient incentive for the private provision of and acquisition of education.

2) An educated and informed citizenry is essential for the proper functioning of a democracy.
If one were serious about this, require a civics test before voting. The tortured history of slavery and civil rights may make this repugnant in the US, but not elsewhere. In any case, immigrants to the US who wish to acquire citizenship and so the vote must pass a such a test.

3) Insurance against the ovarian lottery?
Then, why do we provide it to all? Shouldn’t publicly supported education be means tested? If it is insurance against parents who would not invest in their children, wouldn’t it be better to send the children to boarding schools. Before you roar `how Dickensian’ (Gingrinchian?), it is worth keeping in mind that the wealthy in England have been doing it since before the flood (which upon reflection may not be the strongest argument).

We’ve touched upon the funding question, but there is another. Should the government be in the business of providing education as well? For higher education, in the US there is general acceptance of a model where students have means-tested vouchers (called pell grants, financial aid and student loans) to attend the college of their choice (from among those that have accepted them). Yet, there is resistance to such a system at the primary and secondary level. What is it one should fear happening at this level that does not materialize at the tertiary level? One possibility is sorting of students. If publicly supported education is insurance, one would want to limit the ability of private schools to sort students. One could achieve this with restrictions of selectivity. Indeed, if one looks at tertiary education in the US, private institutions that take money from state, even indirectly, are subject to regulation by the state (who takes the King’s coin etc).

If vouchers became prevalent in early schooling, the attendant boom in private school enrollments would bring with it questions of what regulations are appropriate. Drastic changes in the composition of schools make it very difficult to say what would come of a large-scale program. This is a case where using state or local-level school systems as a laboratory for new ideas is valuable. In some communities, reform is underway in the form of charter schools, but slots are very limited. For a recent article on these matters, see the following NYT Op-Ed.

A (non)Application of Walkup’s Theorem to Matchings in Large Markets

This is a corrected version of an earlier post. A commenter (see below) spotted a mistake in the earlier post. I had thought that A (Walkup’s Theorem) implied B (perfect matchings are almost stable). A is certainly  true, and B is also true but at least the way I formulated it the implication did not follow. I mark the error with an asterisk below.

A forgotten gem in matching theory is David Walkup’s theorem about perfect matchings in random regular bipartite graphs (Discrete Math, 1980). Let be the set of girl vertices,  the set of boy vertices and suppose that . Have each boy vertex choose two girl vertices at random and each boy vertex choose two girl vertices at random. Then, according to Walkup, with probability  this bipartite graph contains a perfect matching. Karonski and Szpankowski (1992) showed you get by without having each vertex choose two vertices on the other side but roughly  of them; have each vertex choose one vertex on the other side. A vertex not chosen by a vertex on the opposite side gets another choice. Walkup’s Theorem was the first step on the road that led eventually to the proof of the  Parisi conjecture by Nair, Prabhakar and Sharma (2005). I have my own little contribution in this literature that I’d like to advertise.

Now lets put Walkup’s theorem to work. Let the utility that boy assigns to  girl be . Similarly, the utility that girl assigns to boy is . Assume that is large. Suppose the ‘s and ‘s are independent draws from distributions over For fixed ,    must have cardinality at least 2 for all  with high probability for large enough. Similarly, define

Now, let each boy chooses his favorite and second favorite girl from . *Observe that this is like choosing 2 vertices uniformly at random from the opposite side. Let each girl chooses her favorite and second favorite boy from . From Walkup we know that the resulting bipartite graph has a perfect matching with high probability.*

There is a fix not using Walkup. We care only about edges such that and . The probability that such an edge  exists (independently of the others) will be some fixed constant depending on and not . For example, if the distribution from which the and ‘s was uniform, it would be . From Erdos-Renyi such a random graph would have a perfect matching with high probability.

What can we say about this matching? If a boy prefers a girl not in , she clearly prefers one of the boys in that she is matched to, so the pair can’t form a blocking pair. If the matching so obtained can be blocked, no blocking pair can improve their utility by more than .

Consider now a large matching market. Tell each boy and girl to report their `top’ choices only. In other words, declare that you would rather be unmatched than be matched with someone not in the top . Pick a perfect matching with the property that no boy or girl is matched with anyone below their top (one exists with high probability). By the above, the matching will be `close’ to stable (if you accept a cardinal interpretation of utilities and that utilities of all agents are denominated on a common scale) and no agent can gain by much from misreporting their preferences. In other words, when markets are large (in this model) you don’t need to run a stable matching algorithm to get essentially a stable and incentive compatible outcome.

Kellogg’s Course Bidding System

I’m often asked about the course bidding system used at Kellogg to assign students to classes. Can it be gamed? Could it be improved? My advice  is don’t think hard about it because its largely cosmetic. Certain classes at Kellogg are scarce. They are scarce in spite of multiple sections being offered, because  the faculty member is not substitutable (like my colleague David Besanko who can make the problem of counting sheep riveting). Or, the course is scarce because the combination of subject and faculty is not substitutable (Kraemer on leadership). A scarce resource has to be rationed.

One could ration with money. Genuine coin of the realm. This would mean students in the same program end up paying different amounts for their degree. If one were to `think bravely’ for a moment, why not? Imagine one charges a flat fee plus a separate per course fee that depends on the scarcity of that course. Thus a student who cares very much about which professor delivers which course would pay more than one who did not care as much. One could argue that a program consisting entirely of Allon, Besanko, Chopra, Diermeier, Kraemer, Petersen, Rogers, Rucker, Stern, Zettlemeyer is very different from one consisting of Schmo, Schmo, Schmo and Vohra.

One could ration by lottery. This what we used to do. It imposed a tax on the administration because students who did not win would complain. After all, through no fault of their own they were denied the chance to take Professor X’s class.

One could use some combination of funny money and auctions. This is what we do. Students get a budget of points. The same budget for all students. A smaller number of classes are still oversubscribed as many bid essentially all their points for these classes. In these cases they are rationed by lottery. The only real effect is that complaints to administration drop. Now when a student does not get into a class, its their responsibility because they did not bid enough. It is true that there are simple modifications that could remove some of the anxiety associated with this system, but, again, this is cosmetic.

The vast majority of instructor-course combinations are substitutable. This is reflected in the bid prices for these combinations. In these cases, what drives preferences is time of day; 8.30 vs. 10.30 vs. 1.30 etc. The number of classrooms limits the number of 10.30 classes that can be offered. Packing bums into seats is easy. Ration and allow trade to sort out the preferences over time slots. There is little reason to agonize over getting an 8.30 slot when one wanted a 10.30 slot.  A more important issue  is what one thinks a Kellogg experience is supposed to be. Is it, for example, vital that each student have a chance to be at least in one class taught by a Kellogg faculty member generally acknowledged to be, for want of a word, WOW? If so, it is easy to determine which ones. Hand each member of the entering class a ticket to a subset of these course that guarantees them a seat if they choose to register for that class. Allow them to trade the tickets to sort out time and subject preferences.

A Sure Fire Research Idea

One provision of Dodd-Frank is that US companies must report the ratio of CEO pay to median employee pay in annual proxy statements. Call this quantity RATIO. Now pick some measure of company performance like return on equity (ROE) or return on assets (ROA). Regress RATIO against ROE etc. Report the sign of the coefficient. Whatever its sign (or p-value), one will have an interesting result that will be reported in the media. Here is the headline and title of the paper: Equity and the Bottom Line.