Author name cluster

Evdokia Nikolova

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

TCS Journal 2024 Journal Article

Eliciting truthful reports with partial signals in repeated games

Yutong Wu
Ali Khodabakhsh
Bo Li
Evdokia Nikolova
Emmanouil Pountourakis

We consider a repeated game where a player self-reports her usage of a service and is charged a payment accordingly by a center. The center observes a partial signal, representing part of the player's true consumption, which is generated from a publicly known distribution. The player can report any value that does not contradict the signal and the center issues a payment based on the reported information. Such problems find application in net metering billing in the electricity market, where a customer's actual consumption of the electricity network is masked and complete verification is impractical. When the underlying true value is relatively constant, we propose a penalty mechanism that elicits truthful self-reports. Namely, besides charging the player the reported value, the mechanism charges a penalty proportional to her inconsistent reports. We show how fear of uncertainty in the future incentivizes the player to be truthful today. For Bernoulli distributions, we give the complete analysis and optimal strategies given any penalty. Since complete truthfulness is not possible for continuous distributions, we give approximate truthful results by a reduction from Bernoulli distributions. We also extend our mechanism to a multi-player cost-sharing setting and give equilibrium results.

Details DOI

JAIR Journal 2019 Journal Article

Computing Multi-Modal Journey Plans under Uncertainty

Adi Botea
Akihiro Kishimoto
Evdokia Nikolova
Stefano Braghin
Michele Berlingerio
Elizabeth Daly

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.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing?

Richard Cole
Thanasis Lianeas
Evdokia Nikolova

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.

PDF Details

AAAI Conference 2016 Conference Paper

Approximation Algorithms for Route Planning with Nonlinear Objectives

Ger Yang
Evdokia Nikolova

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 nonlinearity arises, the problem becomes NP-hard and little is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efﬁciently 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 a more general linear constraint that sometimes is useful. As a by-product, we show that our algorithm can be applied to the problem of ﬁnding a path that is most likely to be on time for a given deadline.

PDF Details

IJCAI Conference 2016 Conference Paper

Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing

Thanasis Lianeas
Evdokia Nikolova
Nicolas E. Stier-Moses

We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on arc flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers, by introducing jitter in transmission delays which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. The price of risk aversion (PRA) has been defined as the worst-case ratio of the cost of an equilibrium with risk-averse players who seek risk-minimizing paths, and that of an equilibrium with risk-neutral users who minimize the mean travel time of a path [Nikolova and Stier-Moses, 2015]. This inefficiency metric captures the degradation of system performance caused by variability and risk aversion. In this paper, we provide the first lower bounds on the PRA. First, we show a family of structural lower bounds, which grow linearly with the size of the graph and players' risk-aversion. They are tight for graph sizes that are powers of two. We also provide asymptotically tight functional bounds that depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we provide a closed-form formula of the PRA for a family of graphs that generalize series-parallel graphs and the Braess graph. This formula also applies to the mean-standard deviation user objective a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs.

PDF Details

AAAI Conference 2015 Conference Paper

Approximately Optimal Risk-Averse Routing Policies via Adaptive Discretization

Darrell Hoy
Evdokia Nikolova

Mitigating risk in decision-making has been a longstanding problem. Due to the mathematical challenge of its nonlinear nature, especially in adaptive decisionmaking 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 -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.

PDF Details

ICAPS Conference 2013 Conference Paper

Multi-Modal Journey Planning in the Presence of Uncertainty

Adi Botea
Evdokia Nikolova
Michele Berlingerio

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 major delays in the arrival. We model the scenario as a non-deterministic planning problem with continuous time and time-dependent probabilities of non-deterministic effects. We present new hardness results. We introduce a heuristic search planner, based on Weighted AO* (WAO*). The planner includes search enhancements such as sound pruning, based on state dominance, and an admissible heuristic. Focusing on plans that are robust to uncertainty, we demonstrate our ideas on data compiled from real historical data from Dublin, Ireland. Repeated calls to WAO*, with decreasing weights, have a good any-time performance. Our search enhancements play an important role in the planner's performance.

Details

IJCAI Conference 2013 Conference Paper

Sample Complexity of Risk-Averse Bandit-Arm Selection

Jia Yuan Yu
Evdokia Nikolova

We consider stochastic multiarmed bandit problems where each arm generates i. i. d. rewards according to an unknown distribution. Whereas classical bandit solutions only maximize the expected reward, we consider the problem of minimizing risk using notions such as the value-at-risk, the average value-at-risk, and the mean-variance risk. We present algorithms to minimize the risk over a single and multiple time periods, along with PAC accuracy guarantees given a ﬁnite number of reward samples. In the single-period case, we show that ﬁnding the arm with least risk requires not many more samples than the arm with highest expected reward. Although minimizing the multiperiod value-at-risk is known to be hard, we present an algorithm with comparable sample complexity under additional assumptions.

PDF Details DOI

AAAI Conference 2008 Conference Paper

Route Planning under Uncertainty: The Canadian Traveller Problem

Evdokia Nikolova

The Canadian Traveller problem is a stochastic shortest paths problem in which one learns the cost of an edge only when arriving at one of its endpoints. The goal is to find an optimal policy that minimizes the expected cost of travel. The problem is known to be #P-hard. Since there has been no significant progress on approximation algorithms for several decades, we have chosen to seek out special cases for which exact solutions exist, in the hope of demonstrating techniques that could lead to further progress. Applying a mix of techniques from algorithm analysis and the theory of Markov Decision Processes, we provide efficient exact algorithms for directed acyclic graphs and (undirected) graphs of disjoint paths from source to destination with random two-valued edge costs. We also give worst-case performance analysis and experimental data for two natural heuristics.

PDF Details

FOCS Conference 2007 Conference Paper

On the Hardness and Smoothed Complexity of Quasi-Concave Minimization

Jonathan A. Kelner
Evdokia Nikolova

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.

Details

ICAPS Conference 2006 Conference Paper

Optimal Route Planning under Uncertainty

Evdokia Nikolova
Matthew Brand
David R. Karger

We present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for defining the optimal route: for a given source S and destination T in the graph, we seek an ST-path of lowest expected cost where the edge travel times are random variables and the cost is a nonlinear function of total travel time. Although this is a natural model for route-planning on real-world road networks, results are sparse due to the analytic difficulty of finding closed form expressions for the expected cost (Fan, Kalaba & Moore), as well as the computational/combinatorial difficulty of efficiently finding an optimal path which minimizes the expected cost. We identify a family of appropriate cost models and travel time distributions that are closed under convolution and physically valid. We obtain hardness results for routing problems with a given start time and cost functions with a global minimum, in a variety of deterministic and stochastic settings. In general the global cost is not separable into edge costs, precluding classic shortest-path approaches. However, using partial minimization techniques, we exhibit an efficient solution via dynamic programming with low polynomial complexity.

Details