Spanning tree modulus and secure broadcast games

Abstract

The theory of p-modulus provides a general framework for quantifying the richness of a family of objects on a graph. When applied to the family of spanning trees, p-modulus has an interesting probabilistic interpretation. In particular, the 2-modulus problem in this case has been shown to be equivalent to the problem of finding a probability distribution on spanning trees that utilizes the edges of the graph as fairly as possible. In this dissertation, we use the above fact to produce a game-theoretic interpretation of modulus by employing modulus to solve a secure broadcast game between a network broadcaster and an eavesdropper in a network.

First, we review the concept of modulus in the continuum, and the discrete modulus in networks in general. Then, a set of necessary and sufficient conditions for a mixed-strategy solution to the secure broadcast game is proven. An explicit connection between the 2-modulus problem (formulated as a minimum expected overlap problem) on the spanning trees of a graph and the solution to the game is provided. Moreover, we show a comparison between the solution method presented in this dissertation and other methods for solving the game from different literature.

This dissertation also provides an algorithm for computing the spanning tree modulus by recursively solving the secure broadcast game on subgraphs. The theories of matroids and network flows are used with modulus theory to implement this algorithm. We present a polynomial time worst-case upper bound for the time complexity along with some numerical computations.

In addition, we consider maximizing 2-modulus for families of objects on a graph. This idea can open new directions for spanning tree modulus for secure broadcast games with weight constraints, which we explain briefly and will investigate more as future research.