def smith_minimax(matrix):
    candidates = list(matrix.keys())
    
    # Step 1: Determine the Smith set
    smith_set = find_smith_set(matrix)
    
    # If Smith set has only one candidate, that's our winner
    if len(smith_set) == 1:
        return smith_set[0]
    
    # Step 2: Apply Minimax within the Smith set
    worst_defeats = {}

    for candidate in smith_set:
        worst_defeat = float('-inf')
        for opponent in smith_set:
            if candidate != opponent:
                # Using "winning votes" method
                defeat = matrix[opponent][candidate]
                worst_defeat = max(worst_defeat, defeat)
        worst_defeats[candidate] = worst_defeat

    # Return the candidate with the least worst defeat
    return min(worst_defeats, key=worst_defeats.get)

def find_smith_set(matrix):
    candidates = list(matrix.keys())
    smith_set = candidates.copy()
    
    for i in range(len(candidates)):
        for j in range(len(candidates)):
            if i != j:
                candidate = candidates[i]
                opponent = candidates[j]
                
                if matrix[candidate][opponent] > matrix[opponent][candidate]:
                    # candidate beats opponent
                    smith_set = [c for c in smith_set if c == opponent or 
                                 any(matrix[s][candidate] > matrix[candidate][s] for s in smith_set)]
    
    return smith_set