- Equilibria in Multi-Class and Multi-Dimensional Atomic Congestion Games (Max Klimm and Andreas Schütz)
Mathematics of Operations Research, 2022.
@article{KlimmSchuetz2022,
author = {Max Klimm and Andreas Sch{\"u}tz},
doi = {10.1287/moor.2021.1223},
journal = {Mathematics of Operations Research},
title = {Equilibria in Multi-Class and Multi-Dimensional Atomic Congestion Games},
year = {2022},
}
This paper studies the existence of pure Nash equilibria in atomic congestion games with different user classes where the cost of each resource depends on the aggregated demand of each class. A set of cost functions is called consistent for this class if all games with cost functions from the set have a pure Nash equilibrium. We give a complete characterization of consistent sets of cost functions showing that the only consistent sets of cost functions are sets of certain affine functions and sets of certain exponential functions. This characterization is also extended to a larger class of games where each atomic player may control flow that belongs to different classes.
- Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs (Max Klimm and Philipp Warode)
Mathematics of Operations Research, 47(1):812–846, 2022.
@article{KlimmWarode2021,
author = {Max Klimm and Philipp Warode},
doi = {10.1287/moor.2021.1151},
journal = {Mathematics of Operations Research},
number = {1},
pages = {812--846},
title = {Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs},
volume = {47},
year = {2022},
}
We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the initialization, a rank 1 update for each nondegenerate step and the solution of a convex quadratic program for each degenerate step. For nonhomogeneous cost functions, the initialization requires the solution of a convex quadratic program instead. For multi-commodity networks, both the initialization and every step of the algorithm require the solution of a convex program. As each step is mirrored by a breakpoint in the output this yields output-polynomial algorithms in every case.
- Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents (Yann Disser, Jan Hackfeld and Max Klimm)
Journal of the ACM, 66(6):40:1–40:41, 2019.
@article{DisserHackfeldKlimm2019,
author = {Yann Disser and Jan Hackfeld and Max Klimm},
doi = {10.1145/3356883},
journal = {Journal of the ACM},
number = {6},
pages = {40:1--40:41},
tier2 = {1},
title = {Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents},
volume = {66},
year = {2019},
}
We study the problem of deterministically exploring an undirected and initially unknown graph with $n$ vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles $\Theta(\log n)$ bits of memory are necessary and sufficient to explore any graph with at most $n$ vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory $\Theta(\log \log n)$ pebbles are necessary and sufficient for exploration. We further prove that using collaborating agents instead of pebbles does not help as $\Theta(\log \log n)$ agents with constant memory each are necessary and sufficient for exploration. For the upper bounds, we devise an algorithm for a single agent with constant memory that explores any $n$-vertex graph using $\mathcal{O}(\log \log n)$ pebbles, even when $n$ is not known a priori. The algorithm terminates after polynomial time and returns to the starting vertex. We further show that the algorithm can be realized with additional constant-memory agents rather than pebbles, implying that $\mathcal{O}(\log \log n)$ agents with constant memory can explore any $n$-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph with at most n vertices is already $\Omega(\log \log n)$ when we allow each agent to have at most $\mathcal{O}((\log n)^{1-ε})$ bits of memory for any $\epsilon > 0$. Our argument also implies that a single agent with sublogarithmic memory needs $\Theta(\log \log n)$ pebbles to explore any $n$-vertex graph.
- Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids (Tobias Harks, Max Klimm and Britta Peis)
SIAM Journal on Optimization, 28(3):2222–2245, 2018.
@article{HarksKlimmPeis2018,
author = {Tobias Harks and Max Klimm and Britta Peis},
doi = {10.1137/16M1107450},
journal = {SIAM Journal on Optimization},
number = {3},
pages = {2222--2245},
title = {Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids},
volume = {28},
year = {2018},
}
We study the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the cost of each element and the polytope. Under convexity and a regularity assumption on the functional dependency of the cost function with respect to the parameters, we show that reoptimization after a change in parameters can be done by elementary local operations. Applying this result, we derive that starting from any optimal solution, there is a new optimal solution to new parameters such that the $L_1$-norm of the difference of the two solutions is at most two times the $L_1$-norm of the difference of the parameters. We apply these sensitivity results to a class of noncooperative games with a finite set of players where a strategy of a player is to choose a vector in a player-specific integral polymatroid base polytope defined on a common set of elements. The players' private cost functions are regular, convex-separable, and the cost of each element is a nondecreasing function of the own usage of that element and the overall usage of the other players. Under these assumptions, we establish the existence of a pure Nash equilibrium. The existence is proven by an algorithm computing a pure Nash equilibrium that runs in polynomial time whenever the rank of the polymatroid base polytope is polynomially bounded. Both the existence result and the algorithm generalize and unify previous results appearing in the literature. We finally complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any nonpolymatroid region, there is a corresponding optimization problem for which the sensitivity results do not hold. In addition, there is a game where the players' strategies are isomorphic to the nonpolymatroid region and that does not admit a pure Nash equilibrium.
- Complexity and Approximation of the Continuous Network Design Problem (Martin Gairing, Tobias Harks and Max Klimm)
SIAM Journal on Optimization, 27(3):1554–1582, 2017.
@article{GairingHarksKlimm2017,
author = {Martin Gairing and Tobias Harks and Max Klimm},
doi = {10.1137/15M1016461},
journal = {SIAM Journal on Optimization},
number = {3},
pages = {1554--1582},
title = {Complexity and Approximation of the Continuous Network Design Problem},
volume = {27},
year = {2017},
abstrat = {We revisit a classical problem in transportation, known as the (bilevel) continuous network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing costs of the induced Wardrop equilibrium and the investment costs for installing the edge's capacities. While this problem is considered to be challenging in the literature, its complexity status was still unknown. We close this gap, showing that CNDP is strongly $\mathsf{NP}$-hard and $\mathsf{APX}$-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions [P. Marcotte, Math. Prog., 34 (1986), pp. 142--162]. We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. Then, we prove that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, for example, this best-of-two approach achieves an approximation factor of $49/41 \approx 1.195$, which improves on the factor of $5/4$ that has been shown before by Marcotte.},
}
- Packing a Knapsack of Unknown Capacity (Yann Disser, Max Klimm, Nicole Megow and Sebastian Stiller)
SIAM Journal on Discrete Mathematics, 31(3):1477–1497, 2017.
@article{DisserKlimmMegow+2017,
author = {Yann Disser and Max Klimm and Nicole Megow and Sebastian Stiller},
doi = {10.1137/16M1070049},
journal = {SIAM Journal on Discrete Mathematics},
number = {3},
pages = {1477--1497},
title = {Packing a Knapsack of Unknown Capacity},
volume = {31},
year = {2017},
}
We study the problem of packing a knapsack without knowing its capacity. Whenever we attempt to pack an item that does not fit, the item is discarded; if the item fits, we have to include it in the packing. We show that there is always a policy that packs a value within factor 2 of the optimum packing, irrespective of the actual capacity. If all items have unit density, we achieve a factor equal to the golden ratio $\varphi \approx 1.6128$. Both factors are shown to be best possible. In fact, we obtain the above factors using packing policies that are universal in the sense that they fix a particular order of the items in the beginning and try to pack the items in this order, without changing the order later on. We give efficient algorithms computing these policies. On the other hand, we show that, for any $\alpha > 1$, the problem of deciding whether a given universal policy achieves a factor of $\alpha$ is $\mathsf{coNP}$-complete. If $\alpha$ is part of the input, the same problem is shown to be $\mathsf{coNP}$-complete for items with unit densities. Finally, we show that it is $\mathsf{coNP}$-hard to decide, for given $\alpha$, whether a set of items admits a universal policy with factor $\alpha$, even if all items have unit densities.
- Optimal Impartial Selection (Felix A. Fischer and Max Klimm)
SIAM Journal on Computing, 44(5):1263–1285, 2015.
@article{FischerKlimm2015,
author = {Felix A. Fischer and Max Klimm},
doi = {10.1137/140995775},
journal = {SIAM Journal on Computing},
number = {5},
pages = {1263--1285},
title = {Optimal Impartial Selection},
volume = {44},
year = {2015},
}
We study a fundamental problem in social choice theory, the selection of a member of a set of agents based on impartial nominations by agents from that set. Studied previously by Alon et al. [Proceedings of TARK, 2011, pp. 101–110] and by Holzman and Moulin [Econometrica, 81 (2013), pp. 173–196], this problem arises when representatives are selected from within a group or when publishing or funding decisions are made based on a process of peer review. Our main result concerns a randomized mechanism that in expectation selects an agent with at least half the maximum number of nominations. This is best possible subject to impartiality and resolves a conjecture of Alon et al. Further results are given for the case where some agent receives many nominations and the case where each agent casts at least one nomination.
- On the Existence of Pure Nash Equilibria in Weighted Congestion Games (Tobias Harks and Max Klimm)
Mathematics of Operations Research, 37(3):419–436, 2012.
@article{HarksKlimm2012,
author = {Tobias Harks and Max Klimm},
doi = {10.1287/moor.1120.0543},
journal = {Mathematics of Operations Research},
number = {3},
pages = {419--436},
title = {On the Existence of Pure Nash Equilibria in Weighted Congestion Games},
volume = {37},
year = {2012},
}
We study the existence of pure Nash equilibria in weighted congestion games. Let $\mathcal{C}$ denote a set of cost functions. We say that $\mathcal{C}$ is consistent if every weighted congestion game with cost functions in $\mathcal{C}$ possesses a pure Nash equilibrium. Our main contribution is a complete characterization of consistency of continuous cost functions. We prove that a set $\mathcal{C}$ of continuous functions is consistent for two-player games if and only if $\mathcal{C}$ contains only monotonic functions and for all nonconstant functions $c_1, c_2 \in \mathcal{C}$, there are constants $a, b \in \mathbb{R}$ such that $c_1(x) = a c_2(x) + b$ for all $x \in \mathbb{R}_{\geq 0}$. For games with at least three players, we prove that $\mathcal{C}$ is consistent if and only if exactly one of the following cases holds: (a) $\mathcal{C}$ contains only affine functions; (b) $\mathcal{C}$ contains only exponential functions such that $c(x) = a_c e^{\phi x} + b_c$ for some $a_c, b_c, \phi ∈ \mathbb{R}$, where $a_c$ and $b_c$ may depend on $c$, while $\phi$ must be equal for every $c \in \mathcal{C}$. The latter characterization is even valid for three-player games. Finally, we derive several characterizations of consistency of cost functions for games with restricted strategy spaces, such as weighted network congestion games or weighted congestion games with singleton strategies.