This paper considers a time-varying game with @math players. Every time slot, players observe their own random events and then take a control action. The events and control actions affect the individual utilities earned by each player. The goal is to maximize a concave function of time average utilities subject to equilibrium constraints. Specifically, participating players are provided access to a common source of randomness from which they can optimally correlate their decisions. The equilibrium constraints incentivize participation by ensuring that players cannot earn more utility if they choose not to participate. This form of equilibrium is similar to the notions of Nash equilibrium and correlated equilibrium, but is simpler to attain. A Lyapunov method is developed that solves the problem in an online fashion by selecting actions based on a set of time-varying weights. The algorithm does not require knowledge of the event probabilities and has polynomial convergence time. A similar method can be used to compute a standard correlated equilibrium, albeit with increased complexity.
In contrast, while the current paper treats a stochastic problem with more limited structure, the resulting solution is simple and grows as @math . Specifically, the algorithm uses a number of that is linear in @math , rather than exponential in @math , resulting in polynomial bounds on convergence time. Furthermore, the number of virtual queues grows only linearly in the size of each set @math . This improves on the original conference version of this paper @cite_12 , which required a number of virtual queues that was exponential in the size of @math . The exponential-to-polynomial improvement is done by equivalently modeling the constraints via a grouping of conditional expectations given an observed random event.
@cite_12
1567604129 2950319503 2742049221 2021033250
In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find the surprising result that the distribution of the convergence rate is a scaling function of a single variable. This scaling variable combines the convergence rate with the problem size (i.e., the number of variables and the number of constraints). We also estimate numerically the distribution of the computation time to an approximate solution, which is the time required to reach a vicinity of the attracting fixed point. We find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times to the approximate solution. We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used. The time complexity is significantly better than both spectral and SDP-based approaches. The main contribution of the algorithm is in the case of unequal sizes in the bipartition (corresponding to odd uniformity in the CSP). Here our algorithm succeeds at a significantly lower density than the spectral approaches, surpassing a barrier based on the spectral norm of a random matrix. Other significant features of the algorithm and analysis include (i) the critical use of power iteration with subsampling, which might be of independent interest; its analysis requires keeping track of multiple norms of an evolving solution (ii) it can be implemented statistically, i.e., with very limited access to the input distribution (iii) the algorithm is extremely simple to implement and runs in linear time, and thus is practical even for very large instances. The multi-armed bandit (MAB) problem features the classical tradeoff between exploration and exploitation. The input specifies several stochastic arms which evolve with each pull, and the goal is to maximize the expected reward after a fixed budget of pulls. The celebrated work of , surveyed in [8], presumes a condition on the arms called the martingale assumption. In [9], A. obtained an LP-based 1 48-approximation for the problem with the martingale assumption removed. We improve the algorithm to a 4 27-approximation, with simpler analysis. Our algorithm also generalizes to the case of MAB superprocesses with (stochastic) multi-period actions. This generalization captures the framework introduced by Guha and Munagala in [11], and yields new results for their budgeted learning problems. Also, we obtain a (1 2 -- e)-approximation for the variant of MAB where preemption (playing an arm, switching to another arm, then coming back to the first arm) is not allowed. This contains the stochastic knapsack problem of Dean, Goemans, and Vondrak in [6] with correlated rewards, where we are given a knapsack of fixed size, and a set of jobs each with a joint distribution for its size and reward. The actual size and reward of a job can only be discovered in real-time as it is being scheduled, and the objective is to maximize expected reward before the knapsack size is exhausted. Our (1 2 -- e)-approximation improves the 1 16 and 1 8 approximations in [9] for correlated stochastic knapsack with cancellation and no cancellation, respectively, providing to our knowledge the first tight algorithm for these problems that matches the integrality gap of 2. We sample probabilities from an exponential-sized dynamic programming solution, whose existence is guaranteed by an LP projection argument. We hope this technique can also be applied to other dynamic programming problems which can be projected down onto a small LP. This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window and capacity constraints. The fleet is homogeneous and is located at a common depot. Each node requires the same type of service. An exact method is introduced based on branch and cut. In the computations, ever increasing lower bounds on the optimal solution are obtained by solving a series of relaxed problems that incorporate newly found valid inequalities. Feasible solutions or upper bounds are obtained with the help of greedy randomized adaptive search procedure (GRASP). A wide variety of cuts is introduced to tighten the linear programming (LP) relaxation of the original mixed-integer program. To find violated cuts, it is necessary to solve a separation problem. A substantial portion of the paper is aimed at describing the heuristics developed for this purpose. A new approach for obtaining feasible solutions from the LP relaxation is also discussed. Numerical results for standard 50- and 100-node benchmark problems are reported.