Assignment 4: Flow Game

Deadline for submission to BRUTE is 09.01.2024

Your goal will be to estimate the influence of agents on the throughput of a network.

Firstly, you will need to derive a flow game from the networks assigned to you; then estimate the Shapley value of each agent using the sampling algorithm based on statistical estimation.

The estimation accuracy will be set by parameters delta and epsilon. The probability that the allocations estimated by your solution deviate more than epsilon from their true value must be less than delta; that is P(|estimate - shapley| ≥ ε) ≤ δ.

You will receive the flow game over standard input, and the parameters delta and epsilon as program arguments. The flow network will have the following format:

vertex_count edge_count agent_count
edge[0].from edge[0].to edge[0].capacity edge[0].agent
edge[1].from edge[1].to edge[1].capacity edge[1].agent
...

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

phi[0] phi[1] phi[2] ...

Expected usage python main.py delta eps < graph.txt > allocations.txt.

• Upload all files as a single archive,
• The main file must reside in the root of the archive (not in a sub-directory),
• You are not allowed to read or write to any files,
• Your program must accept input from stdin and output to stdout.

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.

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

You may use our template and examples to get started.

Firstly, estimate the marginal-contribution variance, then use Chebyshev's inequality to compute the required sample count. Finally, compute the Shapley value as the mean of the marginal contributions over randomly generated permutations.

• Implementing an algorithm for the exact value is not required, but might be useful for debugging,
• Make sure You are not writing debugging output to stdout,
• Reuse flows computed for players earlier in the permutation,
• Caching may be less practical when the number of agents gets large,
• The expected length of your solution in values.py is around 50 lines.