Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as missed connections and major delays in the arrival. This paper presents an approach to computing optimal contingent plans in multi-modal journey planning. The problem is modeled as a search in an and/or state space. We describe search enhancements used on top of the AO* algorithm. Enhancements include admissible heuristics, multiple types of pruning that preserve the completeness and the optimality, and a hybrid search approach with a deterministic and a nondeterministic search. We demonstrate an NP-hardness result, with the hardness stemming from the dynamically changing distributions of the travel time random variables. We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty.

We address the problem of constructing a graph Fourier transform (GFT) for both undirected and directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, we seek orthonormal bases that yield maximally-spread frequency components in the graph spectral domain to better capture low, medium and high frequencies. To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., frequency on a digraph) a candidate basis vector can attain; and (ii) minimize a smooth spectral dispersion function over the achievable frequency range to obtain the desired spread GFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are efficiently tackled via a provably convergent, feasible optimization method on the Stiefel manifold. We illustrate the effectiveness of the novel GFT construction algorithm through numerical tests on synthetic and real-world graphs.

We seek to understand when heterogeneity in agent preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many multi-agent settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that agents trade-off two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions are: 1) A participant-oriented measure of cost in the presence of agent diversity; 2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands.

When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. The previous algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics for speed.

Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance. Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands.

We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs to capture a penalty for early arrival. It is known that as non-linearity arises, the problem can become NP-hard and little is known on computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efficiently computed under some natural constraints. In particular, we provide a fully polynomial approximation scheme under hop constraints. Our approximation algorithm can extend to run in pseudo-polynomial time under an additional linear constraint that sometimes is useful. As a by-product, we show that our algorithm can be applied to the problem of finding a path that is most likely to be on time for a given deadline.

Mitigating risk in decision-making has been a long-standing problem. Due to the mathematical challenge of its nonlinear nature, especially in adaptive decision-making problems, finding optimal policies is typically intractable. With a focus on efficient algorithms, we ask how well we can approximate the optimal policies for the difficult case of general utility models of risk. Little is known about efficient algorithms beyond the very special cases of linear (risk-neutral) and exponential utilities since general utilities are not separable and preclude the use of traditional dynamic programming techniques. In this paper, we consider general utility functions and investigate efficient computation of approximately optimal routing policies, where the goal is to maximize the expected utility of arriving at a destination around a given deadline. We present an adaptive discretization variant of successive approximation which gives an $\error$-optimal policy in polynomial time. The main insight is to perform discretization at the utility level space, which results in a nonuniform discretization of the domain, and applies for any monotone utility function.

Considering congestion games with uncertain delays, we compute the inefficiency introduced in network routing by risk-averse agents. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time-scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the price of risk aversion (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk-neutral. For networks with general delay functions and a single source-sink pair, we show that the PRA depends linearly on the agents' risk tolerance and on the degree of variability present in the network. In contrast to the price of anarchy, in general the PRA increases when the network gets larger but it does not depend on the shape of the delay functions. To get this result we rely on a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For series-parallel (SP) graphs, the PRA becomes independent of the network topology and its size. As a result of independent interest, we prove that for SP networks with deterministic delays, Wardrop equilibria maximize the shortest-path objective among all feasible flows.

The inefficiency of the Wardrop equilibrium of nonatomic routing games can be eliminated by placing tolls on the edges of a network so that the socially optimal flow is induced as an equilibrium flow. A solution where the minimum number of edges are tolled may be preferable over others due to its ease of implementation in real networks. In this paper we consider the minimum tollbooth ( $${MINTB}$$ ) problem, which seeks social optimum inducing tolls with minimum support. We prove for single commodity networks with linear latencies that the problem is NP-hard to approximate within a factor of 1.1377 through a reduction from the minimum vertex cover problem. Insights from network design motivate us to formulate a new variation of the problem where, in addition to placing tolls, it is allowed to remove unused edges by the social optimum. We prove that this new problem remains NP-hard even for single commodity networks with linear latencies, using a reduction from the partition problem. On the positive side, we give the first exact polynomial solution to the $${MINTB}$$ problem in an important class of graphs—series-parallel graphs. Our algorithm solves $${MINTB}$$ by first tabulating the candidate solutions for subgraphs of the series-parallel network and then combining them optimally.

In algorithmic game theory, the price of anarchy framework studies efficiency loss in decentralized environments. In optimization and decision theory, the price of robustness framework explores the tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. We establish a connection between the two that provides a novel analytic framework for proving tight performance guarantees for distributed systems in uncertain environments. We present applications of this framework to novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude towards uncertainty has a critical effect on system performance and should therefore be a subject of close and systematic investigation.

Disaster Response Networks (DRNs) are disruption tolerant networks designed to deliver mission critical data during disaster recovery, while operating with limited energy resources. While Quality of Service is desired, it is difficult to offer guarantees because of the unpredictable nature of mobility in such DRNs. The variance of the packet delivery delay (PDV, more commonly called jitter), an important QoS metric which in DRNs is measured in tens of minutes instead of milliseconds, has not been sufficiently addressed in recent research. Smartphones used by first responders generate large data workloads, causing the PDV to further degrade. Reducing packet replication at these workloads will lower energy consumption, but reduces the packet delivery ratio (PDR). The complex interplay between these QoS metrics remains unclear, making their control difficult. We present Raven, a routing protocol for DRNs that offers control over QoS, especially the PDV. Stochastic graph theory which deals with probabilistic edge weights having a mean and variance is used to model mobility in the disaster area. A stochastic version of the K-Shortest Paths algorithm routes data over multiple paths simultaneously. Raven has been thoroughly evaluated in simulation using realistic settings. The dynamics between performance and energy consumption is analyzed mathematically, and its control is demonstrated.

In this paper, we resolve, the smoothed and approximative complexity of low-rank quasi-concave minimization, providing both upper and lower bounds. As an upper bound, we provide the first smoothed analysis of quasi-concave, minimization. The analysis is based on a smoothed bound for the number of extreme points of the projection of the feasible polytope onto a k-dimensional subspace. where k is the rank (informally, the dimension of nonconvexity)ofthe quasi-concave function. Our smoothed bound is polynomial in the original dimension of the problem n and the perturbation size p. and it is exponential in the rank of the function k. From this, we obtain the first randomized fully polynomial-time approximation scheme for low-rank quasi-concave minimization under broad conditions. In contrast with this, we prove log n-hardness of approximation for general quasi-concave minimization. This shows that our smoothed bound is essentially tight, in that no polynomial smoothed bound is possible for quasi-concave functions of general rank k. The tools that we introduce for the smoothed analysis may be of independent interest. All previous smoothed analyses of polytopes analyzed projections onto two-dimensional subspaces and studied them using trigonometry to examine the angles between vectors and 2-planes in Ropf". In this paper, we provide what is, to our knowledge, the first smoothed analysis of the projection of polytopes onto higher-dimensional subspaces. To do this, we replace the trigonometry with tools from random matrix theory and differential geometry on the Grassmannian. Our hardness reduction is based on entirely different proofs that may also be of independent interest; we show that the stochastic 2-stage minimum spanning tree problem has a supermodular objective and that supermodular minimization is hard to approximate.

We consider a permutation betting scenario, where people wager on the final ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly matching up wagers or, equivalently, finding arbitrage opportunities among the proposed wagers. Requiring bidders to explicitly list the orderings that they'd like to bet on is both unnatural and intractable, because the number of orderings is n! and the number of subsets of orderings is 2n!. We propose two expressive betting languages that seem natural for bidders, and examine the computational complexity of the auctioneer problem in each case. Subset betting allows traders to bet either that a candidate will end up ranked among some subset of positions in the final ordering, for example, "horse A will finish in positions 4, 9, or 13-21", or that a position will be taken by some subset of candidates, for example "horse A, B, or D will finish in position 2". For subset betting, we show that the auctioneer problem can be solved in polynomial time if orders are divisible. Pair betting allows traders to bet on whether one candidate will end up ranked higher than another candidate, for example "horse A will beat horse B". We prove that the auctioneer problem becomes NP-hard for pair betting. We identify a sufficient condition for the existence of a pair betting match that can be verified in polynomial time. We also show that a natural greedy algorithm gives a poor approximation for indivisible orders.

Information markets, which are designed specifically to aggregate traders' information, are becoming increasingly popular as a means for predicting future events. Recent research in information markets has resulted in two new designs, market scoring rules and dynamic parimutuel markets. We develop an analytic method to guide the design and strategic analysis of information markets. Our central contribution is a new abstract betting game, the projection game, that serves as a useful model for information markets. We demonstrate that this game can serve as a strategic model of dynamic parimutuel markets, and also captures the essence of the strategies in market scoring rules. The projection game is tractable to analyze, and has an attractive geometric visualization that makes the strategic moves and interactions more transparent. We use it to prove several strategic properties about the dynamic parimutuel market. We also prove that a special form of the projection game is strategically equivalent to the spherical scoring rule, and it is strategically similar to other scoring rules. Finally, we illustrate two applications of the model to analysis of complex strategic scenarios: we analyze the precision of a market in which traders have inertia, and a market in which a trader can profit by manipulating another trader's beliefs.

No abstract available.

We study first-price auction mechanisms for auctioning flow between given nodes in a graph.We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all strong ffl-Nash equilibria of a first-price auction for this problem, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves (VCG) mechanism. We then present a randomized version of the first-price auction, for which the equilibrium condition can be relaxed to ffl-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known to the edges. For this model, we show that a simple ex ante first-price auction may not have any ffl-Nash equilibria. We then present a modified auction mechanism with 2-parameter bids, and show that it has an