Sensitivity analysis for convex optimisation over polymatroids with applications to game theory

 

We consider situations in which resources of limited capacity are commonly used by various participants. Prominent examples of such situations can be found in scheduling, where jobs need to be assigned to machines, or in routing, where traffic needs to be sent between certain origin-destination pairs through a network, or in broadcasting, where messages are sent along spanning trees in some underlying undirected graph.

We distinguish between
a) the associated optimisation problem, in which a central authority decides on a feasible assignment with the goal to minimise the resulting total cost of all participants, and
b) its game-theoretic variant in which each participant selfishly decides on an assignment with the goal to minimise his/her individual cost. Within this research project we study the impact of changes in the input parameters, like resource capacity and demand, towards optimal solutions and equilibria. As it turns out, almost everything behaves nicely as long as the cost functions obey certain convexity conditions, and as long as the underlying feasibility regions can be described by submodular functions. In {references below}, we show that under such convexity- and submodularity conditions

  1. small changes in the input parameter allow for fast re-optimization and for new optimal solutions being close to the old ones,
  2. existence of equilibria and convergence of best-response dynamics, and
  3. immunity to anomalies like the Braess paradox.

This project is contributed by Britta Peis.