# Extending the extended Stable Marriage Problem using a Python class

As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the paper arxiv link here entirely using a class, I saw this question here that uses loops.

I still think that when one sees the Stable Marriage Problem, an agent like solution comes to mind. I would like to ask the community whether my implementation is sound and pythonic.

The central point is a Persons class as per below. The idea is that all functionality: sending messages, receiving messages, maintaining ranking of other group preferences, storing partner, matching and divorcing is a single agent class.

Then, other code GitHub/BAFurtado/HISMP/main.py calls the class, generates the agents and applies the conditions.

The biggest advantage, I see, is the flexibility to adapt and change the class. Hence, I extended the instability problem with the possibility that any of the agents (belonging to either group: Male or Female) could actually be active messengers. I also included a self.j signal that informs me whether a given agent has successfully messaged all the members of the other group.

Would gladly listen to your opinions and suggestions.

EDITED: Answering the comment below, I include the main code which calls the class, generates groups and makes one run, below the Persons class.

""" Main class of the agents.
Either Males or Females
Already prepared to be either ACTIVE or PASSIVE agents (see accompanying paper at arXiv)
"""

import numpy as np

class Person:

def __init__(self, name, active):
self.id = name
self.j = 0
self.my_ranking = None
self.my_partner = None
self.my_energy = None
self.status = active
self.messaged = False

def ranking(self, other_group):
group = other_group.copy()
np.random.shuffle(group)
self.my_ranking = group

def match(self, candidate):
self.my_partner = candidate

def divorce(self):
self.my_partner = None

def send_msg(self):
if self.status == True:
if self.my_partner == None:
for i in range(self.j, len(self.my_ranking)):
result = self.my_ranking[self.j].receive_msg(self)
self.j += 1
if self.j == len(self.my_ranking):
self.messaged = True
if result == '+':
break

def receive_msg(self, candidate):
if self.my_partner is None:
self.match(candidate)
candidate.match(self)
return '+'
elif [i.id for i in self.my_ranking].index(candidate.id) < \
[i.id for i in self.my_ranking].index(self.my_partner.id):
self.my_partner.divorce()
self.match(candidate)
candidate.match(self)
return '+'
else:
return '-'

def energy(self):
if self.my_partner is not None:
self.my_energy = [i.id for i in self.my_ranking].index(self.my_partner.id) + 1
return self.my_energy
else:
self.my_energy = len(self.my_ranking) + 1
return self.my_energy

class Male(Person):
pass

class Female(Person):
pass


And here the main code:

""" Actual running of each repetition """

import numpy as np

from persons import Male, Female

def main(males, females):
# Running algorithm
# Shuffle
np.random.shuffle(males)
np.random.shuffle(females)
# Personal Ranking
[i.ranking(females) for i in males]
[i.ranking(males) for i in females]

singles = (max(0, len(males) - len(females)), max(0, len(females) - len(males)))
# Messaging service
# All active people have sent messages to everyone on the other group
current = sum([1 for each in [males, females] for x in each if x.my_partner == None])
not_msg = sum([1 for each in [males, females] for x in each if (x.status == True) and (x.my_partner == None)
and (x.messaged == False)])
print('M, F theoretical singles: ', singles)
print('All currently single: ', current)
print('Not messaged: ', not_msg)

while not_msg > 0:
[x.send_msg() for x in males]
[x.send_msg() for x in females]
current = sum([1 for each in [males, females] for x in each if x.my_partner == None])
not_msg = sum([1 for each in [males, females] for x in each if (x.status == True)
and (x.my_partner == None)
and (x.messaged == False)])
print('Still single: ', current)
print('Not messaged: ', not_msg)
print('')

return males, females

def gen_groups(group1, group2, alpha, beta=1):
# Generate groups with a percentage (alpha) of active status (actively sends messages)
m1, f1 = [], []
for i in range(group1):
m1.append(Male(i, np.random.choice([True, False], p=[beta, 1 - beta])))
for j in range(group2):
f1.append(Female(j, np.random.choice([True, False], p=[alpha, 1 - alpha])))
return m1, f1

def calculate_energy(gr1, gr2, pp, homme, femme):
res_f = np.mean([femme[i].energy() for i in range(len(femme))])
res_m = np.mean([homme[i].energy() for i in range(len(homme))])
with open('saved-data/energy.csv', 'a') as fl:
fl.write('{};{};{};{};{}'.format(gr1, gr2, pp, res_m, res_f))
return res_m, res_f

if __name__ == '__main__':
g1 = 1000
g2 = 1000
p = 1
m, f = gen_groups(g1, g2, p)
m, f = main(m, f)
# 3. Print Energy
print('Final mean energy males: {}, females: {}'.format(calculate_energy(g1, g2, p, m, f)))


## 1 Answer

1. You set a precedence that your names are poorly chosen, and don't mean what you've selected. And so they make your code hard to read.

Pick one id or name. Looking at your code id/name is an int, and so why would you ever call it name?

status is a bool (and also called active), but a persons status can be a wide verity of things. Is it relationship-status - Single, married, looking? But that's three states, and you've used a bool...

my_partner has the useless prefix my_. And makes your code a little harder to read at times:

self.my_partner.my_partner
# vs
self.partner.partner


You have one function called match and another divorce. Where are unmatch and marry?

All this piles up to make me think 'is anything named correctly?' Which means I now no-longer trust your code and have to find the definition and usage of everything in your function to build that trust again.

2. Your class Person should change:

1. Rename all your functions and variables so they make sense and actually relate to each other and the task they're performing.
2. Move the messaged, my_ranking and j all out of Person. They're about the persons candidates, and so should go in their own class.
3. You should make a function _ranking that finds the index of the target passed to it from the candidates. This is as you've used the same code multiple times.
4. match is a two-way relationship, but you've only defined it one way. Either get rid of the function and use partner directly or make it two way. Same with divorce.
5. You should change send_msg to use guard statements so you don't get lots of indentation.
6. Changing receive_msg's name to attempt_match it makes sense to return a boolean on if the match was successful or not. Which is far better than + and -.
7. Remove the ranking function from Person. It makes your code harder to test and doesn't make much sense to me to have it in the class.
3. Add a Candidates class, this should be a standard iterable, whilst exhibiting a value queue that should be an iterator. This iterator should contain the code regarding messaged.

4. You should keep the np.random.shuffle and the Person.ranking code in the gen_groups function. As they're generating the groups.
5. You should move a lot of your main code into reusable functions.
6. Don't use comprehensions for side effects. If you need to loop over something and call a function use a for loop.
7. Most of your comprehensions are quite hard to read.
class Candidates:
def __init__(self, candidates):
self._candidates = candidates
self.messaged = False
self.queue = self._build_queue()

def __iter__(self):
return iter(self._candidates)

def _build_queue(self):
end = len(self.candidates)
for i, candidate in enumerate(self):
if i == end:
self.messaged = True
yield candidate

class Person:
def __init__(self, id_, active):
self.id = id_
self.active = active
self.partner = None
self.candidates = None

def _ranking(self, target):
return [c.id for c in self.candidates].index(target)

def match(self, partner):
self.partner = partner
partner.partner = self

def unmatch(self):
self.partner.partner = None
self.partner = None

def initiate_match_attempts(self):
if not self.status or self.partner is not None:
return

for candidate in self.candidates.queue:
if candidate.attempt_match(self):
break

def attempt_match(self, candidate):
if self.partner is None:
self.match(candidate)
return True

if self._ranking(candidate.id) >= self._ranking(self.partner.id):
return False

self.unmatch()
self.match(candidate)
return True

def energy(self):
if self.partner is not None:
return self._ranking(self.partner.id) + 1
else:
return len(self.candidates) + 1

import numpy as np

from persons import Candidates, Person

def join(males, females):
yield from males
yield from females

def find_solo(males, females):
return [
person
for persion in join(males, females)
if person.partner is None
]

def find_not_messaged(males, females):
return [
person
for person in join(males, females)
if person.active
and person.partner is None
and not person.candidates.messaged
]

def main(males, females):
delta = len(males) - len(females)
if delta >= 0:
singles = delta, 0
else:
singles = 0, abs(delta)

current = len(find_solo(males, females))
not_msg = len(find_not_messaged(males, females))

print('M, F theoretical singles: ', singles)
print('All currently single: ', current)
print('Not messaged: ', not_msg)

while not_msg:
for person in join(males, females):
person.initiate_match_attempts()

current = len(find_solo(males, females))
not_msg = len(find_not_messaged(males, females))
print('Still single: ', current)
print('Not messaged: ', not_msg)
print('')
return males, females

def randomize_candidates(sample):
sample = sample.copy()
np.random.shuffle(sample)
return Candidates(sample)

def gen_groups(group1, group2, alpha, beta=1):
males = [
Person(i, np.random.choice([True, False], p=[beta, 1 - beta]))
for i in range(group1)
]
females = [
Person(i, np.random.choice([True, False], p=[alpha, 1 - alpha]))
for i in range(group2)
]

np.random.shuffle(males)
np.random.shuffle(females)

for male in males:
male.candidates = randomize_candidates(females)

for female in females:
female.candidates = randomize_candidates(males)

return males, females

def calculate_energy(gr1, gr2, pp, homme, femme):
res_f = np.mean([femme[i].energy() for i in range(len(femme))])
res_m = np.mean([homme[i].energy() for i in range(len(homme))])
with open('saved-data/energy.csv', 'a') as fl:
fl.write('{};{};{};{};{}'.format(gr1, gr2, pp, res_m, res_f))
return res_m, res_f

if __name__ == '__main__':
g1 = 1000
g2 = 1000
p = 1
m, f = gen_groups(g1, g2, p)
m, f = main(m, f)
# 3. Print Energy
print('Final mean energy males: {}, females: {}'.format(calculate_energy(g1, g2, p, m, f)))

• There is typo in find_solo function, an extra i. Also, it should be 'active', instead of status in initiate_match_attempts. Running was about the same time (4.79-08). All in all, the suggestions make good sense. I had never used yield and having a candidates class and not keeping the whole other group within each object is also nice. However, I was not able to replicate my output (maybe a bug on my part?). And that I think is relevant. The script never stopped for the case with groups sized 1, 999. Couldn't understand why. Anyway, appreciate all the lessons learned. Thanks. – B Furtado Mar 17 '19 at 15:50