Implementation of algorithm for optimal ex ante persuasive signaling scheme in Bayesian network congestion games

Bayesian Network Congestion Games (BNCGs) are a model used in Game Theory to represent multi-agent interactions. Applying the Bayesian Framework to the well-understood model of network congestion game, BNCGs investigates the possibility to study real-world situations in which the state of the network is unknown and determines the costs incurred by the players. Our goal is to study the problem of computing an optimal ex ante persuasive signaling scheme in symmetric BNCG with affine costs. Under these assumptions, the problem has been proved to be computable in polynomial time and an algorithm was developed. The aim of the present work is to study the framework and analyze the algorithm, proposing an implementation in the Python programming language. Finally, we conclude our work reporting the experimental results obtained by the execution of different tests.

I Bayesian Network Congestion Game (BNCG) sono un modello della Teoria dei Giochi adatto a rappresentare le interazioni tra una moltitudine di agenti. Applicando l’ambiente bayesiano al ben noto modello di Congestion Game, i BNCG indagano la possibilità di studiare situazioni del mondo reale in cui lo stato della rete è sconosciuto e determina i costi sostenuti dai giocatori. Il nostro obiettivo è studiare il problema del calcolo di uno schema di segnalazione ottimale ex ante persuasivo in BNCG simmetriche con costi affini. Sotto questi presupposti, è stato dimostrato che il problema è calcolabile in un tempo polinomiale ed è stato sviluppato un algoritmo. Lo scopo del presente lavoro è dunque analizzare in dettaglio l’algoritmo, proponendo un’implementazione nel linguaggio di programmazione Python. Infine, concludiamo il nostro lavoro riportando i risultati sperimentali ottenuti dall’esecuzione di diversi test.