-
作者：De Loera, Jesus A.; Klee, Steven
作者单位：University of California System; University of California Davis
摘要：Provan and Billera defined the notion of weak k-decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly k-decomposable simplicial complex Delta is bounded above by a polynomial function of the number of k-faces in Delta and its dimension. For weakly 0-decomposable complexes, this bound is linear in the number of vertices and the dimension. In this paper we exhibit the first examples of non-weakly 0-decomposab...
-
作者：Manshadi, Vahideh H.; Gharan, Shayan Oveis; Saberi, Amin
作者单位：Massachusetts Institute of Technology (MIT); Stanford University
摘要：We consider the online stochastic matching problem proposed by Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 - 1/e. Annual IEEE Sympos. Foundations Comput. Sci. 117-126] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins, and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribut...
-
作者：Feinberg, Eugene A.; Kasyanov, Pavlo O.; Zadoianchuk, Nina V.
作者单位：State University of New York (SUNY) System; Stony Brook University; Ministry of Education & Science of Ukraine; Igor Sikorsky Kyiv Polytechnic Institute; National Academy of Sciences Ukraine; Institute for Applied System Analysis of the National Technical University of Ukraine Igor Sikorsky Kyiv Polytechnic Institute
摘要：This paper presents sufficient conditions for the existence of stationary optimal policies for average cost Markov decision processes with Borel state and action sets and weakly continuous transition probabilities. The one-step cost functions may be unbounded, and the action sets may be noncompact. The main contributions of this paper are: (i) general sufficient conditions for the existence of stationary discount optimal and average cost optimal policies and descriptions of properties of value...
-
作者：Rinott, Yosef; Scarsini, Marco; Yu, Yaming
作者单位：Hebrew University of Jerusalem; Hebrew University of Jerusalem; Luiss Guido Carli University; University of California System; University of California Irvine
摘要：We consider a stochastic version of the well-known Blotto game, called the gladiator game. In this zero-sum allocation game two teams of gladiators engage in a sequence of one-on-one fights in which the probability of winning is a function of the gladiators' strengths. Each team's strategy is the allocation of its total strength among its gladiators. We find the Nash equilibria and the value of this class of games and show how they depend on the total strength of teams and the number of gladia...
-
作者：Nishimura, Hiroki; Ok, Efe A.
作者单位：New York University
摘要：This paper provides a systematic solvability analysis for (generalized) variational inequalities on separable Hilbert lattices. By contrast to a large part of the existing literature, our approach is lattice-theoretic, and is not based on topological fixed point theory. This allows us to establish the solvability of certain types of (generalized) variational inequalities without requiring the involved (set-valued) maps be hemicontinuous or monotonic. Some of our results generalize those obtain...
-
作者：Budhiraja, Amarjit; Liu, Xin
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of Minnesota System; University of Minnesota Twin Cities
摘要：A family of constrained diffusions in a random environment is considered. Constraint set is a polyhedral cone and coefficients of the diffusion are governed by, in addition to the system state, a finite-state Markov process that is independent of the driving noise. Such models arise as limit objects in the heavy traffic analysis of generalized Jackson networks (GJN) with Markov-modulated arrival and processing rates. We give sufficient conditions (which, in particular, includes a requirement o...
-
作者：Wan, Cheng
作者单位：Universite Paris Cite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite
摘要：This work shows that the formation of a finite number of coalitions in a nonatomic network congestion game benefits everyone. At the equilibrium of the composite game played by coalitions and individuals, the average cost to each coalition and the individuals' common cost are all lower than in the corresponding nonatomic game (without coalitions). The individuals' cost is lower than the average cost to any coalition. Similarly, the average cost to a coalition is lower than that to any larger c...
