-
作者：Buchbinder, Niv; Chen, Shahar; Naor, Joseph (Seffi); Shamir, Ohad
作者单位：Tel Aviv University; Technion Israel Institute of Technology; Weizmann Institute of Science
摘要：Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learni...
-
作者：Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：We study disjunctive conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone, or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that, under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient to describe the convex hull. We focus on the properties of K-minimal inequalities by establishing algebraic nece...
-
作者：Feinberg, Eugene A.; Kasyanov, Pavlo O.; Zgurovsky, Michael Z.
作者单位：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; Ministry of Education & Science of Ukraine; Igor Sikorsky Kyiv Polytechnic Institute
摘要：This paper describes sufficient conditions for the existence of optimal policies for partially observable Markov decision processes (POMDPs) with Borel state, observation, and action sets, when the goal is to minimize the expected total costs over finite or infinite horizons. For infinite-horizon problems, one-step costs are either discounted or assumed to be nonnegative. Action sets may be noncompact and one-step cost functions may be unbounded. The introduced conditions are also sufficient f...
-
作者：Matsui, Tomomi; Ano, Katsunori
作者单位：Institute of Science Tokyo; Tokyo Institute of Technology; Shibaura Institute of Technology
摘要：This paper addresses Bruss' odds problem with multiple stopping chances. A decision maker sequentially observes a sequence of independent 0/1 (failure/success) random variables to correctly predict the last success with multiple stopping chances. First, we give a nontrivial lower bound of the probability of win (obtaining the last success) for the problem with m-stoppings. Next, we show that the asymptotic value for each classical secretary problem with multiple stoppings attains our lower bou...
-
作者：Pflug, Georg Ch.; Pichler, Alois
作者单位：University of Vienna; International Institute for Applied Systems Analysis (IIASA); Norwegian University of Science & Technology (NTNU)
摘要：In management and planning it is commonplace for additional information to become available gradually over time. It is well known that most risk measures (risk functionals) are time inconsistent in the following sense: it may happen that at a given time period, some loss distribution appears to be less risky than another one, but looking at the conditional distribution at a later time, the opposite relation holds almost surely. The extended conditional risk functionals introduced in this paper...
-
作者：Jaskiewicz, Anna; Nowak, Andrzej S.
作者单位：Wroclaw University of Science & Technology; University of Zielona Gora
摘要：In this paper, we study discounted stochastic games with Borel state and compact action spaces depending on the state variable. The primitives of our model satisfy standard continuity and measurability conditions. The transition probability is a convex combination of finitely many probability measures depending on states, and it is dominated by some finite measure on the state space. The coefficients of the combination depend on both states and action profiles. This class of models contains st...
-
作者：Cai, Yang; Candogan, Ozan; Daskalakis, Constantinos; Papadimitriou, Christos
作者单位：McGill University; University of Chicago; Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley
摘要：We show that in zero-sum polymatrix games, a multiplayer generalization of two-person zero-sum games, Nash equilibria can be found efficiently with linear programming. We also show that the set of coarse correlated equilibria collapses to the set of Nash equilibria. In contrast, other important properties of two-person zero-sum games are not preserved: Nash equilibrium payoffs need not be unique, and Nash equilibrium strategies need not be exchangeable or max-min.
-
作者：Fleiner, Tamas; Kamiyama, Naoyuki
作者单位：Budapest University of Technology & Economics; Eotvos Lorand University; Kyushu University
摘要：In 2010, Huang introduced the laminar classified stable matching problem (LCSM for short) that is motivated by academic hiring. This problem is an extension of the well-known hospitals/residents problem in which a hospital has laminar classes of residents and it sets lower and upper bounds on the number of residents that it can hire in each class. Against the intuition that variations of the stable matching problem with lower quotas are difficult in general, Huang proved that LCSM can be solve...
-
作者：Tran, Ngoc Mai
作者单位：University of Texas System; University of Texas Austin
摘要：In the context of pairwise comparison ranking, we show that HodgeRank (row geometric mean), is the limit of Perron Rank (ranking with principal eigenvector) as a certain parameter k goes to 0. This result provides a novel mathematical link between two important pairwise ranking methods. It complements the known result that as k approaches infinity, Perron Rank converges to Tropical Rank. Thus, these three pairwise ranking methods belong to the same parametrized family. Our proof technique is u...
-
作者：Charpentier, Arthur; Galichon, Alfred; Henry, Marc
作者单位：University of Quebec; University of Quebec Montreal; Universite de Rennes; Institut d'Etudes Politiques Paris (Sciences Po); New York University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：We revisit Machina's local utility as a tool to analyze attitudes to multivariate risks. We show that for nonexpected utility maximizers choosing between multivariate prospects, aversion to multivariate mean preserving increases in risk is equivalent to the concavity of the local utility functions, thereby generalizing Machina's result [Machina M (1982) Expected utility analysis without the independence axiom. Econometrica 50:277-323]. To analyze comparative risk attitudes within the multivari...
