bluuebunny/crossref_metadata_2025 huggingface dataset:
Multilinear Expected Utility
Authors: Fishburn Peter C.
Published: October 2008

For each i in {1, …, n} let pi be a convex set of finitely additive probability measures defined on an atomic Boolean algebra of subsets of Xi, and let P = P1 × ⋯ × Pn and X = X1 × ⋯ × Xn. Under specified structural assumptions, axioms are stated for a preference relation ≻ on P which are necessary and sufficient for the existence of a real valued utility function u on X for which ∫X u(x1, …, xn) dpn(xn), …, dp1(x1) is finite for all (p1, …, pn) in P and for which p ≻ q iff [Formula: see text] for all p and q in P. A simpler set of axioms yields the same results when each algebra is a Borel algebra and all measures are countably additive. The axioms allow the Pi to contain nonsimple measures without necessarily implying that u is bounded. The relevance of the formulation to n-person games and other situations is noted.
On Piecewise Linear Functions and Piecewise Linear Equations
Authors: Schramm Ruben
Published: October 2008

In this paper we treat of the number of solutions of certain piecewise linear (p.l.) equations and of necessary and sufficient conditions for a PL function to be a homeomorphism. The function f: Rn → Rm is PL when a finite set H of hyperplanes exists such that Rn\∪H is the disjoint union of open polyhedral sets C1, …, Cq and F ∣ C̄ (x) = Aix + bi with Ai ∈ Rn,n, Bi ∈ Rn for i = 1, …, q. Letting H* be the set of points common to at least two hyperplanes in ∪ H, we show that when det A1, … , det Aq all have the same sign then F, restricted to Rn\F−1 [F(H*)], is a covering map. From this we conclude that for γ ∈ Rn/F(H*) the number m of solutions of the equation F(x) = γ is independent of γ, whereas for γ ∈ F(H*) it is m at most. The particular case m = 1 provides several alternative sets of necessary and sufficient conditions for F to be a homeomorphism. Sufficient conditions were earlier provided by Fujisawa and Kuh. By one of our theorems equality of the signs of det A1 …, det Aq is necessary and sufficient for F to be a homeomorphism when at each point of H* the normals to the hyperplanes Hi ∈ H meeting at that point are linearly independent. Theorems for the local homeomorphism of F are provided as well. All the theorems on homeomorphism are also cast in the form of algorithms by which homeomorphism can be determined in practice.
Optimal Stopping for a Markov Process: A New Characterisation of the Optimal Policy
Authors: McNamara J. M.
Published: October 2008

This paper is concerned with optimal stopping for a continuous time (nonstationary) Markov process. The stopping problem is formulated in terms of a continuation cost with zero stopping cost.

A new characterisation of the optimal continuation region is given. This characterisation is then used to obtain further results about optimal stopping.
The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
Authors: Todd Michael J.
Published: October 2008

We exhibit a d-polytope P with n facets and a linear form ϕ such that all paths from a certain vertex of P to a ϕ-minimizing vertex that are nonincreasing in ϕ have length at least n − d + 1, provided d ≥ 4 and n − d ≥ 4. Indeed the discrepancy between the minimum length of such paths and n − d is at least min{[d/4], [(n − d)/4]} for some such polytope.
On the Generality of the Subadditive Characterization of Facets
Authors: Johnson Ellis L.
Published: October 2008

Gomory's characterization of facets of the group problem and Araoz's characterization for certain semigroups are shown to apply to a very general situation where only closure of the addition operation is assumed.
Relationships Between Some Notions Which are Common to Reliability Theory and Economics
Authors: Chandra Mahesh , Singpurwalla Nozer D.
Published: October 2008

Our objective in writing this paper is to point out some interesting relationships between the commonly referred to indices of economic inequality, and a central notion used in reliability theory. Specifically, we show that the “Lorenz curve” and the “Gini index” of economics are related to the “total time on test” and the “mean residual life” of reliability theory. An advantage of observing these relationships is that we are now able to consolidate knowledge that has independently evolved in two apparently diverse areas, and furthermore, we are able to: show that a recently proposed test for exponentiality based on the Gini index is identical to the one based on the total time on test; obtain some new inequalities for the Lorenz curve, the Gini index, and the “redundancy” (which is another measure of economic inequality); present some preservation properties for the Lorenz curve, which do not appear to be known; suggest that the Lorenz curve can be used to obtain a different interpretation of lifetime data; and characterize the limit of a class of lifetime distributions with decreasing failure rate in terms of its Lorenz curve.
Value Theory Without Efficiency
Authors: Dubey Pradeep , Neyman Abraham , Weber Robert James
Published: October 2008

A semivalue is a symmetric positive linear operator on a space of games, which leaves the additive games fixed. Such an operator satisfies all of the axioms defining the Shapley value, with the possible exception of the efficiency axiom. The class of semivalues is completely characterized for the space of finite-player games, and for the space pNA of nonatomic games.
An Exact Penalty Method for Mixed-Integer Programs
Authors: Blair C. E. , Jeroslow R. G.
Published: October 2008

It is shown that a norm penalty method is exact for mixed integer programs in rational data, in the sense that the minimization of the criterion plus penalty over the nonnegativities and integrality constraints has the same set of globally optimal solutions as does the mixed integer program with the equality constraints present. This result is then extended to mixed-integer programs with complementarity constraints.

An example shows that no differentiable penalty can be exact for mixed integer programs.
The System Point Method in Exponential Queues: A Level Crossing Approach
Authors: Brill P. H. , Posner M. J. M.
Published: October 2008

The purpose of this paper is to describe the new System Point method for analyzing queues. It considers the stationary probability distribution of the waiting time in variations of the M/M/R queue with first come first served discipline for a large class of service mechanisms. It is shown that the stationary probability density function of the waiting time evaluated at w > 0 can be interpreted as the long run average of the number of times that the virtual wait becomes less than w, per unit time. Theorems are presented which establish this interpretation of the probability density function of the virtual waiting time in terms of point processes generated by level crossings in the state space. These theorems, in combination with the principle of stationary set balance, generate a system of model equations that can be written directly. In addition, the forms of these equations are often linear Volterra integral equations of the second kind with parameter, which yield direct analytical solutions. An analogous theorem is proved for a variant of M/G/1. Two illustrative examples are presented.
Singular Games have Asymptotic Values
Authors: Neyman Abraham
Published: October 2008

The asymptotic value of a game v with a continuum of players is defined whenever all the sequences of Shapley values of finite games that “approximate” v have the same limit. In this paper we prove that if v is defined by v(S) = f(μ(S)), where μ is a nonatomic probability measure and f is a function of bounded variation on [0, 1] that is continuous at 0 and at 1, then v has an asymptotic value. This had previously been known only when v is absolutely continuous. Thus, for example, our result implies that the nonatomic majority voting game, defined by v(S) = 0 or 1 according as μ(S) ≤ 1/2 or μ(S) > 1/2, has an asymptotic value. We also apply our result to show that other games of interest in economics and political science have asymptotic values, and adduce an example to show that the result cannot be extended to functions f that are not of bounded variation.
Exponential Lower Bounds on a Class of Knapsack Algorithms
Authors: Hausmann Dirk , Kannan Ravindran , Korte Bernhard
Published: October 2008

The 0-1 knapsack problem is a well known NP-hard optimization problem. The proof of the generally believed hypothesis that there is no polynomial optimization algorithm for this problem would settle the famous NP ≠ P question.

We show here the nonexistence of a polynomial knapsack algorithm within the class of algorithms having restricted access to the input. Algorithms for the problem max{c(S): a(S) ≤ b, S ⊆ En} that can only check the sign of a(S) − b cannot have a better performance guarantee than the greedy algorithm; furthermore even if they can exploit the order of the densities ci/ai, 1 ≤ i ≤ n, or of the weights a(S), S ⊆ En, they cannot be guaranteed to find the optimum.
Scheduling Jobs with Exponential Processing and Arrival Times on Identical Processors so as to Minimize the Expected Makespan
Authors: van der Heyden Ludo
Published: October 2008

In this note we study a problem related to the scheduling of jobs on p identical processors (p ≥ 2). Jobs arrive randomly, interarrival times being exponentially distributed. The processing times are also exponential with mean drawn upon arrival from an arbitrary distribution function. Preemptions are allowed. The objective is to minimize the expected time until this M/G/p queuing system is first empty. We prove that an optimal policy processes jobs currently in the system in decreasing order of expected processing time.
Incomplete Information Games with Transcendental Values
Authors: Mertens Jean-François , Zamir Shmuel
Published: October 2008

In a repeated zero-sum two-person game with incomplete information on both sides, the asymptotic value is defined as v = limn→∞vn, where vn is the value of the game with n repetitions. It is shown here that v may be a transcendental number even for games in which all parameters defining the game are rational. This is in contrast to the situation in stochastic games where by the result of Bewley-Kohlberg (Bewley, T., E. Kohlberg. 1976. The asymptotic theory of stochastic games. Math. Oper. Res. 1 197–208.) v is algebraic. This indicates a fundamental difference between stochastic games and repeated games with incomplete information.
Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
Authors: Zemel Eitan
Published: October 2008

We point out the difficulties associated with measuring the quality of an approximate (heuristic) solution by “Percentage-Error” as is customary. We define a set of properties that are to be expected from a proper measure of solution quality and investigate the family of functions which satisfy those conditions. In particular, we show that for any class of 0–1 programming problems appropriate functions do exist and that they are uniquely defined up to monotone transformations. We conclude with several examples of linear functions which are suitable for certain classes of problems.
A Dynamic Programming Model of Fractional Flows with Application to Maintenance and Replacement Problems
Authors: Flynn James
Published: October 2008

This paper studies a deterministic dynamic programming model of fractional flows in an n-sector system, characterizing its solutions under general conditions, and developing algorithms for their computation. The calculations that the latter entail are not much more difficult than those needed for an n-state Markovian decision process (in certain restrictive cases, the model is “isomorphic” to an n-state MDP). Some of our results extend to a stochastic model as a “certainty equivalence.” Applications include a maintenance/replacement/sales model, a manpower retention model that extends Flynn (Flynn, J. 1970. Linear Production Models with Incentives: A Dynamic Programming Approach. Ph.D. dissertation, University of California, Berkeley; Flynn, J. 1975. Retaining productive units: A dynamic programming model with a good steady state solution. Management Sci. 21 753–764.), Grinold-Stanford (Grinold, R., R. Stanford. 1974. Optimal control of a graded manpower system. Management Sci. 8 1201–1216.) and Stanford (Stanford, R. 1976. Analytical solution of a dynamic transaction. Math. Programming 10 214–229.), and a constrained version of Pliska’s (Pliska, S. 1976. Optimization of multitype branching processes. Management Sci. 23 117–124.) branching model.
Cores of Nonatomic Linear Production Games
Authors: Billera Louis J. , Raanan Joseph
Published: October 2008

Cores of games of the form f ∘ μ, where μ is a vector of nonatomic measures and f(z) = max{〈c, x〉 ∣ xA ≤ z, x ≥ 0} or, equivalently, f(z) = min〈z, ai〉, are described in terms of μ and the data defining f. Along the way, we give a general condition on a game which implies that each measure in its core is a linear combination of a fixed finite set of nonatomic measures.
Proximal Subgradients, Marginal Values, and Augmented Lagrangians in Nonconvex Optimization
Authors: Rockafellar R. T.
Published: October 2008

The Clarke subgradients of a nonconvex function p on Rn are characterized in terms of limits of “proximal subgradients.” In the case where p is the optimal value function in a nonlinear programming problem depending on parameters, proximal subgradients correspond to saddlepoints of the augmented Lagrangian. When the constraint and objective functions are sufficiently smooth, this leads to a characterization of marginal values for a given problem in terms of limits of Lagrange multipliers in “neighboring” problems for which the standard second-order sufficient conditions for optimality are satisfied at a unique point.
A Vector-Sum Theorem and its Application to Improving Flow Shop Guarantees
Authors: Bárány Imre
Published: October 2008

We prove that if a closed polygonal path in Rd consists of a finite number of line segments of at most unit length, then it is possible to transpose the segments in such a way that the new polygonal path is contained in a ball of radius [[Formula: see text]]. Using this result we give a near optimal algorithm for the NP-complete flow shop problem. The error of the algorithm cannot exceed a constant depending on the maximal execution time and the number of machines but not depending on the number of jobs. Our theorems improve earlier results of the same type by Belov and Stolin.
Equivalence of Nonlinear Complementarity Problems and Least Element Problems in Banach Lattices
Authors: Riddell R. C.
Published: October 2008

A class of not necessarily linear operators A: V → V* is introduced, where the Banach space V and its dual V* carry dual vector-lattice orderings ≥. These operators, called Z-maps, generalize the n × n real matrices with nonnegative off-diagonal elements. If A is a strictly monotone Z-map with certain regularity and growth conditions, and if ℱ denotes the set of all vectors v ∈ V for which v ≥ 0, and A(v) ≥ 0, then it is shown that the complementarity problem, to find v ∈ ℱ such that 〈A(v), v〉 = 0, and the least element problem, to find v ∈ ℱ with v ≤ w for all w ∈ ℱ, have the same unique solution. Some other problems equivalent to these, and some examples are discussed.
Convergence of Dynamic Programming Models
Authors: Langen Hans-Joachim
Published: October 2008

Weak conditions are presented for approximating dynamic programming models. For a sequence of these models, continuous convergence of the sequence of associated optimal value functions is obtained under the condition that state and action space converge in the sense of Kuratowski, and that the mappings of admissible actions as well as the transition law, the discount factors and the reward functions converge continuously. Further a relation for the associated sets of optimal actions is given. The analysis is based on results about convergence preserving properties of supremum value functions and integrals. The approximation results are extended to so-called upper-semi-continuous convergent sequences and are related to discretization procedures by using projections.
A New Look at the Existence of P-Optimal Policies in Dynamic Programming
Authors: Balder E. J.
Published: October 2008

A new look at a class of existence results in dynamic programming under the expected utility—or p̄-optimality—criterion is afforded by embedding the policies in an abstract L∞-space (Balder, E. J. 1979. On a useful compactification for optimal control theory. J. Math. Anal. Appl. 72 391–398; Balder, E. J. 1981. Relaxed inf-compactness for variational problems by Hilbert cube compactification. J. Math. Anal. Appl. 79 1–12; Balder, E. J. 1981. Lower semicontinuity of integral functionals with nonconvex integrands by relaxation-compactification. SIAM J. Control Optim. 19 533–542.). The results obtained in this way form a generalization of (Schäl, M. 1975. On dynamic programming: Compactness of the space of policies. Stochastic Processes Appl. 3 345–364, §5).
Distribution of the Interoverflow Time for the GI/G/1 Loss System
Authors: Halfin S.
Published: October 2008

We derive the distribution of the time between overflows (losses) for the GI/G/1 loss system in equilibrium. The resulting arrivals-overflows relation can be iterated n times to obtain an approximation (which is exact for exponential service times) for the overflow process from the GI/G/n loss system. Applications to the MG/G/1 and GI/Ek/1 loss systems are presented.
Approximate Labelling for Simplicial Algorithms and Two Classes of Special Subsets of the Sphere
Authors: Todd Michael J.
Published: October 2008

Call a subset of Rn complete if the origin is in its convex hull. We are concerned with the construction of large finite sets of points on the unit sphere whose complete subsets are, in some sense, easy to describe. Our motivation comes from simplicial algorithms for approximating zeroes of functions. We construct two classes of such subsets of the sphere, both of which generalize a subset that corresponds to usual integer labelling.
Conjugate Relations and Weak Subdifferentials of Relations
Authors: Kawasaki Hidefumi
Published: October 2008

The duality theory for convex programs is based on a concept “conjugate” of functions, and the set of solutions is characterized by “subdifferential” of a function. The purpose of this paper is to extend the concepts “conjugate” and “subdifferential” to those of set-valued functions (relations) and to investigate their properties.
Brownian Excursion, the M/M/1 Queue and Their Occupation Times
Authors: Cohen J. W. , Hooghiemstra G.
Published: October 2008

The one- and two-dimensional distributions of the occupation time and of the local time of Brownian excursion are derived. These results follow from a suitable conditioned weak limit theorem. More specifically we shall prove that the normalized virtual waiting time process of the M/M/1 queue, conditioned by the length of its first busy period, weakly converges to the Brownian excursion process. At the end of this paper we shall discuss the connection between the local time of the Brownian excursion process and the number of downcrossings during the first busy period of an M/G/1 queue. This connection seems to be very interesting for the theory of branching processes.
On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N Person Games
Authors: van der Laan G. , Talman A. J. J.
Published: October 2008

In this paper an algorithm based on the principle of simplicial approximation is introduced to compute fixed points of upper semicontinuous point to set mappings from the product space S of unit simplices into itself. The algorithm is a modification of an algorithm, introduced in an earlier paper. The main feature is that it starts with an arbitrary chosen point in S and that the triangulation of S depends on the starting point. Moreover, the algorithm can terminate with a non-full-dimensional subsimplex, yielding a good approximation. An application is given for non cooperative n person games, where S is the strategy space. Some computational experiences are given.
Minimax Policies for Unobservable Inspections
Authors: Diamond Harvey
Published: October 2008

On a finite closed lime interval an inspector wishes lo detect an event as soon as possible after its occurrence. A loss f(d) is incurred if the event remains undetected for a period d. Generally, f is assumed continuous and monotone increasing. Exactly N inspections are allowed. We seek a randomized inspection policy yielding the minimax expected loss. The problem is reformulated as a two-person zero-sum game between the inspector and an inspectee and a pair of equilibrium strategies is sought. An explicit solution for the linear case, f(d) = d is obtained and its asymptotic properties (N large) determined. A computational procedure for calculating the optimal policies in the nonlinear case is presented. Two additional related games are briefly treated. The optimal inspection policies each have the salient property of being a randomization over a one parameter family of pure strategies.
Optimal Behavioral Strategies In 0-Sum Games with Almost Perfect Information
Authors: Ponssard Jean-Pierre , Sorin Sylvain
Published: October 2008

This paper provides the general construction of the optimal strategies in a special class of zero sum games with incomplete information, those in which the players move sequentially. It is shown that at any point of the game tree, a player's optimal behavioral strategy may be derived from a state variable involving two components: the first one keeps track of the information he revealed, the second one keeps track of the (vector) payoff he should secure over his opponent's possible position. This construction gives new insights on earlier results obtained in the context of sequential repeated games. Several examples are discussed in detail.
A Remark on Search and Sequencing Problems
Authors: Kelly F. P.
Published: October 2008

It is shown that a variety of sequential optimization problems can be expressed as special cases of an elementary search model.
Allocation of Shared Costs: A Set of Axioms Yielding A Unique Procedure
Authors: Billera Louis J. , Heath David C.
Published: October 2008

Often when several goods or services are produced by a common process or organization some estimate of the per-unit costs of these goods is required. In this note we consider cost allocation procedures and show that there is exactly one such procedure which possesses four desirable properties. Both the methods and the result were inspired by the recent work of Aumann and Shapley on nonatomic games.
Demand Compatible Equitable Cost Sharing Prices
Authors: Mirman Leonard J. , Tauman Yair
Published: October 2008

We propose here a new approach for equitable cost sharing pricing based upon the Shapley value for nonatomic games. However, it is shown that the proposed price mechanism can be justified on economic terms since it is uniquely determined by a set of axioms involving only cost functions and quantities consumed and not any notion of game theory. Moreover, taking into account the utilities of the consumers, one can prove the existence of an equilibrium under this price mechanism for a general class of cost functions. This approach has the advantage of not involving any interpersonal comparisons of utilities.
Unit Execution Time Shop Problems
Authors: Gonzalez Teofilo
Published: October 2008

The problem of preemptively (and nonpreemptively) scheduling a set of n independent jobs on an m machine open shop, flow shop or job shop is studied. It is shown that the problem of constructing optimal mean finishing time preemptive and nonpreemptive schedules is NP-hard. These problems are not only NP-hard in the strong sense, but remain NP-hard even when all nonzero tasks have identical execution time requirements. These results will also apply to the case when the problem is to construct an optimal finish time preemptive and nonpreemptive schedule for a flow shop or a job shop. We also discuss the problem of constructing no-wait schedules for these problems.
Existence of Limiting Distributions in the GI/G/s Queue
Authors: Whitt Ward
Published: October 2008

A new proof is given for the Kiefer-Wolfowitz (Kiefer, J., J. Wolfowitz. 1955. On the theory of queues with many servers. Trans. Amer. Math. Soc. 78 1–18.) theorem: In the GI/G/s queue the sequence of workload vectors, and thus also the sequence of waiting times, has a proper limiting distribution independent of the initial conditions if and only if p < 0.1 (assuming the interarrival times and service times have finite means). From stochastic monotonicily, convergence is easy to establish if the system starts off empty. The limit is shown lo be proper here by bounding the standard FCFS system by the corresponding s-server system with a cyclic assignment discipline, using a recent construction of Wolff (Wolff, R. W. 1977. An upper bound for multi-channel queues. J. Appl. Probab. 14 884–888.). The general initial condition case is treated by appropriately bounding the original sequence above and below by sequences of countable-state Markov chains for which zero is always a regenerative state. This paper thus illustrates how recent stochastic comparison and continuity results can be applied to prove limit theorems. The bounding systems are also of special interest in regenerative simulation because they provide a way lo increase the number of regeneration points.
A Duality Theorem in Multiobjective Nonlinear Programming
Authors: Kawasaki Hidefumi
Published: October 2008

We give a duality theorem in multiobjective nonlinear programming problems by means of conjugate set-valued functions which were introduced in (Kawasaki, H. 1981. Conjugate relations and weak subdifferentials of relations. Math. Oper. Res. 6 593–607.). The duality theorem is reflexive in the sense analogous to (Ekeland, I., R. Temam. 1976. Convex Analysis and Variational Problems. North-Holland, Amsterdam.).
The Contraction Mapping Approach to the Perron-Frobenius Theory: Why Hilbert's Metric?
Authors: Kohlberg Elon , Pratt John W.
Published: October 2008

The Perron-Frobenius Theorem says that if A is a nonnegative square matrix some power of which is positive, then there exists an x0 such that Anx/‖Anx‖ converges to xn for all x > 0. There are many classical proofs of this theorem, all depending on a connection between positively of a matrix and properties of its eigenvalues. A more modern proof, due to Garrett Birkhoff, is based on the observation that every linear transformation with a positive matrix may be viewed as a contraction mapping on the nonnegative orthant. This observation turns the Perron-Frobenius theorem into a special ease of the Banach contraction mapping theorem. Furthermore, it applies equally to linear transformations which are positive in a much more general sense.

The metric which Birkhoff used to show that positive linear transformations correspond to contraction mappings is known as Hilbert's projective metric. The definition of this metric is rather complicated. It is therefore natural to try to define another, less complicated metric, which would also turn positive matrices into contractions. The main result of this paper is that, essentially, this is impossible.

The paper also gives some other results of possible interest in themselves, as well as enough background to make the presentation self-contained.
The Generalized Quasi-Variational Inequality Problem
Authors: Chan D. , Pang J. S.
Published: October 2008

In this paper, we introduce the generalized quasi-variational inequality problem and develop a theory for the existence of solution. This new problem includes as special cases two existing generalizations of the classical variational inequality problem. Relationship with a certain implicit complementarity problem is also studied.
Dimensional Reduction Variant of the Ellipsoid Algorithm for Linear Programming Problems
Authors: Jones Philip C. , Marwil Earl S.
Published: October 2008

A technique for dimensional reduction is combined with the ellipsoid algorithm and another acceleration technique lo solve linear programming problems. The new method yields exact rather than approximate solutions and provides a natural procedure for determining infeasibility.
On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
Authors: Todd Michael J.
Published: October 2008

We give formulae for minimum volume ellipsoids that contain one-sided or two-sided cuts of a given ellipsoid. These formulae may be of use in the recent ellipsoid algorithms for convex and linear programming.
Projection in Certain Spaces of Set Functions
Authors: Ruckle William H.
Published: October 2008

Let (I, 𝒞) denote a measurable space which is isomorphic to the space ([0, 1], ℬ) where ℬ denotes the collection of Borel subsets of [0, 1]. The space BV consists of all real valued functions u on 𝒞 of the form u = u+ − u− where u+ and u− are increasing. It is first shown that BV is a dual space. We use this fact to establish the existence of a linear mapping T from BV onto FA (finitely additive set functions) which is positive, efficient and satisfies a weak form of symmetry, namely in variance under a semigroup of automorphisms of (I, 𝒞).
On Hart Production Games
Authors: Muto Shigeo
Published: October 2008

Some symmetric n-person games which reflect simple production economies were presented by Hart in (Hart, S. 1973. Symmetric solutions of some production economies. Internat. J. Game Theory 2 53–62.). Some unsolved problems about symmetric solutions (or stable sets) for these games are investigated.
Renewal Plans and Persistent Optimality in Countably Additive Gambling
Authors: Kertz Robert P.
Published: October 2008

In countably additive gambling models with general utility functions, plans for play are constructed which persist in being conditionally ϵ-optimal along every history and which are conditionally optimal whenever possible. Such plans are formed by piecing together plans which are known to be good for the gambler at single time periods. Verification of the optimality properties of these plans uses transient renewal theoretic arguments.
Restricted Primitive Sets and Simplicial Subdivisions with Arbitrary Refinement Factors
Authors: Van der Heyden Ludo
Published: October 2008

We discuss the implementation of a refinement procedure for fixed point computations using Scarf's primitive sets. The procedure, presented in Van der Heyden (Van der Heyden, L. 1982. A Refinement procedure for computing fixed points using Scarf's primitive sets. Math. Oper. Res. 7 295–313.), moves between combinatorial objects called restricted primitive sets. We characterize restricted primitive sets when the vectors in these sets belong to a sequence of regular grids with increasing grid sizes. The refinement factor between successive grids is an arbitrary integer. These restricted primitive sets are associated with a set of easily implementable rules which guide the movement of the refinement procedure. We also present a geometrical interpretation of these restricted sets in terms of simplicial subdivisions.
On Sufficient Conditions in Nonsmooth Optimization
Authors: Chaney R. W.
Published: October 2008

Second-order conditions are given which are sufficient for a point to be a local minimizer for certain nonlinear programming problems defined on Banach spaces. The functions involved in the problems are not required to be smooth or convex; indeed, they are required only to satisfy certain conditions which are weak enough to be satisfied by all locally Lipschitzian functions. The sufficiency conditions are expressed in terms of Clarke generalized gradients (as extended by Rockafellar). An account is given of the connections between these results and some earlier sufficiency theorems.
Totally Balanced Games and Games of Flow
Authors: Kalai Ehud , Zemel Eitan
Published: October 2008

A class of characteristic function games arising from maximum flow problems is introduced and is shown to coincide with the class of totally balanced games. The proof relies on the max flow-min cut theorem of Ford and Fulkerson and on the observation that the class of totally balanced games is the span of the additive games with the minimum operation.
Inconsistencies of Weighted Summation Voting Systems
Authors: Saari Donald G.
Published: October 2008

Let αN be any ordinal ordering of N ≥ 3 alternatives. Select some one alternative and let αN−1 be some ordering of the remaining (N − 1) alternatives where αN−1, need not have any relationship to αn. It is shown for a voting system coming from a large class of weighted summation voting systems that there exist examples of voter profiles such that if the voters vote on N alternatives the aggregated result is αN, but if they vote on (N − 1) alternatives, the aggregated result is αN−1. This result holds even if the voting system changes with the number of alternatives.
Games with No Solutions and Empty Cores
Authors: Lucas W. F. , Rabie M.
Published: October 2008

Rather general existence theorems are known for two of the three classical models in game theory. These include the theorems by J. von Neumann and J. F. Nash on the existence of equilibria for 2-person, zero-sum and n-person, general-sum games in normal (strategic) form; as well as the theorems on information and the nature of optimal strategies by E. Zermelo, H. W. Kuhn, N. N. Vorob'ev and G. L. Thompson for games in extensive (tree) form. This paper discusses the lack of a general existence theorem for the von Neumann-Morgenstern theory of solutions (stable sets) for their multiperson cooperative games in characteristic function (coalitional) form. In particular, it demonstrates that there are games of 14 or more players for which no such solution exists, and for which the core (an alternate solution concept) is the empty set.
Duality and Pricing in Multiple Right-Hand Choice Linear Programming Problems
Authors: Granot Daniel , Granot Frieda , Johnson Ellis L.
Published: October 2008

The main problem studied in this paper is a linear programming problem with multiple right-hand choice of the form Min{cx ∣ x ≥ 0, Ax ≥ b for some b ∈ B}, where B is a finite subset of Rm. The dual to the above problem is introduced to be of the form Max{Minb∈B π(b) ∣ π(A) ≤ c, π ∈ p}, where P is the collection of all subadditive, positively homogeneous and monotone functions from Rm to the extended real line. We prove that the above pair of problems satisfy both weak and strong duality, and provide necessary and sufficient conditions for strong duality to hold when the dual functions π are restricted to be linear.

It is shown that the class of functions P arises naturally even in linear programming, i.e., when |B| = 1. Indeed, linear functions will not suffice for pricing functions in a degenerate linear programming problem. In fact, in this case the pricing function p is piecewise linear, superadditive and positively homogeneous and thus concave, i.e., −p ∈ P. On the other hand, we show that the pricing function of the multiple right-hand choice linear program is not necessarily concave. This indicates the difficulties of pricing in integer programming. Finally, a more symmetric pair of dual problems is introduced, and duality relationship between the two problems is studied.
Renewal Decisions when Category Life Distributions are of Phase-Type
Authors: Assaf David
Published: October 2008

A system must operate for t units of time. A certain component is essential for the operation of the system and must be replaced by a new component whenever it fails. There are n types of replacement categories available (with an infinite supply of each) differing only in price and life distribution. The main problem is to select the proper category for replacement at any time a failure occurs, so as to minimize the total expected cost of running the system.

In this paper the problem is studied when category life distributions have a common matrix phase type representation. The generalized Erlang and the hyperexponential distributions, as well as coherent structures of the latter distributions, are some special cases of this representation. Our main result is that in many of these cases, the problem of finding an optimal replacement policy is reduced to that of determining a specified number (at most n − 1) of points on the real time axis. Also provided is a condition for identifying categories which should never be used, thus reducing the problem by eliminating them. This work generalizes previous results obtained when all category life distributions were assumed exponential. Several illustrative examples are provided.
Moment-Preserving Shifts and Stochastic Dominance
Authors: Fishburn Peter C.
Published: October 2008

Let Mn be the set of signed measures on the line with nonempty finite supports whose first n − 1 moments vanish and which satisfy a specified positivity condition. Let Mn* be the minimum-support measures in Mn. Then Mn is the convex cone spanned by Mn* if n ≤ 3 but not if n ≥ 4.
Erratum
Authors: Lawler E. L. , Lenstra J. K. , Rinnooy Kan A. H. G.
Published: October 2008

In §3 of (Lawler, E. L., J. K. Lenstra, A. H. G. Rinnooy Kan. 1981. Minimizing maximum lateness in a two-machine open shop. Math. Oper. Res. 6 153–158.) we have given an erroneous proof of the fact that the problem of minimizing maximum lateness in a two-machine open shop when no preemptions are allowed is NP-hard.
An Algorithm for the Open-Shop Problem
Authors: Fiala Tibor
Published: October 2008

The open-shop problem is known to be NP-complete. However we give an algorithm, which solves the problem in polynomial time, whenever the sum of execution times for one processor is large enough with respect to the maximal execution time. According to the schedule given by our algorithm one of the processors works without idle time. Construction of this schedule is based on a suitable generalization of several “integer-making” techniques.
Convergence Rates of the Ellipsoid Method on General Convex Functions
Authors: Goffin Jean-Louis
Published: October 2008

The ellipsoid method is applied to the unconstrained minimization of a general convex function. The method converges at a geometric rate, which depends only upon the dimension of the space but not on the actual function. This rate can be improved somewhat if the function satisfies some Lipschitz-type condition, or if the minimum set has dimension greater than zero. If the ellipsoid entirely contains the optimal set, equating the Steiner polynomial associated to the optimal set, and the volume of the ellipsoid at a given iteration, will give an upper bound on the minimum recorded function value.
Smoothed Functionals in Stochastic Optimization
Authors: Rubinstein R. Y.
Published: October 2008

We consider the problem of finding a global extremum for a nonconvex function by constructing another smoothed function, which has a better “behavior” than the original one. Then, operating only with the smoothed function, we find the global extremum for the original function.
Extreme Points of Certain Sets of Probability Measures, with Applications
Authors: Karr Alan F.
Published: October 2008

Let K be the set of probability measures on a metric space having prescribed values for the integrals of (a finite number of) prescribed functions fi. Extreme points of K are characterized in general. Under a restriction on the fi extreme points and more general faces of K are characterized. Applications to inverse balayage problems, measures with prescribed moments or values of Laplace transforms, measures with prescribed marginal distributions and the queueing system GI/M/1 are presented.
Interpretation of a Variable Dimension Fixed Point Algorithm with an Artificial Level
Authors: Laan G. van der , Talman A. J. J.
Published: October 2008

In this paper two interpretations of the variable dimension algorithm to compute a fixed point of a continuous function from the product space S of simplices into itself, introduced in an earlier paper, are given. The first interpretation yields a subdivision, whereas the second one yields a triangulation of the convex hull of the set S on the natural level and some set on the artificial level. After labelling the vertices of the latter set in such a way that this set is completely labelled, a path of adjacent polyhedra (or simplices) can be generated with common completely labelled facets starting with the set on the artificial level and terminating with a completely labelled simplex on the natural level yielding an approximate fixed point. The intersection of the path with this level is the sequence of the simplices of variable dimension of the algorithm. So, the algorithm can be viewed as tracing zeroes of a piecewise linear homotopy function.
A Superlinearly Convergent Algorithm for One-Dimensional Constrained Minimization Problems with Convex Functions
Authors: Mifflin Robert
Published: October 2008

This paper presents a globally and superlinearly convergent algorithm for solving one-dimensional constrained minimization problems involving (not necessarily smooth) convex functions. The constraint is handled by what can be interpreted as a new type of penalty method. The algorithm does not require the objective function to be evaluated at infeasible points and it does not use constraint function values at feasible points. The penalty parameter is automatically generated by the algorithm via linear approximation of the constraint function. As in the unconstrained case developed by Lemarechal and the author, the algorithm uses a step that is the shorter of a quadratic approximation step and a polyhedral approximation step. Here the latter is actually a “penalized” polyhedral step whose computation is well conditioned if the constraint satisfies a nondegeneracy assumption.
Nonconvexities in Univalence
Authors: Zangwill W. I.
Published: October 2008

When a mapping is univalent (one-to-one) on a set is a question which has received considerable study. Much of the recent research has focused on the shape of the set on which the mapping is defined. It has been suggested, in fact, that the set must be convex for univalence to hold. This paper presents conditions under which the set need not be convex. We demonstrate first that the set can be diffeomorphic to a convex set and, second, that the set can have holes inside of it. These somewhat surprising results differ from previous results in that they depend not only upon the Jacobian, but also upon the function value. To provide further insight, we also examine the underlying geometry of the situation.
A Unique Bargaining Solution Based on Competitive Commitments
Authors: Sussangkarn Chal
Published: October 2008

In this paper, a bargaining solution is defined based on the ability of bargainers to commit themselves to various minimum utility levels. The solution is descriptive rather than axiomatic. Bargainers must spend resources for commitments, and they argue about the respective merits of the various outcomes, making objections and counterobjections. The solution is based on Aumann and Maschler’s bargaining set for cooperative games in characteristic function form. Existence and uniqueness (in utilities) are shown using assumptions weak enough to be satisfied in most applications. The solution is illustrated by a simple example.
Strong and Weak Convexity of Sets and Functions
Authors: Vial Jean-Philippe
Published: October 2008

In this paper we study two classes of sets, strongly and weakly convex sets. For each class we derive a series of properties which involve either the concept of supporting ball, an obvious extension of the concept of supporting hyperplane, or the normal cone to the set. We also study a class of functions, denoted ρ-convex, which satisfy for arbitrary points x1 and x2 and any value λ ∈ [0, 1] the classical inequality of convex functions up to a term ρ(1 − λ) λ‖x1 − x2‖2. Depending on the sign of the constant ρ the function is said to be strongly or weakly convex. We provide characteristic properties of this class of sets and we relate it to strongly and weakly convex sets via the epigraph and the level sets. Finally, we give three applications: a separation theorem, a sufficient condition for global optimum of a nonconvex programming problem, and a sufficient geometrical condition for a set to be a manifold.
Gambling Problems with a Limit Inferior Payoff
Authors: Sudderth William D.
Published: October 2008

In the gambling theory of Dubins and Savage, the payoff from a sequence of states is the limit superior of their utilities. Here the limit inferior is used instead. For example, if the utility function is the indicator of a set G, then the Dubins and Savage payoff is 1 when infinitely many states are in G, while the payoff here is 1 when all but finitely many states are in G. There are some resulting changes in the theory, but it remains true that optimal stationary plans exist for finite problems.
Complete Closedness of Maximal Monotone Operators
Authors: Qi Liqun
Published: October 2008

(This paper is dedicated to the memory of Professor Kwan Chao-Chin, former academic member and director of the Institute of System Science of the Academy of Chinese Sciences.) A maximal monotone operator in Rn is completely closed, i.e., not only closed for points, but also closed for directions. Such a completely closed operator is locally bounded at a point if and only if it is bounded at that point.
The Fair Division of a Fixed Supply Among a Growing Population
Authors: Thomson William
Published: October 2008

We reconsider the traditional problem of fair division. Division principles should be general enough to accommodate changes in what is to be divided as well as variations in the number of agents among whom the division is to take place. In the usual treatment of the question, this number is assumed to be fixed. Here, we explicitly allow it to vary.

Agents are assumed to have von Neumann–Morgenstern utility functions and division problems are defined as subsets of the utility space. Our approach is axiomatic. Apart from the familiar axioms of Pareto-optimality, scale invariance, continuity and anonymity, we formulate and impose an axiom of monotonicity with respect to changes in the number of agents, stating that if sacrifices have to be made to support an additional agent, then everybody should contribute. There is a unique division principle that satisfies them all: it is the natural extension to the n-person case of the two-person solution proposed by Kalai and Smorodinsky.
Impulse Control of Brownian Motion
Authors: Harrison J. Michael , Sellke Thomas M. , Taylor Allison J.
Published: October 2008

Consider a storage system, such as an inventory or cash fund, whose content fluctuates as a (μ, σ2) Brownian motion in the absence of control. Holding costs are continuously incurred at a rate proportional to the storage level and we may cause the storage level to jump by any desired amount at any time except that the content must be kept nonnegative. Both positive and negative jumps entail fixed plus proportional costs, and our objective is to minimize expected discounted costs over an infinite planning horizon. A control band policy is one that enforces an upward jump to q whenever level zero is hit, and enforces a downward jump to Q whenever level S is hit (0 < q < Q < S). We prove the existence of an optimal control band policy and calculate explicitly the optimal values of the critical numbers (q, Q, S).
Polychromatic Acyclic Tours in Colored Multigraphs
Authors: Blair Douglas H. , Pollak Robert A.
Published: October 2008

We present two graph-theoretic propositions in this paper that provide the basis for a result paralleling Arrow’s (Arrow, K. J. 1963. Social Choice and Individual Values. 2nd ed. Yale University Press, New Haven.) impossibility theorem.
Erratum
Authors: Anderson E. J. , Nash P. , Philpott A. B.
Published: October 2008

In (Anderson, E. J., P. Nash, A. B. Philpott. 1982. A class of continuous network flow problems. Math. Oper. Res. 7 501–514, §5), we state two corollaries to a continuous maximum flow-minimum cut theorem. The second corollary is incorrect, owing to an implicit assumption that the optimal cut is unique.