Modelling congestion games in python without tons of for loop

Question

In the bidirected triangle network as shown below, 4 agents $\{s1,s2,s3,s4\}$ have their own destination $\{t1,t2,t3,t4\}$. I am trying to model this problem with a python script without any game theory library as a challenge.

Since the cost of most of the edges (except edge $vu$ and $wu$) depend on the number of agents using it, I need to know all the strategy for all agents before getting the final cost of each edge.

So my algorithm outlines as:

1. Loop the strategy of agent 1, add cost to the edges he used
2. Inside the previous loop, loop the strategy of agent 2, add cost to the edges he used
3. Inside the previous loop, loop the strategy of agent 3, add cost to the edges he used
4. Inside the previous loop, loop the strategy of agent 4, add cost to the edges he used
5. After knowing all their strategy, add calculate the cost for each agent
6. Before exploring alternative strategy, remove 1 cost on the edge that has given up by the agent who's changing his strategy.
7. Repeat step 1-6

Shown below is my python script, but you can see I have 1 for loop for 1 agent. It would be difficult for me to try 10 agents in the future. Anyway to improve the algorithm?

# Initializing Paraemeters
agent_dict = {
    'agent1': [['uv'], ['uw','wv']],
    'agent2': [['uw'], ['uv','vw']],
    'agent3': [['vw'], ['vu','uw']],
    'agent4': [['wv'], ['wu', 'uv']],
}

# Variables
uv = 0
uw = 0
wv = 0
vw = 0

path_to_cost = {
'uv': uv,
'uw': uw,
'wv': wv,
'vw': vw,
'vu': 0,
'wu': 0
}

cost_list = []
strategy_set = []

for path1 in agent_dict['agent1']:

    for edge1 in path1: # Step 1
        if edge1 == 'vu' or edge1 == 'wu':
            pass
        else:
            path_to_cost[edge1]+=1

    for path2 in agent_dict['agent2']: # Step 2
        for edge2 in path2:
            if edge2 == 'vu' or edge2 == 'wu':
                pass
            else:
                path_to_cost[edge2]+=1

        for path3 in agent_dict['agent3']: # Step 3
            for edge3 in path3:
                if edge3 == 'vu' or edge3 == 'wu':
                    pass
                else:                        
                    path_to_cost[edge3]+=1

            for path4 in agent_dict['agent4']: # Step 4
                for edge4 in path4:
                    if edge4 == 'vu' or edge4 =='wu':
                        pass
                    else:            
                        path_to_cost[edge4]+=1

                # Step 5
                cost1 = [path_to_cost[x] for x in path1]
                cost2 = [path_to_cost[x] for x in path2]
                cost3 = [path_to_cost[x] for x in path3]
                cost4 = [path_to_cost[x] for x in path4]
                social_cost = sum(cost1) + sum(cost2) + sum(cost3) + sum(cost4)
                cost_list.append(social_cost)
                strategy_set.append([path1,path2,path3,path4])
                print('agent1 is using {}, agent2 is using {}, agent3 is using {}, and agent4 is using {}'.format(path1,path2,path3,path4))
                print('agent1 costs {}, agent2 costs {}, agent3 costs {}, agent4 is using {}'.format(cost1,cost2,cost3,cost4))
                print('Social cost = {}\n'.format(social_cost))

                        # Step 6: Resetting cost for each agent for next trial
                for edge4 in path4: # resetting agent 4 strategy 
                    if edge4 == 'vu' or edge4 =='wu':
                        pass
                    else: 
                        path_to_cost[edge4]-=1

            for edge3 in path3:
                if edge3 == 'vu' or edge3 == 'wu':
                    pass
                else:  
                    path_to_cost[edge3]-=1


        for edge2 in path2:
            if edge2 == 'vu' or edge2 == 'wu':
                pass
            else:
                path_to_cost[edge2]-=1

    for edge1 in path1:
        if edge1 == 'vu' or edge1 == 'wu':
            pass
        else:        
            path_to_cost[edge1]-=1

My 2nd attempt to the problem using S0AndS0's suggestions

from points import Point
points = {
          'u': Point(address = 'u', neighbors = {'v': 0, 'w': 0}),
          'v': Point(address = 'v', neighbors = {'u': 0, 'w': 0}),
          'w': Point(address = 'w', neighbors = {'u': 0, 'v': 0}),
        }    

# Strategy 1 u-v (if choice == 'v')
agent1_pos = 'u'
agent1_target = 'v'

agent2_pos = 'u'
agent2_target = 'w'

agent3_pos = 'v'
agent3_target = 'w'

agent4_pos = 'w'
agent4_target = 'v'

choice_a1 = agent1_target
points[agent1_pos]['neighbors'][choice_a1]+=1

choice_a2 = agent2_target
points[agent2_pos]['neighbors'][choice_a2]+=1

choice_a3 = agent3_target
points[agent3_pos]['neighbors'][choice_a3]+=1

choice_a4 = agent4_target
points[agent4_pos]['neighbors'][choice_a4]+=1

edge_cost = lambda base_cost, drivers: base_cost * drivers # no information about the driver along the edges

Answer 1

Note from the future, if this is your first time here know that this has been made apart of a Git Pages hosted documentation series with tips on various aspects split out to separate posts, and source code examples are just a git clone away. Those wondering why scripts where moved, they're frozen in time (with some git magics) to ensure that the examples here work long into the future, and oh the sweet syntax highlighting; all in all allowing room for more content or answers.

Links to scripts maybe downloaded by clicking the Raw button then Ctrl^s to save it as a regular text file.

---

The following portions are what I'll attempt to aid with as I'm on a similar path...

I am trying to model this problem with a python script without any game theory library as a challenge.

...

It would be difficult for me to try 10 agents in the future. Anyway to improve the algorithm?

... however, unfortunately helping with the tons of for loops I cannot, but I can help in spreading'em out such that cyclomatic complexity checker tools don't flag down what you're trying to accomplish, and code profilers can then give meaningful output for determining where libraries such as numpy are a good fit.

Looking through your code, I think you're on the right track with using dictionaries for some of this, well that is if you're dedicated to minimal library use; which I think is totally a legit way of learning.

The next step seems to be to use Python's OOP (Object Oriented Programing) tendencies, and __doc__ strings to your advantage; first step you've already completed by getting some code that produces your desired output. Because you've stated this is a challenge I'll not be posting a complete answer, but I'll provide some code to illustrate what I mean.

Or in other words, maybe a good idea to get a snack and drink... this is about to get verbose,

---

# Nodes/Points

The current graph looks sorta like the following when unwrapped, note I'm just drawing a sketch to better frame what the code'll be covering.

$$ \color{#000}{\fbox{ w }}{ \color{#2E8B57}{ \xleftarrow[]{\color{#000}{X}} }} \color{#00A}{ \fbox{ u } }{ \color{#2E8B57}{ \xrightarrow[]{\color{#000}{X}} }} \color{#000}{\fbox{ v }} \\ \color{#000}{\fbox{ u }}{ \color{#FF0000}{ \xleftarrow[]{\color{#000}{O}} }} \color{#00A}{ \fbox{ v } }{ \color{#2E8B57}{ \xrightarrow[]{\color{#000}{X}} }} \color{#000}{\fbox{ w }} \\ \color{#000}{\fbox{ v }}{ \color{#2E8B57}{ \xleftarrow[]{\color{#000}{X}} }} \color{#00A}{ \fbox{ w } }{ \color{#FF0000}{ \xrightarrow[]{\color{#000}{O}} }} \color{#000}{\fbox{ u }} $$

Points (the items from the middle column above and defined in the following linked to class) are only concerned with where it is (address), and the costs to each of it's neighbors's addresses. The cheapest (of routes) method (defined within the Point class) calculates the returned value at call time so that neighbors can be added, removed, or modified at any other time.

Link to points/__init__.py

a customized dictionary that'll be used in the following section.

Note for those not Python savvy, don't worry to much about it as the file is less than one hundred lines long (including comments, tests, and __doc__ strings), and really just serves as someway of organizing a portion of the problem space to be modeled.

---

To the mathematically educated, I'd really like to see how to write a similar model through pure math, so feel free to edit this section here with something beautiful.

---

If ya saved the above to a file path such as points/__init__.py, importing could look like...

from points import Point

Initializing a similarly shaped three pointed graph with bi-directional traveling costs between each point's neighbors could look like...

X = 0.2
O = 0.7

points = {
    'u': Point(address = 'u', neighbors = {'v': X, 'w': X}),
    'v': Point(address = 'v', neighbors = {'u': O, 'w': X}),
    'w': Point(address = 'w', neighbors = {'u': O, 'v': X}),
}

Getting the information back out would then look like...

help(points['w'])
# ... prints triple quoted block from class
#     AKA the `__doc__` string ;-)

points['w']['neighbors']
# -> {'u': 0.7, 'v': 0.2}

for name, point in points.items():
    neighbors = point['neighbors']
    print("{name} cheapest routes -> {route}".format(
        name = name,
        route = point.cheapest(neighbors)))
# -> u cheapest routes -> {'w': 0.2, 'v': 0.2}
# -> w cheapest routes -> {'v': 0.2}
# -> v cheapest routes -> {'w': 0.2}

The cheapest of routes differ between points u and v, and so far the information of all possible routes are preserved, because this class inherits from the dict class, that's what the class Point(dict) did, it's possible to dump it's saved/current state via...

print(points)
# -> {'u': {'address': 'u',...}, 'v': {'neighbors': {'u': 0.7, ...}, ...}, ...}

Bellow is a sketch of Point's super relationship with the dict class

$$ \color{#CD8C00}{\fbox{ dict }{ \color{#00A}{\xleftarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{ \xrightarrow[\color{#000}{\text{returned value}}]{} } }} \color{#00A}{\fbox{ Point }} $$

Essentially with one class we can model the graph portion of the graph (minus the agents and something to coordinate iterating states through time), plus it abstracted three for loops and other logic to a something that can be questioned reliably. Utilizing this methodology of splitting things into manageable chunks on the rest of the challenges will make adding more agents, changing algorithms, and even mutating the graph much simpler.

This is probably a good time for an intermission before diving into the next section, it'll be there once the above has been digested.

---

# Customizing Points (updates)

If the cost of each edge depends on the number of agents using it, what X and O should I pass it to the 'neighbors' dictionary?

I believe that the total cost is a result of a function that takes points['w']['population']s travel plans for instance (a property that'll be updated iteratively) and cost (X, or Y depending upon Point). And not to get too lost in the details but both X and O could be functions.

Here's two quick examples of how that could look in Python using lambdas...

• Masking saved cost states

edge_cost = lambda base_cost, drivers: base_cost * drivers

travel_estimate = points['w']['neighbors']['u']
# ... > `O` ... > 0.7
edge_cost(base_cost = travel_estimate, drivers = 2)
# -> 1.4

What I'm asking of edge_cost might also be able to be expressed as $ e{\left( c, d \right)} = d \times c $, though one gotcha (if I remember correctly), is that $\text{`pythonLambda`} {\ne} {lambda}$, because a Python lambda can be asked to do things that don't quite translate cleanly the other-way-round.

• Differing execution/calculations of X and O, or in this case first and business class tickets.

first = lambda base_cost: base_cost + 0.5
business = lambda base_cost: base_cost + 0.2


customers = {
    'bob': {'name': 'Bob', 'ticket': business},
    'alice': {'name': 'Alice', 'ticket': first}}


for key, customer in customers.items():
    print("{name} ticket cost -> {cost}".format(**{
        'name': customer['name'],
        'cost': customer['ticket'](base_cost = 0.4)
    }))
# -> Bob ticket cost -> 0.6
# -> Alice ticket cost -> 0.9

These states a Point for the most part totally doesn't care about from it's frame of reference as a destination that agents leave. At most in the second of the last to examples it would only care about getting it's output by feeding a first class function call. One way to look at is maybe a Point could be like a dispatcher (a stationary agent) who keeps a roaster of other agents in town and maybe picks up calls (_if they must, and it's not a Monday_), from agents about recent traveling conditions after arriving at a neighbor. Defined this way a Point could intentionally give bad information to another agent.

Maybe $v$ has never gotten along with $S_{1}$ and will happily low-ball any travel cost estimates given to that agent, maybe $S_{1}$ doesn't figure this out till the end n of a pay periods when their gas cost vs. compensation are not as they expected. How $v$'s' and $S_{1}$'s personalities cause them to mess with one another I think are within the scope of a Point.

If you wish to question an edge I think it maybe helpful to re-frame an edge (define a class) as the points that are populated on an edge, so that things can be asked about those on an edge. This isn't to say that an edge must contain every point between, computers and $\infty$ usually don't mix, but instead an edge could have a way of calculating things like distances between agents or their destination.

But it seems to me that the point class can only model edges with a constant cost?

Sorta; it depends upon how you use those values or choose to update them. I took some care trying to model only part of the problem because covering everything in one post can cause readers to feel a bit like Joel Miller; which is not my intent, I'd rather hope code be seen as another way to break a problem down to the atomic level if need be.

Think of Point as a starting point for organizing questions about it's state, the using of those states and final calculations are still a bit further up the stack as far as code execution depth if you want fine-grain control. Suppose in the future you want to model the rising and falling travel of costs based on hour of day or number of iterations of a parent's loop. These and other things can be done within another class that either imports or inherits the Point class.

Inheriting a Point to model something based on construction hours for example could look something like...

$$ \color{#CD8C00}{\fbox{ dict }{ \color{#00A}{\xleftarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{ \xrightarrow[\color{#000}{\text{returned value}}]{} } }} \color{#00A}{\fbox{ Point }{ \color{#2E8B57}{\xleftarrow[]{ \color{#000}{\text{super}_{\left(key\_word\_args\right)}} }} \over{\color{#00A}{ \xrightarrow[\color{#000}{\text{returned value}}]{} }} }} \color{#2E8B57}{\fbox{ Construction }} $$

Above is just a sketch to show an overview of the relationships that are being built with the code linked bellow

Link to points/construction.py

which contains the Construction class a customized Point found in points/__init__.py.

By having the Construction class inherit from Point we gain the super powers of pre-processing cheapest within the scope of Construction.cheapest method. Yes that also means there's now some for loop stacking, but the this is just an example of using the scope stacking that Python almost expects of authors, while also addressing one way to have changing cost calculations done by a point.

In other-words, to those yelling at their monitor, right now the focus is optimizing for developer's time and not code execution time; releasing pandas or other libraries and optimizing code can wait till the problem is fleshed-out from components with well defined inputs and outputs.

Importing the Construction point if saved under points/construction.py could then look like...

from points.construction import Construction

Adding a fourth point c to the points dictionary defined previously might then look like...

points.update({
    'c': Construction(
        address = 'w',
        neighbors = {'v': O, 'w': X},
        current_hour = 6,
        hours = {9: 0.1, 10: 0.3,
                 11: 0.4, 13: 0.6,
                 14: 0.7, 15: 0.85,
                 16: 0.3, 17: 0.2}
        )})

City planners kinda dropped the ball by having construction on both out-bound routs, but that kinda models life.

... and updating points['c']'s neighbors could look like...

Z = 0.1
for address in points['c']['neighbors'].keys():
    points[address]['neighbors'].update({'c': Z})

Which then would require some adjustments to the for loop that was being used to iterate over points such as...

hours_start = 1
hours_end = 24
hours_step = 1
days = 2

day_count = 0
for i in range(hours_start, (hours_end * days) + 1, hours_step):
    for address, point in points.items():
        # ... This `try`/`except` syntax is known as
        #     "asking forgiveness" _dig_ into previous
        #     edits for a "asking permission" version ;-)
        try:
            current_hour = point['current_hour']
        except KeyError:
            current_hour = 'NaN'
        else:
            if current_hour >= hours_end:
                point['current_hour'] = hours_start
                day_count += 1
            else:
                point['current_hour'] += hours_step

        finally:
            cheapest_routs = point.cheapest()
            print("{d} {h} {p} cheapest routes -> {r}".format(
                d = day_count, h = current_hour,
                p = address, r = cheapest_routs))

Indeed I've just nested even more loops, so when you're ready, I've addressed one way of mitigating this overall problem on a somewhat related question using Iterators that allow for further unwrapping of loops into their own classes; instances of which are iterable with next() method calls. Right now what is important to grasp from the adjusted model is that we now have a way to consistently mask the initialized cost values within a point based off some other state that is updated. And that regardless of if a Point is a normal point or special point like Construction, the cheapest of routs methods are what is called by what ever process asking the questions of points.

# ... Example _snippets_ of output
0 6 c cheapest routes -> {'w': 0.2}
0 NaN u cheapest routes -> {'w': 0.2, 'v': 0.2}
0 NaN w cheapest routes -> {'c': 0.1}
0 NaN v cheapest routes -> {'c': 0.1}
0 7 c cheapest routes -> {'w': 0.2}
# ...
1 12 c cheapest routes -> {'w': 0.2}
1 NaN u cheapest routes -> {'w': 0.2, 'v': 0.2}
1 NaN w cheapest routes -> {'c': 0.1}
1 NaN v cheapest routes -> {'c': 0.1}
1 13 c cheapest routes -> {'w': 0.8}
# ...

Okay I think it's time for another pause for digestion, hopefully these pointers have helped ya plan out a course.

---

Agent hints

My 2nd attempt to the problem using S0AndS0's suggestions...

You're really close! There are many ways to handle abstracting this part of the problem, I've left some hints within the comments of the question and the answer, but here's just a bit more...

agents = {
    'Bob': {
        'name': 'Bob',
        'address': 'u'},
    'Alice': {
        'name': 'Alice',
        'address': 'u'},
}

# ... having the `points` agree
#     with agents `address`...
for agent in agents.values():
    agent_addr = agent['address']
    points[agent_addr]['population'].append(agent['name'])

... then having Bob go on a random adventure could look a bit like...

from random import randint


for _ in range(5):
    agent = agents['Bob']
    here = points[agent['address']]

    option_limit = len(here['neighbors'].keys()) - 1
    direction = randint(0, option_limit)
    # ... for example `randint(0, 2)` -> `1`
    #     could be a lookup for `w` bellow...
    chosen_addr = here['neighbors'].keys()[direction]
    # ... remember `neighbors` are `{addr: cost}` pairs,
    #     so above is really pulling a random `addr`
    base_cost = here['neighbors'][chosen_addr]

    there = points[chosen_addr]

    here['population'].remove(agent['name'])
    there['population'].append(agent['name'])
    agent['address'] = there['address']

    print("{name} paid {paid} to get from {here} to {there}".format(
        name = agent['name'],
        paid = base_cost,
        here = here['address'],
        there = there['address']))

Output may look similar to...

Bob paid 0.2 to get from u to v
Bob paid 0.7 to get from v to u
Bob paid 0.2 to get from u to v
Bob paid 0.7 to get from v to u
Bob paid 0.2 to get from u to w

Those last few lines with heres population remove some name, theres populated append some name, and agents reassignment address are what updates the object states. Figuring out how ya want to store states in a more efficient manor can be the challenge after getting something that works for the problem you want modeled.

Now with these tips it's getting really close to a solution which is something that I've been trying to dance about so that there's still a challenge left. So I'm going to call this answer's version complete so there's at least some space left for answers on other aspects.

I'll encourage readers once more to make use of the downloads (perhaps first), and the full repo via forking that's been setup for answering questions on a similar path. Questions specific to the code likely should be opened as Issues so that the question here is more about the problem as a whole.

Hope this all helps in making the task of modeling even more complexity something that is within reach.