bluuebunny/crossref_metadata_2025 huggingface dataset:
A Relational View of Information Seeking and Learning in Social Networks
Authors: Borgatti Stephen P. , Cross Rob
Published: December 2003

Research in organizational learning has demonstrated processes and occasionally performance implications of acquisition of declarative (know-what) and procedural (know-how) knowledge. However, considerably less attention has been paid to learned characteristics of relationships that affect the decision to seek information from other people. Based on a review of the social network, information processing, and organizational learning literatures, along with the results of a previous qualitative study, we propose a formal model of information seeking in which the probability of seeking information from another person is a function of (1) knowing what that person knows; (2) valuing what that person knows; (3) being able to gain timely access to that person's thinking; and (4) perceiving that seeking information from that person would not be too costly. We also hypothesize that the knowing, access, and cost variables mediate the relationship between physical proximity and information seeking. The model is tested using two separate research sites to provide replication. The results indicate strong support for the model and the mediation hypothesis (with the exception of the cost variable). Implications are drawn for the study of both transactive memory and organizational learning, as well as for management practice.
Learning Negotiation Skills: Four Models of Knowledge Creation and Transfer
Authors: Nadler Janice , Thompson Leigh , Boven Leaf Van
Published: December 2003

Our review of the learning and training literature revealed four common methods for training people to be more effective negotiators: didactic learning, learning via information revelation, analogical learning, and observational learning. We tested each of these methods experimentally in an experiential context and found that observational learning and analogical learning led to negotiated outcomes that were more favorable for both parties, compared to a baseline condition of learning through experience alone. Information revelation and didactic learning were not significantly different from any other condition. Process measures revealed that negotiators’ schemas about the task (reflected in open-ended essays) were strong predictors of performance in the analogical learning condition, but were poor predictors of performance in the remaining conditions. Interestingly, negotiators in the observation group showed the largest increase in performance, but the least ability to articulate the learning principles that helped them improve, suggesting that they had acquired tacit knowledge that they were unable to articulate.
Newsvendor Bounds and Heuristic for Optimal Policies in Serial Supply Chains
Authors: Shang Kevin H. , Song Jing-Sheng
Published: December 2003

We consider the classic N-stage serial supply systems with linear costs and stationary random demands. There are deterministic transportation leadtimes between stages, and unsatisfied demands are backlogged. The optimal inventory policy for this system is known to be an echelon base-stock policy, which can be computed through minimizing N nested convex functions recursively. To identify the key determinants of the optimal policy, we develop a simple and surprisingly good heuristic. This method minimizes 2Nseparate newsvendor-type cost functions, each of which uses the original problem data only. These functions are lower and upper bounds for the echelon cost functions; their minimizers form bounds for the optimal echelon base-stock levels. The heuristic is the simple average of the solution bounds. In extensive numerical experiments, the average relative error of the heuristic is 0.24%, with the maximum error less than 1.5%. The bounds and the heuristic, which can be easily obtained by simple spreadsheet calculations, enhance the accessibility and implementability of the multiechelon inventory theory. More importantly, the closed-form expressions provide an analytical tool for us to gain insights into issues such as system bottlenecks, effects of system parameters, and coordination mechanisms in decentralized systems.
The Importance of Ordering in Sequential Auctions
Authors: Elmaghraby Wedad
Published: December 2003

To date, the largest part of literature on multi-unit auctions has assumed that there are k homogeneous objects being auctioned, where each bidder wishes to win exactly one or all of k units. These modeling assumptions have made the examination of ordering in sequential auctions inconsequential. The aim of this paper is to introduce and highlight the critical influence that ordering can have on the efficiency of an auction. We study a buyer who outsources via sequential 2nd-price auctions two heterogeneous jobs, and faces a diverse set of suppliers with capacity constraints.
A Threshold Inventory Rationing Policy for Service-Differentiated Demand Classes
Authors: Deshpande Vinayak , Cohen Morris A. , Donohue Karen
Published: December 2003

Motivated by a study of the logistics systems used to manage consumable service parts for the U.S. military, we consider a static threshold-based rationing policy that is useful when pooling inventory across two demand classes characterized by different arrival rates and shortage (stockout and delay) costs. The scheme operates as a (Q, r) policy with the following feature. Demands from both classes are filled on a first-come-first-serve basis as long as on-hand inventory lies above a threshold levelK. Once on-hand inventory falls below this level, low-priority (i.e., low shortage cost) demand is backordered while high-priority demand continues to be filled. We analyze this static policy first under the assumption that backorders are filled according to a special threshold clearing mechanism. Structural results for the key performance measures are established to enable an efficient solution algorithm for computing stock control and rationing parameters (i.e.,Q, r, andK). Numerical results confirm that the solution under this special threshold clearing mechanism closely approximates that of the priority clearing policy. We next highlight conditions where our policy offers significant savings over traditional “round-up” and “separate stock” policies encountered in the military and elsewhere. Finally, we develop a lower bound on the cost of the optimal rationing policy. Numerical results show that the performance gap between our static threshold policy and the optimal policy is small in environments typical of the military and high-technology industries.
Mode Locking and Chaos in a Deterministic Queueing Model with Feedback
Authors: Haxholdt Christian , Larsen Erik R. , van Ackere Ann
Published: December 2003

We consider a simple, deterministic queueing system with feedback, which exhibits the phenomena of sustained oscillation, mode locking, quasi-periodic behaviour, and chaos. This implies that a fully deterministic queueing system can exhibit seemingly unpredictable behaviour. We ignore variability, and focus on two forms of feedback: (i) the service rate increases as queue length increases, and (ii) the arrival rate depends on customers' perception of past waiting times. We model a customer's decision to seek service as a two stage process: (i) deciding whether or not to use a facility, and (ii) deciding the frequency of visit (daily, weekly, monthly, etc.). This frequency is initially constant, and later on replaced by a deterministic, time-dependent pattern. Although highly stylised, this model captures the essential features of many real-life systems whose average arrival rate varies over time. Reducing the amplitude of cycles in demand makes the system more predictable and thus easier to manage. Although we represent this model as a queue of customers waiting for service, the model can be interpreted more generally as any situation where an increase in demand lowers the quality of service.
Computing Power Indices for Large Voting Games
Authors: Leech Dennis
Published: December 2003

Voting power indices enable the analysis of the distribution of power in a legislature or voting body in which different members have different numbers of votes. Although this approach to the measurement of power has been known for a long time, its application to large games has been limited by the difficulty of computing these indices. This paper presents a new method for computing power indices that combines exact methods with an approximate method due to Owen. This method is of most utility in situations where the number of players is large and the voting weights are concentrated in the hands of a small number of members.
Gatekeepers and Referrals in Services
Authors: Shumsky Robert A. , Pinker Edieal J.
Published: December 2003

This paper examines services in which customers encounter a gatekeeper who makes an initial diagnosis of the customer's problem and then may refer the customer to a specialist. The gatekeeper may also attempt to solve the problem, but the probability of treatment success decreases as the problem's complexity increases. Given the costs of treatment by the gatekeeper and the specialist, we find the firm's optimal referral rate from a particular gatekeeper to the specialists. We then consider the principal–agent problem that arises when the gatekeeper, but not the firm, observes the gatekeeper's treatment ability as well as the complexity of each customer's problem. We examine the relative benefits of compensation systems designed to overcome the effects of this information asymmetry and show that bonuses based solely on referral rates do not always ensure first–best system performance and that an appropriate bonus based on customer volume may be necessary as well. We also consider the value of such output–based contracts when gatekeepers are heterogeneous in ability, so that two gatekeeper types face different probabilities of treatment success when given the same problem. We show that the firm may achieve first–best performance by either offering two contracts that separate the gatekeeper types or by offering a single contract that coordinates the treatment decisions of both gatekeepers.
The Logistics Impact of a Mixture of Order-Streams in a Manufacturer-Retailer System
Authors: Iyer Ananth V. , Jain Apurva
Published: December 2003

We model a supply chain with two retail warehouses that place replenishment orders with a common manufacturing capacity. The two retailers differ in the variability of their order-streams. The order-stream from one retail warehouse is modeled as a Poisson process and from the other as a hyperexponential renewal process. Each retail warehouse uses a base-stock policy to place replenishment orders with the manufacturer. The manufacturer is modeled as a first-come-first-serve, single exponential server queue. We analyze the supply-side impact of this mixture of order-streams received by the manufacturer on both retailers. An exact analysis of this base-model generates closed-form expressions for distributions of the lead-time, outstanding orders, and expected inventory costs for each retailer, and leads to comparative results about the two retailers- performance measures. The base-model is extended to accommodate finished goods at the manufacturer, more than two retailers, and bulk-arrivals. We use the model to suggest managerial insights about the impact of the presence of a high-variability retailer on other retailers who share capacity, the distorting impact of manufacturer finished goods inventory on retailer incentives, and the incentives for retailers to participate in variability-reduction programs in the grocery industry.
Subjective Rationality, Self–Confirming Equilibrium, and Corporate Strategy
Authors: Ryall Michael D.
Published: December 2003

This paper presents a formal theory of subjective rationality and demonstrates its application to corporate strategy. An agent is said to be subjectively rational when decisions are consistent with the available facts and, where these are lacking, with the agent's own subjective assessments. A self–confirming equilibrium arises when agents' subjectively rational actions generate events that are consistent with their own expectations. Equilibrium strategies may be suboptimal because certain counterfactual beliefs may be erroneous and yet fail to be contradicted by events observed in equilibrium. This weakening of the stronger rationality assumptions inherent in many of the more familiar equilibrium ideas appears well suited to applications in strategy. In particular, performance advantage may be sustained by a firm when its subjectively rational competitors persistently employ suboptimal self–confirming strategies.
The Data of Levy and Levy (2002) “Prospect Theory: Much Ado About Nothing?” Actually Support Prospect Theory
Authors: Wakker Peter P.
Published: December 2003

Levy and Levy (Management Science2002) present data that, according to their claims, violate prospect theory. They suggest that prospect theory's hypothesis of an S-shaped value function, concave for gains and convex for losses, is incorrect. However, all the data of Levy and Levy are perfectly consistent with the predictions of prospect theory, as can be verified by simply applying prospect theory formulas. The mistake of Levy and Levy is that they, incorrectly, thought that probability weighting could be ignored.
Pricing and Capacity Sizing for Systems with Shared Resources: Approximate Solutions and Scaling Relations
Authors: Maglaras Constantinos , Zeevi Assaf
Published: December 2003

This paper considers pricing and capacity sizing decisions, in a single-class Markovian model motivated by communication and information services. The service provider is assumed to operate a finite set of processing resources that can besharedamong users; however, this shared mode of operation results in a service-rate degradation. Users, in turn, are sensitive to the delay implied by the potential degradation in service rate, and to the usage fee charged for accessing the system. We study the equilibrium behavior of such systems in the specific context of pricing and capacity sizing under revenue and social optimization objectives. Exact solutions to these problems can only be obtained via exhaustive simulations. In contrast, we pursue approximate solutions that exploit large-capacity asymptotics. Economic considerations and natural scaling relations demonstrate that the optimal operational mode for the system is close to “heavy traffic.” This, in turn, supports the derivation of simple approximate solutions to economic optimization problems, via asymptotic methods that completely alleviate the need for simulation. These approximations seem to be extremely accurate. The main insights that are gleaned in the analysis follow: congestion costs are “small,” the optimal price admits a two-part decomposition, and the joint capacity sizing and pricing problem decouples and admits simple analytical solutions that are asymptotically optimal. All of the above phenomena are intimately related to statistical economies of scale that are an intrinsic part of these systems.
The Capacitated Lot-Sizing Problem with Linked Lot Sizes
Authors: Suerie Christopher , Stadtler Hartmut
Published: December 2003

In this paper a new mixed integer programming (MIP) model formulation and its incorporation into a time-oriented decomposition heuristic for the capacitated lot-sizing problem with linked lot sizes (CLSPL) is proposed. The solution approach is based on an extended model formulation and valid inequalities to yield a tight formulation. Extensive computational tests prove the capability of this approach and show a superior solution quality with respect to other solution algorithms published so far.
Application of the Fast Gauss Transform to Option Pricing
Authors: Broadie Mark , Yamamoto Yusaku
Published: December 2003

In many of the numerical methods for pricing American options based on the dynamic programming approach, the most computationally intensive part can be formulated as the summation of Gaussians. Though this operation usually requiresO(NN') work when there areN' summations to compute and the number of terms appearing in each summation isN, we can reduce the amount of work toO(N+N') by using a technique called the fast Gauss transform. In this paper, we apply this technique to the multinomial method and the stochastic mesh method, and show by numerical experiments how it can speed up these methods dramatically, both for the Black-Scholes model and Merton's lognormal jump-diffusion model. We also propose extensions of the fast Gauss transform method to models with non-Gaussian densities.
A Generalization of Pratt-Arrow Measure to Nonexpected-Utility Preferences and Inseparable Probability and Utility
Authors: Nau Robert F.
Published: December 2003

The Pratt-Arrow measure of local risk aversion is generalized for the n-dimensional state-preference model of choice under uncertainty in which the decision maker may have inseparable subjective probabilities and utilities, unobservable stochastic prior wealth, and/or smooth nonexpected-utility preferences. Local risk aversion is measured by the matrix of derivatives of the decision maker's risk-neutral probabilities, without reference to true subjective probabilities or riskless wealth positions, and comparative risk aversion is measured without requiring agreement on true probabilities. Risk-neutral probabilities and their derivatives are shown to be sufficient statistics for approximately optimal investment and financing decisions in complete markets for contingent claims.
Competitive Price Discrimination Strategies in a Vertical Channel Using Aggregate Retail Data
Authors: Besanko David , Dubé Jean-Pierre , Gupta Sachin
Published: December 2003

We explore opportunities for targeted pricing for a retailer that only tracks weekly store-level aggregate sales and marketing-mix information. We show that it is possible, using these data, to recover essential features of the underlying distribution of consumer willingness to pay. Knowledge of this distribution may enable the retailer to generate additional profits from targeting by using choice information at the checkout counter. In estimating demand we incorporate a supply-side model of the distribution channel that captures important features of competitive price-setting behavior of firms. This latter aspect helps us control for the potential endogeneity generated by unmeasured product characteristics in aggregate data. The channel controls for competitive aspects both between manufacturers and between manufacturers and a retailer. Despite this competition, we find that targeted pricing need not generate the prisoner's dilemma in our data. This contrasts with the findings of theoretical models due to the flexibility of the empirical model of demand. The demand system we estimate captures richer forms of product differentiation, both vertical and horizontal, as well as a more flexible distribution of consumer heterogeneity.
Supply Chain Management with Guaranteed Delivery
Authors: Huggins Eric Logan , Olsen Tava Lennon
Published: December 2003

We consider a two-stage supply chain under centralized control. The downstream facility faces discrete stochastic demand and passes supply requests to the upstream facility. The upstream facility always meets the supply requests from downstream. If the upstream facility cannot meet the supply requests from inventory on hand, the shortage must be filled by expediting, which will incur per unit and setup costs. Such expediting may take the form of overtime production, which occurs at the end of the period and incurs relatively high production costs, or premium freight shipments, which involves building products at the beginning of the period they are needed and shipping them very quickly with relatively high shipping costs. We consider the case where one method of filling shortages is available and determine novel optimal inventory policies under centralized control. At both stages, threshold policies that depend only on the current inventory in the system are optimal; for the total inventory in the system, a base-stock policy is optimal. Numerical analysis provides insight into the optimal policies and allows us to compare the supply chains under centralized and decentralized control.
A New Decision Rule for Lateral Transshipments in Inventory Systems
Authors: Axsäter Sven
Published: December 2003

This paper deals with a single–echelon inventory system consisting of a number of parallel local warehouses facing compound Poisson demand. There are standard holding and backorder costs as well as ordering costs at all warehouses. Normally, the warehouses replenish from an outside supplier. However, lateral transshipments between the warehouses are also possible. Such transshipments take no time but incur additional costs. When a demand occurs at a warehouse, the question is whether the whole demand or part of it should be covered by a lateral transshipment from another warehouse. Given a set of alternative decisions, our decision rule minimizes the expected costs under the assumption that no further transshipments will take place. This rule is then used repeatedly as a heuristic. A simulation study illustrates how the suggested technique performs under different conditions.
Into the Black Box: The Knowledge Transformation Cycle
Authors: Carlile Paul R. , Rebentisch Eric S.
Published: December 2003

This paper examines how knowledge is integrated in complex technology and product development settings. By framing the task of knowledge integration as a cycle, we highlight the inability of current knowledge transfer theories to explain the consequences that arise from the path-dependent nature of knowledge. We compare the complexity of this knowledge integration task to previous efforts in terms of its novelty and the organizational properties of specialization and dependence that are required. Drawing on evidence from two empirical studies, we outline three stages of the “knowledge transformation cycle,” which addresses the complexity of this integration task. We conclude with the implications of this knowledge transformation cycle on our understanding of knowledge management and organizational learning.
The Boycott Puzzle: Consumer Motivations for Purchase Sacrifice
Authors: John Andrew , Klein Jill
Published: December 2003

A boycott is never far from a firm's exchanges with its customers. Researchers in marketing need to understand consumer protest behavior, both to aid nongovernmental organizations (NGOs) who wish to organize boycotts, and to assist managers who wish to develop appropriate strategic responses. Boycotts, like many other instances of collective action, are subject to free-rider and small-agent problems: there appears to be little or no motivation for an individual to participate. Yet they assuredly occur. We take an economic and psychological approach to the study of boycotts. Our approach is to develop a typology of motivations for consumer boycotts, to embed these motivations explicitly in a dynamic economic model, and thus to offer explanations for the extent of boycott participation.
The Shape of Utility Functions and Organizational Behavior
Authors: Pennings Joost M. E. , Smidts Ale
Published: December 2003

Based on measurements among 332 owner-managers, we investigate how the global shape of the utility function (i.e., S-shaped versus concave or convex over the total range of outcomes) relates to choice behavior. We find that the global shape of the utility function differs across decision makers (about one-third of the owner-managers exhibit an S-shaped utility function) and that the global shape is linked to organizational behavior (i.e., the production system employed), a result that does not change when using different methods to identify the decision maker's global shape of the utility function. The decision maker's risk attitude (risk averse or risk seeking) does not affect the choice of the production system. Whereas the degree of risk aversion, based on the local shape of the utility function, may be important in explaining owner-managers' trading behavior (Pennings and Smidts 2000), more structural organizational behavior appears to be linked to the global shape of the utility function.
Remark on “Appropriateness and Impact of Platform-Based Product Development”
Authors: Dana James D.
Published: December 2003

When platform-based manufacturing exhibits overdesign costs then platform adoption will lead to a decrease in product line differentiation. In contrast, Krishnan and Gupta (2001) argued that in the presence of overdesign costs and platform economies, platform production always leads to a more differentiated product family. While Krishnan and Gupta analyzed one particular parameterized cost function and define overdesign costs and platform economies narrowly in terms of their parameters, I propose a general definition of overdesign costs and show that platform adoption reduces product differentiation for all cost functions satisfying this definition, regardless of whether or not they exhibit platform economies.
A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems
Authors: Croxton Keely L. , Gendron Bernard , Magnanti Thomas L.
Published: December 2003

We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.
The Random Weighted Interval Packing Problem: The Intermediate Density Case
Authors: Rhee Wansoo T. , Talagrand Michel
Published: December 2003

In this problem, we are given N uniformly distributed random intervals of [0, 1]. For each random interval, I, we are given a weight XI. These weights are independent, independent of the intervals, and satisfy P(XI ≤ t) = tα, where α > 0. A packing of the family is a disjoint set ℐ of these intervals. Its cost is Cℐ = |Rℐ| + ∑I∈ℐXI|I|, where Rℐ is the part of [0, 1] that is not covered by ℐ. We are interested in the optimal (=minimal) cost WN among all packings of the random family. We consider the case 1 < α < 2. If we define ξ by (α/2)ξ = ½, we show that for some constant K depending on α only, we have [Formula: see text]
The Complexity of Optimal Small Policies
Authors: Mundhenk Martin
Published: December 2003

We investigate the complexity of problems concerned with partially-observable Markov decision processes which are run for a finite number of steps under small policies. The calculation of the expected sum of rewards of a process under a small policy is shown to be complete for the complexity class PP, a class which lies intermediate between NP and PSPACE. Optimal small policy computation is shown to be complete for NPPP. The latter contrasts results of Papadimitriou and Tsitsiklis (Papadimitriou and Tsitsiklis 1987), who showed that this problem is PSPACE-complete, if no assumptions about the representability of the policy are made, and that it is P-complete for fully-observable processes.
Optimal Preventive Replacement Under Minimal Repair and Random Repair Cost
Authors: Makis V. , Jiang X. , Cheng K.
Published: December 2003

A repair/replacement problem for a single unit system with random repair cost is considered. When the unit fails, the repair cost is observed and a decision is made whether to replace the unit or repair it. We assume that the repair is minimal, i.e., the unit is restored to its functioning condition just prior to failure, without changing its age. The unit can be preventively replaced at any time. The problem is formulated as a continuous time decision problem and reduced to an optimal stopping problem in discrete time by applying results from the thoery of jump processes. The existence of the optimal policy is proved and its structure is found using semimartingale decomposition and λ-maximization technique. It is shown that the optimal policy is an age replacement, repair-cost-limit policy, and the optimal preventive replacement time and the repair cost limits can be obtained by solving a system of ordinary differential equations with boundary conditions.
The Maxmin of Recursive Games with Incomplete Information on one Side
Authors: Rosenberg Dinah , Vieille Nicolas
Published: December 2003

We prove the existence of the maxmin of zero-sum recursive games with one sided information.
The Quickest Transshipment Problem
Authors: Hoppe Bruce , Tardos Éva
Published: December 2003

A dynamic network consists of a graph with capacities and transit times on its edges. The quickest transshipment problem is defined by a dynamic network with several sources and sinks; each source has a specified supply and each sink has a specified demand. The problem is to send exactly the right amount of flow out of each source and into each sink in the minimum overall time.

Variations of the quickest transshipment problem have been studied extensively; the special case of the problem with a single sink is commonly used to model building evacuation. Similar dynamic network flow problems have numerous other applications; in some of these, the capacities are small integers and it is important to find integral flows. There are no polynomial-time algorithms known for most of these problems.

In this paper we give the first polynomial-time algorithm for the quickest transshipment problem. Our algorithm provides an integral optimum flow. Previously, the quickest transshipment problem could only be solved efficiently in the special case of a single source and single sink.
Almost Perfect Matrices and Graphs
Authors: Padberg Manfred
Published: December 2003

We introduce the notions of ω-projection and κ-projection that map almost integral polytopes associated with almost perfect graphs G with n nodes from ℝn into ℝn−ω, where ω is the maximum clique size in G. We show that C. Berge's strong perfect graph conjecture is correct if and only if the projection (of either kind) of such polytopes is again almost integral in ℝn−ω. Several important properties of ω-projections and κ-projections are established. We prove, among other results, that the strong perfect graph conjecture is wrong if an ω-projection and a related κ-projection of an almost integral polytope with 2 ≤ ω ≤ (n − 1)/2 produce different polytopes in ℝn−ω.
Lipschitzian Multifunctions and a Lipschitzian Inverse Mapping Theorem
Authors: Levy A. B.
Published: December 2003

We introduce a new class of multifunctions whose graphs under certain “kernel inverting” matrices, are locally equal to the graphs of Lipschitzian (single-valued) mappings. We characterize the existence of Lipschitzian localizations of these multifunctions in terms of a natural condition on a generalized Jacobian mapping. One corollary to our main result is a Lipschitzian inverse mapping theorem for the broad class of “max hypomonotone” multifunctions. We apply our theoretical results to the sensitivity analysis of solution mappings associated with parameterized optimization problems. In particular, we obtain new characterizations of the Lipschitzian stability of stationary points and Karush-Kuhn-Tucker pairs associated with parameterized nonlinear programs.
On a New Homotopy Continuation Trajectory for Nonlinear Complementarity Problems
Authors: Zhao Yun-Bin , Li Duan
Published: December 2003

Most known continuation methods for P0 complementarity problems require some restrictive assumptions, such as the strictly feasible condition and the properness condition, to guarantee the existence and the boundedness of certain homotopy continuation trajectory. To relax such restrictions, we propose a new homotopy formulation for the complementarity problem based on which a new homotopy continuation trajectory is generated. For P0 complementarity problems, the most promising feature of this trajectory is the assurance of the existence and the boundedness of the trajectory under a condition that is strictly weaker than the standard ones used widely in the literature of continuation methods. Particularly, the often-assumed strictly feasible condition is not required here. When applied to P* complementarity problems, the boundedness of the proposed trajectory turns out to be equivalent to the solvability of the problem, and the entire trajectory converges to the (unique) least element solution provided that it exists. Moreover, for monotone complementarity problems, the whole trajectory always converges to a least 2-norm solution provided that the solution set of the problem is nonempty. The results presented in this paper can serve as a theoretical basis for constructing a new path-following algorithm for solving complementarity problems, even for the situations where the solution set is unbounded.
Simplex-Like Trajectories on Quasi-Polyhedral Sets
Authors: Anderson Edward J. , Goberna Miguel A. , López Marco A.
Published: December 2003

This paper presents a unified treatment of two new simplex-like methods for linear semi-infinite programming problems with quasi-polyhedral feasible sets. The simplex method combines a purification phase I (which provides an extreme point from a given feasible solution) with the iterative application of a pivot operation, yielding a trajectory which consists of a (possibly infinite) sequence of linked edges (phase II). The reduced gradient method also consists of two phases and it can be applied even when the feasible set has no extreme point.
On the Throughput of a Resource Sharing Model
Authors: Dumas Vincent , Robert Philippe
Published: December 2003

A stochastic model of a parallel system with synchronization constraints is analyzed from a Markovian point of view. Some ergodic properties of this model are proved. We also give bounds on the throughput using results concerning branching processes.
On the Matrix-Cut Rank of Polyhedra
Authors: Cook William , Dash Sanjeeb
Published: December 2003

Lovász and Schrijver (1991) described a semidefinite operator for generating strong valid inequalities for the 0-1 vectors in a prescribed polyhedron. Among their results, they showed that n iterations of the operator are sufficient to generate the convex hull of 0-1 vectors contained in a polyhedron in n-space. We give a simple example, having Chvátal rank 1, that meets this worst case bound of n. We describe another example requiring n iterations even when combining the semidefinite and Gomory-Chvátal operators. This second example is used to show that the standard linear programming relaxation of a k-city traveling salesman problem requires at least ⌊k/8⌋ iterations of the combined operator; this bound is best possible, up to a constant factor, as k + 1 iterations suffice.
A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
Authors: McCormick S. Thomas , Smallwood Scott R. , Spieksma Frits C. R.
Published: December 2003

The following multiprocessor scheduling problem was motivated by scheduling maintenance periods for aircraft. Each maintenance period is a job, and the maintenance facilities are machines. In this context, there are very few different types of maintenances performed, so it is natural to consider the problem with only a small, fixed number C of different types of jobs. Each job type has a processing time, and each machine is available for the same length of time. A machine can handle at most one job at a time, all jobs are released at time zero, there are no due dates or precedence constraints, and preemption is not allowed. The question is whether it is possible to finish all jobs. We call this problem the Multiprocessor Scheduling Problem with C job lengths (MSPC).

Scheduling problems such as MSPC where we can partition the jobs into relatively few types such that all jobs of a certain type are identical are often called high-multiplicity problems. High-multiplicity problems are interesting because their input is very compact: The input to MSPC consists of only 2C + 2 numbers.

For the case C = 2 we present a polynomial-time algorithm. We show that this algorithm guarantees a schedule that uses the minimum possible number of different one-machine schedules, namely three. Further, we extend this algorithm to the case of machine-dependent deadlines (uniform parallel machines), to a multi-parametric case (that contains the case of unrelated parallel machines), and to some related covering problems. Finally, we give some counterexamples showing why our results do not extend to the case C > 2.
Cumulative Prospect Theory for Parametric and Multiattribute Utilities
Authors: Zank Horst
Published: December 2003

Different attitudes towards gains and losses are a prominent feature of cumulative prospect theory for decision under uncertainty. In particular, decision weights for uncertain events can depend on whether the events involve gains or losses, and the shape of the utility function can reveal loss aversion. Decision analyses concentrate on event capacities, which determine decision weights, and on the shape of the utility function. The present paper focuses on linear/exponential, power-function and multilinear utility models for decision under uncertainty. We begin with straightforward preference axioms for a representation by a cumulative prospect theory functional. The axioms include weak ordering, continuity, monotonicity and tail independence. We show that in their presence constant absolute (proportional) risk aversion implies linear/exponential (power) utility. Then, for the multiattribute case, (mutual) utility independence leads to a utility function that is (additive/multiplicative) multilinear.
Shapley-Shubik and Banzhaf Indices Revisited
Authors: Laruelle Annick , Valenciano Federico
Published: December 2003

We provide a new axiomatization of the Shapley-Shubik and the Banzhaf power indices in the domain of simple superadditive games by means of transparent axioms. Only anonymity is shared with the former characterizations in the literature. The rest of the axioms are substituted by more transparent ones in terms of power in collective decision-making procedures. In particular, a clear restatement and a weaker alternative for the transfer axiom are proposed. Only one axiom differentiates the characterization of either index, and these differentiating axioms provide a new point of comparison. In a first step both indices are characterized up to a zero and a unit of scale. Then both indices are singled out by simple normalizing axioms.
Conditioning of Convex Programs from a Primal-Dual Perspective
Authors: Peña Javier
Published: December 2003

Given a convex program and its dual, we analyze the conditioning of the primal-dual system of constraints, obtained by putting the primal and dual constraints together. We show that the conditioning of the primal-dual system can be estimated in terms of the conditioning of the primal and dual systems. In particular, provided both the primal and dual systems are well-conditioned, the primal-dual system is well-conditioned. We also investigate how the conditioning of the primal-dual system relates to properties of both the primal and dual problems, providing in this way a primal-dual viewpoint for the theory of condition numbers for convex programming.
An ϵ-Out-of-Kilter Method for Monotropic Programming
Authors: Tseng Paul
Published: December 2003

The out-of-kilter method was first proposed by Fulkerson (1961) for linear-cost network flow and independently by Minty (1961) for piecewise-linear-cost network flow and was then extended by Rockafellar (1984, Section 11K) to piecewise-linear-cost monotropic programming. We propose an extension of this method, based on Rockafellar's work and on ideas from ϵ-relaxation methods for convex-cost network flow (Bertsekas et al. 1997a, De Leone et al. 1999) to monotropic programming in general. The proposed method is amenable to a complexity analysis and its convergence is based on (essentially) a monotone decrease in vertical distance to the characteristic curve for each index.
A Weak-to-Strong Convergence Principle for Fejér-Monotone Methods in Hilbert Spaces
Authors: Bauschke Heinz H. , Combettes Patrick L.
Published: December 2003

We consider a wide class of iterative methods arising in numerical mathematics and optimization that are known to converge only weakly. Exploiting an idea originally proposed by Haugazeau, we present a simple modification of these methods that makes them strongly convergent without additional assumptions. Several applications are discussed.
Quitting Games
Authors: Solan Eilon , Vieille Nicolas
Published: December 2003

Quitting games are n-player sequential games in which, at any stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; player i then receives a payoff riS, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is 0.

The paper has four goals: (i) We prove the existence of a subgame-perfect uniform ε-equilibrium under some assumptions on the payoff structure; (ii) we study the structure of the ε-equilibrium strategies; (iii) we present a new method for dealing with n-player games; and (iv) we study an example of a four-player quitting game where the “simplest” equilibrium is cyclic with Period 2.

We also discuss the relation to Dynkin's stopping games and provide a generalization of our result to these games.
Absorbing Games with a Signalling Structure
Authors: Coulomb Jean-Michel
Published: December 2003

We consider a subclass of two-person zero-sum undiscounted stochastic games called absorbing games. The perfect monitoring assumption is removed. Instead of being informed of his opponent's previous action, each player is informed of a signal that randomly depends on both player's previous actions. The existence of the max min and similarly of the min max is established.
Cutting Planes and the Elementary Closure in Fixed Dimension
Authors: Bockmayr Alexander , Eisenbrand Friedrich
Published: December 2003

The elementary closure P′ of a polyhedron P is the intersection of P with all its Gomory-Chvátal cutting planes. P′ is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P′ are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull QI include the facets of P′. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of QI.
Bounds on the Performance of a Greedy Algorithm for Probabilities
Authors: Gittins J. C. , Harper G.
Published: December 2003

A bound on the performance of the greedy algorithm for finding the maximum of a submodular set function subject to a cardinality constraint is shown to apply to the problem of selecting a fixed number of events so that the probability that at least one of the selected events occurs is maximized. The bound is improved under an additional assumption which is plausible when the aim is to find a biologically active compound in pharmaceutical research.
Discounted Stochastic Fluid Programs
Authors: Bäuerle Nicole
Published: December 2003

We consider optimal control problems for stochastic fluid models of the following type: Suppose (Zt) is a continuous-time Markov chain with finite state space. As long as Zt = z, the dynamics of the system at time t are given by a function bz(u(·)), where u is a control we have to choose. A cost rate function c is given, depending on the state and the action. We want to control the system in such a way as to minimize the expected discounted cost over an infinite horizon. We will call a problem of this type a Stochastic Fluid Program (SFP). They typically appear in production and telecommunication systems. We formulate the optimization problem as a discrete time Markov decision process and give conditions under which an optimal stationary policy exists. Furthermore, we show how to solve SFPs numerically, using Kushner's approximating Markov chain approach. Last but not least, we apply our results to a multiproduct manufacturing system without backlog.
The Reflection Map with Discontinuities
Authors: Whitt Ward
Published: December 2003

We study the multidimensional reflection map on the spaces D([0, T], ℝk) and D([0, ∞), ℝk) of right-continuous ℝk-valued functions on [0, T] or [0, ∞) with left limits, endowed with variants of the Skorohod (1956) M1 topology. The reflection map was used with the continuous mapping theorem by Harrison and Reiman (1981) and Reiman (1984) to establish heavy-traffic limit theorems with reflected Brownian motion limit processes for vector-valued queue length, waiting time, and workload stochastic processes in single-class open queueing networks. Since Brownian motion and reflected Brownian motion have continuous sample paths, the topology of uniform convergence over bounded intervals could be used for those results. Variants of the M1 topologies are needed to obtain alternative discontinuous limits approached gradually by the converging processes, as occurs in stochastic fluid networks with bursty exogenous input processes, e.g., with on-off sources having heavy-tailed on periods or off periods (having infinite variance). We show that the reflection map is continuous at limits without simultaneous jumps of opposite sign in the coordinate functions, provided that the product M1 topology is used. As a consequence, the reflection map is continuous with the product M1 topology at all functions that have discontinuities in only one coordinate at a time. That continuity property also holds for more general reflection maps and is sufficient to support limit theorems for stochastic processes in most applications. We apply the continuity of the reflection map to obtain limits for buffer-content stochastic processes in stochastic fluid networks.
On ws-Convergence of Product Measures
Authors: Balder Erik J.
Published: December 2003

A number of fundamental results, centered around extensions of Prohorov's theorem, is proven for the ws-topology for measures on a product space. These results contribute to the foundations of stochastic decision theory. They also subsume the principal results of Young measure theory, which only considers product measures with a fixed, common marginal. Specializations yield the criterion for relative ws-compactness of Schäl (1975), the refined characterizations of ws-convergence of Galdéano and Truffert (1997, 1998), and a new version of Fatou's lemma in several dimensions. In a separate, nonsequential development, a generalization is given of the relative ws-compactness criterion of Jacod and Mémin (1981). New applications are given to the existence of optimal equilibrium distributions over player-action pairs in game theory and the existence of most optimistic scenarios in stochastic decision theory.
First-Order Optimality Conditions for Degenerate Index Sets in Generalized Semi-Infinite Optimization
Authors: Stein Oliver
Published: December 2003

We present a general framework for the derivation of first-order optimality conditions in generalized semi-infinite programming. Since in our approach no constraint qualifications are assumed for the index set, we can generalize necessary conditions given by Rückmann and Shapiro (1999) as well as the characterizations of local minimizers of order one, which were derived by Stein and Still (2000). Moreover, we obtain a short proof for Theorem 1.1 in Jongen et al. (1998).

For the special case when the so-called lower-level problem is convex, we show how the general optimality conditions can be strengthened, thereby giving a generalization of Theorem 4.2 in Rückmann and Stein (2001). Finally, if the directional derivative of a certain optimal value function exists and is subadditive with respect to the direction, we propose a Mangasarian-Fromovitz-type constraint qualification and show that it implies an Abadie-type constraint qualification.