Proposed MSc projects for Russell Martin

Combinatorial Properties of the Stable Marriage Problem

The Stable Marriage Problem is a classical combinatorial and algorithmic problem. The problem was first formally stated in 1962 by David Gale and Lloyd Shapley, although hospitals had been using similar procedures to determine intern assignments before this time.

Simply stated, consider a set of n women and n men. Each woman has her own strict preference rating for the men, and similarly each man has one for the women. A marriage is a pairing of the men and women into n pairs (where each man and women are used once, of course in the pairings). The marriage is called "stable" if there does not exist a woman W and a man M such that W prefers M over her current partner and M prefers W over his current partner (else W and M would drop their partners and pair up themselves).

It is well-known that every set of preference lists admits at least one stable marriage, and there are efficient algorithms to find one. There are many variants of this problem such as to the case of roommates, where the pairs need not be male/female pairings.

The focus of this project is to first implement some related algorithms for these matching/marriage problems, and use them to explore the combinatorial properties of the marriage problem instances and related structures that arise from them.

Further description of the "Combinatorial Properties of the Stable Marriage Problem" project.

Simulated Annealing for the Permanent

The permanent is a classical #P-complete problem, meaning that there is no known efficient algorithm for exactly computing the permanent of an arbitrary (non-negative) matrix. Thus, good approximation algorithms for estimating the permanent are interesting and important as this problem arises in a variety of contexts. This project involves implementing one of the most recent approximation algorithms for the permanent that appeared in the 2006 Symposium on Discrete Algorithms, based on simulated annealing and the Markov chain Monte Carlo method. The focus will be on the permanent for a 0/1 matrix, as this is the most widely known problem in which the permanent arises. A 0/1 matrix is the adjacency matrix of a bipartite graph, and the permanent counts the number of perfect matchings in the graph.

The project will involve a significant programming commitment, likely using C/C++ (preferred) or Java. Familiarity with probability and some combinatorics/graph theory is also preferred but not absolutely required. Background material will be provided and supplemented by the project supervisor.

Further description of the "Simulated Annealing Project for the Permanent".

The Subset Take-away Game

David Gale's Subset Take-away Game is a two-player game defined on the set of integers S={1, 2, ..., n} for a positive integer n. Players alternate naming non-empty proper subsets of S, subject to the condition that they can't name a subset that contains a previously named set. A player loses when he or she is unable to name such a set.

For example, when n=2, Player 1 can name either of the sets {1} or {2}, and Player 2 then names the other one (the one that Player 1 didn't choose). Player 1 then loses as there are no sets left to name. When n=3, Player 1 names either a singleton set, or a set containing two elements. Player 2 can then win by naming the complementary set, as this leaves a smaller game equivalent to the case when n=1 (where we know that Player 2 wins). Note also that when n=1, Player 1 loses immediately (as the sets named must be proper subsets of S).

David Gale conjectured that the Subset Take-away Game is always a win for the second player, i.e. Player 2 has a winning strategy that, regardless of the moves of Player 1, can force a win. This has been proven (computationally) up to n=6, but is open beyond that point. A second conjecture is that a winning strategy for Player 2 begins by naming the complement of the first set named by Player 1.

This project is to undertake a computationally assisted demonstration that the conjecture is true (or, more interestingly, false) when n=7. In all honesty, I must admit that I'm not certain how to approach this problem to avoid the "combinatorial explosion" that occurs when examining the game space (or strategy space). There are 2⁷-2=126 non-empty proper subsets of S={1,2, ..., 7}. There is an easy reduction that shows that you need only consider the case when the opening move by Player 1 has either three or four elements in the set. Assuming the second conjecture to be true, this tells you what the first move of Player 2 should be. Beyond that, we're left with the difficult task of exploring the game tree as the game would continue. Without loss of generality, we can assume that Player 1 chooses {1,2,3} as an opening move, and Player 2 responds with {4,5,6,7} (or vice-versa, using the second conjecture to "name the complementary set"). These opening moves remove another 23 of the 126 initial sets (any superset of these two sets), leaving Player 1 with 101 possible second moves. Could some of these possible second moves by Player 1 be immediately dismissed as not viable for a winning strategy? Yes, likely some of them could, as they would leave the players with an equivalent game on a smaller initial ground set in which we know Player 2 has a winning strategy. Even so, the strategy space to explore seems very large, with an exponential-sized game tree.

This project will likely require some sophisticated programming in order to successfully finish this task (e.g. identifying equivalent subproblems that will reduce the overall computational load), but at the same time ensuring that the whole game tree has been examined correctly (i.e. no part of it has been overlooked).

Here is a paper that describes the Subset Take-away Game, a useful reduction, and a geomoetric way of viewing the problem. These authors were the ones who (computationally) proved the conjecture is true (Player 2 has a winning strategy) in the case n=6.

Other Projects

Ideas for other projects will be considered. The ones that will be of most personal interest will either involve a "randomized" component, some combinatorial mathematics, and/or some aspect of game theory.

Back to Russ's home page