MATCH-UP 2015 is the third workshop in the series of interdisciplinary and international
workshops on matching under preferences. It is co-located, and is partially overlapped with, the COST Action IC1205 meeting on Matching and Fair Division
that takes place on 14-16 April 2015.
Group photos from the workshop: 1, 2, 3.
MATCH-UP 2017 will be hosted by Microsoft Research in Cambridge, MA, USA, and will take place between 20-21 April 2017.
The first MATCH-UP was held on 6 July 2008 at Reykjavík University as a satellite workshop of ICALP 2008.
MATCH-UP 2012, second in this series, was held on 19-20 July 2012 at Corvinus University of Budapest.
Matching 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
The remit of this workshop is to explore matching problems with preferences from the perspective of
algorithms and complexity, discrete mathematics, combinatorial optimization, game theory,
mechanism design and economics, and thus a key objective is to bring together
the research communities of the related areas.
List of topics
The matching problems under consideration include, but are not limited to:
- two-sided matchings involving agents on both sides (e.g. college admissions, resident allocation, job markets, school choice, etc.)
- two-sided matchings involving agents and items (e.g. house allocation, course allocation, project allocation, assigning papers to reviewers, school choice, etc.)
- one-sided matchings (roommates problem, kidney exchanges, etc.)
- matching with payments (assignment game, etc.)
- Katarína Cechlárová
Pavol Jozef Šafárik University in Košice, Slovakia
Assignment of teachers to schools - a new variation on an old theme
Several countries more or less successfully use centralized matching schemes for assigning teachers to vacant positions at schools.
We explore combinatorial and computational aspects of a possible similar scheme motivated by the situation characteristic for Slovak and Czech education system where each teacher specializes in two subjects. We present a model that takes into consideration that schools may have different capacities for each subject and show that its combinatorial structure leads to intractable problems even under several strong restrictions concerning the total number of subjects, partial capacities of schools and the number of acceptable schools each teacher is allowed to list. We propose several approximation algorithms. Finally, we present integer programming models and their application to real data.
- Christine Cheng
University of Wisconsin-Milwaukee, USA [+]
Fair Stable Matchings
It has long been known that Gale and Shapley's deferred acceptance
algorithm outputs stable matchings that are highly biased towards one
side of the matching. This has motivated the study of fair stable matchings.
In the first part of the talk, we will discuss the class of globally fair stable matchings.
Their fairness is derived from the fact that they are good representatives of the
set of stable matchings. We will also describe how our results extend to other objects
that form a distributive lattice.
In the second part of the talk, we will consider the Random Order Mechanism (ROM), an
iterative version of the deferred acceptance algorithm. When the ordering of the agents is chosen uniformly at random,
one can argue that the process ROM uses for arriving at a stable matching is procedurally fair. We shall present various
computational results with regards to the stable matchings that ROM can output.
- Hervé Moulin
University of Glasgow, UK [+]
One dimensional mechanism design
When agents' allocations are one-dimensional and preferences are convex, the three perennial goals of mechanism design, efficiency, prior-free incentive compatibility and fairness (horizontal equity) are compatible. This has been known for decades in the cases of voting and of division of a non disposable commodity. We show that it is in fact true when the range of allocation profiles is an arbitrary convex and compact set.
Examples include: load balancing with arbitrary flow graph constraints;!coordinating joint work inside a team or across teams, when individual contributions are substitutable or complementary; and any joint venture with a convex technology where each agent provides a single input or consumes a single output.
The set of efficient, incentive compatible and fair mechanisms is very rich, and additional requirements such as consistency are needed to identify reasonable candidates.
We call for three types of contributions.
See Submissions for more information.
- Format A contributed papers (now closed)
- original contribution
- at most 12 pages
- accepted papers will be published in proceedings
- Format B contributed papers (now closed)
- not necessarily original work
- no page limit
- only the abstract will be published in proceedings
- Poster abstracts
- poster to be presented at the poster session on Thursday evening
- title, abstract and author information will be published in proceedings
The workshop proceedings are available for download.
There are a limited number of assisted places, funded by SICSA, that will be awarded to PhD students studying Computer Science at SICSA universities.
These assisted places will cover the cost of registration but will not cover travel or accommodation.
See Registration for more information.
- Deadline for submission of contributed papers: 1 December 2014 (AoE - Anywhere on Earth)
- Notification of acceptance: 16 January 2015
- Deadline for final versions of papers and abstracts for the proceedings: 16 February 2015
- Deadline for applications for SICSA funded places: 20 February 2015
- Deadline for submission of poster abstracts for the proceedings: 2 March 2015
- Early registration deadline: 12 March 2015
- Workshop: 16-18 April 2015
If you require further information, please use the following email address for all enquiries regarding the workshop: email@example.com.
Click here for information about the MATCH-UP Steering Committee.
We gratefully acknowledge financial support from SICSA (The Scottish Informatics and Computer Science Alliance).
MATCH-UP 2015 is organised in cooperation with COST Action IC1205 on Computational Social Choice.
COST is supported by the
EU Framework Programme Horizon 2020