2
$\begingroup$

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.

bidirected triangle network

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
$\endgroup$
  • 1
    $\begingroup$ Nice question. Not sure if it is suitable here, but I am interested in answering this problem. 1) It appears that this algorithm is not invariant to the order of the loops i.e. are you expecting to obtain the same answer if you start with agent4 first? 2) code can be cleaned up in terms of python. 3) try to think of a data structure you can create before running the algorithm. I will take a look. $\endgroup$ – Chinny84 Mar 1 at 1:30
  • $\begingroup$ I have doubled checked this algorithm, there was some bug in the loop indentation. After fixing it, my algorithm is now invariant. For point number (3), I was also thinking about the possible data structure that I can create, but currently haven't come up with anything better yet. $\endgroup$ – Raven Cheuk Mar 1 at 5:11
  • $\begingroup$ I will give it a go later - but you could also try to use the networkx python library. This will allow you to create the network it self with edges and weights. Then you will be traversing the graph with provided paths. Explain briefly why you are nesting the strategies? I assumed the strategies would be independent? $\endgroup$ – Chinny84 Mar 1 at 16:08
  • $\begingroup$ I will check out networkx. Actually I also want to avoid using so many for loops. But I cannot think of a better way to do it. Nested loop is the only simple thing I can think of at the moment. $\endgroup$ – Raven Cheuk Mar 1 at 23:24
  • 1
    $\begingroup$ I have been playing with the itertools product but due to the nature of the loops and the dict update this is not possible. Recursion may help but I feel the way the algorithm is structured the recursion would be difficult. One last point can you confirm the last decrement loop for strat 1 since it does not seem to follow the same pattern as the increment loops. $\endgroup$ – Chinny84 Mar 1 at 23:42
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for providing such a detail answer. But it seems to me that the point class can only model edges with a constant cost? 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? It's definitely towards the direction I want to go, I will try running the code once I am in front of my computer. $\endgroup$ – Raven Cheuk Mar 30 at 10:12
  • $\begingroup$ You're welcome and glad it seems to be of use, I've updated the answer with details and more code that may address some of your questions (side note, check the diff of the original Point script to see what changed). X and O are just place holders at this point to make sure that there's something functional to play around with and see that things are working as expected. Adding more layers of complexity, as you'll hopefully see in the new code examples, is totally possible while maintaining code readability and organized file paths. $\endgroup$ – S0AndS0 Mar 31 at 9:57
  • $\begingroup$ Thanks for your fantastic answer. This is what I am going to do in the future. But before expanding to a complete work, I would like to solve the agent sustainability issue first. After trying your Point class, it does make the code more readable, but to fully calculate all possible strategies by different agents and their outcome respectively, I still need to do it case by case (see my updated code above). I am not sure if I am using your code correctly. It seems the Point class can only store the node information, but for my problem, the population along each edge is needed. $\endgroup$ – Raven Cheuk Apr 2 at 7:40
  • 1
    $\begingroup$ Most welcome! Here's just a few more tips with Agents...If ya check the Point class you'll find a population list's been waiting for your needs, and was originally there for registering an Agents name. Quick-n-dirty example; suppose agents = {'bob': {'name': 'Bob'}, 'alice': {'name': 'Alice'}...}, then sign Bob into $u$ could look like points['u']['population'].append(agents['bob']['name']), and to move Alice along $w$ to $v$ could look like points['w']['population'].remove(agents['alice']['name']) then points['v']['population'].append(agents['alice']['name']). $\endgroup$ – S0AndS0 Apr 2 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.