A very unoptimized brute-force algorithm determining the maximal price of anarchy for selfish load balancing games on uniformly related machines for a given number of players and machines, searching all integer weights and speeds within a range from 1 to a given end number.

load_balancing_poa_maximizer.py

from __future__ import annotations

from itertools import product, combinations_with_replacement
from sys import argv, exit
from typing import List, Dict


class Player:
    """A player in a selfish load balancing game."""

    def __init__(self, number: int, weight: float):
        assert weight > 0
        self.number = number
        self.weight = weight

    def cost(self, assignment: Dict[Player, Machine]) -> float:
        """Determines the cost of the given assignment for this player."""
        return assignment[self].load(assignment)

    def best_option(self, assignment: Dict[Player, Machine], machines: List[Machine]) -> bool:
        """Determines whether the given assignment is the best option of the player."""
        current_machine = assignment[self]
        current_cost = self.cost(assignment)
        # go through all other machines
        for machine in machines:
            if machine == current_machine:
                continue

            # assume we switch over to it...
            modified_assignment = assignment | {self: machine}
            # ... is it better than the current option?
            if self.cost(modified_assignment) < current_cost:
                return False
        return True

    def __repr__(self):
        return self.__str__()

    def __str__(self) -> str:
        return f"P{self.number} ({self.weight})"


class Machine:
    """Represents a machine in a selfish load balancing game with uniformly related machines."""

    def __init__(self, number: int, speed: float):
        assert speed > 0
        self.speed = speed
        self.number = number

    def load(self, assignment: Dict[Player, Machine]) -> float:
        """Determines the load of this machine under the given assignment."""
        return sum(p.weight / self.speed for p in assignment.keys() if assignment[p] == self)

    def __repr__(self):
        return self.__str__()

    def __str__(self) -> str:
        return f"M{self.number} ({self.speed})"


class Game:
    """Represents a selfish load balancing game with uniformly related machines."""

    # state: Mapping from machines to players on it

    def __init__(self, players: List[Player], machines: List[Machine]):
        self.players = players
        self.machines = machines

    def is_nash(self, assignment: Dict[Player, Machine]) -> bool:
        """Returns true iff the given assignment is a Nash equilibrium for this game."""
        return all(player.best_option(assignment, self.machines) for player in self.players)

    def social_cost(self, assignment: Dict[Player, Machine]) -> float:
        """Returns the social cost of the given assignment under this game."""
        return max(machine.load(assignment) for machine in self.machines)

    def determine_poa(self, print_result=False) -> float:
        """Calculates the price of anarchy of this game.
        For this purpose, the "worst" PNE and the social optimum will be determined by a brute-force approach.
        If `print_result` is `True`, the worst PNE and socially optimal assignment will be printed.
        """
        # Try all possible assignments.
        all_possible = (dict(x) for x in product(*(tuple((x, y) for y in self.machines) for x in self.players)))
        nash_assignment = None
        opt_assignment = None
        nash_cost = 0.0
        optimum_cost = None
        for i, assignment in enumerate(all_possible):
            # simply determine assignments with min social cost and PNEs with max social cost.
            cost = self.social_cost(assignment)
            if self.is_nash(assignment) and cost > nash_cost:
                nash_cost = cost
                nash_assignment = assignment
            if optimum_cost is None or cost < optimum_cost:
                optimum_cost = cost
                opt_assignment = assignment
        if print_result:
            print(f"NASH: {nash_assignment} (cost {nash_cost})\nOPT: {opt_assignment} (cost {optimum_cost})")
        return nash_cost / optimum_cost

    def __str__(self):
        return "Players: " + ", ".join(str(x) for x in self.players) + \
            "\nMachines: " + ", ".join(str(x) for x in self.machines)


def main():
    if not 3 <= len(argv) <= 4:
        print(f"usage: {argv[0]} <n> <m> [<end>]")
        exit(1)

    n = int(argv[1])
    m = int(argv[2])
    end = argv[3] if 3 in argv else 6

    # We want to check every possible game. However, there are infinitely many games, so this is impossible.
    # Hence, we just check all possible weights and speed at some interval [1, end) within the set of natural numbers.
    all_factors = range(1, end)
    player_power = list(combinations_with_replacement(all_factors, n))
    machine_power = list(combinations_with_replacement(all_factors, m))
    print(f"Trying {len(player_power) * len(machine_power)} possible states...")

    # We will try all possible states defined above and remember the game with max PoA.
    max_poa = 0
    max_game = None
    for i, weights in enumerate(player_power):
        print(f"[{i / len(player_power):.2%}]")
        for j, speeds in enumerate(machine_power):
            players = [Player(i + 1, x) for i, x in enumerate(weights)]
            machines = [Machine(i + 1, x) for i, x in enumerate(speeds)]
            game = Game(players, machines)
            poa = game.determine_poa(False)
            if poa > max_poa:
                max_poa = poa
                max_game = game
    print(f"Maximum PoA: {max_poa}")
    print(f"Found for the following game:\n{max_game}")
    print(f"With the following worst Nash equilibrium and social optimum:")
    max_game.determine_poa(True)


if __name__ == "__main__":
    main()