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


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 realworld
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 polynomialtime 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 NPhard
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 NPhard 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)