Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Kitty Meeks: Solving hard stable matching problems involving groups of similar agents

LFCS seminar: Kitty Meeks: Solving hard stable matching problems involving groups of similar agents

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Oct 03, 2017
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

Abstract:

Matching problems occur in a wide range of real-world scenarios, such as the assignment of children to schools, college students to dorm rooms, and junior doctors to hospitals.  It is widely accepted that a "good" solution in such problems should be stable, meaning that is there is no incentive for agents involved in the scheme to make a private arrangement outside the scheme. In 1962, Gale and Shapley famously gave a polynomial-time algorithm to find a stable matching in the classical "stable marriage" problem in which all agents are matched, but in a number of more generalisations of the problem (where, for example, agents may be indifferent between some of the other agents, or find some potential partners unacceptable) it becomes NP-hard to find a stable matching of maximum size or even to determine whether any stable matching exists.

Here, I will present a new approach for addressing intractable matching problems, which allows the design of efficient parameterised algorithms.  We assume that agents can be grouped into "types" of similar agents, where the type of an agent determines both the agent's preferences and the way in which they are perceived by other agents; if agents form their preferences based on just a few attributes of the other agents, the number of different types in the instance is likely to be much smaller than the total number of agents.  Making use of the fixed parameter tractability of Integer Linear Programming, we demonstrate that many NP-hard stable matching problems are in FPT when parameterised by the number of different types of agent.

This is joint work with Baharak Rastegari (University of Bristol)

 

Document Actions