Warning
This page is located in archive. Go to the latest version of this course pages.

Assignment 3: Flow Games

Your goal will be to estimate the influence of agents on the throughput of randomly generated networks.

You will first need to derive a flow game from the networks assigned to you. Use the sampling algorithm based on statistical estimation to compute the values.

Input

Expected usage python main.py value < graph, where value is either banzhaf or shapley.

You are provided with an input describing the graph in the following format:

|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)
where
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 → N+ 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. 
Assume m = |E|, and node ids v.id = 0, if v = source and v.id = 1, if v = sink.

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

Output

The output of your program must be the estimated Shapley, or Banzhaf values for each player, in the following format.

A1 A2 ... An
where n = |N| and Ai is the Allocation to player i assigned by the specified value.

Requirements

  • 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.

The Shapley and the Banzhaf values will be graded separately. The solutions will be considered acceptable if each allocation is within 0.15 of the exact answer. You will still be awarded some fraction of points if you are near the correct answer. Your code must finish within two times of the time set by the (un-optimized) reference solution. Calculate the required number of iterations, or do an experiment (not on BRUTE!). Values such as n! / 2 are not correct and will not finish in time.

The assignment will be graded based on the *last* score achieved, not the best.

Skeleton API

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.'''

Algorithm for Shapley value estimation

Input: Coalitional game v and player i.

1. Determine the size of the random sample.
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.

Algorithm for Banzhaf value estimation

Input: Coalitional game v and player i.

1. Determine the size of the random sample.
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.

Examples

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

• Example Sanity Check

Shapley and Banzhaf values:

1
1

• Example 0

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

Shapley and Banzhaf values:

2 1 1
2 1 1

• Example 1

Shapley and Banzhaf values:

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 

courses/cgt/coalitional_game_theory.txt · Last modified: 2022/11/29 23:34 by votroto1