-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：Technion Israel Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first o...
-
作者：Chang, Cheng-Shang; Liao, Wanjiun; Lien, Ching-Min
作者单位：National Tsing Hua University; National Taiwan University
摘要：One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works in the literature is for the two users to select their own channel hopping sequences and then rendezvous when they both hop to a common unblocked channel at the same time. In this paper, we focus on the fundamental limits of the multichannel re...
-
作者：Saban, Daniela; Sethuraman, Jay
作者单位：Columbia University; Columbia University
摘要：The random priority (RP) mechanism is a popular way to allocate n objects to n agents with strict ordinal preferences over the objects. In the RP mechanism, an ordering over the agents is selected uniformly at random; the first agent is then allocated his most-preferred object, the second agent is allocated his most-preferred object among the remaining ones, and so on. The outcome of the mechanism is a bi-stochastic matrix in which entry (i, a) represents the probability that agent i is given ...
-
作者：Kiseleva, Tatiana; Wagener, Florian
作者单位：Vrije Universiteit Amsterdam; University of Amsterdam
摘要：We study the structure of the solution set of a class of infinite-horizon dynamic programming problems with one-dimensional state spaces, as well as their bifurcations, as problem parameters are varied. The solutions are represented as the integral curves of a multivalued optimal vector field on state space. Generically, there are three types of integral curves: stable points, open intervals that are forward asymptotic to a stable point and backward asymptotic to an unstable point, and half-op...
-
作者：Mordukhovich, B. S.; Nghia, T. T. A.; Rockafellar, R. T.
作者单位：Wayne State University; King Fahd University of Petroleum & Minerals; Oakland University; University of Washington; University of Washington Seattle
摘要：The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems, including those of conic and specifically semidefinite programming. Developing a new technique of variational analysis and generalized differentiation, we derive second-order characterizations of full stability, in both Lipschitzian and Holderian settings, and establish their relationships with the conven...
-
作者：Jevtic, Petar; Steele, J. Michael
作者单位：McMaster University; University of Pennsylvania
摘要：A caterpillar network (or graph) G is a tree with the property that removal of the leaf edges of G leaves one with a path. Here we focus on minimum weight spanning caterpillars where the vertices are points in the Euclidean plane and the costs of the path edges and the leaf edges are multiples of their corresponding Euclidean lengths. The flexibility in choosing the weight for path edges versus the weight for leaf edges gives some useful flexibility in modeling. In particular, one can accommod...
-
作者：Murota, Kazuo; Yokoi, Yu
作者单位：University of Tokyo
摘要：The stable allocation model is a many-to-many matching model in which each pair's partnership is represented by a nonnegative integer. This paper establishes a link between two different formulations of this model: the choice function model studied thoroughly by Alkan and Gale and the discrete-concave (M-concave) value function model introduced by Eguchi, Fujishige, and Tamura. We show that the choice functions induced from M-concave value functions are endowed with consistency, persistence, a...
-
作者：Shioura, Akiyoshi
作者单位：Tohoku University
摘要：We consider the maximization of a gross substitutes utility function under budget constraints. This problem naturally arises in applications such as exchange economies in mathematical economics and combinatorial auctions in (algorithmic) game theory. We show that this problem admits a polynomial-time approximation scheme (PTAS). More generally, we present a PTAS for maximizing a discrete concave function called an M-right angle-concave function under budget constraints. Our PTAS is based on ro...
-
作者：Coucheney, Pierre; Gaujal, Bruno; Mertikopoulos, Panayotis
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：Starting from a heuristic learning scheme for strategic N-person games, we derive a new class of continuous-time learning dynamics consisting of a replicator-like drift adjusted by a penalty term that renders the boundary of the game's strategy space repelling. These penalty-regulated dynamics are equivalent to players keeping an exponentially discounted aggregate of their ongoing payoffs and then using a smooth best response to pick an action based on these performance scores. Owing to this i...
-
作者：He, Xue Dong; Jin, Hanqing; Zhou, Xun Yu
作者单位：Columbia University; University of Oxford; University of Oxford; University of Oxford
摘要：We seek to characterize the trading behavior of an agent, in the context of a continuous-time portfolio choice model, if she measures the risk by a so called weighted value-at-risk (VaR), which is a generalization of both VaR and conditional VaR. We show that when bankruptcy is allowed the agent displays extreme risk-taking behaviors, unless the downside risk is significantly penalized, in which case an asymptotically optimal strategy is to invest a very small amount of money in an extremely r...
