Automate The Decision Tree by Networkx

Bring gut feelings on the paper and analyze choices

Part.2. Automate the decision tree analysis:

In part one of the strategic decision makings, I explained how changing the structure of the decision tree into a network reduces uncertainty by managing the flow of information within the network. In this article, I show you an example of how to automate the computations within such a network.

Think of the decision nodes as following the movements of the ball on the pool table

To compute the total probability/rewards of each scenario, we need to compute the discounted value of the path, which is the sum of each possible outcome multiplied by the cumulative probability.

After implementing the network and computing probabilities (in part.1 of the series), you can generate all paths in the network by the Networkx package:

source_node =1 
terminal_node = 6
path = nx.all_simple_paths(G, source_node, terminal_node)
print('network path:', list(path))

network path: [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 6],
              [1, 2, 3, 6], [1, 2, 6], [1, 6]]

Before we proceed with solving the example path : [1, 2, 3, 4, 5, 6], it is better to add node types to the network and keep tracking of the decisions (this block of code should be added to the implementation of Networkx in part.1)

  # add node type to the network:
  node_type={}
  node_type.update({node_id: dict(zip(['node_type'],[sheet_nodes.cell_value(row_id, 1)]))}) 
  nx.set_node_attributes(G, node_type)

Implement the discounted values of the path:

1. Create a Class path that can keep track of the sequence of nodes and edge attributes in the network:

class Path():
  def __init__(self, node_seq, G):
    self.node_seq = node_seq
    self.G = G

2. Define a function in the class to do the following:

2.1. Keep track of the sequence of the nodes in the path: from 1 to 2, from 2 to 3, from 3 to 4, …

2.2. Find the edges between two nodes, and store the cost and probability associated with the edge. Then compute the discounted value of the path as explained in the beginning of the article.

• Initialize main variables for the function such as Network G and the node sequence and edge attributes such as reward, cost and actions in the nodes.

def compute_payoffs(self):
    G = self.G
    node_seq = self.node_seq
    node_seq_len = len(self.node_seq)
    # create a list of transitions (1 to 2),(2 to 3), ...
     transitions = [(a,b) for a,b in zip(node_seq[:-1], node_seq[1:])]
    
    # set initial values for edge attributes
    cost_total = 0
    prob_total= 0
    set_action = [] # to store actions within the path
 

• Go through the network and find transitions between nodes. for example, from node.1. to node.2. and node.2 to node.3 and so on.
• Based on the transitions, read edges and do the math (take sum of the costs and multiply the probabilities).

for n in node_seq:
      current_transition = [(a,b) for a,b in zip(node_seq[:-1], node_seq[1:])]
      print('-- current transition ' , current_transition)

        node_from  = current_transition[0][0]    
        node_to = current_transition[0][1]
        print('this is from ', node_from, 'to', node_to)
        #------------------
        # Find actions from node_from to the node_to
        #------------------
        edge_attr = G[node_from][node_to]
        print('edge attributes:' , edge_attr)
        
        cost_increment = edge_attr['cost']
        print('-- cost_increment = ', cost_increment)
       
        cost_total = cost_total + cost_increment
        prob_total = prob_total * edge_attr['prob'] 
        print('-- Total cost = ',cost_total )
        print('-- Total prob = ', prob_total ) 
    
      else:  #  for a terminal node there is only one action hence: 
        print('This is the end of sequence and final cost/prob')
        edge_attr = {'action': 'End'}
        cost_total = cost_total
        prob_total = prob_total
        print('-- Total cost = ', cost_total )
        print('-- Total prob = ', prob_total ) 
                     
      seq_action.append(edge_attr['action'])
      # store path information in a dictionary
      path_characteristics = {
          'path_cost': cost_total, 
          'path_prob'  : prob_total,
          'path_action': seq_action}

    return path_characteristics

Now we only need to run the class and see the path output:

example_path = path[0] # select a path from the list of all path
Network_res = Path(example_path, G)
path_characteristics = Network_res.compute_cost_prob()

The class path for the example is printed step by step in the figure below:

Conclusion:

In this article, I explain how to automate the discounted values of the path corresponding to each branch of the decision tree. Next, I explain the famous prisoner’s dilemma as an example of strategic decision-making and how we can use Networkx to implement such decisions.

If you like what you read, please give it a clap and follow me on medium.

Thanks for reading.
Also, feel free to contact me on LinkedIn.