Monthly Archives: December 2016

How to find a dancing partner

And preferably one that doesn’t leave you

Already back in the early 60’s, David Gale and Lloyd Shapley constructed a matching algorithm which has become one of the crucial tools of modern market design. In particular, using examples of college admissions and stability of marriage, they presented a method how a market where money cannot serve as an allocation rule may reach a stable and pareto-optimal equilibrium. Other examples of such markets include organ donations, allocation of children to schools or assigning dorm rooms to college students.

Suppose the following example. There are women and men taking dancing lessons and before each lesson begins, they need to form dancing couples. Naturally, all participants will think about and compare the potential counterparts; they may even consider a list based on their preferences. As the authors prove mathematically, employing the Gale-Shapley (also called “deferred-acceptance”) procedure ensures that the solution to the problem, i.e. the couples that have formed, will be stable. By stable in this example we understand an allocation in which no two people of opposite sex would both rather have each other than their current partners, and thus will not switch partners given that their preferences do not change. After explaining the algorithm and its characteristics, the authors examine the optimality issue, which, however, is a more complex task and depends on a particular set-up of the problem.

The figure below shows an example of a stable outcome of the Gale-Shapley procedure based on the preferences of all 8 participants. The number for each pair represent the ranking of the counterpart among the four potential mates. As an example, the first cell – (1, 3) – tells us that A would be the first choice for alpha and alpha would be the third choice for A. Running the procedure yields the stable pairs whose preferences for each other are circled in the table. An interesting aspect of this particular outcome is that no participant was matched with his or her first choice. Nevertheless, the stability ensures that no participant could improve his situation while not leaving at least one other participant worse off. The results reached in this paper have had an enormously important impact on the future development of market design theory. Lloyd Shapley received a Nobel Prize in Economics in 2012 for this work and passed away in March this year; David Gale, who passed away in 2008, has not received the prize because it can only be awarded to living scientists.

matching algorithm

Reference: Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. Available here.


Get out of your social bubble

Recently, social media have become the primary source of information for many and thus play an increasingly important role in influencing opinions, and apparently more so for the young generation. The problem is that on social media, opinions you usually get exposed to become less and less diverse as a result of both automatic filtering algorithms (whose goal is to get as many shares as possible) and the fact that you are more likely to follow people with similar views (who are, in turn, likely to share information biased in favor of their opinion). An example is your Facebook feed, which is personalized based on your past clicks and likes, making you less likely to “see the bigger picture”. This phenomenon is called a filter bubble and it concerns both search engine results and social media. However, as some people argue (here or here), social media are a more powerful tool for filter bubbles, and this is a problem. Others think that when it comes to the really important decisions, it might not be that bad just yet, and there are even guidelines on how to get out of your filter bubble.

In a recent working paper, Shane Greenstein, Yuan Gu and Feng Zhu (all from Harvard Business School) analyzed whether Wikipedia, and in particular articles about US politics, are also affected by filter bubbles and thus become more biased over time. They chose politics because it is a good example of the so-called contested knowledge, which can be loosely defined as knowledge that answers questions for which there is no single “right answer”. Relying on metrics developed by Gentzkow and Shapiro’s 2010 article in Econometrica, the authors measure empirically whether selected Wikipedia articles become more or less segregated (i.e. slanted towards a certain view) over time.

Their results, somewhat optimistically, show that Wikipedia contributors increasingly offer content to those with different points of view, which reinforces unsegregated conversations at Wikipedia over time. Interestingly enough, the authors additionally estimate that this slant convergence process takes one year longer on average for Republicans than for Democrats. The authors stress the importance of the option to remove previously added material (such as on Wiki-style pages) or using aggregate contributions (such as Yelp or Rotten Tomatoes) over the social media style, where additional material just gets piled up on top of what is already there.

Collective intelligence, of which Wikipedia is perhaps the most astounding source, thus seems to cope fairly well with the filter bubble problem, at least for now. While we can, let’s all try to use that to our advantage and rely more on objective sources when forming opinions, challenge ideas shared by people we follow on social media, verify facts using multiple sources and most importantly, keep an open mind. And share this article with our filter bubbles.

Reference: Greenstein, S., Gu, Y., & Zhu, F. (2016). Ideological Segregation among Online Collaborators: Evidence from Wikipedians (No. w22744). National Bureau of Economic Research. Available here.