Whats the problem? Something like stable marriage problem but without sex. Stable Marriage Problem (SM) Whats the problem? Ant: Bea, Ann, Cat Ann: Bob, Ant, Cal

Bob: Bea, Cat, Ann Bea: Cal, Ant, Bob Cal: Ann, Bea, Cat Cat: Cal, Bob, Ant -

- Men rank women, Women rank men Match men to women in a matching M such that there is no incentive for a (m,w) pair not in M to divorce and elope i.e. it is stable, there are no blocking pairs Order n squared

Stable Marriage Problem (SM) Whats the problem? Ant: Bea, Ann, Cat Ann: Bob, Ant, Cal Bob: Bea, Cat, Ann Bea: Cal, Ant, Bob

Cal: Ann, Bea, Cat Cat: Cal, Bob, Ant - - Men rank women, Women rank men

Match men to women in a matching M such that there is no incentive for a (m,w) pair not in M to divorce and elope i.e. it is stable, there are no blocking pairs Order n squared Stable Marriage Problem (SM) Whats the problem?

Ant: Bea, Ann, Cat Ann: Bob, Ant, Cal Bob: Bea, Cat, Ann Bea: Cal, Ant, Bob Cal: Ann, Bea, Cat Cat: Cal, Bob, Ant

- - Men rank women, Women rank men Match men to women in a matching M such that there is no incentive for a (m,w) pair not in M to divorce and elope i.e. it is stable, there are no blocking pairs

Order n squared Stable Marriage Problem (SM) Whats the problem? Ant: Bea, Ann, Cat Ann: Bob, Ant, Cal

Bob: Bea, Cat, Ann Bea: Cal, Ant, Bob Cal: Ann, Bea, Cat Cat: Cal, Bob, Ant - -

Men rank women, Women rank men Match men to women in a matching M such that there is no incentive for a (m,w) pair not in M to divorce and elope i.e. it is stable, there are no blocking pairs Order n squared Stable Roommates (SR)

Whats the problem? Stable Roommates (SR) Whats the problem? Order n squared (Knuth thought not) Stable Roommates (SR)

Whats the problem? Order n squared (Rob thought so) Stable Roommates (SR) Whats the problem? The green book

Stable Roommates (SR) Whats the problem? Taken from The green book 10 agents, each ranks 9 others, gender-free (n=10, n should be even) Stable Roommates (SR)

Whats the problem? 7 stable matchings Taken from The green book Stable Roommates (SR) 1985 Whats the problem?

Code The Algorithm (Pascal) Stable Roommates (SR) 1985 Whats the problem?

Code The Algorithm (Pascal) Stable Roommates (SR) Whats the problem? The Algorithm (Pascal) Stable Roommates (SR)

Whats the problem? The Algorithm (Pascal) Stable Roommates (SR) Whats the problem? The Algorithm (Pascal)

Stable Roommates (SR) Whats the problem? The Algorithm (Pascal) Stephan & Ciaran spotted something! Stable Roommates (SR) A simple constraint

model Stable Roommates (SR) A simple constraint model Preference list for agent i Stable Roommates (SR)

A simple constraint model Preference list for agent i , = agent j is agent is kth choice

Stable Roommates (SR) A simple constraint model Preference list for agent i 3=5,6,8,2,1,7,10,4,9 Stable Roommates (SR)

A simple constraint model Preference list for agent i 3,5=1 The 5th preference of agent 3 is agent 1

Stable Roommates (SR) A simple constraint model Preference list for agent i , = agent j is agent is kth choice

, = agent j is agent is kth choice Stable Roommates (SR) A simple constraint model

Preference list for agent i , = agent j is agent is kth choice , = agent j is agent is kth choice NOTE: a rank value that is low is a preferred choice (large numbers are bad)

Stable Roommates (SR) A simple constraint model Preference list for agent i , =

agent j is agent is kth choice 3,5 =1 agent 5 is agent 3s 1st choice Stable Roommates (SR) A simple constraint model

Preference list for agent i , = agent j is agent is kth choice 3,5 =1 agent j is agent is kth choice

{1. . 1 } constrained integer variable agent i with a domain of ranks Stable Roommates (SR) A simple constraint model Preference list for agent i

, = agent j is agent is kth choice 3,5 =1 agent j is agent is kth choice 7=6

agent 7 gets 6th choice and that is agent 10 Stable Roommates (SR) A simple constraint model Given two agents, i and j, if agent i is matched to an agent he prefers less than agent j then agent j must match up with an agent he prefers to agent i

Stable Roommates (SR) A simple constraint model Given two agents, i and j, if agent i is matched to an agent he prefers less than agent j then agent j must match up with an agent he prefers to agent i Stable Roommates (SR)

A simple constraint model Given two agents, i and j, if agent i is matched to an agent he prefers less than agent j then agent j must match up with an agent he prefers to agent i (1) agent variables, actually we allow incomplete lists! Stable Roommates (SR)

A simple constraint model Given two agents, i and j, if agent i is matched to an agent he prefers less than agent j then agent j must match up with an agent he prefers to agent i (1) agent variables, actually we allow incomplete lists! (2) If agent i is matched to agent he prefers less than agent j then agent j must match with someone better than agent i

Stable Roommates (SR) A simple constraint model Given two agents, i and j, if agent i is matched to an agent he prefers less than agent j then agent j must match up with an agent he prefers to agent i (1) agent variables, actually we allow incomplete lists! (2) If agent i is matched to agent he prefers less than agent j

then agent j must match with someone better than agent i (3) If agent i is matched to agent j then agent j is matched to agent i Given two agents, 1 and 3, if agent 1 is matched to an agent he prefers less than agent 3 then agent 3 must match with an agent he prefers to agent 1 (2)

1: 8 2 9 3

6 4 5 7 10 3:

5 6 8 2 1

7 10 4 9 Given two agents, 1 and 3, if agent 1 is matched to agent 3 then agent 3 is matched to

agent 1 (3) 1: 8 2 9

3 6 4 5 7

10 3: 5 6 8 2

1 7 10 4 9

choco choco Read in the problem choco Build the model choco

Find and print first matching Neat Can model SMI as SRI Ant: Bea, Ann, Cat Bob: Bea, Cat, Ann

Cal: Ann, Bea, Cat Ann: Bob, Ant, Cal SM Bea: Cal, Ant, Bob Cat: Cal, Bob, Ant men SRI women

women+6 Yes, but whats new here? Yes, but whats new here? 1. Model appeared twice in workshops 2. Applied to SM but not SR! (two sets of variables, more complicated) 3. One model for SM, SMI, SR & SRI 4. Simple & elegant

Yes, but whats new here? 1. Model appeared twice in workshops 2. Applied to SM but not SR! (two sets of variables, more complicated) 3. One model for SM, SMI, SR & SRI 4. Simple & elegant But this is hard to believe it is slower than Robs 1985 results!

Yes, but whats new here? 1. Model appeared twice in workshops 2. Applied to SM but not SR! (two sets of variables, more complicated) 3. One model for SM, SMI, SR & SRI 4. Simple & elegant But this is hard to believe it is slower than Robs 1985 results! Cubic to achieve phase-1 table

Not so neat A specialised constraint When an agent s d om ain is filt

ered AC revises a ll constra ints that invo lve that variable. A specialised constraint

When an agent s d om ain is filt ered AC revises a ll constra ints aints

r t s n o is n c t a h t case

s i h t n I that invo lve that variable.

A specialised constraint When an agent s d om ain is filt ered AC revises a ll constra ints

that invo aints r t s n o is n c t

a h t case s i h t n I We ca

n do b etter t han th is, reduci n g com plexity

of mo d el by O (n) lve that variable. A specialised constraint

I implemented a specialised binary SR constraint and an n-ary SR constraint This deals with incomplete lists This is presented in the paper You can also download and run this A specialised constraint Heres the code. Not much to it A specialised constraint

Constructor A specialised constraint awakening A specialised constraint lower bound changes

A specialised constraint upper bound changes A specialised constraint removal of a value A specialised constraint instantiate

Empirical study When I was younger, my mother did things to annoy me Empirical study SR: simple constraint model, enumerated domains SRB: simple constraint model, bound domains SRN: specialised n-ary constraint, enumerated domains

10 < n < 100: read, build, find all stable matchings 100 < n < 1000: read, build, find all stable matchings This is new (so says Rob and David) n, average run time, nodes (maximum), proportion with matchings, maximum number of matchings So? Well, think on this

Whats still to do? Prove that the model finds a stable matching in quadratic time This was all my own work well, with some help from David Manlove Rob Irving,

Jeremy Singer Ian Gent Chris Unsworth Stephan Mertens Ciaran McCreesh Paul Cockshott Joe Sventek Augustine Kwanashie Andrea