Search
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] ...
phi[i]
i
Expected usage python main.py delta eps < graph.txt > allocations.txt.
python main.py delta eps < graph.txt > allocations.txt
stdin
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.
values.py