-
作者：Fishburn, PC; Pekec, A; Reeds, JA
作者单位：AT&T; Duke University
摘要：This paper investigates algebraic and combinatorial properties of the set of linear orders on the algebra of subsets of a finite set that are representable by positive measures. It is motivated by topics in decision theory and the theory of measurement, where an understanding of such properties can facilitate the design of strategies to elicit comparisons between subsets that, for example, determine an individual's preference order over subsets of objects or an individual's qualitative probabi...
-
作者：Wright, SJ; Orban, D
作者单位：University of Wisconsin System; University of Wisconsin Madison; Northwestern University
摘要：We examine the sequence of local minimizers of the log-barrier function for a nonlinear program near a solution at which second-order sufficient conditions and the Mangasarian-Fromovitz constraint qualification are satisfied, but the active constraint gradients are not necessarily linearly independent, When a strict complementarity condition is satisfied, we show uniqueness of the local minimizer of the barrier function in the vicinity of the nonlinear program solution, and we obtain a semiexp...
-
作者：Granot, D; Kuipers, J; Chopra, S
作者单位：University of British Columbia; Maastricht University; Northwestern University; Northwestern University
摘要：We analyze a cost allocation problem which could naturally arise from a situation wherein a tree network T = (N boolean OR {0}, E), serving heterogeneous customers, has to be constructed. The customers, located at N, require some service from a central supplier, located at vertex 0. The customers have heterogeneous preferences for the level or quality of service received from the central supplier. We formulate the above cost allocation problem as a cooperative game, referred to as an extended ...
-
作者：Bernstein, DS; Givan, R; Immerman, N; Zilberstein, S
作者单位：University of Massachusetts System; University of Massachusetts Amherst; Purdue University System; Purdue University
摘要：We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference b...
-
作者：Dan, H; Yamashita, N; Fukushima, M
作者单位：Kyoto University
摘要：The purpose of this paper,is to present an algorithm for solving the monotone nonlinear complementarity problem (NCP) that enjoys superlinear convergence in a genuine sense without the uniqueness and nondegeneracy conditions. Recently, Yamashita and Fukushima (2001) proposed a method based on the proximal point algorithm (PPA) for monotone NCP. The method has the favorable property that a generated sequence converges to the solution set of NCP superlinearly. However, when a generated sequence ...
-
作者：De Farias, IR; Johnson, EL; Nemhauser, GL
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and the model is Lightened by introducing strong inequalities valid for the resulting MIP. We use an alternative approach, in which we keep in the model only the continuous variables, and we tighten the model by introducing inequalities that define facets of the convex hull of the set of feasible solu...
-
作者：Borkar, VS
作者单位：Tata Institute of Fundamental Research (TIFR)
摘要：We propose for risk-sensitive control of finite Markov chains a counterpart of the popular Q-learning algorithm for classical Markov decision processes. The algorithm is shown to converge with probability one to the desired solution. The proof technique is an adaptation of the o.d.e. approach for the analysis of stochastic approximation algorithms, with most of die work involved used for the analysis of the specific o.d.e.s. that arise.
