#!/usr/bin/env python3
"""
Python3 implementation of solvers for fair inter- and intragroup pairing problems
Copyright (C) 2023-2026 Raymond Bisdorff
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
"""
#######################
__version__ = "$Revision: Python 3.13.13"
#-------------
from graphs import BipartiteGraph
[docs]
class InterGroupPairing(BipartiteGraph):
"""
Abstract root class with private and public methods for intergroup pairing graphs
"""
def __init__(self):
print('Abstract root class with private and public methods for intergroup pairing graphs')
def __repr__(self):
"""
Default description for FairPairing instances.
"""
reprString = '*------- InterGroupPairing instance description ------*\n'
reprString += 'Instance class : %s\n' % self.__class__.__name__
reprString += 'Instance name : %s\n' % self.name
reprString += 'Group sizes : %d\n' % len(self.vpA.voters)
reprString += 'Graph Order : %d\n' % self.order
reprString += 'Graph size : %d\n' % self.size
try:
reprString += 'Partners swappings : %d\n' % self.iterations
except:
pass
reprString += 'Attributes : %s\n' % list(self.__dict__.keys())
reprString += '---- Constructor run times (in sec.) ----\n'
try:
val = self.runTimes['totalTime']
reprString += 'Total time : %.5f\n' % val
except:
pass
try:
val = self.runTimes['dataInput']
reprString += 'Data input : %.5f\n' % val
except:
pass
try:
val = self.runTimes['storeData']
reprString += 'Store data : %.5f\n' % val
except:
pass
try:
val = self.runTimes['bipartiteGraph']
reprString += 'Bipartite graph : %.5f\n' % val
except:
pass
try:
val = self.runTimes['GroupCorrelations']
reprString += 'Group correlations : %.5f\n' % val
except:
pass
try:
val = self.runTimes['Correlations']
reprString += 'Average correlation: %.5f\n' % val
except:
pass
try:
val = self.runTimes['enhancing']
reprString += 'Enhancing fairness : %.5f\n' % val
except:
pass
try:
val = self.runTimes['copelandGraph']
reprString += 'Copeland graph : %.5f\n' % val
except:
pass
try:
val = self.runTimes['bachetGraph']
reprString += 'Bachet graph : %.5f\n' % val
except:
pass
try:
val = self.runTimes['maximalMatching']
reprString += 'Maximal matching : %.5f\n' % val
except:
pass
return reprString
[docs]
def computePermutation(self,matching):
"""
Renders the matching's permutation of *A* and *B* indexes.
.. note:: The prefix of group *A* voters must preceed the prefix of the group *B* voters in alphabetic order
"""
permutation = []
pairs = []
aKeys = [k for k in self.vpA.voters]
bKeys = [k for k in self.vpB.voters]
for m in matching:
pair = list(m)
sortedPair = []
if pair[0] in bKeys:
pairs.append([pair[1],pair[0]])
else:
pairs.append([pair[0],pair[1]])
pairs.sort()
for pair in pairs:
a = pair[1]
ai = bKeys.index(a)
permutation.append(ai+1)
return permutation
[docs]
def computePermutationGraph(self,matching):
"""
Renders the permutation graph of the matching
"""
from graphs import PermutationGraph
permutation = self.computePermutation(matching)
pg = PermutationGraph(permutation)
pg.name = 'matching-permutation'
return pg
def showPairing(self,matching=None):
print('*------------------------------*')
pairs = []
aKeys = [k for k in self.vpA.voters]
bKeys = [k for k in self.vpB.voters]
if matching is None:
matching = self.matching
for m in matching:
pair = list(m)
sortedPair = []
if pair[0] in aKeys:
pairs.append([pair[0],pair[1]])
else:
pairs.append([pair[1],pair[0]])
pairs.sort()
for pair in pairs:
print(pair)
[docs]
def showCopelandRankingScores(self):
"""
Print the individual Copeland ranking scores
"""
print('*---- Copeland ranking scores ----*')
aKeys = [x for x in self.vpA.voters]
bKeys = [x for x in self.vpB.voters]
print('group A',end=':\t')
for bj in bKeys:
print(bj,end='\t')
print()
for ai in aKeys:
print(' ',ai,end=':\t')
for bj in bKeys:
print('%d'% (self.copelandScores[ai][bj]), end='\t')
print()
print('----')
print('group B',end=':\t')
for ai in aKeys:
print(ai,end='\t')
print()
for bj in bKeys:
print(' ',bj,end=':\t')
for ai in aKeys:
print('%d'% (self.copelandScores[bj][ai]), end='\t')
print()
[docs]
def showBachetRankingScores(self):
"""
Print the individual Copeland ranking scores
"""
print('*---- Bachet ranking scores ----*')
aKeys = [x for x in self.vpA.voters]
bKeys = [x for x in self.vpB.voters]
print('group A',end=':\t')
for bj in bKeys:
print(bj,end='\t')
print()
for ai in aKeys:
print(' ',ai,end=':\t')
for bj in bKeys:
print('%d'% (self.bachetScores[ai][bj]), end='\t')
print()
print('----')
print('group B',end=':\t')
for ai in aKeys:
print(ai,end='\t')
print()
for bj in bKeys:
print(' ',bj,end=':\t')
for ai in aKeys:
print('%d'% (self.bachetScores[bj][ai]), end='\t')
print()
def showMatchingFairness(self,matching=None,
WithGroupCorrelations=True,
WithIndividualCorrelations=True):
#from decimal import Decimal
from statistics import mean,stdev
vpA = self.vpA
vpB = self.vpB
groupA = [a for a in vpA.voters]
groupB = [b for b in vpB.voters]
if matching is None:
matching = self.matching
self.showPairing(matching)
print('-----')
fitness = self.computeIndividualCorrelations(matching)
groupAScores = fitness[4]
groupBScores = fitness[5]
if WithIndividualCorrelations:
print('group A correlations:')
for pers in groupAScores:
print(' \'%s\': %+.3f' % (pers,groupAScores[pers]))
if WithGroupCorrelations:
corrs = [ groupAScores[pers] for pers in groupAScores]
print('group A average correlation (a) : %.3f' % (mean(corrs)))
print('group A standard deviation : %.3f' % (stdev(corrs)))
print('-----')
if WithIndividualCorrelations:
print('group B correlations:')
for pers in groupBScores:
print(' \'%s\': %+.3f' % (pers,groupBScores[pers]))
if WithGroupCorrelations:
corrs = [ groupBScores[pers] for pers in groupBScores]
print('group B average correlation (b) : %.3f' % (mean(corrs)))
print('group B standard deviation : %.3f' % (stdev(corrs)))
print('-----')
print('Average correlation : %.3f' % fitness[1])
print('Standard Deviation : %.3f' % fitness[2])
print('Unfairness |(a) - (b)| : %.3f' % fitness[6])
[docs]
def exportPairingGraphViz(self,fileName=None,
Comments=True,
graphType='png',graphSize='7,7',
matching=None,
edgeColor='blue',
bgcolor='cornsilk',
lineWidth=1):
"""
Exports GraphViz dot file for bipartite graph drawing filtering.
"""
import os
if Comments:
print('*---- exporting a dot file for GraphViz tools ---------*')
Akeys = [x for x in self.vpA.voters]
Bkeys = [x for x in self.vpB.voters]
vertexkeys = Akeys + Bkeys
n = len(vertexkeys)
if matching is None:
matching = self.matching
edges = matching
#Med = self.valuationDomain['med']
i = 0
if fileName is None:
name = self.name
else:
name = fileName
dotName = name+'.dot'
if Comments:
print('Exporting to '+dotName)
fo = open(dotName,'w')
fo.write('graph G {\n')
if bgcolor is not None:
fo.write('graph [ bgcolor = %s, fontname = "Helvetica-Oblique",\n fontsize = 12,\n label = "' % (bgcolor) )
else:
fo.write('graph [ fontname = "Helvetica-Oblique",\n fontsize = 12,\n label = "')
fo.write('\\nDigraph3 (graphviz), R. Bisdorff, 2023", size="')
fo.write(graphSize),fo.write('"];\n')
fo.write('splines=false;\n')
fo.write('node[shape=circle]\n')
fo.write('edge[color=%s]\n' % edgeColor)
fo.write('subgraph cluster_1r {\n')
n = len(Akeys)
for i in range(n):
fo.write(' %s [label="%s",fillcolor=white]\n' % (Akeys[i],Akeys[i]) )
for i in range(n-1):
fo.write(' %s--' % Akeys[i])
fo.write(' %s [style=invis]\n' % (Akeys[n-1]) )
fo.write(' label = "group A"\n')
fo.write(' color = white\n')
fo.write('}\n')
fo.write('subgraph cluster_1l {\n')
n = len(Bkeys)
for i in range(n):
fo.write(' %s [label="%s",fillcolor=white]\n' % (Bkeys[i],Bkeys[i]) )
for i in range(n-1):
fo.write(' %s--' % Bkeys[i])
fo.write(' %s [style=invis]\n' % Bkeys[n-1] )
fo.write(' label = "group B"\n')
fo.write(' color = white\n')
fo.write('}\n')
for m in matching:
pair = list(m)
pair.sort()
fo.write('%s--%s [constraint=false]\n' % (pair[0],pair[1]))
fo.write('}\n')
fo.close()
layout = "dot"
commandString = '%s -T%s %s -o %s.%s' % (layout,graphType,dotName,name,graphType)
if Comments:
print(commandString)
try:
from os import system
system(commandString)
except:
if Comments:
print('graphViz tools not avalaible! Please check installation.')
print('On Ubuntu: ..$ sudo apt-get install graphviz')
[docs]
def computeGaleShapleyMatching(self,Reverse=False):
"""
Documentation:
https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm
Our implementation is inspired by
https://johnlekberg.com/blog/2020-08-22-stable-matching.html
When *Reverse==False*, group *A* is proposing.
Otherwise, group *B* is proposing
"""
if Reverse:
vpA = self.vpB
vpB = self.vpA
else:
vpA = self.vpA
vpB = self.vpB
def pref_to_rank(pref):
# helper fct
return { a: {b: idx for idx, b in enumerate(a_pref)}
for a, a_pref in pref.items()}
from collections import deque
A = [a for a in vpA.voters]
B = [b for b in vpB.voters]
A_pref = vpA.linearBallot
B_pref = vpB.linearBallot
B_rank = pref_to_rank(B_pref)
# lvA candidates are the proposers
ask_list = {a: deque(bs) for a, bs in A_pref.items()}
pair = {}
#
remaining_A = set(A)
while len(remaining_A) > 0:
a = remaining_A.pop()
b = ask_list[a].popleft()
if b not in pair:
pair[b] = a
else:
a0 = pair[b]
b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
if b_prefer_a0:
remaining_A.add(a)
else:
remaining_A.add(a0)
pair[b] = a
#
return [frozenset([a, b]) for b, a in pair.items()]
[docs]
def isStableMatching(self,matching,Comments=True,Debug=False):
"""
Test for the existance of matching instabilities.
Our implementation is inspired by
https://johnlekberg.com/blog/2020-08-22-stable-matching.html
"""
def pref_to_rank(pref):
# helper fct
return { a: {b: idx for idx, b in enumerate(a_pref)} \
for a, a_pref in pref.items()}
from collections import namedtuple
vpA = self.vpA
vpB = self.vpB
Pair = namedtuple("Pair", ["groupA", "groupB"])
groupA = {a for a in vpA.voters}
groupB = {b for b in vpB.voters}
A_rank = pref_to_rank(vpA.linearBallot)
B_rank = pref_to_rank(vpB.linearBallot)
pairedMatching = []
for pair in matching:
pl = list(pair)
pl.sort()
pairedMatching.append(Pair(groupA=pl[0], groupB=pl[1]))
if Debug:
print(pairedMatching)
match_A = {pair.groupA : pair for pair in pairedMatching}
match_B = {pair.groupB : pair for pair in pairedMatching}
#print(match_B)
Unstable = False
for a in groupA:
for b in groupB:
if a != match_B[b].groupA and b != match_A[a].groupB:
if A_rank[a][b] < A_rank[a][match_A[a].groupB]\
and B_rank[b][a] < B_rank[b][match_B[b].groupA]:
if Comments:
print('Unstable match: ',\
a,match_A[a],b,match_B[b])
print(a,b,'<--', match_A[a].groupB)
print(A_rank[a][b],\
A_rank[a][match_A[a].groupB])
print(b,a,'<--',match_B[b].groupA)
print(B_rank[b][a], \
B_rank[b][match_B[b].groupA])
Unstable = True
if Unstable:
if Comments:
self.showPairing(matching)
print(' is unstable!')
return False
else:
if Comments:
self.showPairing(matching)
print(' is stable!')
return True
[docs]
def computeIndividualCorrelations(self,matching,Debug=False):
"""
Individual correlations for groups A and B
returns a tuple called fitness with following content
fitness=(matching,avgCorr,stdCorr,avgCorr-stdCorr,
groupAScores,groupBScores,
abs(avgCorrA-avgCorrB))
"""
# computing groupA's scores
from digraphs import IndeterminateDigraph
from decimal import Decimal
from statistics import mean, stdev
groupAScores = {}
vpA = self.vpA
vpB = self.vpB
groupA = [a for a in vpA.voters]
groupB = [b for b in vpB.voters]
for m in groupA:
edg = IndeterminateDigraph(order=len(vpA.candidates))
edg.actions = groupB
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
mmatch = [x for x in matching if m in x]
mmatch = [x for x in mmatch[0] if x != m]
relation = {}
for x in groupB:
relation[x] = {}
for y in groupB:
relation[x][y] = Med
n = len(edg.actions)
for i in range(n):
x = groupB[i]
for j in range(i+1,n):
y = groupB[j]
if x == mmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == mmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
#corr = edg.computeRankingCorrelation(vpA.linearBallot[m])
corr = edg.computeOrdinalCorrelation(vpA.ballot[m])
groupAScores[m] = Decimal('%.3f' % corr['correlation'])
# computing groupB's scores
groupBScores = {}
for w in groupB:
edg.actions = groupA
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
wmmatch = [x for x in matching if w in x]
wmmatch = [x for x in wmmatch[0] if x != w]
relation = {}
for x in groupA:
relation[x] = {}
for y in groupA:
relation[x][y] = Med
n = len(edg.actions)
for i in range(n):
x = groupA[i]
for j in range(i+1,n):
y = groupA[j]
if x == wmmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == wmmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
#corr = edg.computeRankingCorrelation(vpB.linearBallot[w])
corr = edg.computeOrdinalCorrelation(vpB.ballot[w])
groupBScores[w] = Decimal('%.3f' % corr['correlation'])
# computing matching fitness scores
fitness = []
aCorrelations = []
for w in groupAScores:
aCorrelations.append(groupAScores[w])
ACorr = mean(aCorrelations)
bCorrelations = []
for m in groupBScores:
bCorrelations.append(groupBScores[m])
BCorr = mean(bCorrelations)
fairness = abs(ACorr-BCorr)
matchingCorrelations = aCorrelations + bCorrelations
if Debug:
print(matching)
print(matchingCorrelations)
avgCorr = mean(matchingCorrelations)
stdCorr = stdev(matchingCorrelations)
if Debug:
print(avgCorr,stdCorr)
fitness=(matching,avgCorr,stdCorr,avgCorr-stdCorr,
groupAScores,groupBScores,fairness)
return fitness
[docs]
def enhanceMatchingLVFairness(self,matching,Reversed=False,
maxIterations=10,
Comments=False,Debug=False):
"""
Enhance fairness of given matching by using reciprocal linear voting profiles
"""
vpA = self.vpA
vpB = self.vpB
fg = matching
pairs = []
aKeys = [k for k in self.vpA.voters]
bKeys = [k for k in self.vpB.voters]
for m in matching:
pair = list(m)
sortedPair = []
if pair[0] in aKeys:
pairs.append([pair[0],pair[1]])
else:
pairs.append([pair[1],pair[0]])
pairs.sort()
## pairs = []
## for p in fg:
## pair = list(p)
## pair.sort(reverse=Reversed)
## pairs.append(pair)
## pairs.sort()
if Comments:
print(pairs)
n = len(pairs)
newPairs = pairs.copy()
t = 1
Enhanced = True
history = []
maxIterations = maxIterations
while Enhanced:
Enhanced = False
if Comments:
print('==>>> Iteration: ', t)
if Debug:
print(pairs)
enhanceFitness = []
for i in range(n):
pair1 = pairs[i]
for j in range(i+1,n):
if Debug:
print(i,j)
pair2 = pairs[j]
if [pair1,pair2] not in history:
# exchange right hands
rankDifA1 = -(vpA.linearBallot[pair1[0]].index(pair2[1]) \
-vpA.linearBallot[pair1[0]].index(pair1[1]))
rankDifA2 = -(vpA.linearBallot[pair2[0]].index(pair1[1]) \
- vpA.linearBallot[pair2[0]].index(pair2[1]))
difGroupA = rankDifA1 + rankDifA2
rankDifB1 = -(vpB.linearBallot[pair1[1]].index(pair2[0]) \
- vpB.linearBallot[pair1[1]].index(pair1[0]))
rankDifB2 = - (vpB.linearBallot[pair2[1]].index(pair1[0]) \
- vpB.linearBallot[pair2[1]].index(pair2[0]))
difGroupB = rankDifB1 + rankDifB2
if difGroupA <= difGroupB:
# enhance group A correlations
enhanceFitness.append(((difGroupA + difGroupB),(difGroupB-difGroupA),(i,j)))
else:
# enhance group B correlations
enhanceFitness.append(((difGroupA + difGroupB),(difGroupA-difGroupB),(i,j)))
if Debug:
print(enhanceFitness)
from operator import itemgetter
enhanceFitness.sort(reverse=True,key=itemgetter(0,1))
if Debug:
print(enhanceFitness[0])
i = enhanceFitness[0][2][0]
j = enhanceFitness[0][2][1]
if Comments:
print(i,pairs[i])
print(j,pairs[j])
pair1 = pairs[i]
pair2 = pairs[j]
npair1 = [pair1[0],pair2[1]]
npair2 = [pair2[0],pair1[1]]
if [npair1,npair2] in history:
print('!!!! Cycling :', [npair1,npair2])
if Debug:
print(history)
Enhanced = False
elif (enhanceFitness[0][0] >= 0):
# and (enhanceFitness[0][1] >= 0):
if Comments:
print(pair1,npair1)
print(pair2,npair2)
if Debug:
print(pair1[0],self.vpA.linearBallot[pair1[0]])
print(pair1[1],self.vpB.linearBallot[pair1[1]])
print(pair2[0],self.vpA.linearBallot[pair2[0]])
print(pair2[1],self.vpB.linearBallot[pair2[1]])
print(npair1,npair2)
print(newPairs)
newPairs.pop(i)
newPairs.insert(i,npair1)
newPairs.pop(j)
newPairs.insert(j, npair2)
if Debug:
print(newPairs)
history.append([npair1,npair2])
Enhanced = True
pairs = newPairs.copy()
t += 1
if t > maxIterations:
print('!!!! Too many iterations (max=%d): %d\n' % (maxIterations,t))
print('You may adjust the *maxIterations* parameter')
Enhanced = False
nfg = []
for pair in newPairs:
nfg.append(frozenset(pair))
if Comments:
print('Given matching')
self.showMatchingFairness(fg)
print('Fairness enhanced matching')
self.showMatchingFairness(nfg)
print('number of iterations:',t)
return nfg,t,history
[docs]
def computeCopelandScore(self,vpA,a,b):
"""
Replacement for the linear voting profiles information
when searching for promising swapping candidates
"""
from decimal import Decimal
ba = vpA.ballot[a]
score = Decimal('0')
candidates = [b for b in vpA.candidates]
k = len(candidates)
for i in range(k):
score += ba[b][candidates[i]] - ba[candidates[i]][b]
return score
[docs]
def computeBachetScore(self,vpA,a,b,Reversed=False):
"""
Replacement for the linear voting profiles information
when searching for promising swapping candidates
"""
from bachetNumbers import BachetInteger as BN
ba = vpA.ballot[a]
candidates = [b for b in vpA.candidates]
k = len(candidates)
vectorA = []
vectorB = []
for i in range(k):
vectorA.append(ba[b][candidates[i]])
vectorB.append(ba[candidates[i]][b])
bna = BN(vector=vectorA)
bnb = BN(vector=vectorB)
if Reversed:
score = (~bna) - (~bnb)
else:
score = bna - bnb
return score
[docs]
def enhanceMatchingGeneralFairness(self,matching,
maxIterations=10,
Comments=False,Debug=False):
"""
Enahance fairness of a given matching using any reciprocal voting profiles
"""
vpA = self.vpA
vpB = self.vpB
fg = matching
pairs = []
aKeys = [k for k in self.vpA.voters]
bKeys = [k for k in self.vpB.voters]
for m in matching:
pair = list(m)
sortedPair = []
if pair[0] in aKeys:
pairs.append([pair[0],pair[1]])
else:
pairs.append([pair[1],pair[0]])
pairs.sort()
if Comments:
print(pairs)
n = len(pairs)
newPairs = pairs.copy()
t = 1
Enhanced = True
history = []
maxIterations = maxIterations
while Enhanced:
Enhanced = False
if Comments:
print('==>>> Iteration: ', t)
if Debug:
print(pairs)
enhanceFitness = []
for i in range(n):
pair1 = pairs[i]
for j in range(i+1,n):
if Debug:
print(i,j)
pair2 = pairs[j]
if [pair1,pair2] not in history:
rankDifA1 = self.fitnessScores[pair1[0]][pair2[1]] - \
self.fitnessScores[pair1[0]][pair1[1]]
rankDifA2 = self.fitnessScores[pair2[0]][pair1[1]] - \
self.fitnessScores[pair2[0]][pair2[1]]
difGroupA = rankDifA1 + rankDifA2
rankDifB1 = self.fitnessScores[pair1[1]][pair2[0]] - \
self.fitnessScores[pair1[1]][pair1[0]]
rankDifB2 = self.fitnessScores[pair2[1]][pair1[0]] - \
self.fitnessScores[pair2[1]][pair2[0]]
difGroupB = rankDifB1 + rankDifB2
if difGroupA <= difGroupB:
# enhance group B correlations
enhanceFitness.append(((difGroupA + difGroupB),(difGroupB-difGroupA),(i,j)))
else:
# enhance group A correlations
enhanceFitness.append(((difGroupA + difGroupB),(difGroupA-difGroupB),(i,j)))
else:
if Debug:
print([pair1,pair2], ' in history !')
## if Debug:
## print(enhanceFitness)
from operator import itemgetter
enhanceFitness.sort(reverse=True,key=itemgetter(0))
if Debug:
print(enhanceFitness)
ie = enhanceFitness[0][2][0]
je = enhanceFitness[0][2][1]
if Comments:
print(ie,pairs[ie])
print(je,pairs[je])
pair1 = pairs[ie]
pair2 = pairs[je]
npair1 = [pair1[0],pair2[1]]
npair2 = [pair2[0],pair1[1]]
if [npair1,npair2] in history:
if Debug:
print(history)
print('!!!! Cycling :', [npair1,npair2])
Enhanced = False
elif (int(enhanceFitness[0][0]) >= 0):
if Comments:
print(pair1,npair1)
print(pair2,npair2)
if Debug:
print(npair1,npair2)
print(newPairs)
newPairs.pop(ie)
newPairs.insert(ie,npair1)
newPairs.pop(je)
newPairs.insert(je, npair2)
if Debug:
print(newPairs)
history.append([npair1,npair2])
Enhanced = True
pairs = newPairs.copy()
t += 1
if Debug:
nfgt = []
for pair in newPairs:
nfgt.append(frozenset(pair))
fitness = self.computeIndividualCorrelations(nfgt)
print( '%.3f, %.3f, %.3f' \
% (fitness[1],fitness[2],fitness[6]) )
if t > maxIterations:
print('!!!! Too many iterations (max=%d): %d\n' % (maxIterations,t))
print('You may adjust the *maxIterations* parameter')
Enhanced = False
nfg = []
for pair in newPairs:
nfg.append(frozenset(pair))
fitness = self.computeIndividualCorrelations(nfg)
if Comments:
print('Given matching')
self.showMatchingFairness(fg)
print('Fairness enhanced matching')
self.showMatchingFairness(nfg)
print('number of iterations:',t)
return nfg,t,history,fitness
#------ specialized pairing classes -------
[docs]
class FairestBachetInterGroupMatching(InterGroupPairing):
"""
Testing
"""
def __init__(self,vpA,vpB,
maxIterations=None,
Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
self.runTimes = {}
t0 = time()
# store input data
self.vpA = vpA
self.vpB = vpB
self.verticesKeysA = [x for x in vpA.voters]
self.verticesKeysB = [y for y in vpB.voters]
self.name = 'fairness-enhanced-matching'
k = len(vpA.voters)
self.order = 2 * k
if maxIterations is None:
maxIterations = self.order
self.maxIterations = maxIterations
bac = BestBachetInterGroupMatching(vpA,vpB)
self.bac = bac
initialMatching = bac.matching
self.fitnessScores = bac.bachetScores
if Comments or Debug:
print('Best Bachet initial matching')
print(bac.matching)
fitness = self.computeIndividualCorrelations(initialMatching)
#print(fitness)
t2 = time()
if fitness[1] == Decimal('1.0'):
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
em,it,history,fitnessG = self.enhanceMatchingGeneralFairness(
initialMatching,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
#print(fitnessG)
if fitness[1] >= fitnessG[1] and fitness[2] <= fitnessG[2]:
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('Storing maximal fairness enhanced given matching')
self.initialMatching = initialMatching
self.matching = fitnessG[0]
self.iterations = it
self.history = history
self.maxCorr = fitnessG[1]
self.stDev = fitnessG[2]
self.groupAScores = fitnessG[4]
self.groupBScores = fitnessG[5]
self.runTimes['enhancing'] = time() - t2
#storing the Graph data
self.vertices = vpA.voters | vpB.voters
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
self.runTimes['totalTime'] = time() - t0
[docs]
class FairnessEnhancedInterGroupMatching(InterGroupPairing):
"""
The class enhances the fairness of a given matching.
*Parameters*:
* *vpA* : any VotingProfile instance
* *vpB* : reciprocal VotingProfile instance
* *initialMatching* : a given perfect matching
if *None* a matching is being previously constructed
elif 'bestCopeland' a best Copeland intergroup matching is used,
elif 'Random' a shuffled version of the bi is matched to the ai,
* The *seed* parameter is used for allowing to repete the same experiment
See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
"""
def __init__(self,vpA,vpB,
initialMatching=None,
fitnessScores='Copeland',
#RandomInit=False,
seed=None,
maxIterations=None,
Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
self.runTimes = {}
t0 = time()
if initialMatching == 'random':
RandomInit = True
import random
random.seed(seed)
self.seed = seed
else:
RandomInit = False
# store input data
self.vpA = vpA
self.vpB = vpB
self.verticesKeysA = [x for x in vpA.voters]
self.verticesKeysB = [y for y in vpB.voters]
self.name = 'fairness-enhanced-matching'
k = len(vpA.voters)
self.order = 2 * k
if maxIterations is None:
maxIterations = self.order
self.maxIterations = maxIterations
if Comments:
print('Initial matching:', initialMatching)
if fitnessScores == 'Copeland':
# precomputing Copeland ranking scores
copelandScores = {}
aKeys = [a for a in vpA.voters]
bKeys = [b for b in vpB.voters]
n = len(aKeys)
for i in range(n):
ai = aKeys[i]
bi = bKeys[i]
copelandScores[ai] = {}
copelandScores[bi] = {}
for j in range(n):
aj = aKeys[j]
bj = bKeys[j]
copelandScores[ai][bj] = Decimal()
copelandScores[bi][aj] = Decimal()
for i in range(n):
ai = aKeys[i]
for j in range(n):
bj = bKeys[j]
copelandScores[ai][bj] = self.computeCopelandScore(vpA,ai,bj)
for j in range(n):
bj = bKeys[j]
for i in range(n):
ai = aKeys[i]
copelandScores[bj][ai] = self.computeCopelandScore(vpB,bj,ai)
self.fitnessScores = copelandScores
## if Debug:
## self.showCopelandRankingScores()
elif fitnessScores == 'Bachet':
# precomputing Bachet ranking scores
bachetScores = {}
aKeys = [a for a in vpA.voters]
bKeys = [b for b in vpB.voters]
n = len(aKeys)
for i in range(n):
ai = aKeys[i]
bi = bKeys[i]
bachetScores[ai] = {}
bachetScores[bi] = {}
for i in range(n):
ai = aKeys[i]
for j in range(n):
bj = bKeys[j]
bachetScores[ai][bj] = self.computeBachetScore(vpA,ai,bj)
for j in range(n):
bj = bKeys[j]
for i in range(n):
ai = aKeys[i]
bachetScores[bj][ai] = self.computeBachetScore(vpB,bj,ai)
self.fitnessScores = bachetScores
elif fitnessScores == 'BachetReversed':
## precomputing Bachet ranking scores
bachetScores = {}
aKeys = [a for a in vpA.voters]
bKeys = [b for b in vpB.voters]
n = len(aKeys)
for i in range(n):
ai = aKeys[i]
bi = bKeys[i]
bachetScores[ai] = {}
bachetScores[bi] = {}
for i in range(n):
ai = aKeys[i]
for j in range(n):
bj = bKeys[j]
bachetScores[ai][bj] = self.computeBachetScore(vpA,ai,bj,Reversed=True)
for j in range(n):
bj = bKeys[j]
for i in range(n):
ai = aKeys[i]
bachetScores[bj][ai] = self.computeBachetScore(vpB,bj,ai,Reversed=True)
self.fitnessScores = bachetScores
else:
# error wrong fitnessScores request
print('!!!Error: fitnessScores = %s is not provided. Only Copeland, Bachet and BachetREversed are provided.')
return
t1 = time()
self.runTimes['dataInput'] = t1 - t0
# test initialMatching
t2 = time()
if initialMatching == 'bestCopeland':
if Debug:
print(initialMatching)
cop = BestCopelandInterGroupMatching(vpA,vpB)
initialMatching = cop.matching
if Comments or Debug:
print('Best Copeland initial matching')
print(cop.matching)
fitness = self.computeIndividualCorrelations(initialMatching)
if fitness[1] == Decimal('1.0'):
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
em,it,history,fitnessG = self.enhanceMatchingGeneralFairness(
initialMatching,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
if fitness[1] >= fitnessG[1] and fitness[2] <= fitnessG[2]:
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('Storing maximal fairness enhanced given matching')
self.initialMatching = initialMatching
self.matching = fitnessG[0]
self.iterations = it
self.history = history
self.maxCorr = fitnessG[1]
self.stDev = fitnessG[2]
self.groupAScores = fitnessG[4]
self.groupBScores = fitnessG[5]
self.runTimes['enhancing'] = time() - t2
if initialMatching == 'bestBachet':
if Debug:
print(initialMatching)
bac = BestBachetInterGroupMatching(vpA,vpB,BestQualified=True)
self.fitnessScores = bac.bachetScores
self.Reversed = bac.Reversed
initialMatching = bac.matching
if Comments or Debug:
print('Best Bachet initial matching')
print(bac.matching)
fitness = self.computeIndividualCorrelations(initialMatching)
if fitness[1] == Decimal('1.0'):
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
em,it,history,fitnessG = self.enhanceMatchingGeneralFairness(
initialMatching,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
if fitness[1] >= fitnessG[1] and fitness[2] <= fitnessG[2]:
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('Storing maximal fairness enhanced given matching')
self.initialMatching = initialMatching
self.matching = fitnessG[0]
self.iterations = it
self.history = history
self.maxCorr = fitnessG[1]
self.stDev = fitnessG[2]
self.groupAScores = fitnessG[4]
self.groupBScores = fitnessG[5]
self.runTimes['enhancing'] = time() - t2
# compute initial matching
elif initialMatching is None or initialMatching == 'random':
## try:
## print(self.fitnessScores)
## except:
## print('no finess scores yet computed !!!')
## self.fitnessScores = self.copelandScores
initialMatchingL = set()
initialMatchingR = set()
aKeys = [a for a in vpA.voters]
bKeys = [b for b in vpB.voters]
if initialMatching == 'random':
random.shuffle(bKeys)
n = len(aKeys)
for i in range(n):
initialMatchingL.add(frozenset([aKeys[i],bKeys[i]]))
initialMatchingR.add(frozenset([aKeys[i],bKeys[-(i+1)]]))
# enhance left matching
if Comments or Debug:
print('==>>> Left initial matching')
fitnessL = self.computeIndividualCorrelations(initialMatchingL)
if fitnessL[1] < Decimal('1.0'):
emL,itL,historyL,fitnessL = self.enhanceMatchingGeneralFairness(
initialMatchingL,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
if fitnessL[1] == Decimal('1.0'):
if Comments or Debug:
print('Storing left initial matching maximum result')
self.initialMatching = initialMatchingL
self.matching = fitnessL[0]
self.iterations = itL
self.history = historyL
self.maxCorr = fitnessL[1]
self.stDev = fitnessL[2]
self.groupAScores = fitnessL[4]
self.groupBScores = fitnessL[5]
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('==>>> Right initial matching')
emR,itR,historyR,fitnessR = self.enhanceMatchingGeneralFairness(
initialMatchingR,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
t2 = time()
self.runTimes['enhancing'] = t2 - t1
# storing the results
if fitnessL[1] >= fitnessR[1] and fitnessL[2] <= fitnessR[2] :
if Comments or Debug:
print('Storing left maximal fair matching')
self.initialMatching = initialMatchingL
self.matching = fitnessL[0]
self.iterations = itL
self.history = historyL
self.maxCorr = fitnessL[1]
self.stDev = fitnessL[2]
self.groupAScores = fitnessL[4]
self.groupBScores = fitnessL[5]
t3 = time()
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatchingR
self.matching = fitnessR[0]
self.iterations = itR
self.history = historyR
self.maxCorr = fitnessR[1]
self.stDev = fitnessR[2]
self.groupAScores = fitnessR[4]
self.groupBScores = fitnessR[5]
self.runTimes['enhancing'] = time() - t2
else: # left initial correlation = +1.000
if Comments:
print('Storing left matching maximum result')
self.initialMatching = initialMatchingL
self.matching = fitnessL[0]
self.iterations = itL
self.history = historyL
self.maxCorr = fitnessL[1]
self.stDev = fitnessL[2]
self.groupAScores = fitnessL[4]
self.groupBScores = fitnessL[5]
self.runTimes['enhancing'] = time() - t2
else:
t2 = time()
if Debug:
print(initialMatching)
if Comments:
print('Given initial matching')
print(initialMatching)
fitness = self.computeIndividualCorrelations(initialMatching)
if fitness[1] == Decimal('1.0'):
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
em,it,history,fitnessG = self.enhanceMatchingGeneralFairness(
initialMatching,
maxIterations=maxIterations,
Comments=Comments,
Debug=Debug)
if fitness[1] >= fitnessG[1] and fitness[2] <= fitnessG[2]:
if Comments or Debug:
print('Storing given initial maximal fair matching')
self.initialMatching = initialMatching
self.matching = initialMatching
self.iterations = 0
self.history = []
self.maxCorr = fitness[1]
self.stDev = fitness[2]
self.groupAScores = fitness[4]
self.groupBScores = fitness[5]
self.runTimes['enhancing'] = time() - t2
else:
if Comments or Debug:
print('Storing maximal fairness enhanced given matching')
self.initialMatching = initialMatching
self.matching = fitnessG[0]
self.iterations = it
self.history = history
self.maxCorr = fitnessG[1]
self.stDev = fitnessG[2]
self.groupAScores = fitnessG[4]
self.groupBScores = fitnessG[5]
self.runTimes['enhancing'] = time() - t2
#storing the Graph data
self.vertices = vpA.voters | vpB.voters
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
self.runTimes['totalTime'] = time() - t0
#---------------
[docs]
class BestBachetInterGroupMatching(InterGroupPairing):
"""
The class computes the individual Bachet ranking scores and
constructs a best determined perfect intergroup matching
with a ranked pairs rule
*Parameters*:
* *vpA* : any VotingProfile instance
* *vpB* : reciprocal VotingProfile instance
* *BestQualified*: *False* | *True* (default). If *True*,
both the original and the reversed ordering of the actions will
be taken into account for computing the pairing fitness scores
and the best qualified Bachet intergroup matching result will eventually returned.
See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
"""
def __init__(self,vpA,vpB,BestQualified=True,Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
from bachetNumbers import BachetInteger as BN
self.runTimes = {}
t0 = time()
# store input data
self.vpA = vpA
self.vpB = vpB
order = len(vpA.voters)
self.order = 2 * order
# precomputing Copeland ranking scores
bachetScores = {}
aKeys = [a for a in vpA.voters]
self.verticesKeysA = aKeys
bKeys = [b for b in vpB.voters]
self.verticesKeysB = bKeys
for i in range(order):
ai = aKeys[i]
bi = bKeys[i]
bachetScores[ai] = {}
bachetScores[bi] = {}
maxScore = BN(0)
for i in range(order):
ai = aKeys[i]
for j in range(order):
bj = bKeys[j]
bachetScores[ai][bj] = self.computeBachetScore(vpA,ai,bj,
Reversed=BestQualified)
if abs(bachetScores[ai][bj]) > maxScore:
maxScore = bachetScores[ai][bj]
for j in range(order):
bj = bKeys[j]
for i in range(order):
ai = aKeys[i]
bachetScores[bj][ai] = self.computeBachetScore(vpB,bj,ai,
Reversed=BestQualified)
if abs(bachetScores[bj][ai]) > maxScore:
maxScore = bachetScores[bj][ai]
self.bachetScores = bachetScores
if Debug:
self.showBachetRankingScores()
t1 = time()
self.runTimes['dataInput'] = t1 - t0
#storing the Bachet graph data
t2 = time()
self.name = 'bachetMatching'
self.vertices = vpA.voters | vpB.voters
Min = Decimal('%d' % ( -(2*int(maxScore)) ) )
Med = Decimal('0')
Max = Decimal('%d' % ( 2*int(maxScore) ) )
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max,
'IntegerValuation' : True,
}
verticesList = [v for v in self.vertices]
n = len(verticesList)
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
edges[edgeKey] = Min
for i in range(order):
for j in range(order):
edgeKey = frozenset([aKeys[i],bKeys[j]])
edges[edgeKey] = 2*Max + int(self.bachetScores[aKeys[i]][bKeys[j]]) \
+ int(self.bachetScores[bKeys[j]][aKeys[i]])
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
t3 = time()
self.runTimes['bachetGraph'] = t3 - t2
# computing the best determined maximal matching
t4 = time()
remainingAKeys = [a for a in self.vpA.voters]
remainingBKeys = [b for b in self.vpB.voters]
if Debug:
print(remainingAKeys,remainingBKeys)
pairs = []
edges = self.edges
na = len(remainingAKeys)
for i in range(na):
for j in range(na):
edgeKey = frozenset({remainingAKeys[i],
remainingBKeys[j]})
pairs.append((edges[edgeKey],edgeKey))
pairs.sort(reverse=True)
if Debug:
print(pairs)
lmatching = []
i = 0
na = len(pairs)
while i < na:
keys = list(pairs[i][1])
if Debug:
print(keys)
if (keys[0] in remainingAKeys and keys[1] in remainingBKeys):
remainingAKeys.remove(keys[0])
remainingBKeys.remove(keys[1])
lmatching.append(pairs[i][1])
i += 1
if Debug:
print(i,keys,remainingAKeys,remainingBKeys)
print(lmatching)
elif (keys[1] in remainingAKeys and keys[0] in remainingBKeys):
remainingAKeys.remove(keys[1])
remainingBKeys.remove(keys[0])
lmatching.append(pairs[i][1])
i += 1
if Debug:
print(i,keys,remainingAKeys,remainingBKeys)
print(lmatching)
else:
i += 1
if Debug:
print(len(lmatching),lmatching)
fitness = self.computeIndividualCorrelations(lmatching)
if BestQualified: # compare the average correlation figures
revSelf = BestBachetInterGroupMatching(vpA,vpB,BestQualified=False)
revFitness = self.computeIndividualCorrelations(revSelf.matching)
if revFitness[1] < fitness[1]:
self.matching = lmatching
self.Reversed = True
else:
self.matching = revFitness[0]
self.bachetScores = revSelf.bachetScores
self.Reversed = False
else:
self.matching = lmatching
self.Reversed = False
t5 = time()
self.runTimes['maximalMatching'] = t5 - t4
t7 = time()
self.runTimes['totalTime'] = t7 - t0
def showMatchingWithFitnessScores(self):
aKeys = [k for k in self.vpA.voters]
matches = []
for e in self.matching:
matches.append( (int(self.edges[e]),e) )
matches.sort(reverse=True)
for m in matches:
edgeKey = m[1]
pair = list(m[1])
if pair[0] in aKeys:
print('%s (%d)' %([pair[0],pair[1]], int(self.edges[edgeKey])) )
else:
print('%s (%d)' %([pair[1],pair[0]], int(self.edges[edgeKey])) )
#----------
[docs]
class BestCopelandInterGroupMatching(InterGroupPairing):
"""
The class computes the individual Copeland ranking scores and
constructs a best determined perfect intergroup matching
with a ranked pairs rule
*Parameters*:
* *vpA* : any VotingProfile instance
* *vpB* : reciprocal VotingProfile instance
See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
"""
def __init__(self,vpA,vpB,Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
self.runTimes = {}
t0 = time()
# store input data
self.vpA = vpA
self.vpB = vpB
order = len(vpA.voters)
self.order = 2 * order
# precomputing Copeland ranking scores
copelandScores = {}
aKeys = [a for a in vpA.voters]
self.verticesKeysA = aKeys
bKeys = [b for b in vpB.voters]
self.verticesKeysB = bKeys
for i in range(order):
ai = aKeys[i]
bi = bKeys[i]
copelandScores[ai] = {}
copelandScores[bi] = {}
for j in range(order):
aj = aKeys[j]
bj = bKeys[j]
copelandScores[ai][bj] = Decimal()
copelandScores[bi][aj] = Decimal()
minScore = Decimal('0.0')
for i in range(order):
ai = aKeys[i]
for j in range(order):
bj = bKeys[j]
copelandScores[ai][bj] = self.computeCopelandScore(vpA,ai,bj)
if copelandScores[ai][bj] < minScore:
minScore = copelandScores[ai][bj]
for j in range(order):
bj = bKeys[j]
for i in range(order):
ai = aKeys[i]
copelandScores[bj][ai] = self.computeCopelandScore(vpB,bj,ai)
if copelandScores[bj][ai] < minScore:
minScore = copelandScores[bj][ai]
self.copelandScores = copelandScores
if Debug:
self.showCopelandRankingScores()
t1 = time()
self.runTimes['dataInput'] = t1 - t0
#storing the Copeland graph data
t2 = time()
self.name = 'copelandMatching'
self.vertices = vpA.voters | vpB.voters
Min = Decimal('%d' % (4*minScore) )
Med = Decimal('0')
Max = Decimal('%d' % (4*abs(minScore)) )
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
edges[edgeKey] = Min
for i in range(order):
for j in range(order):
edgeKey = frozenset([aKeys[i],bKeys[j]])
edges[edgeKey] = (2*abs(minScore)) + self.copelandScores[aKeys[i]][bKeys[j]] \
+ self.copelandScores[bKeys[j]][aKeys[i]]
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
t3 = time()
self.runTimes['copelandGraph'] = t3 - t2
# computing the best determined maximal matching
t4 = time()
remainingAKeys = [a for a in self.vpA.voters]
remainingBKeys = [b for b in self.vpB.voters]
if Debug:
print(remainingAKeys,remainingBKeys)
pairs = []
edges = self.edges
na = len(remainingAKeys)
for i in range(na):
for j in range(na):
edgeKey = frozenset({remainingAKeys[i],
remainingBKeys[j]})
pairs.append((edges[edgeKey],edgeKey))
pairs.sort(reverse=True)
if Debug:
print(pairs)
lmatching = []
i = 0
na = len(pairs)
while i < na:
keys = list(pairs[i][1])
if Debug:
print(keys)
if (keys[0] in remainingAKeys and keys[1] in remainingBKeys):
remainingAKeys.remove(keys[0])
remainingBKeys.remove(keys[1])
lmatching.append(pairs[i][1])
i += 1
if Debug:
print(i,keys,remainingAKeys,remainingBKeys)
print(lmatching)
elif (keys[1] in remainingAKeys and keys[0] in remainingBKeys):
remainingAKeys.remove(keys[1])
remainingBKeys.remove(keys[0])
lmatching.append(pairs[i][1])
i += 1
if Debug:
print(i,keys,remainingAKeys,remainingBKeys)
print(lmatching)
else:
i += 1
if Debug:
print(len(lmatching),lmatching)
self.matching = lmatching
t5 = time()
self.runTimes['maximalMatching'] = t5 - t4
t7 = time()
self.runTimes['totalTime'] = t7 - t0
def showMatchingWithFitnessScores(self):
aKeys = [k for k in self.vpA.voters]
for e in self.matching:
pair = list(e)
if pair[0] in aKeys:
print('%s (%d)' %([pair[0],pair[1]], int(self.edges[e])) )
else:
print('%s (%d)' %([pair[1],pair[0]], int(self.edges[e])) )
#----------
##class _InterGroupCopelandMatching(InterGroupPairing):
## """
## !!! Not a satisfactory determined perfect matching guaranteed !!!
##
## The class computes the individual Copeland ranking scored
## based maximal matching resulting from the best determined spanning forest
## of the bipartite Copeland scores graph.
##
## *Parameters*:
##
## * *vpA* : any VotingProfile instance
## * *vpB* : reciprocal VotingProfile instance
##
## See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
## """
## def __init__(self,vpA,vpB,Comments=False,Debug=False):
##
## from time import time
## from decimal import Decimal
## from copy import deepcopy
## self.runTimes = {}
## t0 = time()
## # store input data
## self.vpA = vpA
## self.vpB = vpB
## self.name = 'copelandMatching'
## order = len(vpA.voters)
## self.order = order
## # precomputing Copeland ranking scores
## copelandScores = {}
## aKeys = [a for a in vpA.voters]
## self.verticesKeysA = aKeys
## bKeys = [b for b in vpB.voters]
## self.verticesKeysB = bKeys
## for i in range(order):
## ai = aKeys[i]
## bi = bKeys[i]
## copelandScores[ai] = {}
## copelandScores[bi] = {}
## for j in range(order):
## aj = aKeys[j]
## bj = bKeys[j]
## copelandScores[ai][bj] = Decimal()
## copelandScores[bi][aj] = Decimal()
## minScore = 0.0
## for i in range(order):
## ai = aKeys[i]
## for j in range(order):
## bj = bKeys[j]
## copelandScores[ai][bj] = self.computeCopelandScore(vpA,ai,bj)
## if copelandScores[ai][bj] < minScore:
## minScore = copelandScores[ai][bj]
## for j in range(order):
## bj = bKeys[j]
## for i in range(order):
## ai = aKeys[i]
## copelandScores[bj][ai] = self.computeCopelandScore(vpB,bj,ai)
## if copelandScores[bj][ai] < minScore:
## minScore = copelandScores[bj][ai]
## self.copelandScores = copelandScores
## if Debug:
## self.showCopelandRankingScores()
## t1 = time()
## self.runTimes['dataInput'] = t1 - t0
##
## #storing the Graph data
## t2 = time()
## self.vertices = vpA.voters | vpB.voters
## Min = Decimal('%d' % (4*minScore) )
## Med = Decimal('0')
## Max = Decimal('%d' % (4*abs(minScore)) )
## self.valuationDomain = {'min': Min,
## 'med': Med,
## 'max': Max}
## verticesList = [v for v in self.vertices]
## n = len(verticesList)
## edges = {}
## for i in range(n):
## vi = verticesList[i]
## for j in range(i+1,n):
## vj = verticesList[j]
## edgeKey = frozenset({vi,vj})
## edges[edgeKey] = Min
## for i in range(order):
## for j in range(order):
## edgeKey = frozenset([aKeys[i],bKeys[j]])
## edges[edgeKey] = (2*abs(minScore)) + self.copelandScores[aKeys[i]][bKeys[j]] \
## + self.copelandScores[bKeys[j]][aKeys[i]]
## self.edges = edges
## self.gamma = self.gammaSets()
## t3 = time()
## self.runTimes['copelandGraph'] = t3 - t2
##
## # computing the best determined maximal matching
## t4 = time()
## from graphs import BestDeterminedSpanningForest
## bsf = BestDeterminedSpanningForest(self)
## if Debug:
## bsf.exportGraphViz(WithSpanningTree=True,layout='circo')
## dbsf = bsf.graph2Digraph()
## dbsf.showRelationTable(ndigits=0)
## matching = []
## unPaired = []
## gamma = bsf.gamma
## sortedVerticesList = [(len(gamma[v]),v) for v in self.vertices]
## sortedVerticesList.sort()
## verticesList = [v[1] for v in sortedVerticesList]
## if Debug:
## print(verticesList)
##
## while len(verticesList) > 0:
## sortedVerticesList = [(len(gamma[v]),v) for v in verticesList]
## sortedVerticesList.sort()
## verticesList = [v[1] for v in sortedVerticesList]
## for v1 in verticesList:
## if Debug:
## print('==>>v1', v1, gamma[v1])
## if len(gamma[v1]) == 1:
## v2 = gamma[v1].pop()
## if [v1,v2] not in matching and [v2,v1] not in matching:
## matching.append(frozenset({v1,v2}))
## if Debug:
## print(matching)
## verticesList.remove(v1)
## verticesList.remove(v2)
## gamma[v2] = set()
## if Debug:
## print(v1,gamma[v1],v2,gamma[v2])
## for v3 in verticesList:
## if Debug:
## print('v3',v3,gamma[v3])
## if v1 in gamma[v3]:
## gamma[v3].remove(v1)
## if v2 in gamma[v3]:
## gamma[v3].remove(v2)
## if Debug:
## print('v3',v3,gamma[v3])
## elif len(gamma[v1]) == 0:
## verticesList.remove(v1)
## unPaired.append(v1)
## if Comments:
## print(len(matching),matching)
## print('==>> unpaired:', unPaired)
## if len(matching) < order:
## remainingAKeys = [a for a in self.vpA.voters]
## remainingBKeys = [b for b in self.vpB.voters]
## for m in matching:
## lm = list(m)
## lm.sort()
## remainingAKeys.remove(lm[0])
## remainingBKeys.remove(lm[1])
## if Debug:
## print(remainingAKeys,remainingBKeys)
## pairs = []
## edges = self.edges
## na = len(remainingAKeys)
## for i in range(na):
## for j in range(na):
## edgeKey = frozenset({remainingAKeys[i],
## remainingBKeys[j]})
## pairs.append((edges[edgeKey],edgeKey))
## pairs.sort(reverse=True)
## if Debug:
## print(pairs)
## lmatching = [m for m in matching]
## i = 0
## na = len(pairs)
## while i < na:
## keys = list(pairs[i][1])
## if Debug:
## print(keys)
## #keys.sort()
## if (keys[0] in remainingAKeys and keys[1] in remainingBKeys):
## remainingAKeys.remove(keys[0])
## remainingBKeys.remove(keys[1])
## lmatching.append(pairs[i][1])
## #na -= 1
## i += 1
## if Debug:
## print(i,keys,remainingAKeys,remainingBKeys)
## print(lmatching)
## elif (keys[1] in remainingAKeys and keys[0] in remainingBKeys):
## remainingAKeys.remove(keys[1])
## remainingBKeys.remove(keys[0])
## lmatching.append(pairs[i][1])
## #na -= 1
## i += 1
## if Debug:
## print(i,keys,remainingAKeys,remainingBKeys)
## print(lmatching)
## else:
## i += 1
##
##
## matching = lmatching
## if Debug:
## print(len(matching),matching)
##
##
## self.matching = matching
## t5 = time()
## self.runTimes['maximalMatching'] = t5 - t4
##
## t7 = time()
## self.runTimes['totalTime'] = t7 - t0
#----------
[docs]
class FairestGaleShapleyMatching(InterGroupPairing):
"""
The class computes both Gale-Shapley matchings -- group A proposes and group B proposes--
and renders the fairest of both.
*Parameters*:
* *lvA* : LinearVotingProfile instance
* *lvB* : reciprocal LinearVotingProfile
See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
"""
def __init__(self,lvA,lvB,Comments=False):
from decimal import Decimal
from copy import deepcopy
from time import time
t0 = time()
self.runTimes = {}
# store input data
self.vpA = lvA
self.vpB = lvB
self.name = 'fairest-Gale-Shapley'
k = len(lvA.voters)
self.order = 2 * k
self.verticesKeysA = [x for x in lvA.voters]
self.verticesKeysB = [y for y in lvB.voters]
self.runTimes['dataInput'] = time() - t0
# compute Gale-Shapley matchings
t1 = time()
gs1 = self.computeGaleShapleyMatching()
gs2 = self.computeGaleShapleyMatching(Reverse=True)
self.runTimes['galeShapley'] = time() - t1
# choose the fairest of both
t2 = time()
corr1 = self.computeIndividualCorrelations(gs1)
corr2 = self.computeIndividualCorrelations(gs2)
if corr1[1] > corr2[1]:
gs = gs1
elif corr1[1] == corr2[1] and corr1[2] < corr2[2]:
gs = gs1
else:
gs = gs2
if Comments:
print('Fairest Gale-Shapley matching')
print(gs)
self.showMatchingFairness(gs,WithIndividualCorrelations=True)
self.matching = gs
self.runTimes['chooseFairest'] = time() - t2
# store Graph data
t3 = time()
self.vertices = lvA.voters | lvB.voters
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(k):
vi = verticesList[i]
for j in range(i+1,k):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
self.runTimes['storeGraph'] = time() - t3
self.runTimes['totalTime'] = time() - t0
[docs]
class FairestInterGroupPairing(InterGroupPairing):
"""
The class computes the fitness scores of the complete set of maximal matchings between
two groups *A* and *B* of persons of equal number *k* and delivers, based on these fitness scores, a fairest pairing of the persons of both groups.
*Parameters*:
* *vpA* : any type of VotingProfile instance
* *vpB* : reciprocal VotingProfile instance
* *oderLimit* : preventing a potential CPU memory or time overflow
* *StableMatchings* : False (default) / True limits to only stable matchings
See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
"""
def __init__(self,vpA,vpB,orderLimit=6,
StableMatchings=False,
Comments=False,Debug=False):
from copy import deepcopy
from decimal import Decimal
runTimes = {}
from time import time
# check size of problem
groupA = [x for x in vpA.voters]
k = len(groupA)
if Debug:
print('groupA',groupA)
if k > orderLimit:
print('The size %d of the groups to pair is too high' % k)
print('The order limit is %d' % orderLimit)
print('Use the orderLimit parameter for larger orders')
return
t0 = time()
groupB = [x for x in vpB.voters]
if Debug:
print('groupB',groupB)
# from graphs import BipartiteGraph
# verticesKeys = groupA + groupB
# if Debug:
# print(verticesKeys)
# storing input data
self.name = 'pairingProblem'
self.order = 2 * k
self.vpA = vpA
self.vpB = vpB
self.verticesKeysA = groupA
self.verticesKeysB = groupB
t1 = time()
runTimes['inputData'] = t1 - t0
if Comments:
print(runTimes)
# compute bipartite graph
# g = CompleteGraph(verticesKeys=verticesKeys)
# dg = g.graph2Digraph()
# from digraphs import BipartitePartialDigraph
# bpdg = BipartitePartialDigraph(dg,groupA,groupB,Partial=False)
# bpg = bpdg.digraph2Graph()
from graphs import CompleteBipartiteGraph
bpg = CompleteBipartiteGraph(groupA,groupB)
if Debug:
print('bipartite graph',bpg)
t2 = time()
runTimes['bipartiteGraph'] = t2 - t1
if Comments:
print(runTimes)
# compute maximal matchings
from graphs import LineGraph
lbpg = LineGraph(bpg)
lbpg.computeMIS()
maximalMatchings = lbpg.misset
nm = len(maximalMatchings)
t3 = time()
runTimes['maximalMatching'] = t3 - t2
if Comments:
print(runTimes)
# computing matching correlations
from statistics import mean, stdev
from decimal import Decimal
from digraphs import IndeterminateDigraph
pairings = []
groupAScores = {}
groupBScores = {}
ni = 1
for matching in maximalMatchings:
if Comments:
print('%d/%d' % (ni,nm) )
ni += 1
# computing groupA's scores
groupAScores = {}
for m in groupA:
edg = IndeterminateDigraph(order=len(vpA.candidates))
edg.actions = groupB
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
mmatch = [x for x in matching if m in x]
mmatch = [x for x in mmatch[0] if x != m]
relation = {}
for x in groupB:
relation[x] = {}
for y in groupB:
relation[x][y] = Med
n = len(edg.actions)
for i in range(n):
x = groupB[i]
for j in range(i+1,n):
y = groupB[j]
if x == mmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == mmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
#corr = edg.computeRankingCorrelation(vpA.linearBallot[m])
corr = edg.computeOrdinalCorrelation(vpA.ballot[m])
groupAScores[m] = Decimal('%.3f' % corr['correlation'])
# computing groupB's scores
groupBScores = {}
for w in groupB:
edg.actions = groupA
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
wmmatch = [x for x in matching if w in x]
wmmatch = [x for x in wmmatch[0] if x != w]
relation = {}
for x in groupA:
relation[x] = {}
for y in groupA:
relation[x][y] = Med
n = len(edg.actions)
for i in range(n):
x = groupA[i]
for j in range(i+1,n):
y = groupA[j]
if x == wmmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == wmmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
#corr = edg.computeRankingCorrelation(vpB.linearBallot[w])
corr = edg.computeOrdinalCorrelation(vpB.ballot[w])
groupBScores[w] = Decimal('%.3f' % corr['correlation'])
t3a = time()
runTimes['GroupCorrelations'] = t3a - t3
# computing matching fitness scores
aCorrelations = [groupAScores[w] for w in groupAScores]
## for w in groupAScores:
## aCorrelations.append(groupAScores[w])
bCorrelations = [groupBScores[m] for m in groupBScores]
## for m in groupBScores:
## bCorrelations.append(groupBScores[m])
ACorr = mean(aCorrelations)
BCorr = mean(bCorrelations)
fairness = abs(ACorr-BCorr)
matchingCorrelations = aCorrelations + bCorrelations
if Debug:
print(matching)
print(matchingCorrelations)
avgCorr = mean(matchingCorrelations)
stdCorr = stdev(matchingCorrelations)
if Debug:
print(avgCorr,stdCorr)
pairings.append((matching,avgCorr,-stdCorr,avgCorr-stdCorr,
groupAScores,groupBScores,-fairness))
# sorting the fitness scores
from operator import itemgetter
pairings.sort(reverse=True,key=itemgetter(1,6,2))
#pairings.sort(reverse=True,key=itemgetter(6,1,3))
t4 = time()
runTimes['Correlations'] = t4 - t3a
# index to stable pairings
if StableMatchings:
stableIndex = []
n = len(pairings)
for i in range(n):
m = pairings[i]
matching = m[0]
if self.isStableMatching(matching,Comments=False):
stableIndex.append(i)
self.stableIndex = stableIndex
t5 = time()
runTimes['StableIndex'] = t5 -t4
# storing results
self.bpg = bpg
self.pairings = pairings
self.matching = pairings[0][0]
#storing the Graph data
self.vertices = vpA.voters | vpB.voters
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.size = self.computeSize()
self.gamma = self.gammaSets()
t6 = time()
runTimes['totalTime'] = t6 - t0
self.runTimes = runTimes
# showing the faires pairing
if Comments:
print('Fairest pairing solution')
self.showPairing(pairings[0][0])
#------------- class methods
# def exportBipartiteGraphViz(self,fileName=None,rank=1):
# """
# Bipartite graph circular drawing with Fairness ranked (default= fairest) matching in colour.
# The *rank* parameter allows to select a lesser fair matching in the self.pairings list.
# """
# from graphs import BipartiteGraph
# BipartiteGraph.exportBipartiteGraphViz(self,fileName=('pairing%d' % rank),
# matching=self.pairings[rank-1][0],
# layout='circo')
[docs]
def showFairestPairing(self,rank=1,WithIndividualCorrelations=False):
"""
Setting the *rank* parameter to a value > 1,
gives access to lesser fitting pairings.
The *WithIndividualCorrelations* flag shows the correlations with
the individual pairing preferences.
"""
index = rank - 1
print('*------------------------------*')
if index == 0:
print('Fairest pairing')
elif index == 1:
print('2nd-ranked pairing')
elif index == 2:
print('3rd-ranked pairing')
else:
print('%th-ranked pairing' % (index+1))
fitness = self.pairings
self.showMatchingFairness(fitness[index][0],
WithIndividualCorrelations=WithIndividualCorrelations)
[docs]
def computeMatchingFairnessIndex(self,matching,Comments=False):
"""
Renders the index position of the given matching in the
fairness ranked self.pairings list.
"""
# converting to the frozenset formst
pairing = []
for pair in matching:
pairing.append(frozenset(pair))
pairing = frozenset(pairing)
n = len(self.pairings)
for i in range(n):
if pairing == self.pairings[i][0]:
if Comments:
print('Fairness index of matching: ',i)
break
return i
from graphs import Graph
[docs]
class IntraGroupPairing(Graph):
"""
Abstract root class for IntraGroup pairing solutions
"""
def __init__():
print('Abstract root class for intragroup pairing graphs')
def __repr__(self):
"""
Default description for FairPairing instances.
"""
reprString = '*------- IntraGroupPairing instance description ------*\n'
reprString += 'Instance class : %s\n' % self.__class__.__name__
reprString += 'Instance name : %s\n' % self.name
reprString += 'Group size : %d\n' % self.order
try:
reprString += 'Nbr of matchings : %d\n' % self.nbrOfMatchings
except:
pass
try:
reprString += 'Partners swapping : %d\n' % self.iterations
except:
pass
reprString += 'Attributes : %s\n' % list(self.__dict__.keys())
reprString += '---- Constructor run times (in sec.) ----\n'
try:
val = self.runTimes['totalTime']
reprString += 'Total time : %.5f\n' % val
except:
pass
try:
val = self.runTimes['dataInput']
reprString += 'Data input : %.5f\n' % val
except:
pass
try:
val = self.runTimes['maximalMatching']
reprString += 'Maximal matchings : %.5f\n' % val
except:
pass
try:
val = self.runTimes['matchingCorrelations']
reprString += 'Pairing correlations : %.5f\n' % val
except:
pass
try:
val = self.runTimes['sortingFitness']
reprString += 'Sorting Fitness : %.5f\n' % val
except:
pass
try:
val = self.runTimes['storeResults']
reprString += 'Storing results : %.5f\n' % val
except:
pass
try:
val = self.runTimes['CopelandGraph']
reprString += 'Copeland graph : %.5f\n' % val
except:
pass
try:
val = self.runTimes['PairingsSize']
reprString += 'Pairings size : %.5f\n' % val
except:
pass
try:
val = self.runTimes['enhancing']
reprString += 'Enhancing fairness : %.5f\n' % val
except:
pass
try:
val = self.runTimes['leftEnhancing']
reprString += 'Left enhancing : %.5f\n' % val
except:
pass
try:
val = self.runTimes['rightEnhancing']
reprString += 'Right enhancing : %.5f\n' % val
except:
pass
return reprString
[docs]
def showPairing(self,matching=None):
"""
shows the intragroup pairing solution when *matching is None*
"""
print('Matched pairs')
pairs = []
aKeys = self.persons
if matching is None:
matching = self.matching
for m in matching:
pair = list(m)
pairs.append([pair[0],pair[1]])
pairs.sort()
n = len(pairs)
for i in range(n):
print("{'%s', '%s'}" % (pairs[i][0],pairs[i][1]))
[docs]
def showMatchingFairness(self,matching=None,
WithIndividualCorrelations=True):
"""
Shows the intragroup faines of a given matching.
When *matching is None* the fairest matching of the class is used
"""
#from decimal import Decimal
from statistics import mean,stdev
vpA = self.vpA
groupA = self.persons
if matching is None:
matching = self.matching
self.showPairing(matching)
correlation,stdDev,groupAScores = \
self.computeIndividualCorrelations(matching)
if WithIndividualCorrelations:
print('----')
print('Individual correlations:')
for pers in groupAScores:
print(' \'%s\': %+.3f' % (pers,groupAScores[pers]) )
print('-----')
print('Average correlation : %+.3f' % correlation)
print('Standard deviation : %.3f' % stdDev)
[docs]
def exportPairingGraphViz(self,fileName=None,
Comments=True,
graphType='png',graphSize='7,7',
matching=None,
edgeColor='blue',
bgcolor='cornsilk',
lineWidth=2):
"""
Exports GraphViz dot file for pairing graph drawing filtering.
"""
import os
if Comments:
print('*---- exporting a dot file for GraphViz tools ---------*')
#Akeys = self.persons
#Bkeys = self.persons
vertexKeys = self.persons
n = len(vertexKeys)
k = n//2
## aKeys = vertexKeys[:k]
## bKeys = vertexKeys[k:]
if matching is None:
edges = self.edges
else:
mt = {}
for m in matching:
mt.append(frozenset(m))
edges = {}
for i in range(n):
vi = vertexKeys[i]
for j in range(i+1,n):
vj = vertexKeys[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
Med = self.valuationDomain['med']
aKeys = []
bKeys = []
pairs = []
for edgeKey in edges:
if edges[edgeKey] > Med:
pair = list(edgeKey)
pair.sort()
pairs.append(pair)
if edges[edgeKey] > Med:
aKeys.append(pair[0])
bKeys.append(pair[1])
i = 0
if fileName is None:
name = self.name
else:
name = fileName
dotName = name+'.dot'
if Comments:
print('Exporting to '+dotName)
fo = open(dotName,'w')
fo.write('graph G {\n')
if bgcolor is not None:
fo.write('graph [ bgcolor = %s, fontname = "Helvetica-Oblique",\n fontsize = 12,\n label = "' % (bgcolor) )
else:
fo.write('graph [ fontname = "Helvetica-Oblique",\n fontsize = 12,\n label = "')
fo.write('\\nDigraph3 (graphviz), R. Bisdorff, 2023", size="')
fo.write(graphSize),fo.write('"];\n')
fo.write('splines=false;\n')
fo.write('node[shape=circle]\n')
fo.write('edge[color=%s]\n' % edgeColor)
fo.write('subgraph cluster_1r {\n')
for i in range(k):
fo.write(' a%d [label="%s",fillcolor=white]\n' % (i+1,aKeys[i]) )
for i in range(k-1):
fo.write(' a%d--' % (i+1) )
fo.write(' a%d [style=invis]\n' % k )
fo.write(' label = "Paired"\n')
fo.write(' color = white\n')
fo.write('}\n')
fo.write('subgraph cluster_1l {\n')
for i in range(k):
fo.write(' b%d [label="%s",fillcolor=white]\n' % (i+1,bKeys[i]) )
for i in range(k-1):
fo.write(' b%d--' % (i+1) )
fo.write(' b%d [style=invis]\n' % k )
fo.write(' label = "Persons"\n')
fo.write(' color = white\n')
fo.write('}\n')
Med = self.valuationDomain['med']
for pair in pairs:
inda = aKeys.index(pair[0]) + 1
indb = bKeys.index(pair[1]) + 1
fo.write('a%d--b%d [constraint=false]\n' % (inda,indb))
fo.write('}\n')
fo.close()
layout = "dot"
commandString = '%s -T%s %s -o %s.%s' % (layout,graphType,dotName,name,graphType)
if Comments:
print(commandString)
try:
from os import system
system(commandString)
except:
if Comments:
print('graphViz tools not avalaible! Please check installation.')
print('On Ubuntu: ..$ sudo apt-get install graphviz')
[docs]
def computeIndividualCorrelations(self,matching=None,Debug=False):
"""
Individual correlations for intragroup pairing solution
returns a tuple called fitness with following content
avgCorr,stdCorr, groupScores
"""
# computing groupA's scores
from digraphs import IndeterminateDigraph
from decimal import Decimal
from statistics import mean, stdev
groupAScores = {}
vpA = self.vpA
groupA = self.persons
if matching is None:
matching = self.matching
for m in groupA:
groupB = groupA
edg = IndeterminateDigraph(order=len(groupA))
edg.actions = groupB
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
mmatch = [x for x in matching if m in x]
mmatch = [x for x in mmatch[0] if x != m]
relation = {}
for x in groupB:
relation[x] = {}
for y in groupB:
relation[x][y] = Med
n = len(groupB)
for i in range(n):
x = groupB[i]
for j in range(i+1,n):
y = groupB[j]
if x == mmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == mmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
if Debug:
print(m)
edg.showRelationTable()
ballot = vpA.ballot[m]
if Debug:
edg.showRelationTable(relation=ballot)
corr = edg.computeOrdinalCorrelation(ballot)
groupAScores[m] = Decimal('%.3f' % corr['correlation'])
scores = [groupAScores[m] for m in groupAScores]
return mean(scores), stdev(scores), groupAScores
[docs]
def computeCopelandScore(self,a,b):
"""
Computes fitness of swapping candidates
"""
from decimal import Decimal
vpA = self.vpA
ba = self.vpA.ballot[a]
#ba = ballot
score = Decimal('0')
candidates = [b for b in vpA.voters]
n = len(candidates)
for i in range(n):
score += ba[b][candidates[i]] - ba[candidates[i]][b]
return score
[docs]
def computeBachetScore(self,a,b):
"""
Computes fitness of swapping candidates
"""
from decimal import Decimal
from bachetNumbers import BachetInteger as BN
vpA = self.vpA
ba = self.vpA.ballot[a]
candidates = [b for b in vpA.voters]
n = len(candidates)
vectorA = []
vectorB = []
for i in range(n):
vectorA.append(ba[b][candidates[i]])
vectorB.append(ba[candidates[i]][b])
score = BN(vector=vectorA) - BN(vector=vectorB)
return score
def showMatchingFitnessScores(self):
try:
Test = self.copelandInitialMatching
except:
print('The initial matching is not the best Copeland matching')
return
copelandScores = self.copelandScores
copEdges = {}
MaxScore = 0
vertices = [v for v in self.persons]
nv = len(vertices)
for i in range(nv):
p1 = vertices[i]
for j in range(i+1,nv):
p2 = vertices[j]
if p1 != p2:
edgeKey = frozenset([p1,p2])
copp1p2 = copelandScores[p1][p2]
copEdges[edgeKey] = copp1p2
if abs(copp1p2) > MaxScore:
MaxScore = abs(copp1p2)
self.showEdgesCharacteristicValues(edges=copEdges,ndigits=0)
print('Valuation range: [%d; %d]' % (-MaxScore,MaxScore))
[docs]
def showEdgesCharacteristicValues(self,edges=None,ndigits=2):
"""
Prints the edge links of the bipartite graph instance
"""
verticesKeys = [x for x in self.vertices]
if edges is None:
edges = self.edges
try:
IntegerValuation = self.valuationDomain['IntegerValuation']
except:
IntegerValuation = False
print('\t|', end=' ')
n = len(verticesKeys)
for i in range(1,n):
x = verticesKeys[i]
print("'"+x+"'\t", end=' ')
print('\n--------|--------------------')
for i in range(n-1):
x = verticesKeys[i]
print(" '"+x+"' | ", end=' ')
for j in range(1,n):
if j < (i+1):
print('\t',end=' ')
else:
y = verticesKeys[j]
edgeKey = frozenset([x,y])
if IntegerValuation:
print('%+d\t' % (edges[edgeKey]), end=' ')
else:
formatString = '%%+2.%df\t' % ndigits
print(formatString % (edges[edgeKey]), end=' ')
print('')
## if IntegerValuation:
## print('Valuation domain: [%+d;%+d]'% (self.valuationDomain['min'],
## self.valuationDomain['max']))
## else:
## formatString = 'Valuation domain: [%%+2.%df;%%+2.%df]' % (ndigits,ndigits)
## print( formatString % (self.valuationDomain['min'],
## self.valuationDomain['max']))
[docs]
def enhanceMatchingFairness(self,matching,
Comments=False,Debug=False):
"""
Heuristic for fairness enhancing of given matching
"""
from copy import copy
from decimal import Decimal
vpA = self.vpA
persons = self.persons
initialMatching = matching
pairs = []
aKeys = persons
bKeys = persons
matchesVisited = [initialMatching]
corrA, stdDevA, groupAScores =\
self.computeIndividualCorrelations(initialMatching)
maxCorr = corrA
for m in initialMatching:
pair = list(m)
pairs.append(pair)
pairs.sort()
if Comments:
print('*---- Initial matching ----*')
print(pairs)
n = len(pairs)
newPairs = pairs.copy()
self.t += 1
if maxCorr < Decimal('1.0'):
Enhanced = True
else:
Enhanced = False
if Debug:
print('the given matching is fairest possible')
print(newPairs,maxCorr)
return pairs,maxCorr,matchesVisited
#history = []
while Enhanced and self.t <= self.maxIterations:
Enhanced = False
if Comments:
print('Enhancing iteration : ', self.t)
if Debug:
print(pairs)
enhanceFitness = []
for i in range(n):
pair1 = pairs[i]
for j in range(i+1,n):
if Debug:
print(i,j)
pair2 = pairs[j]
#if (pair1,pair2) not in history:
#history.append((pair1,pair2))
rankDifA1 = self.fitnessScores[pair1[0]][pair2[1]] - \
self.fitnessScores[pair1[0]][pair1[1]]
rankDifA2 = self.fitnessScores[pair2[0]][pair1[1]] - \
self.fitnessScores[pair2[0]][pair2[1]]
## if Debug:
## print('rankDifferences A')
## print([pair1,pair2])
## print(pair1[0],pair2[1],pair1[1],rankDifA1)
## print(pair2[0],pair1[1],pair2[1],rankDifA2)
difGroupA = rankDifA1 + rankDifA2
rankDifB1 = self.fitnessScores[pair1[1]][pair2[0]] - \
self.fitnessScores[pair1[1]][pair1[0]]
rankDifB2 = self.fitnessScores[pair2[1]][pair1[0]] - \
self.fitnessScores[pair2[1]][pair2[0]]
## if Debug:
## print('rankDifferences B')
## print([pair1,pair2])
## print(rankDifB1)
## print(rankDifB2)
difGroupB = rankDifB1 + rankDifB2
enhanceFitness.append( ( (difGroupA + difGroupB), (i,j), False ) )
## if Debug:
## print('Twisted')
## print('avant',pair1,pair2)
tpair1 = copy(pair1)
tpair2 = copy(pair2)
sw = copy(tpair1[1])
tw = copy(tpair2[0])
tpair1[1] = tw
tpair2[0] = sw
if Debug:
print(tpair1,tpair2)
## if [pair1,pair2] not in history:
rankDifA1 = self.fitnessScores[tpair1[0]][tpair2[0]] - \
self.fitnessScores[tpair1[0]][tpair1[1]]
rankDifA2 = self.fitnessScores[tpair2[0]][tpair1[0]] - \
self.fitnessScores[tpair2[0]][tpair2[1]]
## if Debug:
## print('rankDifferences A')
## print([tpair1,tpair2])
## print(rankDifA1,tpair1[0],tpair2[0],tpair1[1])
## print(rankDifA2,tpair2[0],tpair1[0],tpair2[1])
difGroupA = rankDifA1 + rankDifA2
rankDifB1 = self.fitnessScores[tpair2[1]][tpair1[1]] - \
self.fitnessScores[tpair2[1]][tpair2[0]]
rankDifB2 = self.fitnessScores[tpair1[1]][tpair2[1]] - \
self.fitnessScores[tpair1[1]][tpair1[0]]
## if Debug:
## print('rankDifferences B')
## print([tpair1,tpair2])
## print(rankDifB1,)
## print(rankDifB2)
difGroupB = rankDifB1 + rankDifB2
enhanceFitness.append( ( -(difGroupA + difGroupB), (i,j), True ) )
## else:
## print((pair1,pair2), 'already in history')
if Debug:
print(self.t, enhanceFitness)
#print(history)
from operator import itemgetter
enhanceFitness.sort(reverse=True,key=itemgetter(0))
if Debug:
print(enhanceFitness)
ne = len(enhanceFitness)
_nbrOfSwappingRetrials = self._nbrOfSwappingRetrials
if _nbrOfSwappingRetrials >= ne:
_nbrOfSwappingRetrials = ne
sortPosition = 0
ie = -1
je = -1
while enhanceFitness[sortPosition][0] >= Decimal('0') and\
ie not in enhanceFitness[sortPosition][1] and \
je not in enhanceFitness[sortPosition][1]:
## and sortPosition < _nbrOfSwappingRetrials:
newPairs = copy(pairs)
if Debug:
print('sortPosition:', sortPosition)
print(pairs)
ie = enhanceFitness[sortPosition][1][0]
je = enhanceFitness[sortPosition][1][1]
Twisted = enhanceFitness[sortPosition][2]
if Debug:
print(ie,pairs[ie])
print(je,pairs[je])
pair1 = pairs[ie]
pair2 = pairs[je]
if Twisted:
npair1 = [pair1[0],pair2[0]]
npair2 = [pair1[1],pair2[1]]
else:
npair1 = [pair1[0],pair2[1]]
npair2 = [pair2[0],pair1[1]]
## if Debug:
## print(Twisted,npair1,npair2)
## print(pair1,'-->>', npair1)
## print(pair2,'-->>', npair2)
## print(newPairs)
newPairs.pop(ie)
newPairs.insert(ie,npair1)
newPairs.pop(je)
newPairs.insert(je,npair2)
if Debug:
print('-->>>', newPairs)
corrA, stdDevA, groupAScores =\
self.computeIndividualCorrelations(newPairs)
## if Debug:
## print('sortPosition:', sortPosition)
## print(newPairs,corrA,stdDevA)
if corrA == Decimal('1.0'):
if Debug:
print('Current matching is fairest possible')
print(newPairs,corrA)
return newPairs,corrA,matchesVisited
if newPairs in matchesVisited:
if Debug:
print('Cycling:', newPairs)
sortPosition += 1
elif corrA < maxCorr:
if Debug:
print('No more correlation climbing')
print('maxCorr: %.3f, corrA: %.3f' % (maxCorr,corrA))
enhanced = False
break
elif corrA >= maxCorr:
if Debug:
print('Correlation climbing')
print('maxCorr: %.3f, corrA: %.3f' % (maxCorr,corrA))
maxCorr = corrA
pairs = newPairs.copy()
matchesVisited.append(pairs)
Enhanced = True
sortPosition += 1
if Debug:
self.showMatchingFairness(pairs)
else:
Enhanced = False
break
self.t += 1
## if sortPosition < _nbrOfSwappingRetrials:
## #history.append([npair1,npair2])
## maxCorr = corrA
## pairs = newPairs.copy()
## matchesVisited.append(pairs)
## Enhanced = True
## t += 1
## if Debug:
## self.showMatchingFairness(pairs)
if self.t > self.maxIterations:
print('!!!! Too many iterations (max=%d): %d\n' % (self.maxIterations,self.t))
print('You may adjust the *maxIterations* parameter')
Enhanced = False
## nfg = []
## for pair in newPairs:
## nfg.append(frozenset(pair))
if Debug:
print('Given matching')
self.showMatchingFairness(initialMatching)
print('Fairness enhanced matching')
self.showMatchingFairness(pairs,WithIndividualCorrelations=True)
print('number of iterations:',self.t)
return pairs,maxCorr,matchesVisited
#-----------------------
[docs]
class FairnessEnhancedIntraGroupMatching(IntraGroupPairing):
"""
Solver for computing fair IntraGroup pairings using a similar hill climbing heuristic as the
one for the intergroup pairing problem. The enhancing is guided by fitness ranking scores.
*Parameters*:
* *intraVp* : a IntraGroup voting profile instance with *2k* voters where the *2k-1* candidates of
each person are the other persons
* *initialMatching* : None (default) | 'random' | 'bestCopeland' the matching from which
the fairness enhancing algorithm is starting.
If *None*, a right --[pi,pi+1] for i = 1..2k-1 step 3-- and a left --[pi,p-i] for i = 1..k-- initial matching will be used
elif 'random' a random maximal matching will be used with given *seed*
elif 'bestCopeland' the best Copeland matching will be used as initial matching
* *fitnessScores* : 'Bachet' | 'Copeland' (default)
See the :ref:`tutorial on computing fair intragroup pairings <Fair-IntraGroup-Pairings-label>`.
"""
def __init__(self,intraVp=None,
maxIterations=None,
initialMatching=None,
fitnessScores='Copeland',
_nbrOfSwappingRetrials=None,
#RandomInit=False,
seed=None,
Comments=False,Debug=False):
from decimal import Decimal
from time import time
from copy import deepcopy
runTimes = {}
t0 = time()
self.name = 'fairnessEnhanced'
if intraVp is None:
print('!!! Error: a voting profile of even order is required')
return
else:
if intraVp.IntraGroup:
persons = [x for x in intraVp.voters]
else:
print('!!! Error: the voting profile is not IntraGroup as required')
return
order = len(persons)
if (order % 2) != 0:
print('!!! Error: the group size %d is not even' % order)
return
self.persons = persons
self.order = order
self.vpA = intraVp
# precomputing ranking scores
if fitnessScores == 'Bachet':
from bachetNumbers import BachetInteger as BN
bachetScores = {}
for i in range(order):
pi = persons[i]
bachetScores[pi] = {}
for j in range(order):
pj = persons[j]
bachetScores[pi][pj] = BN()
for i in range(order):
pi = persons[i]
for j in range(i+1,order):
pj = persons[j]
bachetScores[pi][pj] = self.computeBachetScore(pi,pj)
bachetScores[pj][pi] = self.computeBachetScore(pj,pi)
self.fitnessScores = bachetScores
elif fitnessScores == 'Copeland':
copelandScores = {}
for i in range(order):
pi = persons[i]
copelandScores[pi] = {}
for j in range(order):
pj = persons[j]
copelandScores[pi][pj] = Decimal()
for i in range(order):
pi = persons[i]
for j in range(i+1,order):
pj = persons[j]
copelandScores[pi][pj] = self.computeCopelandScore(pi,pj)
copelandScores[pj][pi] = self.computeCopelandScore(pj,pi)
self.fitnessScores = copelandScores
else:
print('!! Error: wrong fitnessScores: %s' % fitnessScores)
return
if Debug:
print(self.fitnessScores)
if initialMatching == 'random':
RandomInit = True
import random
if seed is None:
seed = random.randint(1,99)
random.seed(seed)
else:
RandomInit = False
self.seed = seed
if maxIterations is None:
self.maxIterations = 2 * len(persons)
else:
self.maxIterations = maxIterations
if _nbrOfSwappingRetrials is None:
self._nbrOfSwappingRetrials = 1
else:
self._nbrOfSwappingRetrials = _nbrOfSwappingRetrials
# set enhancing iterations counter t
self.t = 0
runTimes['dataInput'] = time() - t0
te = time()
if initialMatching is None or initialMatching == 'random':
n = self.order
if RandomInit:
persons = [x for x in intraVp.voters]
random.shuffle(persons)
if Debug:
print('Shuffled list of persons:',persons)
# left hand initial matching
if Comments or Debug:
print('===>>> Enhancing left initial matching')
tleft = time()
initialMatchingL = []
for i in range(1,n,2):
initialMatchingL.append( [persons[i-1],persons[i]] )
if Comments or Debug:
print('Initial left matching')
print(initialMatchingL)
corrInitialL, stdDevA, groupAScores =\
self.computeIndividualCorrelations(initialMatchingL)
if corrInitialL == Decimal('1'):
if Comments or Debug:
print('left initial matching is fairest possible')
self.matching = initialMatchingL
self.maxCorr = corrInitialL
self.iterations = 0
self.matchesVisited = []
runTimes['leftEnhancing'] = time() - tleft
runTimes['rightEnhancing'] = 0
runTimes['enhancing'] = time() - te
#runTimes['totalTime'] = t3 - t0
#self.runTimes = runTimes
else:
self.maxCorr = corrInitialL
femL,maxCorrL,matchesVisitedL =\
self.enhanceMatchingFairness(
initialMatchingL,
Comments=Debug,
Debug=Debug)
if Comments:
print('Fairness enhanced left matching')
print(femL, ', correlation: %.3f' % maxCorrL)
if maxCorrL == Decimal('1'):
if Comments or Debug:
print('left enhanced matching is fairest possible')
self.matching = femL
self.maxCorr = maxCorrL
self.iterations = self.t
self.matchesVisited = matchesVisitedL
runTimes['leftEnhancing'] = time() - tleft
runTimes['rightEnhancing'] = 0
runTimes['enhancing'] = time() - te
#runTimes['totalTime'] = t3 - t0
#self.runTimes = runTimes
else:
# right hand initial matching
if Comments or Debug:
print('===>>> Enhancing right initial matching')
tright = time()
initialMatchingR = []
if RandomInit:
#persons = [x for x in intraVp.voters]
random.shuffle(persons)
for i in range(1,n,2):
initialMatchingR.append( [persons[i-1],persons[-i]] )
if Comments or Debug:
print('Initialright matching')
print(initialMatchingR)
corrInitialR, stdDevA, groupAScores =\
self.computeIndividualCorrelations(initialMatchingR)
if corrInitialR == Decimal('1'):
if Comments or Debug:
print('right initial matching is fairest possible')
self.matching = initialMatchingR
self.maxCorr = corrInitialR
#self.iterations = self.t
#self.matchesVisited = []
runTimes['rightEnhancing'] = time() - tright
runTimes['enhancing'] = time() - te
#runTimes['totalTime'] = t3 - t0
#self.runTimes = runTimes
else:
self.maxCorr = corrInitialR
femR,maxCorrR,matchesVisitedR =\
self.enhanceMatchingFairness(
initialMatchingR,
Comments=Debug,
Debug=Debug)
if Comments or Debug:
print('Fairness enhanced right matching')
print(femR, ', correlation: %.3f' % maxCorrR)
if maxCorrR == Decimal('1'):
if Comments or Debug:
print('right enhanced matching is fairest possible')
self.matching = femR
self.maxCorr = maxCorrR
self.iterations = self.t
try:
self.matchesVisited |= matchesVisitedR
except:
self.matchesVisited = matchesVisitedR
runTimes['rightEnhancing'] = time() - tright
runTimes['enhancing'] = time() - te
#self.runTimes = runTimes
else:
# choosing the best initial matching
if maxCorrL >= maxCorrR:
if Debug:
print('==>> Store left initial matching',maxCorrL)
print(femL)
self.initialMatching = initialMatchingL
self.matching = femL
self.iterations = self.t
self.maxCorr = maxCorrL
else:
if Debug:
print('==>> Store right initial matching',maxCorrR)
print(femR)
self.initialMatching = initialMatchingR
self.matching = femR
self.iterations = self.t
self.maxCorr = maxCorrR
runTimes['rightEnhancing'] = time() - tright
runTimes['enhancing'] = time() -te
else: # given matching
if initialMatching == 'bestCopeland':
from pairings import BestCopelandIntraGroupMatching
cop = BestCopelandIntraGroupMatching(self.vpA,Comments=False)
initialMatching = cop.matching
self.copelandInitialMatching = cop.matching
self.cop = cop
if Comments:
print('Best Copeland initial matching')
elif initialMatching == 'bestBachet':
from pairings import BestBachetIntraGroupMatching
bbi = BestBachetIntraGroupMatching(self.vpA,Comments=False)
initialMatching = bbi.matching
self.bachetInitialMatching = bbi.matching
self.bbi = bbi
if Comments:
print('Best Bachet initial matching')
elif type(initialMatching) == list or type(initialMatching) == frozenset:
self.initialMatching = initialMatching
if Debug:
print('*---- Given Initial Matching ----*')
print(persons,initialMatching)
else:
print('Error !!: initialMatching = %s is not correctly given' % initialMatching )
print('Must be either None, "bestCopeland" or a given intragroup pairing solution')
return
corrInitialCop, stdDevCop, groupScoresCop =\
self.computeIndividualCorrelations(initialMatching)
if corrInitialCop == Decimal('1'):
if Comments or Debug:
print('Initial Copeland matching is fairest possible')
self.matching = initialMatching
self.maxCorr = corrInitialCop
self.iterations = 0
self.matchesVisited = []
runTimes['enhancing'] = time() - te
runTimes['leftEnhancing'] = 0
runTimes['rightEnhancing'] = 0
#self.runTimes = runTimes
else:
self.t = 0
self.maxCorr = corrInitialCop
fecop,maxCorrecop,matchesVisitedecop =\
self.enhanceMatchingFairness(
initialMatching,
Comments=Comments,
Debug=Debug)
self.matching = fecop
self.maxCorr = maxCorrecop
self.iterations = self.t
self.matchesVisited = matchesVisitedecop
runTimes['leftEnhancing'] = 0
runTimes['rightEnhancing'] = 0
runTimes['enhancing'] = time() - te
## t4 = time()
## runTimes['totalTime'] = t4 -t0
## self.runTimes = runTimes
if Debug:
try:
print(self.initialMatching)
except:
print(self.copelandInitialMatching)
print(self.matching)
print(self.maxCorr)
print(self.iterations)
# store graph data
tg = time()
self.vertices = deepcopy(intraVp.voters)
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(self.order):
vi = verticesList[i]
for j in range(i+1,self.order):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.gamma = self.gammaSets()
runTimes['storeGraph'] = time() - tg
runTimes['totalTime'] = time() - t0
self.runTimes = runTimes
if Comments:
print('===>>> Best fairness enhanced matching')
self.showPairing()
print('Average correlation: %+.3f' % self.maxCorr)
print('Total run time: %.3f sec.' % self.runTimes['totalTime'] )
#------------
[docs]
class FairestIntraGroupPairing(IntraGroupPairing):
"""
The class computes average ordinal correlations for the complete set of maximal IntraGroup matchings
of an een-sized set of persons and delivers, based on these correlations scores,
a fairest possible pairing of the persons
*Parameters*:
* *vpA* : any type of VotingProfile instance
* *oderLimit* : preventing a potential CPU memory or time overflow
See the :ref:`tutorial on computing fair intragroup pairings <Fair-IntraGroup-Pairings-label>`.
"""
def __init__(self,vp,orderLimit=6,
Comments=False,Debug=False):
from copy import deepcopy
from decimal import Decimal
from time import time
runTimes = {}
# check size of problem
persons = [x for x in vp.voters]
order = len(persons)
if Debug:
print('persons',persons)
if order > orderLimit:
print('The size %d of the group to pair is too high' % order)
print('The order limit is %d' % orderLimit)
print('Use the orderLimit parameter for larger orders')
return
if order % 2 != 0:
print('The size %d of the group is not even' % order)
return
# check IntraGroup voting profile version
if not vp.IntraGroup:
print('!!!Error: the voting profile is not an IntraGroup instance')
return
# data input
t0 = time()
#groupB = [x for x in vpA.voters]
#if Debug:
# print('groupB',groupB)
verticesKeys = [x for x in vp.voters]
## self.candidates = vpA.voters
## self.approvalBallot = {}
## self.ballot = vpA.ballot
## self.pairingPreferences = pairingPreferences
self.name = 'IntraGroupPairing'
self.persons = persons
self.order = order
self.vpA = vp
runTimes['dataInput'] = time() - t0
if Comments:
print('Run time for input data: %.4f sec.' % runTimes['dataInput'])
# compute maximal matchings
tmm = time()
from graphs import CompleteGraph,LineGraph
cg = CompleteGraph(verticesKeys=verticesKeys)
lcg = LineGraph(cg)
lcg.computeMIS()
maximalMatchings = lcg.misset
nbrOfMatchings = len(maximalMatchings)
if Comments:
print('Number of maximal matchings: %d' % nbrOfMatchings)
self.nbrOfMatchings = nbrOfMatchings
runTimes['maximalMatching'] = time() - tmm
if Comments:
print('Run time for computing the maximxal matchings: %.4f sec.' %\
runTimes['maximalMatching'])
# computing matching correlations
tmc = time()
from statistics import mean, stdev
from decimal import Decimal
from digraphs import IndeterminateDigraph
pairings = []
groupScores = {}
for matching in maximalMatchings:
if Debug:
print('matching:', matching)
# computing groupA's scores
groupScores = {}
for m in persons:
edg = IndeterminateDigraph(order=len(vp.candidates))
edg.actions = [x for x in vp.voters]
Min = edg.valuationdomain['min']
Med = edg.valuationdomain['med']
Max = edg.valuationdomain['max']
mmatch = [x for x in matching if m in x]
if Debug:
print(mmatch)
mmatch = [x for x in mmatch[0] if x != m]
if Debug:
print(mmatch)
relation = {}
for x in edg.actions:
relation[x] = {}
for y in edg.actions:
relation[x][y] = Med
n = len(edg.actions)
for i in range(n):
x = edg.actions[i]
for j in range(i+1,n):
y = edg.actions[j]
if x == mmatch[0]:
relation[x][y] = Max
relation[y][x] = Min
elif y == mmatch[0]:
relation[x][y] = Min
relation[y][x] = Max
else:
pass
edg.relation = relation
edg.gamma = edg.gammaSets()
edg.notGamma = edg.notGammaSets()
corr = edg.computeOrdinalCorrelation(vp.ballot[m])
groupScores[m] = Decimal('%.3f' % corr['correlation'])
# computing matching fitness scores
correlations = [groupScores[w] for w in groupScores]
avgCorr = mean(correlations)
stdCorr = stdev(correlations)
if Debug:
print(avgCorr,stdCorr)
pairings.append((matching,avgCorr,stdCorr,
groupScores,-stdCorr))
runTimes['matchingCorrelations'] = time() - tmc
if Comments:
print('Run time for individual correlations: %.4f sec.' %\
runTimes['matchingCorrelations'])
# sorting the fitness scores
ts = time()
from operator import itemgetter
pairings.sort(reverse=True,key=itemgetter(1,4))
runTimes['sortingFitness'] = time() - ts
if Comments:
print('Run time for fitness ranking: %.4f sec.' %\
runTimes['sortingFitness'])
#self.cg = cg
tst = time()
self.pairings = pairings
self.matching = pairings[0][0]
self.avgCorr = pairings[0][1]
self.stdCorr = pairings[0][2]
self.groupScores = pairings[0][3]
self.runTimes = runTimes
# storing the Graph data
self.vertices = deepcopy(vp.voters)
Min = Decimal('-1')
Med = Decimal('0')
Max = Decimal('1')
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
mt = []
for m in self.matching:
mt.append(frozenset(m))
edges = {}
for i in range(self.order):
vi = verticesList[i]
for j in range(i+1,self.order):
vj = verticesList[j]
edgeKey = frozenset({vi,vj})
if edgeKey in mt:
edges[edgeKey] = Max
else:
edges[edgeKey] = Min
self.edges = edges
self.gamma = self.gammaSets()
runTimes['storeResults'] = time() - tst
if Comments:
print('Run time for storing results: %.4f sec.' %\
runTimes['storeResults'])
######
runTimes['totalTime'] = time() - t0
if Comments:
print('Total run time: %.4f sec.' %\
runTimes['totalTime'])
# showing the faires pairing
if Comments:
print('Fairest pairing solution')
self.showPairing(pairings[0][0])
print('Average correlation : %.3f' % self.avgCorr )
print('Fairness (stdev) : %.3f' % self.stdCorr )
#------------- class methods
[docs]
def computeMatchingFairnessIndex(self,matching,Comments=False):
"""
Renders the index position of the given matching in the
fairness ranked self.pairings list.
"""
# converting to the frozenset formst
pairing = []
for pair in matching:
pairing.append(frozenset(pair))
pairing = frozenset(pairing)
n = len(self.pairings)
for i in range(n):
if pairing == self.pairings[i][0]:
if Comments:
print('Fairness index of matching: ',i)
break
return i
#---------------
##class _IntraGroupCopelandMatching(IntraGroupPairing):
## """
## !!! Not a satisfactory determined perfect matching guaranteed !!!
##
## The class computes the individual Copeland ranking scores
## based maximal matching resulting from the best determined spanning forest
## of the bipartite Copeland scores graph.
##
## *Parameters*:
##
## * *vpA* : intragroup *VotingProfile* instance
##
## See the :ref:`tutorial on computing fair intergroup pairings <Fair-InterGroup-Pairings-label>`.
## """
## def __init__(self,vpA,Comments=True,Debug=False):
##
## from time import time
## from decimal import Decimal
## from copy import deepcopy
## self.runTimes = {}
## t0 = time()
## # store input data
## self.vpA = vpA
## self.name = 'copelandMatching'
## if vpA is None:
## print('!!! Error: a voting profile of even order is required')
## return
## else:
## if vpA.IntraGroup:
## persons = [x for x in vpA.voters]
## else:
## print('!!! Error: the voting profile is not IntraGroup as required')
## return
## order = len(persons)
## if (order % 2) != 0:
## print('!!! Error: the group size %d is not even' % order)
## return
## self.persons = persons
## self.order = order
## self.vpA = vpA
## # precomputing Copeland ranking scores
## copelandScores = {}
## minScore = 0.0
## for i in range(order):
## pi = persons[i]
## copelandScores[pi] = {}
## for j in range(order):
## pj = persons[j]
## copelandScores[pi][pj] = Decimal()
## for i in range(order):
## pi = persons[i]
## for j in range(i+1,order):
## pj = persons[j]
## copelandScores[pi][pj] = self.computeCopelandScore(pi,pj)
## copelandScores[pj][pi] = self.computeCopelandScore(pj,pi)
## score = copelandScores[pi][pj] + copelandScores[pj][pi]
## if Debug:
## print(score)
## if score < minScore:
## minScore = score
##
## self.copelandScores = copelandScores
## if Debug:
## print(copelandScores)
## print('minScore:', minScore)
## t1 = time()
## self.runTimes['dataInput'] = t1 - t0
##
## #storing the Graph data
## t2 = time()
## self.vertices = vpA.voters
## Min = Decimal('%d' % (2*minScore) )
## Med = Decimal('0')
## Max = Decimal('%d' % (2*abs(minScore)) )
## self.valuationDomain = {'min': Min,
## 'med': Med,
## 'max': Max}
## verticesList = [v for v in self.vertices]
## n = len(verticesList)
## edges = {}
## for i in range(n):
## vi = verticesList[i]
## for j in range(i+1,n):
## vj = verticesList[j]
## edgeKey = frozenset([vi,vj])
## edges[edgeKey] = abs(minScore) + copelandScores[vi][vj] \
## + copelandScores[vj][vi]
##
#### for i in range(order):
#### for j in range(order):
#### edgeKey = frozenset([aKeys[i],bKeys[j]])
#### edges[edgeKey] = self.copelandScores[aKeys[i]][bKeys[j]] \
#### + self.copelandScores[bKeys[j]][aKeys[i]]
## self.edges = edges
## self.gamma = self.gammaSets()
## self.edges = edges
## if Debug:
## dself = self.graph2Digraph()
## dself.showRelationTable(ndigits=0)
## t3 = time()
## self.runTimes['copelandGraph'] = t3 - t2
##
## # computing the best determined maximal matching
## t4 = time()
## from graphs import BestDeterminedSpanningForest
## bsf = BestDeterminedSpanningForest(self)
## if Debug:
## bsf.exportGraphViz(WithSpanningTree=True,layout='circo')
## dbsf = bsf.graph2Digraph()
## dbsf.showRelationTable(ndigits=0)
## matching = []
## unPaired = []
## gamma = bsf.gamma
## sortedVerticesList = [(len(gamma[v]),v) for v in self.vertices]
## sortedVerticesList.sort()
## verticesList = [v[1] for v in sortedVerticesList]
## if Debug:
## print(verticesList)
##
## while len(verticesList) > 0:
## sortedVerticesList = [(len(gamma[v]),v) for v in verticesList]
## sortedVerticesList.sort()
## verticesList = [v[1] for v in sortedVerticesList]
## for v1 in verticesList:
## if Debug:
## print('==>>v1', v1, gamma[v1])
## if len(gamma[v1]) == 1:
## v2 = gamma[v1].pop()
## if [v1,v2] not in matching and [v2,v1] not in matching:
## matching.append(frozenset({v1,v2}))
## if Debug:
## print(matching)
## verticesList.remove(v1)
## verticesList.remove(v2)
## gamma[v2] = set()
## if Debug:
## print(v1,gamma[v1],v2,gamma[v2])
## for v3 in verticesList:
## if Debug:
## print('v3',v3,gamma[v3])
## if v1 in gamma[v3]:
## gamma[v3].remove(v1)
## if v2 in gamma[v3]:
## gamma[v3].remove(v2)
## if Debug:
## print('v3',v3,gamma[v3])
## elif len(gamma[v1]) == 0:
## verticesList.remove(v1)
## unPaired.append(v1)
## if Comments:
## print(len(matching),matching)
## print('==>> unpaired:', unPaired)
## if len(matching) < order:
## #aKeys = [a for a in self.vpA.voters]
## #bKeys = [b for b in self.vpB.voters]
## remaining = [v for v in self.vertices]
## for m in matching:
## lm = list(m)
## lm.sort()
## remaining.remove(lm[0])
## remaining.remove(lm[1])
## if Debug:
## print(remaining)
## pairs = []
## edges = self.edges
## na = len(remaining)
## for i in range(na):
## for j in range(i+1,na):
## edgeKey = frozenset({remaining[i],remaining[j]})
## pairs.append((edges[edgeKey],edgeKey))
## pairs.sort(reverse=True)
## if Debug:
## print(pairs)
## lmatching = [m for m in matching]
## i = 0
## while na > 0:
## keys = list(pairs[i][1])
## if Debug:
## print(keys)
## if keys[0] in remaining and keys[1] in remaining:
## remaining.remove(keys[0])
## remaining.remove(keys[1])
## lmatching.append(pairs[i][1])
## na -= 2
## i += 1
## else:
## i += 1
## matching = lmatching
## if Debug:
## print(len(matching),matching)
##
##
## self.matching = matching
## t5 = time()
## self.runTimes['maximalMatching'] = t5 - t4
##
## t7 = time()
## self.runTimes['totalTime'] = t7 - t0
#------------
[docs]
class BestCopelandIntraGroupMatching(IntraGroupPairing):
"""
The class computes the individual Copeland ranking scores and
construct the best determined perfect matching with a ranked pairs rule
from the reciprocal Copeland ranking scores graph
*Parameters*:
* *vpA* : intragroup *VotingProfile* instance
See the :ref:`tutorial on computing fair intragroup pairings <Fair-IntraGroup-Pairings-label>`.
"""
def __init__(self,vpA,Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
self.runTimes = {}
t0 = time()
# store input data
self.vpA = vpA
self.name = 'copelandMatching'
if vpA is None:
print('!!! Error: a voting profile of even order is required')
return
else:
if vpA.IntraGroup:
persons = [x for x in vpA.voters]
else:
print('!!! Error: the voting profile is not IntraGroup as required')
return
order = len(persons)
if (order % 2) != 0:
print('!!! Error: the group size %d is not even' % order)
return
self.persons = persons
self.order = order
self.vpA = vpA
# precomputing Copeland ranking scores
copelandScores = {}
maxScore = 0
for i in range(order):
pi = persons[i]
copelandScores[pi] = {}
for j in range(order):
pj = persons[j]
copelandScores[pi][pj] = Decimal()
for i in range(order):
pi = persons[i]
for j in range(i+1,order):
pj = persons[j]
copelandScores[pi][pj] = self.computeCopelandScore(pi,pj)
copelandScores[pj][pi] = self.computeCopelandScore(pj,pi)
score = copelandScores[pi][pj] + copelandScores[pj][pi]
if Debug:
print(pi,pj,copelandScores[pi][pj],copelandScores[pj][pi],score)
if abs(score) > maxScore:
maxScore = abs(score)
if Debug:
print(pi,pj,maxScore)
self.copelandScores = copelandScores
if Debug:
print(copelandScores)
print('maxScore:', maxScore)
t1 = time()
self.runTimes['dataInput'] = t1 - t0
#storing the Graph data
t2 = time()
self.vertices = vpA.voters
Min = Decimal('%d' % (-maxScore) )
Med = Decimal('0')
Max = Decimal('%d' % (maxScore) )
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset([vi,vj])
edges[edgeKey] = copelandScores[vi][vj] \
+ copelandScores[vj][vi]
self.edges = edges
self.gamma = self.gammaSets()
if Debug:
dself = self.graph2Digraph()
dself.showRelationTable(ndigits=0)
self.showEdgesCharacteristicValues(ndigits=0)
t3 = time()
self.runTimes['CopelandGraph'] = t3 - t2
# computing the best determined maximal matching
t4 = time()
remaining = [v for v in self.vertices]
if Debug:
print(remaining)
pairs = []
edges = self.edges
na = len(remaining)
for i in range(na):
for j in range(i+1,na):
edgeKey = frozenset({remaining[i],remaining[j]})
pairs.append((edges[edgeKey],edgeKey))
pairs.sort(reverse=True)
if Debug:
print(pairs)
lmatching = []
i = 0
while na > 0:
keys = list(pairs[i][1])
if Debug:
print(keys)
if keys[0] in remaining and keys[1] in remaining:
remaining.remove(keys[0])
remaining.remove(keys[1])
lmatching.append(pairs[i][1])
na -= 2
i += 1
else:
i += 1
if Debug:
print(len(lmatching),lmatching)
self.matching = lmatching
t5 = time()
self.runTimes['maximalMatching'] = t5 - t4
t7 = time()
self.runTimes['totalTime'] = t7 - t0
[docs]
def showMatchingWithFitnessScores(self,matching=None):
"""
shows the intragroup pairing solution when *matching is None*
"""
print('Matched pairs')
pairs = []
aKeys = self.persons
if matching is None:
matching = self.matching
for m in matching:
pair = list(m)
print("{'%s', '%s'}(%d)" % (pair[0],pair[1],self.edges[m]))
[docs]
def showMatchingFitnessScores(self,edges=None,ndigits=0):
"""
Prints the edge links of the graph
"""
verticesKeys = [x for x in self.vertices]
if edges is None:
edges = self.edges
try:
IntegerValuation = self.valuationDomain['IntegerValuation']
except:
IntegerValuation = False
print('\t|', end=' ')
n = len(verticesKeys)
for i in range(1,n):
x = verticesKeys[i]
print("'"+x+"'\t", end=' ')
print('\n--------|--------------------')
for i in range(n-1):
x = verticesKeys[i]
print(" '"+x+"' | ", end=' ')
for j in range(1,n):
if j < (i+1):
print('\t',end=' ')
else:
y = verticesKeys[j]
edgeKey = frozenset([x,y])
if IntegerValuation:
print('%+d\t' % (edges[edgeKey]), end=' ')
else:
formatString = '%%+2.%df\t' % ndigits
print(formatString % (edges[edgeKey]), end=' ')
print('')
print('Valuation domain: [%d, %d]' % (self.valuationDomain['min'],
self.valuationDomain['max']) )
#------------
[docs]
class BestBachetIntraGroupMatching(IntraGroupPairing):
"""
The class computes the individual Bachet ranking scores and
construct the best determined perfect matching with a ranked pairs rule
from the reciprocal Bachet ranking scores graph
*Parameters*:
* *vpA* : intragroup *VotingProfile* instance
See the :ref:`tutorial on computing fair intragroup pairings <Fair-IntraGroup-Pairings-label>`.
"""
def __init__(self,vpA,Comments=False,Debug=False):
from time import time
from decimal import Decimal
from copy import deepcopy
from bachetNumbers import BachetInteger as BN
self.runTimes = {}
t0 = time()
# store input data
self.vpA = vpA
self.name = 'copelandMatching'
if vpA is None:
print('!!! Error: a voting profile of even order is required')
return
else:
if vpA.IntraGroup:
persons = [x for x in vpA.voters]
else:
print('!!! Error: the voting profile is not IntraGroup as required')
return
order = len(persons)
if (order % 2) != 0:
print('!!! Error: the group size %d is not even' % order)
return
self.persons = persons
self.order = order
self.vpA = vpA
# precomputing Copeland ranking scores
bachetScores = {}
maxScore = BN(0)
for i in range(order):
pi = persons[i]
bachetScores[pi] = {}
for j in range(order):
pj = persons[j]
bachetScores[pi][pj] = BN()
for i in range(order):
pi = persons[i]
for j in range(i+1,order):
pj = persons[j]
bachetScores[pi][pj] = self.computeBachetScore(pi,pj)
bachetScores[pj][pi] = self.computeBachetScore(pj,pi)
score = bachetScores[pi][pj] + bachetScores[pj][pi]
if Debug:
print(pi,pj,bachetScores[pi][pj],bachetScores[pj][pi],score)
if abs(score) > maxScore:
maxScore = abs(score)
if Debug:
print(pi,pj,maxScore)
self.bachetScores = bachetScores
if Debug:
print(bachetScores)
print('maxScore:', maxScore)
t1 = time()
self.runTimes['dataInput'] = t1 - t0
#storing the Graph data
t2 = time()
self.vertices = vpA.voters
Min = -maxScore
Med = BN(0)
Max = maxScore
self.valuationDomain = {'min': Min,
'med': Med,
'max': Max,
'IntegerValuation': True,
}
## Min = Decimal('%d' % (-maxScore) )
## Med = Decimal('0')
## Max = Decimal('%d' % (maxScore) )
## self.valuationDomain = {'min': Min,
## 'med': Med,
## 'max': Max}
verticesList = [v for v in self.vertices]
n = len(verticesList)
edges = {}
for i in range(n):
vi = verticesList[i]
for j in range(i+1,n):
vj = verticesList[j]
edgeKey = frozenset([vi,vj])
edges[edgeKey] = bachetScores[vi][vj] \
+ bachetScores[vj][vi]
self.edges = edges
self.gamma = self.gammaSets()
if Debug:
dself = self.graph2Digraph()
dself.showRelationTable(ndigits=0)
self.showEdgesCharacteristicValues(ndigits=0)
t3 = time()
self.runTimes['BachetGraph'] = t3 - t2
# computing the best determined maximal matching
t4 = time()
remaining = [v for v in self.vertices]
if Debug:
print(remaining)
pairs = []
edges = self.edges
na = len(remaining)
for i in range(na):
for j in range(i+1,na):
edgeKey = frozenset({remaining[i],remaining[j]})
pairs.append((edges[edgeKey],edgeKey))
pairs.sort(reverse=True)
if Debug:
print(pairs)
lmatching = []
i = 0
while na > 0:
keys = list(pairs[i][1])
if Debug:
print(keys)
if keys[0] in remaining and keys[1] in remaining:
remaining.remove(keys[0])
remaining.remove(keys[1])
lmatching.append(pairs[i][1])
na -= 2
i += 1
else:
i += 1
if Debug:
print(len(lmatching),lmatching)
self.matching = lmatching
t5 = time()
self.runTimes['maximalMatching'] = t5 - t4
t7 = time()
self.runTimes['totalTime'] = t7 - t0
[docs]
def showMatchingFitnessScores(self,edges=None,ndigits=0):
"""
Prints the edge links of the graph
"""
verticesKeys = [x for x in self.vertices]
if edges is None:
edges = self.edges
try:
IntegerValuation = self.valuationDomain['IntegerValuation']
except:
IntegerValuation = False
print('\t|', end=' ')
n = len(verticesKeys)
for i in range(1,n):
x = verticesKeys[i]
print("'"+x+"'\t", end=' ')
print('\n--------|--------------------')
for i in range(n-1):
x = verticesKeys[i]
print(" '"+x+"' | ", end=' ')
for j in range(1,n):
if j < (i+1):
print('\t',end=' ')
else:
y = verticesKeys[j]
edgeKey = frozenset([x,y])
if IntegerValuation:
print('%+d\t' % (edges[edgeKey]), end=' ')
else:
formatString = '%%+2.%df\t' % ndigits
print(formatString % (edges[edgeKey]), end=' ')
print('')
print('Valuation domain: [%d, %d]' % (self.valuationDomain['min'],
self.valuationDomain['max']) )
#----------test pairings class ----------------
if __name__ == "__main__":
#from transitiveDigraphs import *
print('****************************************************')
print('* Python pairings module *')
print('* $Revision: Python3.13 $ *')
print('* Copyright (C) 2023-2025 Raymond Bisdorff *')
print('* The module comes with ABSOLUTELY NO WARRANTY *')
print('* to the extent permitted by the applicable law. *')
print('* This is free software, and you are welcome to *')
print('* redistribute it if remains free software. *')
print('****************************************************')
print('*-------- Testing classes and methods -------')
from time import time
from votingProfiles import *
#### RandomLinearVotingProfile,\
#### RandomBipolarApprovalVotingProfile,RandomVotingProfile
from random import randint
seed1 = randint(0,99)
seed2 = randint(100,199)
## seed1 = 1
## seed2 = 1616
order = 5
Comments = True
Debug = False
##
## # intragroup experiments
## vpG = RandomLinearVotingProfile(numberOfVoters=order,
## numberOfCandidates=order,
## votersIdPrefix='p',
## IntraGroup=True,
## #candidatesIdPrefix='b',
#### approvalProbability=0.2,
#### disapprovalProbability=0.2,
## seed=seed1,Debug=False)
#### vpG.showBipolarApprovals()
#### t0 = time()
## fp = FairestIntraGroupPairing(vpG,Comments=True,Debug=False,orderLimit=order)
#### t1 =time()
#### #print('fp total run time: %.3f sec.' % (t1-t0))
####
#### cop = BestCopelandIntraGroupMatching(vpG,Comments=False,Debug=False)
#### ecop = FairnessEnhancedIntraGroupMatching(vpG,initialMatching='bestCopeland',
#### Comments=True,Debug=False)
#### fegm = FairnessEnhancedIntraGroupMatching(vpG,initialMatching=fp.pairings[0][0],
#### Comments=True,Debug=False)
## fem = FairnessEnhancedIntraGroupMatching(vpG,initialMatching='bestCopeland',
## Comments=False,Debug=False)
####
#### print('==>> Copeland')
#### cop.showMatchingFairness(WithIndividualCorrelations=True)
#### print(cop.runTimes)
#### print('==>> Fairness enhanced')
#### fem.showMatchingFairness(WithIndividualCorrelations=True)
#### print(fem.runTimes)
#### print('==>> Copeland enhanced')
#### ecop.showMatchingFairness(WithIndividualCorrelations=True)
#### print(ecop.runTimes)
#### print('==>> Fairest')
#### fp.showMatchingFairness(WithIndividualCorrelations=True)
#### print(fp.runTimes)
##
#intergroup experiments
lvA = RandomBipolarApprovalVotingProfile(numberOfVoters=order,
numberOfCandidates=order,
votersIdPrefix='a',
#IntraGroup=True,
candidatesIdPrefix='b',
approvalProbability=0.3,
disapprovalProbability=0.3,
seed=seed1,Debug=False)
lvB = RandomBipolarApprovalVotingProfile(numberOfVoters=order,
numberOfCandidates=order,
votersIdPrefix='b',
#IntraGroup=False,
candidatesIdPrefix='a',
approvalProbability=0.3,
disapprovalProbability=0.3,
seed=seed2,Debug=False)
######## lvA = RandomLinearVotingProfile(numberOfVoters=order,
#### numberOfCandidates=order,
#### votersIdPrefix='a',
#### candidatesIdPrefix='b',
#### PartialLinearBallots=False,
#### lengthProbability=0.3,
#### seed=seed1)
#### lvB = RandomLinearVotingProfile(numberOfVoters=order,
#### numberOfCandidates=order,
#### votersIdPrefix='b',
#### candidatesIdPrefix='a',
#### PartialLinearBallots=False,
#### lengthProbability=0.3,
#### seed=seed2)
t0 = time()
fp = FairestInterGroupPairing(lvA,lvB,Comments=True,Debug=False,orderLimit=order)
t1 =time()
print('fp total run time: %.3f sec.' % (t1-t0))
####
igcg = BestCopelandInterGroupMatching(lvA,lvB,Comments=Comments,Debug=Debug)
print('==>> Copeland')
igcg.showMatchingWithFitnessScores()
## igcg.showMatchingFairness(WithIndividualCorrelations=True)
## print(igcg.runTimes)
## igbg = BestBachetInterGroupMatching(lvA,lvB,Comments=Comments,Debug=Debug)
## print('==>> Bachet')
## igbg.showMatchingFairness(WithIndividualCorrelations=True)
## print(igbg.runTimes,igbg.Reversed)
## igbgr = BestBachetInterGroupMatching(lvA,lvB,BestQualified=False,Comments=Comments,Debug=Debug)
## print('==>> Bachet reversed')
## igbgr.showMatchingFairness(WithIndividualCorrelations=True)
## print(igbgr.runTimes,igbgr.Reversed)
#### from pairings import *
## fpcg = FairnessEnhancedInterGroupMatching(lvA,lvB,initialMatching=None,Comments=False)
#### fpbg = FairnessEnhancedInterGroupMatching(lvA,lvB,initialMatching=igbg.matching,Comments=False)
######
#### print('==>> no initial matching')
## fpcg.showMatchingFairness(WithIndividualCorrelations=True)
#### print('==>> best Bachet initial matching')
#### fpbg.showMatchingFairness(WithIndividualCorrelations=True)
## bbig = FairestBachetInterGroupMatching(lvA,lvB)
## bbig.showMatchingFairness(WithIndividualCorrelations=True)
####
#### print('==>> Fairness random enhanced')
#### fem1 = FairnessEnhancedInterGroupMatching(lvA,lvB,
#### #initialMatching=fp.pairings[10][0],
#### initialMatching = 'random',
#### seed=1,
#### Comments=True,
#### Debug=False)
#### fem1.showMatchingFairness(WithIndividualCorrelations=True)
####
#### print(fem1.runTimes)
####
#### print('==>> Fairness enhanced')
#### fem2 = FairnessEnhancedInterGroupMatching(lvA,lvB,
#### initialMatching = fem1.matching,
#### seed=1,
#### Comments=True,
#### Debug=True)
#### fem2.showMatchingFairness(WithIndividualCorrelations=True)
#### print(fem2.runTimes)
##
#### print('==>> Fairest matching')
####
#### fp.showMatchingFairness(WithIndividualCorrelations=True)
#### print(fp.runTimes)
##
## print('seed1:',seed1, 'seed2:', seed2)
#### vpB.showBipolarApprovals()
## order = 6
## seed = 0.7525016431335723
## seed = None
## rigvp = RandomBipolarApprovalVotingProfile(numberOfVoters=order,
## votersIdPrefix='p',
## seed=seed,
## IntraGroup=True,Debug=False)
##
##
## t2 = time()
## fgm = FairnessEnhancedIntraGroupMatching(vpG,
## seed=seed1,
## initialMatching='random,
## #maxIterations=20,
## Comments=True,Debug=True)
## t3 = time()
## print('fgm total run time: %.3f sec.' % (t3-t2))
## fgm.showMatchingFairness(WithIndividualCorrelations=True)
## fp.showMatchingFairness(WithIndividualCorrelations=True)
## lvA = BipolarApprovalVotingProfile('debug')
## lvA.IntraGroup = True
## lvA.seed = 1
## k = 4
##
## if Comments:
## lvA.showBipolarApprovals()
## fp = FairestIntraGroupPairing(lvA,orderLimit=k,Comments=Comments)
## if Comments:
## fp.showMatchingFairness(fp.matching)
## #matchingIndex = random.randint(10,20)
## em = FairnessEnhancedIntraGroupMatching(lvA,
## initialMatching=None,
## maxIterations=2*k,
## Comments=Comments,Debug=False)
## corropt, stdopt, groupOptScores = fp.computeIndividualCorrelations(fp.matching,Debug=True)
## lvA.showBipolarApprovals()
## from votingProfiles import *
## from pairings import *
## bavp = BipolarApprovalVotingProfile('classmates')
## from pairings import *
## from time import time
## t0 = time()
## bcim = BestCopelandIntraGroupMatching(bavp,Comments=False)
## print(time() -t0)
## t1 = time()
## fec = FairnessEnhancedIntraGroupMatching(bavp,
## initialMatching=bcim.matching,
## fitnessScores='Copeland')
## print(time()-t1)
## t0 = time()
## bbim = BestBachetIntraGroupMatching(bavp,Comments=False)
## print(time() -t0)
## t1 = time()
## feb = FairnessEnhancedIntraGroupMatching(bavp,
## initialMatching=bbim.matching,
## fitnessScores='Bachet')
## print(time()-t1)
print('*------------------*')
print('If you see this line all tests were passed successfully :-)')
print('Enjoy !')
print('*************************************')
print('* R.B. January 2023-202 *')
print('* Version: Python3.13 *')
print('*************************************')