Posts Tagged ‘combinatorics’

Matching theory is an active field in mathematics, economics, and computer science. It ensured a [Nobel memorial prize][1] for [Alvin E. Roth][2] and [Lloyd S. Shapley][3] in 2012. The theory is applied in the real world to match students and colleges, doctors and hospitals, and to organize the allocation of donor organs. It all started with a beautiful paper by [David Gale][4] and Lloyd Shapley in 1962: [College Admissions and the Stability of Marriage][5] (read it!). In this post, we study the simplest version of what is known as the stable marriage problem and take a look at inherent conflicts. The exposition follows chapter 22 of the wonderful book [Game Theory][6] by Michael Maschler, Eilon Solan, and Shmuel Zamir.

What are stable matchings?

There is a set \( G \) of \( n \) girls and a set \( B \) of \( n \) boys. All girls and boys are heterosexual and desperate enough to prefer every member of the opposite sex to staying single. Each girl \( g \) has preferences over the boys, represented by a [total order][7] \( \succeq_g \) on \( B \). Similarly, each boy \( b \) has preferences over the girls, represented by a total order \(\succeq_b\) on \( G \).

We want to pair up the girls and the boys. Formally, a matching is simply a [bijection][8] \( M \) from \(G\) to \(B\) and if \( f(g)=b \), we say that \( g \) and \( b \) are matched (under \( M\)). Now, nobody can force the girls and boys to be together, so we have to look at matchings in which the boys and girls are relatively content with whom they get. To be precise, a matching is stable if we cannot find a girl and a boy who prefer each other under their preference ordering to whomever they are matched with.

Are there any?

Before we go into a deep study of stable matchings, we ought to make sure that there are stable matchings. We do so by giving an explicit algorithm for finding a stable matching, the boy courtship algorithm.

more »

Introduction

Today we will play a small game which is really really simple. We will add up numbers to make numbers. And to keep the matters simple we will only deal with counting numbers \(1, 2, 3, \ldots\) As an example \(2 + 3 = 5\), but to make the game challenging we would reverse the problem. Let’s ask how we can split \(5\) into sum of other numbers. For completeness we take \(5\) also as one of the ways to express \(5\) as sum of numbers. Clearly we have the following other ways $$ 5 = 4 + 1 = 3 + 1 + 1 = 3 + 2 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$$ so that there are \(7\) different ways of adding numbers to make \(5\). We don’t take into account the order of summands. Also one number can be repeated if needed.

Partitions of a Number

It turns out that a whole generation of distinguished mathematicians (Euler, Jacobi, Ramanujan, Hardy, Rademacher etc) were also interested in playing the above game. And needless to say, they made the whole thing very systematic by adding some definitions (its their silly habit so to speak). Following their footprints we say that a tuple \((n_{1}, n_{2}, \ldots, n_{k})\) of positive integers is a partition of a positive integer \(n\) if $$n_{1} \geq n_{2} \geq \cdots \geq n_{k}\text{ and }n_{1} + n_{2} + \cdots + n_{k} = n$$ Thus \((3, 2), (3, 1, 1)\) etc are partitions of \(5\). If \((n_{1}, n_{2}, \ldots, n_{k})\) is a partition of \(n\) then we say that each of the \(n_{i}\) is a part of this partition, \(k\) is the number of parts, \(n_{1}\) is the greatest part and \(n_{k}\) the least part of this partition.

The mathematicians were really not so interested in finding individual partitions of a number \(n\), but were rather interested in finding out the total number of partitions of \(n\). The example above deals with \(n = 5\) and clearly there are \(7\) partitions of \(5\). You should convince yourself by taking a slightly larger number, say \(n = 8\) or \(n = 10\), that finding the number of partitions of any given number \(n\) is not that easy. Especially writing out each partition of \(n\) and then counting them all is very difficult. You may always feel that probably you have missed one of the partitions. Mathematicians however found out a smart way to count partitions. We explore this technique further.

more »