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.