
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 supervertices) with the goal of preserving pairwise
distances as accurately as possible. Formally, given an edgeweighted graph,
the contraction should guarantee that for any two vertices at distance $d$, the
corresponding supervertices 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 realvalued parameters. Specifically, we present polynomialtime
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 (nonoptimal) contractions despite our hardness results.

We consider the problem of maximizing the expected revenue from selling $k$
homogeneous goods to $n$ unitdemand 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 $2k/n$, for regular distributions a
ratio that increases in $n$ and is bounded from above by $1/(1k^k/(e^{k}k!))$,
which is roughly $1/(11/(\sqrt{2\pi k}))$. The lower bounds hold for the
revenue gap between dynamic and static prices. The upper bounds are obtained
via an exante relaxation of the revenue maximization problem, as a consequence
the tight bounds of $2k/n$ in the general case and of $1/(11/(\sqrt{2\pi
k}))$ in the regular case apply also to the potentially larger revenue gap
between the optimal incentivecompatible mechanism and the optimal static
price. Our results imply that for regular distributions the benefit of dynamic
prices vanishes while for nonregular distributions dynamic prices may achieve
up to twice the revenue of static prices.

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.

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 semiconvex 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 oneround 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 oneround walks
that start in an empty starting state are exactly as efficient as
multipleround 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
multipleround 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.

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 demandindependent 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 demandindependent optimum tolls exist if and only if the edge cost
functions are shifted monomials as used by the Bureau of Public Roads.
Moreover, nonnegative demandindependent optimum tolls exist when the network
is a directed acyclic multigraph. Finally, we show that any network with a
single origindestination pair admits demandindependent optimum tolls that,
although not necessarily nonnegative, satisfy a budget constraint.

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.

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 L1norm 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 noncooperative
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 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.

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 NPhard even for identical
jobs. We complement this result with a PTAS for a single segment and
nonidentical jobs. If we allow some pairs of jobs traveling in different
directions to cross a segment concurrently, the problem becomes APXhard 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.

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 (nondecreasing) 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 setfunctions. While all our upper bounds are
attained for the wellknown 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.

We study competitive resource allocation problems in which players distribute
their demands integrally on a set of resources subject to playerspecific
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 integersplittable demands and matroid
congestion games with playerspecific 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 pseudopolynomial algorithm computing a pure
Nash equilibrium.

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 NPcomplete and APXhard, 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.195approximation 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.

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.

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 coNPcomplete. If alpha is part of the input, the
same problem is shown to be coNPcomplete for items with unit densities.
Finally, we show that it is coNPhard to decide, for given alpha, whether a set
of items admits a universal policy with factor alpha, even if all items have
unit densities.

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)/2k^2) /
(1+k^3(k+1)/2k^2) H_k = (1  \Theta(1/k^4)) H_k, where H_k denotes the kth
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 nontrivial 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.

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 nondecreasing 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 noncooperative games captures many elements
of realworld 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 alphaFinite 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.

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.