This project is called The Magical Decision Maker Box. This is an optimal solution finder application developed via Python which helps users make decisions based on management science principles. This is also the term project I had during my course -- Fundamentals of Computer Science and Programming. The goal of this application is to gamify the boring algorithms so that users will easily learn how to make scientific decisions, because I believe that, lecture is not the only way to teach -- making algorithms interactive and gamified is also cool😎!!!
👉🏼Snapshot of this application:
This application is inspired by a course that I took in Fall 2018, called Decision Analysis and Multi-criteria Decision Making, taught by one of the best professors in Carnegie Mellon University. We were asked to calculate the results using paper and pencils to reproduce the methods taught in class. Many classmates of mine had huge trouble with this because the algorithms baffled them. Thus, I started to develop a computer program that allows step-by-step algorithm reproduction in drag-n-click style that allows uses to learn in their own pace.
(😅Ironically, the computer program worked out so well that I now am getting obviously slower than before when I was manually solving the problems. lol.)
This tool asks for following input:
-
What decision does the user want to make? (aka. the decision subject)
-
What choices/candidates does the user have in mind? (aka the candidates that will be competing each other)
-
What are the attributes/features/parameters that the user care about when making this decision?
-
What are the specifications of each attribute of each candidate? (aka. the specification metric)
-
What is the weight of each attribute in the user's mind? (aka. how important is each attribute, compared with each other)
-
What are the sweet spot directions of each attribute? (aka. for each attribute, does the user want the value to be the higher the better?)
In my Decision Analysis class, we were taught methods below:
-
TOPSIS (The Technique for Order of Preference by Similarity to Ideal Solution)
-
AHP (Analytical Hierarchy Process)
-
Series of Rank Based Methods, including:
Plurality Rules, IRV(Instant Run-off Voting), Borda Voting, and Schulze’s Beatpath Method.
With the input above, the Box will be able to come up with a matrix with the given information, transform the matrix into a rank-based one, and present results reached from different algorithms in the back end. The result will be the winner candidate(s) for the user (sometimes there are several winners if there is a tie).
👇🏻Screenshot: User input matrix (left) and transformed rank-based matrix: 📍Users can hover the cursor onto the grid so that the highlight mapping shows how each cell is transformed.
👇🏻Screenshot: The candidate battle ground: 📍Users can drag the competing candidates to the main pathground, and easily arrange the positions at their own will. User actions: single click to select; drag to move nodes; double click to release nodes; drag and move to arrange positions.
👇🏻Screenshot: Step-by-step beathpath relation: 📍Select any of the candidates, and click "Show One Way Path", users can examine all the one-way relations between this particular candidate and another.
👇🏻Screenshot: Detailed interactable calculations: 📍Select any of the score nodes here, users can check the calculation process of that particular beatpath.
👇🏻Screenshot: Two-way paths for further explanation: 📍Select any of the score nodes here and click "Show Two Way Path", users can check the two-way beatpaths for supplemental information.
👇🏻Screenshot: Find the winner -- the Smith Set: 📍Click "Show Smith Set", and the winner among the candidates will be highlighted in yellow/gold. Boom! The winner is here.
-
Minimal dependency on framework: The only framework used here is the built-in Python tkinter. tkinter is used only for the GUI. Other than that, this tool does not depend on any modules/frameworks. Users won't have to install extra packages.
-
Minimal dependency on data structures: As no extra modules are imported, this tool does not rely on data structures from Numpy or Pandas, like Numpy arrays or Pandas DataFrame. All the algorithms are reproduced via the simplest structures: sets, tuples, lists and dictionaries, including nested lists and dictionaries.
-
Minial dependecy on algorithms: I did not refer to any existing algorithms online -- I reproduced the whole process by applying what my professor has taught me in pencil and paper to the computer program. 👉🏻Let me explain: As many decision-making problems are essentially graph theory problems in Mathematics, there are already instant algorithms written for computer programs, such as Floyd–Warshall algorithm in time O(n ^ 3), Kosaraju's algorithm and Tarjan's algorithm in time O(n ^ 2). However, as my initial intention was to enable my fellows to solve the problem by hand, the ready algorithms are not applicable.
-
Smart use of backtracking: As this project also serves as my term project for my computer science class, I was asked to have enough programming complexity. Thus, I used backtracking (a kind of recursion) to my program, which worked out pretty efficiently. I am very proud of using minimal data structures to reproduce these algorithms.
-
Homemade UI widgets: As only tkinter was used (its UI components really suck, no offense), I have to hand code the very basic components on my own. Thus, I coded the click-n-drag, cursor hovering visual effects, intelligent two-way arrow pointing, and smart node spacing to guarantee the quality of the UI.
-
UI/UX design: This is the very first project that requires myself to design the UI/UX. I think I did a great job in creating an intuitive and interactive experience for the users. I also had several users to test my app, which allowed me to tune and tweak the frontend through iterations.
All Python files here are linked internally. It is designed like a chain with one biting another's tail. Therefore, after downloading all the files in a folder, the run.py will serve as a trigger. Run this run.py file will be enough for users to get the whole program moving.
-
Run the run.py file, you will see a welcome page. Type your name in and hit 'start'.
-
Type whatever decision you are making, how many alternatives you have(the candidates that you have difficulty choosing), and how many attributes there are(the different aspects that you care about).
-
Quickly lookup the specifications online of each candidate.
-
Then, the app will convert your original specification matrix into a rank-based matrix. Within each attibute, the alternative with the best specification will be put in the first rank, and the second best alternative gets to be put at second, and so on. If you are confused with the rank base transformation, hover your cursor onto the cell on either matrix, and the other matrix will show where the corresponding cell is.
-
With the matrix done, you are now at the candidate playground. In this battle field, you get to see how one alternative beats another, and who is the final winner. The calculations are hidden in each score node. If you click the node, the matrix will come up and tell you how the score is derived.
-
For a quick answer, click the 'Show Smith Set' button. Winner(s) will be illuminated in a gold color.
import copy
matrix = [ [ 3, 3, 2, 2 ],
['A','B','C','D'],
['B','C','D','A'],
['C','D','A','B'],
['D','A','B','C']
]
bordaPreference = [4,3,2,1]
playerSet = {'A','B','C','D'}
assert(len(bordaPreference) == len(matrix[0]))
def matrix2Dtransformer(matrix, playerSet):
playerList = list(playerSet)
altMatrix = copy.deepcopy(matrix)
header = ["ph"] + altMatrix[0]
# ph is just for placeholder to maintain the rectangular shape
altMatrix[0] = header
rows, cols = len(matrix), len(matrix[0])
for r in range(1,rows):
altMatrix[r] = [0]*len(altMatrix[r])
altMatrix[r].insert(0,playerList[r-1])
return altMatrix,playerList
def bordaCount(matrix, playerSet,bordaPreference):
altMatrix, playerList = matrix2Dtransformer(matrix, playerSet)
rows, cols = len(matrix), len(matrix[0])
for c in range(cols):
for r in range(1, rows):
targetRow = playerList.index(matrix[r][c])
altMatrix[targetRow+1][c+1] = bordaPreference[r-1]
# to link the place with the new row index in the altMatrix
# then assign the corresponding rank borda score to the target
rows, cols = len(altMatrix), len(altMatrix[0])
score = dict.fromkeys(playerList, 0)
for r in range(1,rows):
for c in range(1,cols):
score[altMatrix[r][0]] += altMatrix[r][c] * altMatrix[0][c]
# sumproduct the borda score row and the attribute weight row
return score
print(bordaCount(matrix,playerSet,bordaPreference))def instantRunoffElimination(matrix, score = None):
rows, cols = len(matrix), len(matrix[0])
if not score:
score = dict.fromkeys(matrix[1], 0)
if len(score) == 1: return list(score.keys())[0]
for k in score: score[k] = 0
for c in range(cols):
for r in range(1,rows):
if matrix[r][c] in score:
score[matrix[r][c]] += matrix[0][c]
break
for player in score:
if score[player] >= sum(score.values()) * 0.5:
return max(score, key=score.get)
weakest = min(score.values())
for player in list(score):
if score[player] == weakest:
score.pop(player)
if score == dict(): return "All Tie"
if len(score) == 1: return list(score.keys())[0]
return instantRunoffElimination(matrix, score)
print(instantRunoffElimination(matrix))def pluralityElimination(matrix):
rows, cols = len(matrix), len(matrix[0])
score = dict.fromkeys(matrix[1], 0)
for c in range(cols):
for r in range(1,rows):
if matrix[r][c] in score:
score[matrix[r][c]] += matrix[0][c]
break
maximum = max(score.values())
for player in list(score):
if score[player] != maximum:
score.pop(player)
return list(score.keys())
print(pluralityElimination(matrix))import copy
playerList = ['B','C','D']
matrix = [ [ 4, 1, 2, 3 ],
['A','C','A','C'],
['B','B','D','A'],
['C','D','B','B'],
['D','A','C','D']
]
def pathIdentifier(matrix, playerList):
'''This is a helper func, calculating all two-way paths,
later used in the smithSetFinder func. '''
combSet = set() # initializing an empty set for all combinations
for i in range(len(playerList)):
for j in range(i+1,len(playerList)):
combSet.add((playerList[i], playerList[j]))
rows, cols = len(matrix), len(matrix[0])
scoreList = []
for pair in combSet:
score = dict.fromkeys(pair, 0)
for player in pair:
for c in range(cols):
for r in range(1,rows):
if matrix[r][c] == player:
score[player] += matrix[0][c]
break
if matrix[r][c] in pair:
score[matrix[r][c]] += matrix[0][c]
break
break
scoreList.append(score)
return scoreList, combSet
def positiveBeatFinder(matrix, playerList):
'''this is a helper func to only count the winner in the
pairwise battle'''
if len(playerList) <= 1: raise Exception('Start with at least two players.')
scoreList, combSet = pathIdentifier(matrix, playerList)
scoreBeatList = []
for score in scoreList:
scoreBeat = score.copy()
for player in scoreBeat:
# ties get 0 for both direction
if score[player] == max(score.values()):
scoreBeat[player] -= sorted(score.values())[0]
else: scoreBeat[player] = 0
scoreBeatList.append(scoreBeat)
return scoreBeatList
print(positiveBeatFinder(matrix,playerList))
def underdogOverriderFinder(matrix,playerList):
'''This is a helper func to identify the all-time loser,
and all-time winner.
An all-time loser will never show up in smith set.
Eliminate underdog first.
An all-time winner is the smith set itself.
Most of the time there might not be an all-time winner and loser.'''
playerSet = set(playerList)
scoreBeatList = positiveBeatFinder(matrix,playerList)
atLeastOneWin, atLeastOneLose = set(),set()
for scoreBeat in scoreBeatList:
for player in scoreBeat:
if scoreBeat[player] != 0:
atLeastOneWin.add(player)
else: atLeastOneLose.add(player)
underdogSet = playerSet - atLeastOneWin
overriderSet = playerSet - atLeastOneLose
return underdogSet, overriderSet, scoreBeatList
def isDominantSet(tmpSmith, playerSet, scoreBeatList):
'''For every player in a smith-suspicious set,
if the player is defeated by players outside the set,
this set cannot be Smith set.'''
overflowSet = playerSet - tmpSmith # outside the smith-suspicious set
for scoreBeat in scoreBeatList:
for player in scoreBeat:
if (player in tmpSmith
and scoreBeat[player] == 0 # gets defeated
and max(scoreBeat, key = scoreBeat.get) in overflowSet):
return False
return True
def smithSetFinder(matrix, playerList):
'''this func uses the positive defeat score to eliminate losers
to get the smallest dominating set, aka: the smith set '''
playerSet = set(playerList)
underdogSet, overriderSet, scoreBeatList = underdogOverriderFinder(matrix,playerList)
if overriderSet != set(): return overriderSet
else:
playerSet -= underdogSet
dominantContainer = []
playerList = list(playerSet)
for i in range(len(playerList)):
tmpSmith = set()
for player in playerList[i:]:
# this guarantees that the player will never be visited twice
tmpSmith.add(player)
if isDominantSet(tmpSmith,playerSet,scoreBeatList):
dominantContainer.append(tmpSmith.copy())
break
return min(dominantContainer, key = len) # get the smallest setI plan to further expand the algorithms and methods as there are still a lot of interesting decision-making systems out there.