MATCH-UP: Matching Under Preferences

– Algorithms and Complexity

 

Satellite workshop of ICALP 2008

 

6 July 2008

Reykjavík, Iceland

 

 

David Gale

 

Dedicated to the memory of David Gale, 13 December 1921 - 7 March 2008

 

 

Puffins2Matching problems with preferences occur in widespread applications such as the assignment of school-leavers to universities, junior doctors to hospitals, students to campus housing, children to schools, kidney transplant patients to donors and so on.  The common thread is that individuals have preference lists over the possible outcomes and the task is to find a matching of the participants that is in some sense optimal with respect to these preferences.

 

The remit of this workshop is to explore matching problems with preferences with an emphasis on the algorithms and complexity perspective, but a key objective is also to bring together the computer science and economics communities who have tended to follow different paths when studying these problems previously.  Further background information about the workshop is available.

 

Invited speakers

·        Kurt Mehlhorn, Max Planck Institut fűr Informatik

o   Seminar title: Assigning papers to reviewers

·        Al Roth, Harvard University

o   Seminar title: “Kidney exchange: design and evolution of a computer-assisted matching mechanism”

·        Marilda Sotomayor, Universidade de São Paolo

o   Seminar title: “My encounters with David Gale”


List of topics

The matching problems under consideration include, but are not limited to:

 

 ·

bipartite matching problems with preference lists on both sides, where a matching is optimal if it is:

o   stable – this includes variants of the stable marriage and hospitals / residents problems;

o   rank-maximal (or otherwise optimal with respect to matching profile), minimum cost, popular or Pareto optimal.

 ·

bipartite matching problems with preferences on one side (includes house allocation / job matching / student-project allocation), where a matching is optimal if it is:

o   rank-maximal (or otherwise optimal with respect to matching profile), minimum cost, popular or Pareto optimal.

 ·

non-bipartite matching problems with preferences (includes kidney exchange / chess tournament problems), where a matching is optimal if it is:

o   stable – this includes variants of the stable roommates problem;

o   rank-maximal (or otherwise optimal with respect to matching profile), minimum cost, popular or Pareto optimal.


Submissions

Authors are invited to submit papers focussing on aspects of matching problems with preferences that are of relevance to the workshop.  Such a paper can either (i) be based on original results that have not been published previously, or (ii) survey existing results that have already appeared in the literature (provided that the majority of the survey text has not itself been published previously).

 

Submissions should be at most 12 pages in length, using 11-point font or greater, on A4 or US-letter paper with at least 1-inch margins round the text.  Papers will be selected according to (a) relevance to the workshop, (b) originality, significance and rigour (in the case of type (i) papers), and (c) interest to the community and coverage of the literature (in the case of type (ii) papers).

 

Submissions should be sent by email attachment to matchup@dcs.gla.ac.uk.

 

Accepted papers will be disseminated via the workshop website and informal working notes to be distributed at the workshop – this should not prevent the simultaneous or subsequent submission of contributed papers to other workshops, conferences or journals.  At least one author of each accepted paper must attend the workshop in order to present the paper.

 

Authors of selected accepted papers will be invited to submit their papers to a special issue of Algorithmica.

 

Accepted papers

The accepted papers are available here.

 

Workshop programme

The workshop programme is available here.

 

Workshop proceedings

The informal working notes (6.5Mb) distributed at the workshop can be downloaded from here.

 

Workshop photos

Some photos from the day itself can be viewed here.

 

Important dates

Deadline for submission of contributed papers: 11 May 2008

Notification of acceptance: 1 June 2008

Final version for working notes due: 10 June 2008

Workshop: 6 July 2008

 

Organising committee

·         Magnús M. Halldórsson, Reykjavík University

·         Rob Irving, University of Glasgow

·         Kazuo Iwama, Kyoto University

·         David Manlove, University of Glasgow

 

Registration

Click here for information about how to register for this workshop.  It is not necessary to register for the main ICALP conference in order to participate in this event.

 

Further information

e-mail: matchup@dcs.gla.ac.uk

Kyoto University

 

 

Háskólinn í Reykjavík

 

 

media_32250_en

 

 

 

We gratefully acknowledge financial support from the following sources:

 

School of Informatics, Kyoto University

School of Business, Reykjavík University

Department of Computing Science, University of Glasgow