Search

We prove that the status quo sets induced by the Raiffa Solution to the two-person Bargaining Problem are curves, except when the bargaining domain is rectangular. This property is used in a separate paper by Livne [3] in the axiomatization of the Raiffa Solution. [ABSTRACT FROM AUTHOR]

Focuses on the 'Mathematics of Operations Research' periodical. Increase in the annual number of pages; Contribution of the periodical to the study of operations research and management; Information regarding the circulation of the periodical.

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

We apply a new method of analysis to the asymmetric rendezvous search problem on the line (ARSPL). This problem, previsouly studied in a paper of Alpern and Gal (1995), asks how two blind, speed one players placed a distance d apart on the line, can find each other in minimum expected time. The distance d is drawn from a known cumulative probability distribution G, and players are faced in random directions. We show that the ARSPL is strategically equivalent to a new problem we call the double linear search problem (DLSP), where an object is placed equiprobably on one of two lines, and equiprbably at position ±d. A searcher is placed at the origin of each of these lines. The two searcher move with a combined speed of one, of minimize the expected time before one of them finds the object. Using results from a concurrent paper of the first author and J. V. Howard (1998), we solve the DLSP (and hence the ARSPL) for the case where G is convex on its support, and shown that the solution is that conjectured in a paper of Baston and Gal(1998). [ABSTRACT FROM AUTHOR]

Randomizing (stochastic) global optimization algorithms can be viewed as sampling procedures, where at each iteration a local optimum is sampled from the set of local optima. The effectiveness of such an algorithm depends crucially on the sampling distribution, i.e., on the probabilities of sampling the various local optima. There exists a very large body of research on stochastic global optimization. However, very little is known about the sampling distribution itself and, in particular, on the specific way in which it depends on the function being optimized, on the region in which the search takes place, and on the optimization routine. In this paper we set out to examine these issues in some detail and present some first results in this direction. The case analyzed in this paper is the optimization of a one-dimensional function using a randomizing version of binary search. We give an effective (computable in quadratic time) formula for the sampling distribution and obtain various interesting properties of this distribution which are relevant to the behavior of the algorithm in practice. We also discuss some issues related to adaptive search. [ABSTRACT FROM AUTHOR]

Mathematical models for multistate reliability systems of multistate components have been proposed by Barlow and Wu (1978), El-Neweihi et al. (1978) and Griffith (1980). Unlike the approach used by Barlow and Wu, the other authors preferred to establish their classes of models through sets of axioms extending the early binary notions and containing as special cases the class of models suggested by Barlow and Wu. Since the Barlow and Wu approach is set theoretic and the model definition is essentially qualitative, a question of interest concerns its axiomatic characterization among larger classes of models. In this paper such a characterization is established that relates the Barlow and Wu models to the other classes of models introduced later. [ABSTRACT FROM AUTHOR]

In this paper we show that if Z is a partially ordered linear space with the property that each set with an upper bound has a least upper bound, then any convex operator F from a linear space X into Z has a support at each x∈X(i.e., for each x∈X, there exists an affine operator A such that A(x)=F(x) and A(y) ≤ F(Y) for each y∈X. The results in this paper are actually in the context of a more general condition than convexity, called W-convexity. W-convexity is a pointwise property of an operator and is closely related to another generalization of convexity, called order-convexity, which was introduced by Ortega and Rheinboldt in 1967. [ABSTRACT FROM AUTHOR]

In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and demonstrate that this new class has interesting properties which contrast with properties of potential games. Exploiting the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the equilibrium properties of potential and harmonic games to "nearby" games. [ABSTRACT FROM AUTHOR]

In the paper we consider the chance-constrained version of an affinely perturbed linear matrix inequality (LMI) constraint, assuming the primitive perturbations to be independent with light-tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing a central role in chance-constrained linear/conic quadratic/semidefinite programming, are typically computationally intractable. The goal of this paper is to develop a tractable approximation to these chance constraints. Our approximation is based on measure concentration results and is given by an explicit system of LMIs. Thus, the approximation is computationally tractable; moreover, it is also safe, meaning that a feasible solution of the approximation is feasible for the chance constraint. [ABSTRACT FROM AUTHOR]

A decision maker is engaged in a repeated interaction with Nature. The objective of the decision maker is to guarantee to himself the average payoff as large as the best-reply payoff to Nature's empirical distribution of play, no matter what Nature does. The decision maker with perfect recall can achieve this objective by a simple better-reply strategy. In this paper we demonstrate that the relationship between perfect recall and bounded recall is not straightforward: The decision maker with bounded recall may fail to achieve this objective, no matter how long his recall and no matter what better-reply strategy he uses. [ABSTRACT FROM AUTHOR]

In a recent paper Li and Singer (1998) introduced the notion of global error bound for a convex multifunction at a point of its domain. They showed the existence of such a global error bound when the image of the multifunction at the respective point is bounded and conjectured a result for the case when the image is not bounded. In this paper we solve their conjecture with a positive answer. For this we establish a criterion for the existence of a global error bound using the Pompeiu-Hausdorff excess. We also improve slightly some results of Li and Singer and introduce a gage associated to a multifunction similar to that for well-conditioning of convex functions, with similar properties. [ABSTRACT FROM AUTHOR]

The paper addresses a class of continuous-time, optimal control problems whose solutions are typically characterized by both bang-bang and "singular" control regimes. Analytical study and numerical computation of such solutions are very difficult and far from complete when only techniques from control theory are used. This paper solves optimal control problems by reducing them to the combinatorial search for the shortest path in a specially constructed graph. Since the nodes of the graph are weighted in a sequence-dependent manner, we extend the classical, shortest-path algorithm to our case. The proposed solution method is currently limited to single-state problems with multiple control functions. A production planning problem and a train operation problem are optimally solved to illustrate the method. [ABSTRACT FROM AUTHOR]

The nonlinear complementarity problem has been converted into a system of nonsmooth equations by means of Fischer-Burmeister functional, which may be called the Fischer-Burmeister equation. The local superlinear convergence of the generalized Newton method applied to the Fischer- Burmeister equation has been established under certain regularity assumptions. In contrast to the damped Newton method for systems of smooth equations, global convergence of the damped generalized Newton method for systems of nonsmooth equations cannot be proved in general. In this paper, we show that the natural globalization of the Newton method for smooth equations can be extended to the Fischer-Burmeister equation without any hybrid strategy. Moreover, we are also able to demonstrate that the damped modified Gauss-Newton method can be extended to the Fischer- Burmeister equation. This shows that the elegant convergence analysis of the traditional Newton, damped Newton and damped Gauss-Newton methods can be naturally generalized to the Fischer- Burmeister equation. [ABSTRACT FROM AUTHOR]

We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. The ensuing optimization problem is called robust optimization. In this paper we lay the foundation of robust convex optimization. In the main part of the paper we show that if U is an ellipsoidal uncertainty set, then for some of the most important generic convex optimization problems (linear programming, quadratically constrained programming, semidefinite programming and others) the corresponding robust convex program is either exactly, or approximately, a tractable problem which lends itself to efficient algorithms such as polynomial time interior point methods. [ABSTRACT FROM AUTHOR]

This paper compares solution concepts associated with three location problems on a network: (i) a single-facility distance minimization problem; (ii) a two-facility spatial competition problem; and (iii) a single-facility locational voting problem. It is shown that the three problems have a common global solution when the network exhibits a property of symmetry around a point. For more general networks, this ceases to be true for global solutions but an identity holds for local solutions. [ABSTRACT FROM AUTHOR]

In a recent paper [3] the authors gave sufficient conditions for the weak convergence of a sequence of discrete time Markov decision drift processes to a related continuous time Markov decision drift process. The goal of this analysis was to obtain for the continuous time model conditions for optimality of a limit point of a sequence of discounted discrete time optimal policies. However, the general conditions in [3] can only be applied to a very restrictive class of models. To obtain more widely applicable conditions we are concerned in this paper not with the weak convergence of the stochastic processes induced by policies, but rather with the convergence of the total expected discounted costs. Special attention is paid to the case of unbounded cost functions. Sufficient conditions on model parameters and policies are given to guarantee the convergence of the expected discounted costs of a sequence of discrete time models to those of a related continuous time model These results are used to identify the optimal policy of a continuous lime model by means of the optimal policies of a sequence of approximating discrete time models. An application to an M/M/l queueing model is given. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of generalized equations, which are a unified way of formulating problems of linear and nonlinear programming, complementarity, variational inequalities and mathematical economics among others. We introduce a set of conditions, which we call the strong positivity conditions, prove that they are sufficient for a solution of a generalized equation to be locally unique, and discuss their stability when the functions involved in the problem are subjected to small perturbations. Applications to linear generalized equations and nonlinear programming problems are discussed. [ABSTRACT FROM AUTHOR]

This paper gives sufficient conditions for the existence of average optimal policies in a decision model, which is a generalization of a denumerable state space semi-Markov decision model. The conditions extend most of those previously known; especially, neither unichainedness nor communicatingness is assumed. An average optimal policy can be obtained as a limit of discount optimal policies. If structured policies are discount optimal, there exists a structured average optimal policy. The results are applicable to more general continuous time models such as the one by Yushkevich and Fainberg [35]. [ABSTRACT FROM AUTHOR]

We give two sets of conditions for the association of a system's component life lengths. The conditions are dynamic in the sense that they are based on evaluating, at any given time t, the effect a failure would have on the system's future behaviour. Of basic importance is the concept "weakened by failures" introduced in the paper. Mathematically the paper is based on martingales in the case of jump processes, or marked point processes. [ABSTRACT FROM AUTHOR]

In this paper we deal with continuous time Markov decision drift processes (CTMDP), which permit both controls affecting jump rates of the process and impulsive controls causing immediate transitions. Between two successive jump epochs the state of the process evolves according to a deterministic drift function. Given a CTMDP we construct a sequence of discrete time Markov decision drift processes (DTMDP) with decreasing distance between the successive decision epochs. Sufficient conditions are provided under which the law of the CTMDP controlled by a fixed policy is the limit (in the sense of weak convergence of probability measures) of the laws of the approximating DTMDP's controlled by fixed discrete time policies. The conditions concern both the parameters of the CTMDP and the relation between the discrete time and continuous time policies. An application to a maintenance replacement model is given. [ABSTRACT FROM AUTHOR]

A series of recent articles has established that in continuous alternative spaces where voter preferences are representable by continuous utility functions, there generally exist majority paths between any two points in the space. In this paper, the problem of constructing such paths is dealt with. It is shown that if the dimensionality of the underlying alternative space is at least three, the problem can be decomposed into a series of smaller, limited horizon problems. These smaller problems can then be formulated as several independent convex programming problems, which could be solved by standard methods. [ABSTRACT FROM AUTHOR]

In this paper it is proved that in games with a finite dumber of players and a finite number of moves, if each player observes a private information random variable which has an atomless distribution and is independent of the observations and payoffs of all other players, then the game possesses a pure-strategy equilibrium. Examples are presented that illustrate the importance of the assumptions. [ABSTRACT FROM AUTHOR]

In the "classical" network flow model. Flows are constrained by the capacities of individual arcs. In the "polymatroidal" network flow model introduced in this paper, flows are constrained by the capacities of sets of arcs. Yet the essential features of the classical model are retained: the augmenting path theorem, the integral flow theorem and the max flow min-cut theorem are all shown to yield to straightforward generalization. We describe a maximal flow algorithm which finds augmenting paths by labeling arcs instead of nodes, as in the case of the classical model. As a counterpart of a known result for the classical model, we prove that the number of augmentations required to achieve a maximal value flow is bounded by the cube of the number of arcs in the network, provided each successive augmentation is made along a shortest augmenting path, with ties between shortest paths broken by lexicography. [ABSTRACT FROM AUTHOR]

The Banzhaf index of power in a voting situation depends on the number of ways in which each voter can effect a "swing" in the outcome. It is comparable--but not actually equivalent --to the better-known Shapley-Shubik index, which depends on the number of alignments or "orders of support" in which each voter is pivotal. This paper investigates some properties of the Banzhaf index, the main topics being its derivation from axioms and its behavior in weighted-voting models when the number of small voters tends to infinity. These matters have previously been studied from the Shapley-Shubik viewpoint, but the present work reveals some striking differences between the two indices. The paper also attempts to promote better communication and less duplication of mathematical effort by identifying and describing several other theories, formally equivalent to Banzhaf's, that are found in fields ranging from sociology to electrical engineering. An extensive bibliography is provided. [ABSTRACT FROM AUTHOR]

This paper provides new bounds on the quality of equilibria in finite congestion games with affine cost functions, specifically for atomic network routing games. It is well known that the price of anarchy equals exactly 5/2 in general. For symmetric network routing games, it is at most (5n - 2)/(2n + 1), where n is the number of players. This paper answers to two open questions for congestion games. First, we show that the price of anarchy bound (5n - 2)/(2n + 1) is tight for symmetric network routing games, thereby answering a decade-old open question. Second, we ask whether sequential play and subgame perfection allows to evade worst-case Nash equilibria, and thereby reduces the price of anarchy. This is motivated by positive results for congestion games with a small number of players, as well as recent results for other resource allocation problems. Our main result is the perhaps surprising proof that subgame perfect equilibria of sequential symmetric network routing games with linear cost functions can have an unbounded price of anarchy. We complete the picture by analyzing the case with two players: we show that the sequential price of anarchy equals 7/5 and that computing the outcome of a subgame perfect equilibrium is NP-hard. Keywords: Nash and subgame perfect equilibrium * price of anarchy * congestion games * network routing, 1. Introduction The concept of the price of anarchy (PoA), introduced by Koutsoupias and Papadimitriou [23], has spurred a significant amount of research over the past two decades and has [...]

We study a multiperiod network revenue management problem where a seller sells multiple products made from multiple resources with finite capacity in an environment where the underlying demand function is a priori unknown (in the nonparametric sense). The objective of the seller is to simultaneously learn the unknown demand function and dynamically price the products to minimize the expected revenue loss. For the problem where the number of selling periods and initial capacity are scaled by k > 0, it is known that the expected revenue loss of any non-anticipating pricing policy is [OMEGA]([square root of k]). However, there is a considerable gap between this theoretical lower bound and the performance bound of the best-known heuristic control in the literature. In this paper, we propose a nonparametric self-adjusting control and show that its expected revenue loss is O([k.sup.1/2+[member of]] log k) for any arbitrarily small [member of] > 0, provided that the underlying demand function is sufficiently smooth. This is the tightest bound of its kind for the problem setting that we consider in this paper, and it significantly improves the performance bound of existing heuristic controls in the literature. In addition, our intermediate results on the large deviation bounds for spline estimation and nonparametric stability analysis of constrained optimization are of independent interest and are potentially useful for other applications. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2018.0937. Keywords: revenue management * learning * self-adjusting control * spline approximation * asymptotic analysis, 1. Introduction Revenue management (RM), which was first implemented in the 1960s by legacy airline companies to maintain their edge in the competitive airline market, has recently become widespread in [...]

In this paper, we consider the linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose an inexact augmented Lagrangian (IAL) framework for solving the problem. The stopping criterion used in solving the augmented Lagrangian subproblem in the proposed IAL framework is weaker and potentially much easier to check than the one used in most of the existing IAL frameworks/methods. We analyze the global convergence and the nonergodic convergence rate of the proposed IAL framework. Preliminary numerical results are presented to show the efficiency of the proposed IAL framework and the importance of the nonergodic convergence and convergence rate analysis. Funding: The work of Y.-F. Liu was supported in part by National Natural Science Foundation of China (NSFC) [Grants 11631013, 11331012, 11671419, and 11571221] and Beijing Natural Science Foundation [Grant LI72020]. The work of X. Liu was supported in part by NSFC [Grants 11622112, 11471325, 91530204, and 11688101], the National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences (CAS), and Key Research Program of Frontier Sciences (QYZDJ-SSW-SYS010), CAS. The work of S. Ma was supported in part by a startup package from the Department of Mathematics at University of California, Davis. Keywords: inexact augmented Lagrangian framework * nonergodic convergence rate * composite convex programming, 1. Introduction In this paper, we consider the linearly constrained composite convex optimization problem [mathematical expression not reproducible] (1) where A [member of] [R.sup.mxn] and b [member of] [R.sup.m]; f(x) [...]

In this paper, we propose unbiased sensitivity estimators of the expected functional of one-dimensional diffusion processes. Under general diffusion models, it is common to rely on discretization methods such as the Euler scheme for the generation of sample paths because of the lack of knowledge in the probability distributions associated with the diffusions. The Euler discretization method is easy to apply, but it is difficult to avoid discretization biases. As an alternative approach, we propose unbiased Monte Carlo estimators of sensitivities by taking advantage of the Beskos-Roberts method, which is an exact simulation algorithm for one-dimensional stochastic differential equations (SDEs), and applying the Poisson kernel method. The proposed estimators can be computed by discretely observed Brownian paths, and thus it is simple to implement our algorithms. We illustrate the ideas and algorithms with examples. Funding: This work was supported by the National Research Foundation of Korea (NRF) funded by the Korea government (MEST) [Grant NRF-2017R1A2B4011546]. Keywords: unbiased estimator * sensitivity estimation * derivative estimation * Greeks * Beskos-Roberts method * Poisson kernel method, 1. Introduction In this paper, we develop a method to estimate sensitivities of expected functionals of processes using Monte Carlo simulation under one-dimensional general diffusion models. The accurate estimation of [...]

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - [epsilon]. J. Comput. System Sci. 74(3): 335-349] proved that the problem is NP-hard to approximate within a factor 2- [epsilon], assuming the unique games conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra [Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann. Math. 162(1):439-485]: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates the vertex cover within a factor 2 - [epsilon] has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as semidefinite programming relaxations) that approximate the independent set problem within any constant factor have a super-polynomial size. Funding: Research reported in this paper was partially supported by the National Science Foundation (NSF) [CAREER Grant CMMI-1452463] and [Grant CMMI-1300144] and by the European Research Council (ERC) [Starting Grant 335288-OptApprox] and [Consolidator Grant 615640-ForEFront]. Research was partially conducted at the Oberwolfach Workshop 1446 and Dagstuhl Workshop 15082. Keywords: extended formulations * hardness of approximation * independent set * linear programming * vertex cover, 1. Introduction In this paper, we prove tight inapproximability results for VERTEX COVER with respect to linear programming relaxations of polynomial size, VERTEX COVER is the following classic problem: given [...]

As one of the most plausible convex optimization methods for sparse data reconstruction, [l.sub.1]-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as the restricted isometry property, null space property, and mutual coherence. In this paper, we propose a unified means to develop the so-called weak stability theory for [l.sub.1]-minimization methods under the condition called the weak range space property of a transposed design matrix, which turns out to be a necessary and sufficient condition for the standard [l.sub.1]-minimization method to be weakly stable in sparse data reconstruction. The reconstruction error bounds established in this paper are measured by the so-called Robinson's constant. We also provide a unified weak stability result for standard [l.sub.1]-minimization under several existing compressed sensing matrix properties. In particular, the weak stability of this method under the constant-free range space property of the transposed design matrix is established, to our knowledge, for the first time in this paper. Different from the existing analysis, we utilize the classic Hoffman's lemma concerning the error bound of linear systems as well as Dudley's theorem concerning the polytope approximation of the unit ball to show that [l.sub.1]-minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements. Funding: The research was partially supported by the Engineering and Physical Sciences Research Council (EPSRC) [Grant EP/K00946X/1], the Natural Science Foundation of China (NSFC) [Grants 61571384 and 61731018], and the Leading Talents of Guang Dong Province program [Grant 00201510]. Keywords: sparsity optimization * [l.sub.1]-minimization * convex optimization * linear program * weak stability * weak range space property, 1. Introduction Data might be contaminated by some form of random noise, and the measurements of data are subject to quantization error. Thus a huge effort in sparse data reconstruction [...]

We consider a game where a finite number of retailers choose a location, given that their potential consumers are distributed on a network. Retailers do not compete on price but only on location, therefore each consumer shops at the closest store. We show that when the number of retailers is large enough, the game admits a pure Nash equilibrium and we construct it. We then compare the equilibrium cost borne by the consumers with the cost that could be achieved if the retailers followed the dictate of a benevolent planner. We perform this comparison in terms of the Price of Anarchy (i.e., the ratio of the worst equilibrium cost and the optimal cost) and the Price of Stability (i.e., the ratio of the best equilibrium cost and the optimal cost). We show that, asymptotically in the number of retailers, these ratios are bounded by two and one, respectively. Funding: This work was partially supported by PRIN 20103S5RN3, Galileo G15-30, and MOE2013-T2-1-158. Part of this research was completed while Gaetan Fournier was visiting Singapore University of Technology and Design in 2013 and 2014 and both authors were visiting the Institute for Mathematical Sciences, National University of Singapore in 2015. Support from the Agence nationale de la recherche (ANR) Labex Institute for Advanced Study in Toulouse (IAST) is gratefully acknowledged. Marco Scarsini is a member of Gruppo Nazionale per l'Analisi Matematica, la Probabilita e le loro Applicazioni-Istituto Nazionale di Alta Matematica (GNAMPA-INdAM). Keywords: Price of Anarchy * Price of Stability * location games on networks * Hotelling games * pure equilibria * large games, 1. Introduction 1.1. The Problem In his seminal paper, Hotelling [9] considers duopoly models, where two retailers compete by choosing a location and a price. The paper is extremely rich [...]

In this paper, we study the long-standing open question regarding the computational complexity of one of the core problems in supply chains management, the periodic joint replenishment problem. This problem has received a lot of attention over the years, and many heuristic and approximation algorithms have been suggested. However, in spite of the vast effort, the complexity of the problem remains unresolved. In this paper, we provide a proof that the problem is indeed strongly .N P-hard. Funding: This study was supported by the Israel Science Foundation [Grant 1403/16]. Keywords: computational complexity * joint replenishment problem * supply chain management * twin primes, 1. Introduction Many inventory models are aimed at minimizing ordering and holding costs while satisfying demand. The joint replenishment problem (JRP) deals with the prospect of saving resources through coordinated [...]

This paper studies curves of the form [([rho]([lambda]X)).sub.[lambda][greater than or equal to]0], called risk profiles, where [rho] is a convex risk measure and X a random variable. Financially, this captures the sensitivity of risk to the size of the investment in X, which the original axiomatic foundations of convex risk measures suggest to interpret as liquidity risk. The shape of a risk profile is intimately linked with the tail behavior of X for some notable classes of risk measures, namely shortfall risk measures and optimized certainty equivalents, and shares many useful features with cumulant generating functions. Exploiting this link leads to tractable necessary and sufficient conditions for pointwise bounds on risk profiles, which we call concentration inequalities. These inequalities admit useful dual representations related to transport inequalities, and this leads to efficient uniform bounds for risk profiles for large classes of X. Several interesting mathematical results emerge from this analysis, including a new perspective on nonexponential concentration estimates and some peculiar characterizations of classical transport inequalities. Lastly, the analysis is deepened by means of a surprising connection between time consistency properties of law invariant risk measures and the tensorization of concentration inequalities. Funding: This research is supported by the National Science Foundation [Award DMS-1502980]. Keywords: convex risk measures * liquidity risk * concentration of measure * transport inequalities, 1. Introduction Throughout the paper, a risk measure is a convex functional [rho] acting on random variables satisfying the following axioms: 1. Normalization: [rho](0) = 0. 2. Cash additivity: [rho](X [...]

In this paper, we consider the optimal dividend payment strategy for an insurance company that has two collaborating business lines. The surpluses of the business lines are modeled by diffusion processes. The collaboration between the two business lines permits that money can be transferred from one line to another with or without proportional transaction costs, while money must be transferred from one line to another to help both business lines keep running before simultaneous ruin of the two lines eventually occurs. Keywords: optimal dividends strategy * diffusion model * collaborating businesses * stochastic control, 1. Introduction This paper is concerned with a classical problem of actuarial mathematics, strategies for optimal payout of dividends when two collaborating lines of business are taken into account. Since [...]

In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in (0, (1 +[5.sup.1/2 ])/2). This semi-proximal ADMM, which covers the classic one, has the advantage to resolve the potentially nonsolvability issue of the sub-problems in the classic ADMM and possesses the abilities of handling the multi-block cases efficiently. We demonstrate the usefulness of the obtained results when applied to two- and multi-block convex quadratic (semidefinite) programming. Funding: The research of the first author was supported by the National Natural Science Foundation of China [Projects 11625105 and 11431002]; the research of the second author was supported in part by the Academic Research Fund [Grant R-146-000-207-112]; and the research of the third author was supported by the National Natural Science Foundation of China [Projects 11571059 and 91330206]. Keywords: ADMM * calmness * Q-linear convergence * multiblock * composite conic programming, 1. Introduction In this paper, we shall study the Q-linear rate convergence of the alternating direction method of multipliers (ADMM) for solving the following convex composite optimization problem: min{[?](y + [...]

In this paper, we provide a flexible framework allowing for a unified study of time consistency of risk measures and performance measures (also known as acceptability indices). The proposed framework not only integrates existing forms of time consistency, but also provides a comprehensive toolbox for analysis and synthesis of the concept of time consistency in decision making. In particular, it allows for in-depth comparative analysis of (most of) the existing types of time consistency--a feat that has not been possible before and, which is done in the companion paper by the authors. In our approach, the time consistency is studied for a large class of maps that are postulated to satisfy only two properties--monotonicity and locality. We call these maps LM-measures. The time consistency is defined in terms of an update rule. The form of the update rule introduced here is novel, and is perfectly suited for developing the unifying framework that is worked out in this paper. As an illustration of the applicability of our approach, we show how to recover almost all concepts of weak time consistency by means of constructing appropriate update rules. Funding: The first and second author acknowledge support from the National Science Foundation [Grant DMS-1211256]. The third author acknowledges support by project operated within the Foundation for Polish Science IPP Programme 'Geometry and Topology in Physical Model,' cofinanced by the EU European Regional Development Fund, Operational Program Innovative Economy 2007-2013. Keywords: time consistency * update rule * dynamic LM-measure * dynamic risk measure * dynamic acceptability index * dynamic performance measure, 1. Introduction In the seminal paper by Artzner et al. [3], the authors proposed an axiomatic approach to defining risk measures that are meant to give a numerical value of [...]

This study is concerned with finding a level ideal (LI) of a partially ordered set (poset). Given a finite poset P, the level of each element p ∈ P is defined as the number of ideals that do not include p, then the problem is to find the ith LI-the ideal consisting of elements whose levels are less than a given integer i. The concept of a level ideal is naturally derived from the generalized median stable matchings, introduced by Teo and Sethuraman [Teo, C. P., J. Sethuraman. 1998. The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4) 874-891] in the context of "fairness" of matchings in a stable marriage problem. Cheng [Cheng, C. T. 2010. Understanding the generalized median stable matchings. Algorithmica 58(1) 34-51] showed that finding the ith LI is #P-hard when i = θ (N), where N is the total number of ideals of P. This paper shows that finding the ith LI is #P-hard even if i = θ (N 1/c), where c is an arbitrary constant at least one. Meanwhile, we present a polynomial time exact algorithm when i = O(logN)c', where c' is an arbitrary positive constant. We also devise two randomized approximation schemes for the ideals of a poset, by using an oracle of an almost-uniform sampler. [ABSTRACT FROM AUTHOR]

This paper presents a question of topological dynamics and demonstrates that its affirmation would establish the existence of approximate equilibria in all quitting games with only normal players. A quitting game is an undiscounted stochastic game with finitely many players where every player has only two moves, to end the game with certainty or to allow the game to continue. If nobody ever acts to end the game, all players receive payoffs of 0. A player is normal if and only if by quitting alone she receives at least her min-max payoff. This proof is based on a version of the Kohlberg-Mertens [Kohlberg, E., J.-F. Mertens. 1986. On the strategic stability of equilibria. Econometrica 54(5) 1003-1037] structure theorem designed specifically for quitting games. [ABSTRACT FROM AUTHOR]

In the symmetric rendezvous search game played on n locations two players are initially placed at two distinct locations. The game is played in discrete steps, at each of which each player can either stay where he is or move to a different location. The players share no common labelling of the locations. We wish to find a strategy such that, if both players follow it independently, then the expected number of steps until they are in the same location is minimized. Informal versions of the rendezvous problem have received considerable attention in the popular press. The problem was proposed by Alpern in 1976 [Alpern, S. 1976. Hide and seek games. Seminar at the Institut für Höhere Studien, Vienna], and it has proved notoriously difficult to analyse. In this paper we prove a 20-year-old conjecture that the following strategy is optimal for the game on three locations: in each block of two steps, stay where you are, or search the other two locations in random order, doing these with probabilities 1=3 and 2=3, respectively. This is now the first nontrivial symmetric rendezvous game of any type to be fully solved. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the Chvátal-Gomory closure of a set obtained as an intersection of a strictly convex body and a rational polyhedron is a polyhedron. Thus, we generalize a result of Schrijver [Schrijver, A. 1980. On cutting planes. Ann. Discrete Math. 9 291-296], which shows that the Chvátal-Gomory closure of a rational polyhedron is a polyhedron. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of the orthogonal similarity set of the quadratic part of the objective function. This exploits the matrix structure of QAP and results in a relaxation with much smaller dimension than other current SDP relaxations. We compare the resulting bounds with several other computationally inexpensive bounds such as the convex quadratic programming relaxation (QPB). We find that our method provides stronger bounds on average and is adaptable for branch-and-bound methods. [ABSTRACT FROM AUTHOR]

The famous Frank-Wolfe theorem ensures attainability of the optimal value for quadratic objective functions over a (possibly unbounded) polyhedron if the feasible values are bounded. This theorem does not hold in general for conic programs where linear constraints are replaced by more general convex constraints like positive semidefiniteness or copositivity conditions, despite the fact that the objective can be even linear. This paper studies exact penalizations of (classical) quadratic programs, i.e., optimization of quadratic functions over a polyhedron, and applies the results to establish a Frank-Wolfe-type theorem for the primal-dual pair of a class of conic programs that frequently arises in applications. One result is that uniqueness of the solution of the primal ensures dual attainability, i.e., existence of the solution of the dual. [ABSTRACT FROM AUTHOR]

In a recent paper, Gamarnik and Zeevi [Gamarnik, D., A. Zeevi. 2006. Validity of heavy traffic steady-state approximations in open queueing networks. Ann. Appl. Probab. 16(1) 56-90], it was shown that under suitable conditions stationary distributions of the (scaled) queue-lengths process for a generalized Jackson network converge to the stationary distribution of the associated reflected Brownian motion in the heavy traffic limit. The proof relied on certain exponential integrability assumptions on the primitives of the network. In this note we show that the above result holds under much weaker integrability conditions. We provide an alternative proof of this result assuming (in addition to natural heavy traffic and stability assumptions) only standard independence and square integrability conditions on the network primitives that are commonly used in heavy traffic analysis. Furthermore, under additional integrability conditions we establish convergence of moments of stationary distributions. [ABSTRACT FROM AUTHOR]

In this paper, we present a new approach to constructing schemes for unconstrained convex minimization, which computes approximate solutions with a certain relative accuracy. This approach is based on a special conic model of the unconstrained minimization problem. Using a structural model of the objective function, we can employ the efficient smoothing technique. The fastest of our algorithms solves a linear programming problem with relative accuracy δ in at most e ⋅ m½(2 + ln m) ⋅ (1+1/δ) iterations of a gradient-type scheme, where m is the largest dimension of the problem and e is the Euler number. [ABSTRACT FROM AUTHOR]

Recently, Chan and Sun [Chan, Z. X., D. Sun. Constraint nondegeneracy, strong regularity and nonsingularity in semidefinite programming. SIAM J. Optim. 19 370-376.] reported for semidefinite programming (SDP) that the primal/dual constraint nondegeneracy is equivalent to the dual/primal strong second order sufficient condition (SSOSC). This result is responsible for a number of important results in stability analysis of SDP. In this paper, we study duality of this type in nonlinear semidefinite programming (NSDP). We introduce the dual SSOSC at a Karush-Kuhn-Tucker (KKT) triple of NSDP and study its various characterizations and relationships to the primal nondegeneracy. Although the dual SSOSC is nothing but the SSOSC for the Wolfe dual of the NSDP, it suggests new information for the primal NSDP. For example, it ensures that the inverse of the Hessian of the Lagrangian function exists at the KKT triple and the inverse is positive definite on some normal space. It also ensures the primal nondegeneracy. Some of our results generalize the corresponding classical duality results in nonlinear programming studied by Fujiwara et al. [Fujiwara, O., S.-P. Han, O. L. Mangasarian. 1984. Local duality of nonlinear programs. SIAM J. Control Optim. 22 162-169]. For the convex quadratic SDP (QSDP), we have complete characterizations for the primal and dual SSOSC. Our results reveal that the nearest correlation matrix problem satisfies not only the primal and dual SSOSC but also the primal and dual nondegeneracy at its solution, suggesting that it is a well-conditioned QSDP. [ABSTRACT FROM AUTHOR]

Let M be a matroid on E υ {l}, where l ∉ E is a distinguished element of M, The l-port of M is the set 풫 = {P: P ⊆ E with P υ {l} a circuit of M}. Let A be the 풫-E incidence matrix. Let U2,4 be the uniform matroid on four elements of rank two, let F7 be the Fano matroid, let F7* be the dual of F7, and let F7+ be the unique series extension of F7. In this paper, we prove that the system Ax ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI) if and only if M has no U2.4-minor using l, no F7*-minor using l, and no F7+-minor using l as a series element. Our characterization yields a number of interesting results in combinatorial optimization. [ABSTRACT FROM AUTHOR]

A definition of setwise differentiability for set functions is given through refining the partitions of sets. Such a construction is closely related to the one proposed by Rosenmuller [Rosenmuller, J. 1977. Extreme Games and Their Solutions. Springer-Verlag, Berlin], Epstein [Epstein, L. 1999. A definition of uncertainty aversion. Rev. Econom. Stud. 66 579-608], and Epstein and Marinacci [Epstein, L., M. Marinacci. 2001. The core of large differentiable TU games. J. Econom. Theory 100 235-273]. We present several classes of transferable utility (TU) games that are differentiable and study differentiation rules. The last part of this paper applies refinement derivatives to the computation of value of games. Following Hart and Mas-Colell [Hart, S., A. Mas-Colell. 1989. Potential, value and consistency. Econometrica 57 589-614], we define an operator through the refinement derivative of the potential of the game. We show that this operator is a value, when restricted to the spaces pM∞ and POT2. The latter space is closely related to Myerson's balanced contributions axiom. [ABSTRACT FROM AUTHOR]

Successful efficient rare-event simulation typically involves using importance sampling tailored to a specific rare event. However, in applications one may be interested in simultaneous estimation of many probabilities or even an entire distribution. In this paper, we address this issue in a simple but fundamental setting. Specifically, we consider the problem of efficient estimation of the probabilities P(Sn ≥ na) for large n, for all a lying in an interval A, where Sn denotes the sum of n independent, identically distributed light-tailed random variables. Importance sampling based on exponential twisting is known to produce asymptotically efficient estimates when A reduces to a single point. We show, however, that this procedure fails to be asymptotically efficient throughout A when A contains more than one point. We analyze the best performance that can be achieved using a discrete mixture of exponentially twisted distributions, and then present a method using a continuous mixture. We show that a continuous mixture of exponentially twisted probabilities and a discrete mixture with a sufficiently large number of components produce asymptotically efficient estimates for all a ∊ A simultaneously. [ABSTRACT FROM AUTHOR]