Abstract. We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions [Formula: see text] as we show that the computation is [Formula: see text]-complete. To prove that the problem is contained in [Formula: see text], we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. Using the properties of this matrix allows us to recompute efficiently the Laplacian after the support of the equilibrium changes by matrix pivot operations. These insights give rise to a path following formulation for computing an equilibrium where states correspond to supports that are feasible for some demands and neighboring supports are feasible for increased or decreased flow demands. A closer investigation of the block Laplacian system further allows us to orient the states giving rise to unique predecessor and successor states, thus putting the problem into [Formula: see text]. For the [Formula: see text]-hardness, we reduce from computing an approximate equilibrium of a bimatrix win-lose game. As a byproduct of our reduction we further show that computing a multiclass Wardrop equilibrium with class-dependent affine cost functions is [Formula: see text]-complete as well. As another byproduct of our [Formula: see text]-completeness proof, we obtain an algorithm that computes a continuum of equilibria parametrized by the players’ flow demand. For player-specific costs, the continuum may involve several increases and decreases of the demand and yields an algorithm that runs in polynomial space. For games with player-independent costs, only demand increases are necessary, yielding an algorithm computing all equilibria as a function of the flow demand that runs in time polynomial in the output.

We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario. A continuum of flow particles arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the flow particles observe the signal issued by the system operator, form an updated belief about the realized scenario, and decide on a link to use. Inflow into a link exceeding the link's capacity builds up in a queue that increases the travel time on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected travel time along all links with positive inflow is equal at every point in time. We provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant $ε>0$. The algorithm solves a Langrangian dual of the signaling problem with the Ellipsoid method whose separation oracle is implemented by a cell decomposition technique. We also provide a multiplicative fully polynomial time approximation scheme (FPTAS) that does not rely on strong duality and, thus, allows to compute also the optimal signals. It uses a different cell decomposition technique together with a piece-wise convex under-estimator of the optimal value function. Finally, we consider the makespan of a Bayesian dynamic equilibrium which is defined as the last point in time when a total given value of flow leaves the system. Using a variational inequality argument, we show that full information revelation is a public signaling scheme that minimizes the makespan.

We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions le,i(x) = ae,ix + be,i showing that it is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix. This leads to a path following formulation where states correspond to supports that are feasible for some demands and neighboring supports are feasible for increased or decreased flow demands. A closer investigation of the block Laplacian system allows to orient the states giving rise to unique predecessor and successor states thus putting the problem into PPAD. For the PPAD-hardness, we reduce from computing an approximate equilibrium of a bimatrix win-lose game. As a byproduct of our reduction we further show that computing a multiclass Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As a byproduct of our PPAD-completeness proof, we obtain an algorithm that computes all equilibria parametrized by the players' flow demands. For player-specific costs, this computation may require several increases and decreases of the demands leading to an algorithm that runs in polynomial space but exponential time. For player-independent costs only demand increases are necessary. If the coefficients be,i are in general position, this yields an algorithm computing all equilibria as a function of the flow demand running in time polynomial in the output.

We develop an algorithm that computes for a given undirected or directed network with flow-dependent piece-wise linear edge cost functions all Wardrop equilibria as a function of the flow demand. Our algorithm is based on Katzenelson's homotopy method for electrical networks. The algorithm uses a bijection between vertex potentials and flow excess vectors that is piecewise linear in the potential space and where each linear segment can be interpreted as an augmenting flow in a residual network. The algorithm iteratively increases the excess of one or more vertex pairs until the bijection reaches a point of non-differentiability. Then, the next linear region is chosen in a simplex-like pivot step and the algorithm proceeds. We first show that this algorithm correctly computes all Wardrop equilibria in undirected single-commodity networks along the chosen path of excess vectors. We then adapt our algorithm to also work for discontinuous cost functions which allows to model directed edges and/or edge capacities. Our algorithm is output-polynomial in non-degenerate instances where the solution curve never hits a point where the cost function of more than one edge becomes non-differentiable. For degenerate instances we still obtain an output-polynomial algorithm computing the linear segments of the bijection by a convex program. The latter technique also allows to handle multiple commodities.