We study a market game with n ≥ 2 players competing over m ≥ 1 divisible resources of different finite capacities. Resources are traded via the proportional sharing mechanism, where players are price-anticipating, meaning that they can influence the prices with their bids. Additionally, each player has an initial endowment of the resources which are sold at market prices. Although the players’ total profit functions may be discontinuous in the bids, we prove existence and uniqueness of pure Nash equilibria of the resulting market game. Then, we study a discrete dynamic arising from repeatedly taking the (unique) equilibrium resource allocation as initial endowments for the next market game. We prove that the total utility value of the dynamic converges to either an optimal allocation value (maximizing total utility over the allocation space) or to a restricted optimal allocation value, where the restriction is defined by fixing some tight resources which are exclusively allocated to a single player. As a corollary, it follows that for strictly concave utility functions, the aggregated allocation vector of the dynamic converges to the unique (possibly restricted) optimal aggregated allocation, and for linear utility functions, we even get convergence of the dynamic to a (possibly restricted) optimal solution in the (non-aggregated) original allocation space.

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K (approximately equal to 1.1974) is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an A-approximate equilibrium for any A < K. Thus A = K is the smallest possible value of A such that the existence of an A-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible A among all A-approximate equilibria of the given instance.

In a seminal paper, Chen, Roughgarden, and Valiant [ SIAM J. Comput., 39 (5) (2010), pp. 1799--1832] studied cost sharing protocols for network design with the objective to implement a low-cost Steiner forest as a Nash equilibrium of an induced cost-sharing game. One of the most intriguing open problems to date is to understand the power of separable cost sharing protocols in order to induce low-cost Steiner forests. In this work, we focus on undirected networks and analyze topological properties of the underlying graph so that an optimal Steiner forest can be implemented as a Nash equilibrium (by some separable cost sharing protocol) independent of the edge costs. We term a graph efficient if the above stated property holds. As our main result, we give a complete characterization of efficient undirected graphs for two-player network design games: an undirected graph is efficient if and only if it does not contain (at least) one out of few forbidden subgraphs. Our characterization implies that several graph classes are efficient: generalized series-parallel graphs, fan and wheel graphs, and graphs with small cycles.