Library for Matchings with One Sided Preferences

0.7

Introduction

In Matchings with One Sided Preferences we are given a bipartite graph $G(V,E)$ where $V = \mathcal{A} \cup \mathcal{P}$. Set $\mathcal{A}$ denotes a set of applicants and set $\mathcal{P}$ of posts. Each applicant in $\mathcal{A}$ submits a preference list (a ranking of a subset of the posts, possibly including ties). Edges which are choice $i$ are called rank $i$ edges.

Given this setting we may ask for matchings which satisfy different optimization criteria. This library contains code for the two following such criteria.

Rank-Maximal Matchings

A rank-maximal matching is a matching which contains the maximum number of first choice edges. Given that constraint it contains the maximum number of second choice edges and so on. A rank-maximal matching can be computed in polynomial time. libMOSP contains three implementations which compute such a matching:

Except for the above, libMOSP contains an implementation of a rank-maximal matching algorithm with capacities. In this case the nodes of the right-side partition of the bipartite graph may have capacities larger that 1, i.e. they may be matched more than once. The library contains:

Popular Matchings

We say that a matching $M'$ is more popular than matching $M$ if more applicants prefer $M'$ than those who prefer $M$. Applicants who are indifferent are ignored. A matching $M$ is popular if there is no other matching which is more popular.

Popular matchings can also be computed in polynomial time (see here for more details), but unfortunately they do not always exist. In that case we wish to compute matchings which approximate the least unpopular matching (see here for more details).

libMOSP contains two algorithms.

libMOSP also provides routines to compute the so called "unpopularity factor" and the "unpopularity margin" of a matching (see McCutchen 2007).

Generators

The library also contains 4 random structured instance generators.

Requirements

This implementation is written in C++ and uses LEDA. The structure of the package follows that of a LEDA extension package (LEP).

Supported Platforms

This package has been tested on the following platforms:

  1. gcc 3.x, 4.0.x and 4.1.x under Linux
  2. gcc 3.x under SunOS 5.9
  3. gcc 3.x under Cygwin

but it may work on others too.

License

    This program can be freely used in an academic environment
    ONLY for research purposes, subject to the following restrictions:
 
    1. The origin of this software must not be misrepresented; you must not
       claim that you wrote the original software. If you use this software
       an acknowledgment in the product documentation is required.
    2. Altered source versions must be plainly marked as such, and must not be
       misrepresented as being the original software.
    3. This notice may not be removed or altered from any source distribution.
 
    Any other use is strictly prohibited by the author, without an explicit
    permission.
 
    This software is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Note that this package uses LEDA, which is not free.

News

Download

Code Example

Rank-Maximal Matchings

  #include <LEP/mosp/mosp.h>

  int main() {

      leda::graph G;

      // construct simple, loopfree, bipartite graph G 

      leda::edge_array<int> rank(G, 1);

      // fill up ranks

      leda::list< leda::edge > M = mosp::BI_RANK_MAX_MATCHING( G, rank );

        // do something with M

      return 0;
  }

Popular Matchings

 #include <LEP/mosp/mosp.h>

 int main() {

      leda::graph G;

      // construct simple, loopfree, bipartite graph G 

      leda::list< leda::node > A, B;

      // add left partition nodes to A, right partition nodes to B

      leda::edge_array<int> rank(G, 1);

      // fill up ranks

      leda::list< leda::edge > M;
      bool is_popular = mosp::BI_POPULAR_MATCHING( G, A, B, rank, M );

            // do something with M

      return 0;
 }

Popular Approximation

  #include <LEP/mosp/mosp.h>

  int main() {

      leda::graph G;

      // construct simple, loopfree, bipartite graph G 

      leda::list< leda::node > A, B;

      // add left partition nodes to A, right partition nodes to B

      leda::edge_array<int> rank(G, 1);

      // fill up ranks

      int phase;
      leda::list< leda::edge > M;
      bool is_popular = mosp::BI_APPROX_POPULAR_MATCHING( G, A, B, rank, M, phase );

      int unpopularity_factor;
      if ( mosp::BI_UNPOPULARITY_FACTOR( G, A, B, rank, M, unpopularity_factor ) )
                std::cout << "unpopularity factor = " << unpopularity_factor << std::endl;

            // do something with M

      return 0;
  }
Generated on Tue Feb 2 11:51:02 2010 for mosp LEDA Extension Package by  doxygen 1.6.1