- Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost–Benefit Analysis (Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke and Max Klimm)
PNAS Nexus, 2(2), 2023.
@article{StahlbergSagnolDucke+2022,
author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
title = {Spatiotemporal Reconstruction of Ancient Road Networks Through Sequential Cost--Benefit Analysis},
journal = {PNAS Nexus},
year = {2023},
volume = {2},
number = {2},
accepted = {20.12.2022},
doi = {10.1093/pnasnexus/pgac313},
}
The construction of ancient road networks spanned generations and exhibits temporal path dependence that is not fully captured by established network formation models that are used to support archaeological reasoning. We introduce an evolutionary model that captures explicitly the sequential nature of road network formation: A central feature is that connections are added successively and according to an optimal cost–benefit trade-off with respect to existing connections. In this model, the network topology emerges rapidly from early decisions, a trait that makes it possible to identify plausible road construction orders in practice. Based on this observation we develop a method to compress the search space of path-dependent optimization problems. We use this method to show that the model's assumptions on ancient decision making allow the reconstruction of partially known road networks from the Roman era in good detail and from sparse archaeological evidence. In particular, we identify missing links in the major road network of ancient Sardinia that are in good agreement with expert predictions.
- Packing Under Convex Quadratic Constraints (Max Klimm, Marc E. Pfetsch, Rico Raber and Martin Skutella)
Mathematical Programming, 192:361–386, 2022.
@article{KlimmPfetschRaber+2022b,
author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},
doi = {10.1007/s10107-021-01675-6},
journal = {Mathematical Programming},
pages = {361--386},
title = {Packing Under Convex Quadratic Constraints},
volume = {192},
year = {2022},
}
We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $\mathsf{APX}$-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.
- Equilibria in Multi-Class and Multi-Dimensional Atomic Congestion Games (Max Klimm and Andreas Schütz)
Mathematics of Operations Research, 47:2547–3399, 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},
volume = {47},
issue = {4},
pages = {2547--3399},
}
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.
- Generalized Permutahedra and Optimal Auctions (Michael Joswig, Max Klimm and Sylvain Spitz)
SIAM Journal on Applied Algebra and Geometry, 6(1):711-739, 2022.
@article{JoswigKlimmSpitz2022,
author = {Michael Joswig and Max Klimm and Sylvain Spitz},
title = {Generalized Permutahedra and Optimal Auctions},
journal = {SIAM Journal on Applied Algebra and Geometry},
year = {2022},
volume = {6},
number = {1},
pages = {711-739},
accepted = {30.09.2022},
doi = {10.1137/21M1441286},
}
We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.
- 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},
}
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.
- 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.
