• ### Distance-preserving graph contractions(1705.04544)

Feb. 13, 2019 cs.DS
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into super-vertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an edge-weighted graph, the contraction should guarantee that for any two vertices at distance $d$, the corresponding super-vertices remain at distance at least $\varphi(d)$ in the contracted graph, where $\varphi$ is a tolerance function bounding the permitted distance distortion. We present a comprehensive picture of the algorithmic complexity of the contraction problem for affine tolerance functions $\varphi(x)=x/\alpha-\beta$, where $\alpha\geq 1$ and $\beta\geq 0$ are arbitrary real-valued parameters. Specifically, we present polynomial-time algorithms for trees as well as hardness and inapproximability results for different graph classes, precisely separating easy and hard cases. Further we analyze the asymptotic behavior of contractions, and find efficient algorithms to compute (non-optimal) contractions despite our hardness results.
• ### Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods(1607.07105)

April 15, 2019 cs.GT
We consider the problem of maximizing the expected revenue from selling $k$ homogeneous goods to $n$ unit-demand buyers who arrive sequentially with independent and identically distributed valuations. In this setting the optimal posted prices are dynamic in the sense that they depend on the remaining numbers of goods and buyers. We investigate how much revenue is lost when a single static price is used instead for all buyers and goods, and prove upper bounds on the ratio between the maximum revenue from dynamic prices and that from static prices. These bounds are tight for all values of $k$ and $n$ and vary depending on a regularity property of the underlying distribution. For general distributions we obtain a ratio of $2-k/n$, for regular distributions a ratio that increases in $n$ and is bounded from above by $1/(1-k^k/(e^{k}k!))$, which is roughly $1/(1-1/(\sqrt{2\pi k}))$. The lower bounds hold for the revenue gap between dynamic and static prices. The upper bounds are obtained via an ex-ante relaxation of the revenue maximization problem, as a consequence the tight bounds of $2-k/n$ in the general case and of $1/(1-1/(\sqrt{2\pi k}))$ in the regular case apply also to the potentially larger revenue gap between the optimal incentive-compatible mechanism and the optimal static price. Our results imply that for regular distributions the benefit of dynamic prices vanishes while for non-regular distributions dynamic prices may achieve up to twice the revenue of static prices.
• ### Tight bounds for undirected graph exploration with pebbles and multiple agents(1805.03476)

May 9, 2018 cs.DS, cs.CC
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 the same bound holds for the number of collaborating agents needed for exploration. For the upper bound, 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 unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies 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 of size $n$ is already $\Omega(\log \log n)$ when we allow each agent to have at most $\mathcal{O}( \log n ^{1-\varepsilon})$ bits of memory for any $\varepsilon>0$. This also implies that a single agent with sublogarithmic memory needs $\Theta(\log \log n)$ pebbles to explore any $n$-vertex graph.
• ### Online Best Reply Algorithms for Resource Allocation Problems(1805.02526)

May 7, 2018 cs.GT, cs.DS
We study online resource allocation problems with a diseconomy of scale. In these problems, there are certain requests, each demanding a set of resources, that arrive in an online manner. The cost of each resource is semi-convex and grows superlinearly in the total load on the resource. An irrevocable allocation decision has to be made directly after the arrival of each request with the goal to minimize the total cost on the resources. We focus on two simple greedy online policies that provide very fast and easy approximation algorithms. The first policy is to minimize the individual cost of the current online request with respect to all previous requests that have been allocated before. The second policy is to minimize the marginal total cost over all requests that have arrived up to this point. In the literature, these type of algorithms is also considered as one-round walks in congestion games starting from the empty state. We consider the weighted and unweighted version of the problem. In the weighted variant, and for cost functions that are polynomials with maximal degree $d$ and positive coefficients, we proof a tight competitive ratio of $\left(\sqrt[d]{2}-1\right)^{-(d+1)}$ for the marginal total cost policy. This interestingly exactly matches the approximation factor for the corresponding \emph{multiple}-round walk algorithm. Our work indicates that one-round walks that start in an empty starting state are exactly as efficient as multiple-round walks. We also show that this does not carry over to the unweighted version of the problem. For unweighted instances, we provide lower bounds for both policies that are significantly larger than the corresponding multiple-round walks. We complement our results with an upper and lower bound on the solution quality of the personal cost policy for weighted and unweighted instances.
• ### Demand-Independent Optimal Tolls(1708.02737)

Feb. 17, 2018 cs.GT
Wardrop equilibria in nonatomic congestion games are in general inefficient as they do not induce an optimal flow that minimizes the total travel time. Network tolls are a prominent and popular way to induce an optimum flow in equilibrium. The classical approach to find such tolls is marginal cost pricing which requires the exact knowledge of the demand on the network. In this paper, we investigate under which conditions demand-independent optimum tolls exist that induce the system optimum flow for any travel demand in the network. We give several characterizations for the existence of such tolls both in terms of the cost structure and the network structure of the game. Specifically we show that demand-independent optimum tolls exist if and only if the edge cost functions are shifted monomials as used by the Bureau of Public Roads. Moreover, non-negative demand-independent optimum tolls exist when the network is a directed acyclic multi-graph. Finally, we show that any network with a single origin-destination pair admits demand-independent optimum tolls that, although not necessarily non-negative, satisfy a budget constraint.
• ### Hiring Secretaries over Time: The Benefit of Concurrent Employment(1604.08125)

May 30, 2017 cs.DS
We consider a stochastic online problem where $n$ applicants arrive over time, one per time step. Upon arrival of each applicant their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable, i.e., we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the applicants' costs multiplied with their respective employment durations. We provide a competitive online algorithm for the case that the applicants' costs are drawn independently from a known distribution. Specifically, the algorithm achieves a competitive ratio of 2.965 for the case of uniform distributions. For this case, we give an analytical lower bound of 2 and a computational lower bound of 2.148. We then adapt our algorithm to stay competitive even in settings with one or more of the following restrictions: (i) at most two applicants can be hired concurrently; (ii) the distribution of the applicants' costs is unknown; (iii) the total number $n$ of time steps is unknown. On the other hand, we show that concurrent employment is a necessary feature of competitive algorithms by proving that no algorithm has a competitive ratio better than $\Omega(\sqrt{n} / \log n)$ if concurrent employment is forbidden.
• ### Sensitivity Analysis for Convex Separable Optimization over Integral Polymatroids(1611.05372)

Dec. 8, 2016 cs.DM, cs.GT, cs.DS, math.OC
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 L1-norm of the difference of the two solutions is at most two times the L1 norm of the difference of the parameters. We apply these sensitivity results to a class of non-cooperative polymatroid games and derive the existence of pure Nash equilibria. We complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any non-polymatroid 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 non-polymatroid region and that does not admit a pure Nash equilibrium.
• ### Scheduling Bidirectional Traffic on a Path(1504.07129)

April 27, 2015 cs.DS
We study the fundamental problem of scheduling bidirectional traffic along a path composed of multiple segments. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a segment, while jobs in opposing directions cannot cross a segment at the same time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by proving that it is NP-hard even for identical jobs. We complement this result with a PTAS for a single segment and non-identical jobs. If we allow some pairs of jobs traveling in different directions to cross a segment concurrently, the problem becomes APX-hard even on a single segment and with identical jobs. We give polynomial algorithms for the setting with restricted compatibilities between jobs on a single and any constant number of segments, respectively.
• ### Sharing Non-Anonymous Costs of Multiple Resources Optimally(1412.4456)

Feb. 4, 2015 cs.GT
In cost sharing games, the existence and efficiency of pure Nash equilibria fundamentally depends on the method that is used to share the resources' costs. We consider a general class of resource allocation problems in which a set of resources is used by a heterogeneous set of selfish users. The cost of a resource is a (non-decreasing) function of the set of its users. Under the assumption that the costs of the resources are shared by uniform cost sharing protocols, i.e., protocols that use only local information of the resource's cost structure and its users to determine the cost shares, we exactly quantify the inefficiency of the resulting pure Nash equilibria. Specifically, we show tight bounds on prices of stability and anarchy for games with only submodular and only supermodular cost functions, respectively, and an asymptotically tight bound for games with arbitrary set-functions. While all our upper bounds are attained for the well-known Shapley cost sharing protocol, our lower bounds hold for arbitrary uniform cost sharing protocols and are even valid for games with anonymous costs, i.e., games in which the cost of each resource only depends on the cardinality of the set of its users.
• ### Resource Competition on Integral Polymatroids(1407.7650)

July 29, 2014 cs.DM, cs.GT, math.OC
We study competitive resource allocation problems in which players distribute their demands integrally on a set of resources subject to player-specific submodular capacity constraints. Each player has to pay for each unit of demand a cost that is a nondecreasing and convex function of the total allocation of that resource. This general model of resource allocation generalizes both singleton congestion games with integer-splittable demands and matroid congestion games with player-specific costs. As our main result, we show that in such general resource allocation problems a pure Nash equilibrium is guaranteed to exist by giving a pseudo-polynomial algorithm computing a pure Nash equilibrium.
• ### Complexity and Approximation of the Continuous Network Design Problem(1307.4258)

Nov. 12, 2013 cs.GT, cs.DS, math.OC
We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. We are 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 cost of the induced Wardrop equilibrium and the investment cost. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and 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 (Mathematical Programming, Vol.~34, 1986). Specifically, we derive a closed form expression of its approximation guarantee for arbitrary sets S of allowed latency functions. Second, we propose a different approximation algorithm and show that it has the same approximation guarantee. As our final -- and arguably most interesting -- result regarding approximation, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we give a closed form expression. For affine latencies, e.g., this algorithm achieves a 1.195-approximation which improves on the 5/4 that has been shown before by Marcotte. We finally discuss the case of hard budget constraints on the capacity investment.
• ### Optimal Impartial Selection(1310.8631)

Oct. 31, 2013 cs.GT
We study the problem of selecting a member of a set of agents based on impartial nominations by agents from that set. The problem was studied previously by Alon et al. and Holzman and Moulin and has important applications in situations where representatives are selected from within a group or where publishing or funding decisions are made based on a process of peer review. Our main result concerns a randomized mechanism that in expectation awards the prize to an agent with at least half the maximum number of nominations. Subject to impartiality, this is best possible.
• ### Packing a Knapsack of Unknown Capacity(1307.2806)

July 10, 2013 cs.DS
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. 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 and try to pack the items in this order, independent of the observations made while packing. 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 coNP-complete. If alpha is part of the input, the same problem is shown to be coNP-complete for items with unit densities. Finally, we show that it is 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.
• ### Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games(1211.2090)

March 22, 2013 cs.GT
In this paper we show that the price of stability of Shapley network design games on undirected graphs with k players is at most (k^3(k+1)/2-k^2) / (1+k^3(k+1)/2-k^2) H_k = (1 - \Theta(1/k^4)) H_k, where H_k denotes the k-th harmonic number. This improves on the known upper bound of H_k, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k=3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bil\`o and Bove (Journal of Interconnection Networks, Volume 12, 2011) is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571.
• ### Congestion Games with Variable Demands(1012.1938)

Dec. 13, 2010 cs.GT
We initiate the study of congestion games with variable demands where the (variable) demand has to be assigned to exactly one subset of resources. The players' incentives to use higher demands are stimulated by non-decreasing and concave utility functions. The payoff for a player is defined as the difference between the utility of the demand and the associated cost on the used resources. Although this class of non-cooperative games captures many elements of real-world applications, it has not been studied in this generality, to our knowledge, in the past. We study the fundamental problem of the existence of pure Nash equilibria (PNE for short) in congestion games with variable demands. We call a set of cost functions C consistent if every congestion game with variable demands and cost functions in C possesses a PNE. We say that C is FIP consistent if every such game possesses the alpha-Finite Improvement Property for every alpha>0. Our main results are structural characterizations of consistency and FIP consistency for twice continuously differentiable cost functions. Specifically, we show 1. C is consistent if and only if C contains either only affine functions or only homogeneously exponential functions (c(x) = a exp(p x)). 2. C is FIP consistent if and only if C contains only affine functions. Our results provide a complete characterization of consistency of cost functions revealing structural differences to congestion games with fixed demands (weighted congestion games), where in the latter even inhomogeneously exponential functions are FIP consistent. Finally, we study consistency and FIP consistency of cost functions in a slightly different class of games, where every player experiences the same cost on a resource (uniform cost model). We give a characterization of consistency and FIP consistency showing that only homogeneously exponential functions are consistent.
• ### Strong Nash Equilibria in Games with the Lexicographical Improvement Property(0909.0347)

Sept. 2, 2009 cs.DM, cs.GT
We introduce a class of finite strategic games with the property that every deviation of a coalition of players that is profitable to each of its members strictly decreases the lexicographical order of a certain function defined on the set of strategy profiles. We call this property the Lexicographical Improvement Property (LIP) and show that it implies the existence of a generalized strong ordinal potential function. We use this characterization to derive existence, efficiency and fairness properties of strong Nash equilibria. We then study a class of games that generalizes congestion games with bottleneck objectives that we call bottleneck congestion games. We show that these games possess the LIP and thus the above mentioned properties. For bottleneck congestion games in networks, we identify cases in which the potential function associated with the LIP leads to polynomial time algorithms computing a strong Nash equilibrium. Finally, we investigate the LIP for infinite games. We show that the LIP does not imply the existence of a generalized strong ordinal potential, thus, the existence of SNE does not follow. Assuming that the function associated with the LIP is continuous, however, we prove existence of SNE. As a consequence, we prove that bottleneck congestion games with infinite strategy spaces and continuous cost functions possess a strong Nash equilibrium.