Graudate Student in the Department of Computer Science at Cornell University, Ithaca NY. Resume (pdf, ps)
Abstract: We study on-line decision problems where the set of actions that are available to the decision algorithm vary over time. With a few notable exceptions, such problems remained largely unaddressed in the literature, despite their applicability to a large number of practical problems. Departing from previous work on this ``Sleeping Experts'' problem, we compare algorithms against the payoff obtained by the best ordering of the actions, which is a natural benchmark for this type of problem. We study both the full-information (best expert) and partial-information (multi-armed bandit) settings and consider both stochastic and adaptive adversaries. For all settings we give algorithms achieving (almost) information-theoretically optimal regret bounds (up to a constant or a sub-logarithmic factor) with respect to the best-ordering benchmark.
Informal description: In this paper, we give a simultaneous generalization of two problems, the prize-collecting generalized Steiner tree problem and the prize-collecting Steiner tree problem with submodular penalties. We call the resulting problem prize-collecting forest (PCF) problem. In the PCF problem, the algorithm is given (can be given, since the actual problem is more general) a graph with edge weights, a set of k pairs to connect, and a submodular penalty function on this set of k pairs. The objective is to find a subgraph so as to minimize the cost of selected edges plus the value of the penalty function on the set of disconnected pairs. We give a primal-dual approxmiation algorithm with performance guarantee 3, and an LP-rounding algorithm with performance guarantee 2.54.
Abstract: In this paper, we study the prize-collecting version of constrained forest problems with an arbitrary 0-1 connectivity requirement function and a submodular penalty function. Our framework generalizes the Prize Collecting Generalized Steiner Tree framework of Hajiaghayi and Jain (2006) to incorporate more general connectivity requirements and penalty functions. We generalize their primal-dual algorithm using submodular function minimization to give a 3-approximation algorithm, and devise an LP rounding algorithm with a performance guarantee of 2.54.
Informal descption: In a network routing game, it is well known that the quality of the routing suffers if users act selfishly. Even if some users (a small fraction) are not selfish (they are altruistic), the quality might not improve compared to the case when everybody is selfish. We study the question of finding the maximum fraction of users that even after becoming altruistic cannot improve the quality of the equilibrium solution (over the case when everybody is selfish). We give a closed form expression for the threshold fraction mentioned above.
Abstract: Noncooperative network routing games are a natural model of users trying to selfishly route themselves through a network in order to minimize their own delays. It is well known that the solution resulting from this selfish routing (called the Nash equilibrium) can have social cost strictly higher than the cost of the optimum solution. One way to improve the quality of the resulting solution is to price the service in two different ways such that the users paying the premium price get to choose their own path (selfishly), while the bargain price users are routed by the network administrator. A natural problem for the network administrator is to route bargain price users in such a way that after premium price users choose their paths, the overall cost of the solution is minimized.
This problem falls in the range of well studied Stackelberg routing games. We consider the scenario where the network administrator wants the final solution to be (strictly) better than the Nash equilibrium. In other words, she wants enough users to take the bargain price such that the cost of the resulting routing of bargain users and premium users is strictly smaller than the cost of the Nash equilibrium.
We call the minimum fraction of users which must be centrally routed by the network administrator (equivalently, the fraction of bargain price users) to improve the quality of the resulting solution the Stackelberg threshold. We give a closed form expression for the Stackelberg threshold for parallel links networks with linear latency functions in terms of the Nash equilibrium flows and optimum flows. It turns out that the Stackelberg threshold is the minimum of Nash flows on links which have more optimum flow than Nash flow.
Using our approach to characterize the Stackelberg thresholds, we are able to give a simpler proof for an earlier result which finds the minimum fraction of bargain price users required to induce an optimum solution.
Mahatma Gandhi was the kind of person it is more convenient to forget. The principles he stood for and the way in which he asserted them are easier to admire than to follow. While he was alive he was impossible to ignore. Once he had gone he was impossible to imitate. --Shashi Throor
Advice is what we ask for when we already know the answer but wish we didn't. --Erica Jong