Whats the problem? Something like stable marriage problem

Whats the problem? Something like stable marriage problem

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

Recently Viewed Presentations

  • The Epistles of Paul 14 of the 27

    The Epistles of Paul 14 of the 27

    This format of Paul's Epistles is sometimes a good thing to keep in mind as we go along reading them throughout the year - cause if you are not careful you can get lost in the letter format, get bored...
  • Principles of Macroeconomics

    Principles of Macroeconomics

    Money and the Federal Reserve. 30. Pre-class music: "Money, Money, Money" by ABBA (See Tip #587) According to this song, the only way to get the things one wants in life is to either work or find a wealthy partner...
  • Annual Professional Development Conference 2016 Wednesday 24 August

    Annual Professional Development Conference 2016 Wednesday 24 August

    It is impossible to timetable a subject so delivery starts part way into semester 1 and finishes part way into semester 2. FALSE. TRUE. FALSE. FALSE. Research Skills - True or False Question Answers. Wednesday 24th - Research Skills: Models...
  • MARRIAGES MOST HINDUS MARRY SOMEONE CHOSEN F O

    MARRIAGES MOST HINDUS MARRY SOMEONE CHOSEN F O

    Yes. Getting married is the most important decision a person can make. The most times in a person's life are marked by traditional ceremonies. These are a bit like signposts on the journey through life, guiding a person from one...
  • The Geometry of A Real Thing - Applied mathematics

    The Geometry of A Real Thing - Applied mathematics

    Stress. Steel is a real material (for making our real shelf), and experiences stress when a force is applied to it. Stress has units of force over area, or psi for our purposes. Large force distributed over a large area...
  • Contents of CRE Program Components

    Contents of CRE Program Components

    Times New Roman Pulse Conflict Resolution Education: , Models, Relationships to other Fields Contents of CRE Program Components Content of CRE Essential Skills and Abilities' CRE Program Models Relationship of CRE to Other Fields Violence Prevention Social and Emotional Learning...
  • Chapter 5 Global Reservation Technologies

    Chapter 5 Global Reservation Technologies

    Understand the guest cycle in a hotel - Reception, Registration, and Rooming (3Rs). Discuss the significance of "Moments of Truth" Managing waiting lines in a hotel. Read a Registration Card. List a variety of hotel uniformed service.
  • Hierarchy of Production Decisions  Forecasting: First, a firm

    Hierarchy of Production Decisions Forecasting: First, a firm

    Forecasting: First, a firm must forecast demand for aggregate sales over the planning horizon. ... The MRP gross requirements for Item A are shown here for the next 10 weeks. Lead time for A is three weeks and setup cost...