Your goal will be to estimate the influence of agents on the throughput of randomly generated networks. You need to derive a flow game from the networks assigned to you. For the computation of Shapley value use the sampling algorithm based on the statistical estimation. You can use the source code template we prepared for you.

Submit your solutions to the upload system by January 8th 2021. The maximum number of points for this assignment is 12.

Consider the following:

V is the set of vertices of the graph G.
E is the set of (directed) edges of the graph G.
N is the set of players controlling the edges of G.
E ∋ ei = (u, v), where u, v ∈ V.
c: E → ℜ+ is the capacity function, mapping an edge to a real (upper) capacity value, where ∀e ∈ E : c(e) ≥ 0.
a: E → N is the controlling agent function, mapping an edge to the agent controlling it.
Assume that all lower capacities equal to zero. 

You are provided with an input describing the graph in the following format. Assume m = |E|, and node ids v.id = 0, if v = source and v.id = 1, if v = sink:

|V| |E| |N|
u.id v.id c(e1) a(e1)
...
u.id v.id c(ei) a(ei)
...
u.id v.id c(em) a(em)

Mind the difference in numbering between the vertices and the agents. Vertex indices are zero-based, whereas agents' labels are one-based.

The output of your program must be the estimated Shapley and Banzhaf values for each player, in the following format. Assume n = |N|, Si as the Shapley value of player i, and Bi as the corresponding Banzhaf value:

S1 S2 ... Sn
B1 B2 ... Bn

• Use the name flow_game.py for the main file.
• Upload all files as a single archive.
• The main file must reside in the root of the archive (not in a sub-directory).
• Your program should accept input from stdin and output to stdout.
• Use Python >= 3.6

The Shapley and the Banzhaf values will be graded separately. The solutions will be considered correct if each value is within 0.2 of the exact answer. Each test must finish within ~20 seconds. Try to calculate the required number of iterations (or do an experiment), values such as m = n! / 2 are not correct and will not finish in time.

/

In order to facilitate and encourage the focus on the game theoretic concepts, you are provided with a source code template that implements a graph data structure, along with necessary functionalities. Concretely speaking, you will have access to classes: Agent, Node, DirEdge and Graph.

The expected usage is through the class Graph, while from the rest of classes you only need to use the constructors. The class Graph contains the following API:

class Graph:
  def __init__(self, V=None, E=None):
    '''Takes a set V of Node objects, and a set E of Edge objects.'''
    
  def add_edge(self, e):
    '''Takes an Edge object e and adds it to the graph.'''

  def get_max_flow(self):
    '''Constructs a linear program that computes the maximum flow of the graph.
    Returns a nonnegative real valued number.'''

  def get_induced_graph_by_edges(self, E=None):
    '''Takes a set E of Edge objects (belonging to the graph).
    Returns a new graph G', which is the vertex-induced graph constructed from all the vertices in E.'''

The rest of constructors look as follows:

class DirEdge:
  def __init__(self, tail, head, l, u):
    '''Takes a Node object tail, and a Node object head, where e = (tail, head).
    The values l, u correspond to the lower (l), and upper (u) capacities.'''

class Node(Base):
  def __init__(self, id, incoming=None, outgoing=None):
    '''Takes an integer id,
    a set of incoming edges E- s.t. ∀(u, v) ∈ E-: v = self,
    a set of outgoing edges E+ s.t. ∀(v, w) ∈ E+: v = self.'''

class Agent(Base):
  def __init__(self, id):
    '''Takes an integer id.'''

Input: Coalitional game v and player i.

1. Determine the size of the random sample m ≤ n!.
2. Sample (with replacement) permutations (π1, . . . , πm) from Π with uniform probability 1/n!
3. Estimate the Shapley value as the average of the marginal contributions of player i
(see slides 20, 21, 22 for a refresher), over the whole sample.

Input: Coalitional game v and player i.

1. Determine the size of the random sample m ≤ 2^(n-1).
2. Sample coalitions A ⊆ N\{i} with uniform probability.
3. Calculate the difference between values achieved by coalition A vs A∪{i}.
4. The Banzhaf value estimate is the average of the differences obtained in step 3.

You can use these public test instances we prepared for you. You are still encouraged to write your own tests.

No sniggering at the back! Just you wait till you fail this one.

Solution:

1
1

This flow game comes from M. Maschler, E. Solan, and S. Zamir. Game Theory. Cambridge University Press, 2013.

Solution:

2 1 1
2 1 1

Solution:

0.369 1.119 1.119 0.786 0.560 0.393 0.619 1.036 
0.328 0.953 0.953 0.672 0.375 0.344 0.453 0.828