Group photos from the workshop: 1, 2, 3.

Next workshop

MATCH-UP 2017 will be hosted by Microsoft Research in Cambridge, MA, USA, and will take place between 20-21 April 2017.

Previous workshops

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.

Background

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 these preferences.

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

• 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.)

Invited speakers

• 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.

Submissions

• 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

Proceedings

Funding

Important dates

• 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

Contact us

Steering Committee

Sponsorship

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