bluuebunny/crossref_metadata_2025 huggingface dataset:
Monotonically Improving Limit-Optimal Strategies in Finite-State Decision Processes
Authors: Hill Theodore P. , Van der Wal Jan
Published: October 2008

In every finite-state leavable gambling problem and in every finite-state Markov decision process with discounted, negative or positive reward criteria there exists a Markov strategy which is monotonically improving and optimal in the limit along every history. An example is given to show that for the positive and gambling cases such strategies cannot be constructed by simply switching to a “better” action or gamble at each successive return to a state.
On the Maximum Weight Clique Problem
Authors: Balas Egon , Chvátal Vašek , Nešetřil Jaroslav
Published: October 2008

We introduce several new classes of graphs on which the maximum-weight clique problem is solvable in polynomial time. Their common feature, and the central idea of our algorithms, is that every clique of any of our graphs is contained in some member of a polynomial-sized collection of induced subgraphs that are complements of bipartite graphs.
Continuous Selections for Vector Measures
Authors: Samet Dov
Published: October 2008

A vector measure is a many to one map; it maps many measurable sets onto the same point. A selection for a vector measure is a function which assigns to each point in the range of the vector measure only one measurable set which is mapped onto the point. The existence of a continuous selection for nonatomic vector measures is proved where the distance in the σ-field is the measure (for a given scalar measure) of the symmetric difference. A stronger version of continuous selection exists for strictly convex ranges.
Generalized Descent Methods for Asymmetric Systems of Equations
Authors: Hammond Janice H. , Magnanti Thomas L.
Published: October 2008

We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by the matrix M, then the method converges if M2 is positive definite. We also establish easy to verify conditions on the matrix M that ensure that M2 is positive definite, and develop a scaling procedure that extends the class of matrices that satisfy the convergence conditions. In addition, we establish a local convergence result for nonlinear systems defined by uniformly monotone maps, and discuss a class of general descent methods.

All of the methods that we consider reduce to standard nonlinear programming algorithms for equivalent optimization problems when the Jacobian of the underlying problem map is symmetric. We interpret the convergence conditions for the generalized steepest descent algorithms as restricting the degree of asymmetry of the problem map.
Probabilistic Analysis of a Relaxation for the k-Median Problem
Authors: Ahn Sang , Cooper Colin , Cornuéjols Gérard , Frieze Alan
Published: October 2008

This paper provides a probabilistic analysis of the so-called “strong” linear programming relaxation of the k-median problem when the number of points, say n, goes to infinity. The analysis is performed under four classical models in location theory, the Euclidean, network, tree and uniform cost models. For example, we show that, for the Euclidean model and k → ∞, k = o(n/log n), the value of the relaxation is almost surely within 0.3 percent of the optimum k-median value. For the uniform cost model and the same conditions on k, we show that the value of the relaxation is almost surely 50 percent of the optimum k-median value. We also show that, under various assumptions, branch and bound algorithms that use the strong linear programming relaxation as a bound must almost surely expand a nonpolynomial number of nodes to solve the k-median problem to optimality. Finally, we report extensive computational experiments. As predicted by the probabilistic analysis, the relaxation was not as tight for the problem instances drawn from the uniform cost model as for the other models.
Differential Characterizations of Nonconical Dominance in Multiple Objective Decision Making
Authors: Hazen Gordon B.
Published: October 2008

Suppose a decision maker's preferences are represented by an unknown value function v. Prior information concerning v (in the form of structural assumptions or revealed preferences) may serve to restrict v to some class V of value functions. An alternative y is dominated by an alternative z if v(y) < v(z) for (almost) every v ∈ V, in which case we write y <V z. Continuous variable problems are considered, in which alternatives are sought which are undominated under <V. For these problems we derive necessary and sufficient differential optimality conditions of the Kuhn-Tucker type. An example is presented in which V is a class of measurable value functions of the multiplicative form introduced by Dyer and Sarin. Since <V may be a nonconical order, these results are not subsumed by conventional vector optimization.
Monotonicity in a Markov Decision Process
Authors: Pittenger A. O.
Published: October 2008

Concavity of optimal costs and monotonicity of optimal actions are established for a Markov decision problem in which state space and action space are ordered, but in which the cost functions do not possess properties commonly used to establish monotonicity. The proof is elementary, but depends heavily on the binomial character of the transition probabilities.
Optimality of Stationary Halting Policies and Finite Termination of Successive Approximations
Authors: Erickson Ranel E.
Published: October 2008

The existence of an optimal stopping policy that is stationary and halting in a discrete-time-parameter finite-state finite-action branching Markov decision chain is here characterized by the finite termination of successive approximations. We call a policy stopping if the expected population size at time N converges to zero as N approaches infinity, and halting if the expected population at time N is zero for some N. We show that when the rewards are real valued, the Nth iterate of successive approximations is a fixed point of the optimal return operator for some N when initiated with the value of a stationary halting policy if and only if there exists a halting stationary optimal stopping policy. Similar results are shown for a Gauss-Seidel improvement of successive approximations.
An Extreme-Type Limit Law for a Storage Process
Authors: Greenwood Priscilla E. , Hooghiemstra Gerard
Published: October 2008

A solar energy storage model is studied, where input is exponentially distributed but accepted only conditionally. The resulting Markov chain has a stationary distribution depending on two parameters. A limiting distribution is found as one parameter varies and this is used for computation of the asymptotic mean. The limit law may be regarded as a new type of extremal distribution.
Global Regularity Theorems
Authors: Auslender A. A. , Crouzeix J.-P.
Published: October 2008

For a system of nondifferentiable convex inequalities and linear equalities, the best bound is given for the quotient of the distance of an infeasible point and the norm of the residual vector. Applications to stability theory are then obtained.
Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems
Authors: Bes C. , Sethi S. P.
Published: October 2008

In this paper, we develop a rigorous new framework for the concepts of forecast and decision horizons. These concepts are conditional in nature and, in turn, enable us to unify the existing concepts of “strong” and “weak” horizons. Moreover, we are able to precisely state the questions of existence of forecast/decision horizons. Finally, we are able to further develop the theory of existence of forecast/decision horizons in the discounted case and procedures to compute these horizons.
Extreme Values of Queue Lengths in M/G/1 and GI/M/1 Systems
Authors: Serfozo Richard F.
Published: October 2008

We study the limiting behavior of maximum queue lengths in the M/G/1 and GI/M/1 service systems. When the systems are positive recurrent, the distributions of their maximum queue lengths, under standard linear normalizations, either do not converge or they converge to degenerate limits. Consequently, one cannot use classical extreme value theory to characterize their limiting behavior. We show, however, that by varying the system parameters in a certain way as the time interval grows, these maxima do indeed have three possible limit distributions. Two of them are classical extreme value distributions and the third one is a new distribution. The latter distribution is the best one for practical approximations.
Solving SLP Recourse Problems with Arbitrary Multivariate Distributions—The Dependent Case
Authors: Frauendorfer Karl
Published: October 2008

Bounding the expectation of a convex function of a multivariate random variable is of great importance for solving stochastic linear programming problems (SLP) with recourse. The classic bounds are those of Jensen and Edmundson-Madansky, whereby Jensen's inequality is available in the independent as well as in the dependent case, in contrast with the Edmundson-Madansky (E-M) inequality (Madansky, A. 1959. Bounds on the expectation of a convex function of multivariate random variable. Ann. Math. Statist. 30 743–746.) which is valid only in the independent case.

This paper presents a straightforward extension of the E-M inequality for the dependent case, yielding a discrete distribution that is extremal with respect to a partial ordering of a set of distribution functions. Further, we prove that the bounds for the expectation behave monotonically by applying the obtained inequality to smaller and smaller subintervals. As this requires the evaluation of conditional probabilities and expectations, we replace the given distribution by a discrete one resulting from sampling, and determine the sampling size that keeps the statistical error negligible. Finally we conclude with the application to SLP recourse problems and state some computational results illustrating the effort for solving recourse problems.
Average, Sensitive and Blackwell Optimal Policies in Denumerable Markov Decision Chains with Unbounded Rewards
Authors: Dekker Rommert , Hordijk Arie
Published: October 2008

In this paper we consider a (discrete-time) Markov decision chain with a denumerable state space and compact action sets and we assume that for all states the rewards and transition probabilities depend continuously on the actions.

The first objective of this paper is to develop an analysis for average optimality without assuming a special Markov chain structure. In doing so, we present a set of conditions guaranteeing average optimality, which are automatically fulfilled in the finite state and action model.

The second objective is to study simultaneously average and discount optimality as Veinott (Veinott, A. F., Jr. 1969. On discrete dynamic programming with sensitive discount optimality criteria. Ann. Math. Statist. 40 1635–1660.) did for the finite state and action model. We investigate the concepts of n-discount and Blackwell optimality in the denumerable state space, using a Laurent series expansion for the discounted rewards. Under the same condition as for average optimality, we establish solutions to the n-discount optimality equations for every n.
Odd Submodular Functions, Dilworth Functions and Discrete Convex Functions
Authors: Qi Liqun
Published: October 2008

Three set-function classes more general than submodular ones are discussed. An odd submodular function defines a box totally dual integral system. An integral odd submodular function and its Dilworth truncation, i.e., a Dilworth function, give rise to the same polyhedron with integral vertices. The minimum of two submodular functions is an odd submodular function. The convolution of two submodular functions is a Dilworth function. A Dilworth function is a discrete convex function. A discrete convex function can be characterized by its convex hull, subgradients, epigraph and general subadditivity. Discrete convexity is preserved under many natural operations.
A Stochastic Theory of the Firm
Authors: Li Lode
Published: October 2008

We present a stochastic model of make-to-stock firms based on a buffer flow system with jumps. The cumulative production and the cumulative demand are governed by two Poisson counting processes with random intensities parameterized by production capacity and price respectively. Optimal operating and pricing policies (short-run decisions) and optimal capacity (long-run) decisions are explored by application of a two-stage optimization device. Detailed computations regarding the Poisson buffer flow system and a variation on the basic model with learning effects are also presented.
Infinite Player Noncooperative Games and the Continuity of the Nash Equilibrium Correspondence
Authors: Housman David
Published: October 2008

The usual definition of a noncooperative game is extended in two different ways: first, by replacing the finite player set with a measure space, and second, by eliminating the player set and considering a distribution of the players' characteristics. Feasible strategy profiles and Nash equilibria obtained from the two approaches are compared. The feasible strategy profile correspondence is shown to be continuous. The Nash equilibrium correspondence is shown to be upper hemicontinuous and nearly lower hemicontinuous on the class of convex and equicontinuous games. These results show when it is reasonable to use an infinite player game as an approximation of a large, but finite, player game.
Lower Bounds on Time-Accuracy Trade-Offs for the 0-1 Knapsack Problem
Authors: Peters Joseph G.
Published: October 2008

The 0-1 Knapsack optimization problem is well known to be NP-hard. The best known approximation algorithms for this problem are approximation schemes which exhibit trade-offs between the running time of the algorithm and the guaranteed accuracy of the solution. This paper establishes lower bounds on the time required to find approximate solutions of guaranteed accuracy for a class of knapsack algorithms which must use oracles to perform feasibility tests and dominance tests.
On Eigenvalues and Annealing Rates
Authors: Chiang Tzuu-Shuh , Chow Yunshyong
Published: October 2008

We evaluate asymptotically the eigenvalues of transition rate matrices (Qijϵ)i,j=1n with Qijϵ ∼ exp(−(U(j) − U(i))+/ϵ) for some function U using Ventcel's graphic method. As a consequence, we can compare the “nearly optimal” annealing rate in (Gidas, B. 1985. Global optimization via the Langevin equation. Proc. 24th IEEE Conf. Decision and Control, Ft. Lauderdale, FL, December.) with the true optimal rate in (Hajek, B. Cooling schedules for optimal annealing. Preprint.). A necessary and sufficient condition is given for the coincidence of those rates.
A Geometrically Convergent Subgradient Optimization Method for Nonlinearly Constrained Convex Programs
Authors: Rosenberg Eric
Published: October 2008

In this paper we extend the geometrically convergent subgradient optimization method for minimizing a convex function, proposed independently by Goffin and also Shor and Gamburd, to a class of constrained convex programs. We permit both arbitrary set constraints and convex inequality constraints. Such programs arise, for example, in sizing trunks in a multi-hour alternate routing telecommunications network and in certain location and approximation problems.

The geometric convergence rate depends upon a condition number of the convex program that we define. Our proof of geometric convergence, when explicit convex inequality constraints are present, is the first such result for subgradient optimization. We compare the iterates generated by our method to the limiting behavior, as the penalty parameter approaches infinity, of the sequence of iterates obtained by applying Goffin's method to the exact penalty function corresponding to the convex program. We also show that geometric convergence still holds when ϵ-subgradients (for sufficiently small ϵ > 0) are used instead of subgradients.
Second-Order Properties of the Throughput of a Closed Queueing Network
Authors: Shanthikumar J. George , Yao David D.
Published: October 2008

We show that the throughput of a single-class closed queueing network (CQN) of Jackson type, as a function of the job population, is nondecreasing concave [respectively, convex, anti-starshaped, starshaped, subadditive or superadditive] if the service rate at each node, as a function of the local queue length, has the same property. The key to the proofs is the concept of “equilibrium rate.” For a discrete positive random variable Y the equilibrium rate is defined as a function: r(0) = 0, r(n) = P[Y = n − 1]/P[Y = n], n ≥ 1. It turns out that the equilibrium rate r(n) is nondecreasing in n if and only if the pmf of Y is a Polya frequency function of order two; and it is known that the said property (hence, the nondecreasing property of equilibrium rates) is preserved under convolution. Here, we represent the CQN throughput function as the equilibrium rate of a sum of independent random variables, each corresponding to a node in the network, with the service rate of the node as its equilibrium rate. The second order properties of the CQN throughput are then established by proving that the second-order properties of equilibrium rates are also preserved under convolution.
On the Facial Structure of Independence System Polyhedra
Authors: Conforti Michele , Laurent Monique
Published: October 2008

A polyhedron P whose extreme points are the incidence vectors of the sets of an independence system ℐ is called an independence system polyhedron. In this paper, we consider the problem of describing the facial structure of independence system polyhedra.

Using the fact that this structure is known when the independence system is a matroid, we study the polyhedron P by decomposing the independence system ℐ as a union of matroidal families. We provide a system of valid inequalities for P that contains all its facets. A consequence of this result is the following: the maximum number of distinct coefficients of a facet is bounded by the minimum number of matroidal families whose union gives ℐ. When the independence system ℐ is the union of two matroids, we give necessary and sufficient conditions for an inequality of the above system to define a facet of P.
Optimal Impulse Control of Portfolios
Authors: Eastham Jerome F. , Hastings Kevin J.
Published: October 2008

An investor has the opportunity of holding shares in n risky assets and one nonrisky asset at every time in a fixed interval [t, T]. The risky assets are governed by a stochastic differential equation. At random instants of his choice he may intervene in order to rebalance his portfolio and consume a nonnegative amount of money. Fixed and variable transactions costs are incurred upon intervention. At time T all remaining wealth is consumed. The solution to the problem of maximizing total utility of consumption is given by way of quasi-variational inequalities for the value function. With probability one the investor only intervenes finitely many times. Indication of the solution of the quasi-variational inequalities in the case of one risky asset with log-normal prices is given, together with a description of a discretization procedure.
The Lattice Structure of the Set of Stable Matchings with Multiple Partners
Authors: Blair Charles
Published: October 2008

We continue recent work on the matching problem for firms and workers, and show that, for a suitable ordering, the set of stable matchings is a lattice.
Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
Authors: Todd Michael J.
Published: October 2008

Karmarkar's projective algorithm for linear programming provides not only primal solutions but dual solutions giving bounds on the optimal value. Here we show how improved bounds can be obtained at the expense of solving a two-dimensional linear programming problem at every iteration, and also how an ellipsoid containing all dual optimal solutions can be generated from available information. We also give the results of limited computational experiments related to these topics.
An LIL Version of L = λW
Authors: Glynn Peter W. , Whitt Ward
Published: October 2008

This paper establishes a law-of-the-iterated-logarithm (LIL) version of the fundamental queueing formula L = λW: Under regularity conditions, the continuous-time arrival counting process and queue-length process jointly obey an LIL when the discrete-time sequence of interarrival times and waiting times jointly obey an LIL, and the limit sets are related. The standard relation L = λW appears as a corollary. LILs for inverse processes and random sums are also established, which are of general probabilistic interest because the usual independence, identical-distribution and moment assumptions are not made. Moreover, an LIL for regenerative processes is established, which can be used to obtain the other LILs.
Probabilistic Analysis of the Multidimensional Knapsack Problem
Authors: Dyer M. E. , Frieze A. M.
Published: October 2008

We analyse the multi-constraint zero-one knapsack problem, under the assumption that all coefficients are drawn from a uniform [0, 1] distribution and there are m = 0(1) constraints as the number of variables grows. We show that results on the single-constraint problem can be extended to this situation. Chiefly, we generalise a result of Lueker on the duality gap, and a result of Goldberg/Marchetti-Spaccamela on exact solvability. In the latter case, our methods differ markedly from those for the single-constraint result.
Coercion Functions and Decentralized Linear Programming
Authors: Feinberg Brion
Published: October 2008

This paper describes a decentralized linear programming solution procedure. Unlike the classic Dantzig-Wolfe decomposition algorithm, this procedure is a complete decentralization, where the subproblems act independently to generate the optimal solution. In Dantzig-Wolfe decomposition, the master problem must “dictate” the final optimal solution. Our procedure is an improvement over Dantzig-Wolfe decomposition in this sense. The procedure works by adding a “coercion” function to the subproblem objective. Under proper conditions, this function “coerces” the subproblem to behave as desired. Such total decentralization is important for loosely coupled systems where it is not possible for the master level to dictate optimal decision values for the subsystems.
Open Queueing Systems in Light Traffic
Authors: Reiman Martin I. , Simon Burton
Published: October 2008

Many quantities of interest in open queueing systems are expected values which can be viewed as functions of the arrival rate to the system. We are thus led to consider f(λ), where λ is the arrival rate, and f represents some quantity of interest. The aim of this paper is to investigate the behavior of f(λ), for λ near zero. This ‘light traffic’ information is obtained in the form of f(0) and its derivatives, f(n)(0), n ≥ 1.

Focusing initially on Poisson arrival processes, we provide a method to calculate f(n)(0) for any ‘admissible’ function f. We describe a large class of queueing networks for which we show several standard quantities of interest to be admissible. The proof that the method yields the correct values for the derivatives involves an interchange of limits, whose justification requires a great deal of effort. The determination of f(n)(0) involves consideration of sample paths with n + 1 or fewer arrivals over all of time. These calculations are illustrated via several simple examples.

These results can be extended to arrival processes which, although not Poisson, are ‘driven’ by a Poisson process. We carry out the details for phase type renewal processes and nonstationary Poisson processes.
Martingale Inequalities, Interpolation and NP-Complete Problems
Authors: Rhee Wansoo T. , Talagrand Michel
Published: October 2008

In a previous work (Rhee, W., Talagrand, M. 1987. Martingale inequalities and NP-complete problems. Math. Oper. Res. 12(1) 177–181.), we showed how to use martingale inequalities in the probabilistic analysis of stochastic models of NP-complete problems to obtain sharp bounds on P(|Un − E(Un)| ≥ t), where Un is the objective function value of the problem with n random data. Here, we show how to interpolate between martingale inequalities to obtain even sharper bounds.
A Decomposition Method and Its Application to Convex Programming
Authors: Han Shih-Ping
Published: October 2008

A method is proposed for minimizing a function of the form q(x − d) + f1(x) + ⋯ + fm(x) where q is definite quadratic and fi are proper closed convex. The key feature of the method is its capability of reducing the problem to a sequence of subproblems of the form: min q(x − z) + fi(x). The method is an extension of the successive projection method given in [Han, S.-P. 1988. A successive projection method. Math. Programming 40 1–14.] and has some similar features as the partial inverse method of Spingarn [Spingarn, J. E. 1983. Partial inverse of a monotone operator. Appl. Math. Optim. 10 247–265.]. In combination with the proximal point algorithm [Martinet, B. 1970. Regularisation d'inéquations variationelles par approximations successives. Rev. Francaise Inform. Rech. Oper. 154–159; Martinet, B. 1972. Determination approchée d'un point fixe d'une application pseudo-contractante. C.R. Acad. Sci. Paris 274 163–165; Rockafellar, R. T. 1976. Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5) 877–898.], it can decompose a general convex program. It has attractive convergence properties and is useful for solving large-scale sparse problems.
Structure of Efficient Sets for Convex Objectives
Authors: Ward James
Published: October 2008

This paper considers multiple objective problems in which each objective is the minimization of a convex function defined over a convex solution space, and for which the number of objectives is greater than the dimension of the solution space. Such problems arise in location analysis, where the solution space of possible facility sites may be represented by a plane, but many location objectives may exist. We show that the set of efficient solutions to such problems exhibit structures similar to convex hulls. That is, the solutions on the boundary of the efficient set are efficient for “subproblems” obtained by considering only small subsets of objectives. The number of objectives in these subproblems is at most equal to the dimension of the solution space. When the objectives are continuous, and attain their minimum values in a bounded region over the solution space, the efficient set of the subproblems completely determine an efficient set for the larger problem.
The Worst-Case Step in Karmarkar's Algorithm
Authors: Anstreicher Kurt M.
Published: October 2008

In this note we consider the worst-case performance in a single step of Karmarkar's projective algorithm for linear programming. In the transformed problem which arises on each iteration we show that the critical ratio “r/R” can be improved (asymptotically) by a factor of two. We also show that in the original problem, where performance is characterized by reduction in the potential function, the worst-case reduction can be improved to approximately 0.72. Moreover, we demonstrate that both of these bounds are tight, so that no further improvement based on the analysis of a single step is possible.
Random Search Algorithms with Sufficient Descent for Minimization of Functions
Authors: Wardi Yorai
Published: October 2008

A random search method for function minimization is presented. At each point it randomly searches for the next point, where the value of the objective function is reduced. While thus searching, it does not take as the next point the first point it finds which reduces the objective function, but rather it searches for a point where sufficient descent is obtained. The criterion for “sufficient” depends on the number of iterations of the search at a given point. The scheme is shown to converge a.e. to a set of desirable points, and a new proof of convergence is furnished. The method has the tendency to spend a larger amount of computing time when a desirable point is approached, and a smaller amount of computing time when far away from such a point. It is a general method, and algorithm based on it can easily be developed for specific optimization problems. Such algorithms are provided for three optimization problems: unconstrained local minimization of nondifferentiable functions, local minimization of continuously differentiable functions with functional inequalities, and global minimization of continuous functions.
Maximizing Classes of Two-Parameter Objectives Over Matroids
Authors: Hassin R. , Tamir A.
Published: October 2008

Let M = (N, ℱ) be a matroid. Suppose that each element i in N is associated with an ordered pair of rational numbers (ai, bi). For each subset S in ℱ define A(S) = ∑i∈S ai and B(S) = ∑i∈S bi. Let g be a real convex function defined on R2. Consider the problem of maximizing g(A(S), B(S)) over all bases S of M. We present a polynomial algorithm for this problem when g is a general polynomial. This algorithm is strongly polynomial when the degree of g is at most cubic. Using the latter result we apply appropriate transformations to obtain strongly polynomial algorithms for some cases when g is not polynomial. In particular, we find in strongly polynomial time the minimal cost reliability ratio spanning tree of an undirected graph.
Optimal Assignment of Components to a Two-Stage k-Out-of-n System
Authors: Hwang F. K.
Published: October 2008

A two-stage k-out-of-n system is an l-out-of-m system except that each of the m parts is itself a ki-out-of-ni system. The problem is to assign a set of ∑i=1m ni probabilities to the ∑i=1m ni components in the system to maximize its reliability. In this paper we consider the case ki = k for all i. We give optimal assignments when the first stage is a parallel system or the second stage is a series system. We conjecture that the optimal assignment problems for all other two-stage k-out-of-n systems are NP-complete, but we are able to prove this only when the second stage is a parallel system. We also propose a heuristic assignment algorithm for the general case.
Controlling a Process to a Goal in Finite Time
Authors: Sudderth William D. , Weerasinghe Ananda
Published: October 2008

A player starts at x in (0, 1) and seeks to reach 1 by time t0. The process {X(t), 0 ≤ t ≤ t0} of the player's positions is a diffusion process (or an Ito process) whose infinitesimal parameters μ, σ are chosen by the player at each instant of time from a set depending on the current position. The probability of reaching 1 by time t0 is maximized if the player can and does choose the parameters so that σ and μ/σ2 are maximized, at least when these maxima are sufficiently regular. This result implies that bold play is optimal for subfair, continuous-time red-and-black and roulette when there is a limit on playing time.
An Axiomatization of the Core of Market Games
Authors: Peleg Bezalel
Published: October 2008

We provide an axiomatization of the core of market games (totally balanced coalitional games). We prove that the core is fully characterized by the following five independent properties: (i) nonemptiness; (ii) individual rationality; (iii) superadditivity; (iv) the weak reduced game property; and (v) the converse reduced game property. Also, we consider a possible alternative characterization.
Approximations to the Lifetime Distribution of k-Out-of-n Systems with Cold Standby
Authors: Kroese D. P. , Kallenberg W. C. M.
Published: October 2008

We consider several approximations to the lifetime distribution of general k-out-of-n systems with cold standby, when n becomes large. The approximations are derived from limiting results for N(t), the number of failures in [0, t], when t → ∞. The approximations can be easily evaluated even though the derivation of the limiting result is rather technical, due to the discrete character of N(t). Numerical work shows excellent agreement with the theoretical error structure of the approximations.
The Linear Order Complementarity Problem
Authors: Borwein J. M. , Dempster M. A. H.
Published: October 2008

The classical complementarity problem in Euclidean space can be viewed alternatively as a variational inequality or as a lattice orthogonality problem. Generalizations of the former have been extensively studied, but infinite-dimensional analogues of the latter have been largely ignored. Moreover, as we show, many well-known results about the classical complementarity problem are more appropriately viewed order-theoretically. This is particularly true of least element solutions, which are central to the present study of order complementarity in vector lattices. We emphasize that the lattice theoretic descriptions we employ are very useful even in the standard finite-dimensional setting.
On Abstract Integral Dependence
Authors: Llewellyn Donna Crystal , Trotter L. E.
Published: October 2008

The concept of a tag system is introduced. In its general form the combinatorial structure of a dual pair of tag systems arises through composition of blocking pairs of clutters. This leads to a “painting” characterization for dual pairs of tag systems which is useful for establishing combinatorial theorems of the alternative for certain classes of tag systems. Integral tag systems arise as a natural combinatorial abstraction of integral linear dependence properties of rational vectors in analogy with the manner in which matroids arise from linear dependence properties. Tag systems subsume matroids and several characterizations of matroids as tag systems are given; however, tag systems are shown to be generally less tractable computationally than matroids by establishing NP-completeness for the problem of determining a smallest base for an integral tag system.
An Abstract Linear Duality Model
Authors: Carvalho P. C. P. , Trotter L. E.
Published: October 2008

We investigate an abstract linear duality model which has as special instances several duality systems of interest in combinatorial optimization: subspace orthogonality, cone polarity, lattice duality, blocking polyhedra and antiblocking polyhedra. The descriptive duality present in the model is that of specifying a set in terms of linear constraints or viewing a set as being generated by certain types of linear combinations. We define properties of Weyl, Farkas and Minkowski for the general model by analogy with classical results in cone polarity and we investigate relationships among these properties and further properties of Lehman and Fulkerson, defined by analogy with results on dual pairs of polyhedra of the blocking or antiblocking type. In particular, we show that, for any given duality system, the Weyl property is equivalent to the combined properties of Farkas and Minkowski (or Lehman), that the Farkas property implies the Fulkerson property and that the Minkowski property is equivalent to the combined properties of Lehman and Fulkerson. We also adapt results of Dixon (Dixon, J. D. 1981. On duality theorems. Linear Algebra Appl. 39 223–228.) in order to obtain general sufficient conditions for validity of the Weyl property.

In the second part of the paper, specific instances of the model are examined in more detail. The instances studied here are “integral duality” and “nonnegative integral duality,” which are related to the problem of finding integral solutions and nonnegative integral solutions, respectively, for linear systems. For each instance, the validity of the Weyl, Minkowski, Farkas, Lehman and Fulkerson properties is examined. We also characterize the constrained sets under each duality.
An Axiomatic Approach to Proportionality Between Matrices
Authors: Balinski M. L. , Demange G.
Published: October 2008

Given a matrix p ≥ 0 what does it mean to say that a matrix f (of the same dimension), whose row and column sums must fall between specific limits, is “proportional to” p? This paper gives an axiomatic solution to this question in two distinct contexts. First, for any real “allocation” matrix f. Second, for any integer constrained “apportionment” matrix f.

In the case of f real the solution turns out to coincide with what has been variously called biproportional scaling and diagonal equivalence and has been much used in econometrics and statistics. In the case of f integer the problem arises in the simultaneous apportionment of seats to regions and to parties and also in the rounding of tables of census data.
Asymptotic Measure-Based Values of Nonatomic Games
Authors: Monderer Dov
Published: October 2008

Let v = min(μ1, μ2, …, μn), where μ1, μ2, …, μn are mutually singular nonatomic probability measures, i.e., v is the market game derived from an n-glove nonatomic market with transferable utility. We describe the set of all μ-asymptotic values of v, where μ ranges over all non-atomic probability measures for which μi is absolutely continuous with respect to μ and dμ/dμ ∈ L2(μ) for all 1 ≤ i ≤ n. This set is proved to be convex and relatively open.
Upper Bounds on the Expected Value of a Convex Function Using Gradient and Conjugate Function Information
Authors: Birge John , Teboulle Marc
Published: October 2008

New upper bounds are given for the expected value of a convex function. The bounds employ subgradient information and the conjugate function. In contrast to most other bounds, explicit moment information is not needed. We derive the bounds and compare them with previous bounds with different information requirements.
Characterizations of the Dimension for Classes of Concordant Polytopes
Authors: Lee Jon
Published: October 2008

The spectral method is used to completely describe the set of possible dimensions for concordant polytopes arising from complete undirected and directed graphs. For concordant polytopes satisfying c-factor or c-difactor constraints, we determine the more limited sets of possible dimensions and characterize the polytopes of each dimension. We also demonstrate how the spectral method may be used to refine the direct method for determining the dimension of a concordant polytope.
Comparing Policies in Markov Decision Processes: Mandl's Lemma Revisited
Authors: Shwartz Adam , Makowski Armand M.
Published: October 2008

A general framework is developed for comparing the long-run average cost of a Markov stationary policy with that of another related policy. The underlying methodology constitutes an extension of some ideas of Mandl to randomized policies, and to Polish state and action spaces. Sufficient conditions for the applicability of the methodology are given. These conditions, which are easy to verify, have a natural probabilistic interpretation in terms of the “stability” of the chain and of the convergence of the control values. The usefulness of the general framework proposed here is illustrated on several applications. Standard results on the convergence of adaptive policies are readily recovered under conditions which are more transparent than the ones existing in the literature, and the convergence of randomized policies is handled as a special case. Finally, a novel application to “probing controls” is outlined.
A Stochastic Control Approach to the Pricing of Options
Authors: Barron Emmanuel Nicholas , Jensen Robert
Published: October 2008

We construct a stochastic control model of a portfolio in which the investor may invest in stock, call options on the stock, or risk free bonds. He may also borrow funds. We assume that the investor is attempting to maximize expected utility of total wealth at expiration of the options where the utility function is given as wealth to the power γ, 0 ≤ γ ≤ 1. This includes both the risk averse and risk neutral cases. We allow the borrowing interest rate, R, to be distinct from the lending interest rate, r. We make two fundamental assumptions: (i) the investor cannot achieve infinite expected utility of wealth in finite time (“stable markets”) and (ii) the market will set the option price to minimize the investor's maximal expected utility of wealth, i.e., options are priced using a minimax strategy. The market is stable only when R ≥ r. We prove in the case R > r and γ < 1 that the minimax (European) call option price, F(t, S), is given as the solution of the Black-Scholes equation Ft + ½ σ2S2FSS + δ S FS − δ F = 0, where δ = r when r ≥ α + σ2(γ − 1); δ = R when α + σ2(γ − 1) ≥ R; and δ = α + σ2(γ − 1) if R ≥ α + σ2(γ − 1) ≥ r. The parameter α is the stock return drift and σ is the stock return diffusion. If R = r, then the call option price must, by stable markets, always be the Black-Scholes price with rate r. In the risk neutral (γ = 1) case we must have R ≥ α ≥ r for a stable market and the option price given by the Black-Scholes equation but with δ = α. Explicit solutions are presented and the optimal portfolios and returns are also derived. Comparable results are obtained for American call options which can be exercised at any time up to and including the expiration date. In this case, the option pricing function is shown to be the solution of an obstacle problem.
A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
Authors: Monteiro Renato D. C. , Adler Ilan , Resende Mauricio G. C.
Published: October 2008

We describe an algorithm for linear and convex quadratic programming problems that uses power series approximation of the weighted barrier path that passes through the current iterate in order to find the next iterate. If r ≥ 1 is the order of approximation used, we show that our algorithm has time complexity O(n½(1 + 1/r)L(1 + 1/r)) iterations and O(n3 + n2r) arithmetic operations per iteration, where n is the dimension of the problem and L is the size of the input data. When r = 1, we show that the algorithm can be interpreted as an affine scaling algorithm in the primal-dual setup.
Deterministic Equivalence in Stochastic Infinite Horizon Problems
Authors: Higle Julia L. , Bean James C. , Smith Robert L.
Published: October 2008

We consider a general infinite horizon problem with stochastic data. We establish conditions under which the stochastic problem may be correctly solved using an equivalent deterministic problem. In particular, we establish conditions under which there exists an equivalent interest rate, which permits replacement of the stochastic data by their expectations. This equivalent interest rate can be approximated by a linear function of the ratio of the variance to the mean of the stochastic data. Applications to production planning are included.
Continuous Time Stopping Games with Monotone Reward Structures
Authors: Huang Chi-Fu , Li Lode
Published: October 2008

We prove the existence of a Nash equilibrium for a class of continuous time stopping games when certain monotonicity conditions are satisfied.
On a Network Design Problem That Is Intractable on Trees
Authors: Bienstock Dan , Marcotte Odile
Published: October 2008

In this paper we study an optimization problem that arises in the design of communication networks. We show that this problem is NP-hard even when restricted to trees, and present several approximation results. In particular, we show that an integer programming formulation of the problem yields bounded ratio estimates for instances of the problem defined on trees.
Multivariate Stochastic Orderings and Positive Dependence in Reliability Theory
Authors: Shaked Moshe , Shanthikumar J. George
Published: October 2008

Stochastic orderings are introduced for vectors of lifetimes based on hazard rates and cumulative hazard functions. Relations are established between those orderings and other ones such as the totally positive ordering of Karlin and Rinott (1980). Positive dependence notions in reliability theory are recast in terms of the new stochastic orderings. Relationships are also established between the notion of multivariate total positivity and the notion of hazard increase upon failure.
An Axiomatic Approach to Location on Networks
Authors: Holzman Ron
Published: October 2008

The problem under consideration is that of locating a facility on a tree-network, given data specifying the locations of the users on the network. The approach taken is to formulate axioms that require consistent response of the solution to variations in the users' location data. It is shown that three independent axioms determine together a unique solution, located at the point that minimizes the sum of the squares of the distances to the users.
Limiting Behavior of Trajectories Generated by a Continuation Method for Monotone Complementarity Problems
Authors: Kojima Masakazu , Mizuno Shinji , Noma Toshihito
Published: October 2008

Defining the mapping F from the 2n-dimensional Euclidean space R2n into itself by

F(x, y) = (x1 y1, …, xn yn, y1 − f1(x), …, yn − fn(x))

for every (x, y) ∈ R2n, we write the CP, the complementarity problem, with a mapping f: Rn → Rn as the system of equations

F(x, y) = 0 and (x, y) ∈ R+2n,

where R+2n denotes the nonnegative orthant of R2n. Under the assumption that f is a monotone function on R+n, we show that F maps the positive orthant R++2n of R2n homeomorphically. This result then ensures the existence of a trajectory consisting of the solutions (x, y, t) of the system of equations

F(x, y) = w(t) and (x, y, t) ∈ R++2n × (0, 1],

where w is a continuous mapping from the unit interval [0, 1] into F(R++2n) such that w(0) = 0; if t = 0, the system coincides with the CP. We study limiting behavior of the trajectory as t → 0, and give some sufficient conditions for the trajectory to lead to a solution of the CP. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving positive semidefinite linear complementarity problems.
A Milnor Condition for Nonatomic Lipschitz Games and Its Applications
Authors: Monderer Dov
Published: October 2008

One of Milnor's reasonable axioms is generalized to nonatomic games. Several uses of this generalization are discussed. In particular, the general form of values and semivalues on subspaces of pNA∞ is derived.
Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
Authors: Steele J. Michael
Published: October 2008

The classical problems reviewed are the traveling salesman problem, minimal spanning tree, minimal matching, greedy matching, minimal triangulation, and others. Each optimization problem is considered for finite sets of points in ℝd, and the feature of principal interest is the value of the associated objective function. Special attention is given to the asymptotic behavior of this value under probabilistic assumptions, but both probabilistic and worst case analyses are surveyed.
On Optimal Packing of Randomly Arriving Objects
Authors: Courcoubetis Costas , Rothblum Uriel G.
Published: October 2008

Objects of finitely many types arrive at a facility according to independent stationary Poisson processes. The objects are to be placed in boxes as they arrive. There are finitely many types of boxes and each box type has its own packing configuration. There is an unlimited supply of boxes of each type and once an object is placed in a box it cannot be moved to another box in the future. When a box is completely filled it produces a reward which depends on its configuration. The objective is to select a rule for placing the arriving objects in boxes so as to maximize expected reward. We show how to construct optimal and ε-optimal policies under which the expected number of partially packed boxes does not explode.
Multichain Markov Decision Processes with a Sample Path Constraint: A Decomposition Approach
Authors: Ross Keith W. , Varadarajan Ravi
Published: October 2008

We consider finite-state finite-action Markov decision processes which accumulate both a reward and a cost at each decision epoch. We study the problem of finding a policy that maximizes the expected long-run average reward subject to the constraint that the long-run average cost be no greater than a given value with probability one. We establish that if there exists a policy that meets the constraint, then there exists an ε-optimal stationary policy. Furthermore, an algorithm is outlined to locate the ε-optimal stationary policy. The proof of the result hinges on a decomposition of the state space into maximal recurrent classes and a set of transient states.