Search

This paper develops algorithms to solve strong-substitutes product-mix auctions: it finds competitive equilibrium prices and quantities for agents who use this auction's bidding language to truthfully express their strong-substitutes preferences over an arbitrary number of goods, each of which is available in multiple discrete units. Our use of the bidding language and the information it provides contrasts with existing algorithms that rely on access to a valuation or demand oracle. We compute market-clearing prices using algorithms that apply existing submodular minimization methods. Allocating the supply among the bidders at these prices then requires solving a novel constrained matching problem. Our algorithm iteratively simplifies the allocation problem, perturbing bids and prices in a way that resolves tie-breaking choices created by bids that can be accepted on more than one good. We provide practical running time bounds on both price finding and allocation and illustrate experimentally that our allocation mechanism is practical. Funding: E. Baldwin and P. Klemperer were supported by the Economic and Social Research Council [Grant ES/L003058/1]. P. W. Goldberg and E. Lock were supported by a JP Morgan faculty fellowship during the work on the final version of the paper. Supplemental Material: The online companion is available at https://doi.org/10.1287/moor.2019.0248. [ABSTRACT FROM AUTHOR]

The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various "footholds" offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. Funding: This work was supported in part by the National Science Foundation [Grant CCF-2230414]. [ABSTRACT FROM AUTHOR]

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]

In this paper, we propose a general procedure for establishing the geometric landscape connections of a Riemannian optimization problem under the embedded and quotient geometries. By applying the general procedure to the fixed-rank positive semidefinite (PSD) and general matrix optimization, we establish an exact Riemannian gradient connection under two geometries at every point on the manifold and sandwich inequalities between the spectra of Riemannian Hessians at Riemannian first-order stationary points (FOSPs). These results immediately imply an equivalence on the sets of Riemannian FOSPs, Riemannian second-order stationary points (SOSPs), and strict saddles of fixed-rank matrix optimization under the embedded and the quotient geometries. To the best of our knowledge, this is the first geometric landscape connection between the embedded and the quotient geometries for fixed-rank matrix optimization, and it provides a concrete example of how these two geometries are connected in Riemannian optimization. In addition, the effects of the Riemannian metric and quotient structure on the landscape connection are discussed. We also observe an algorithmic connection between two geometries with some specific Riemannian metrics in fixed-rank matrix optimization: there is an equivalence between gradient flows under two geometries with shared spectra of Riemannian Hessians. A number of novel ideas and technical ingredients—including a unified treatment for different Riemannian metrics, novel metrics for the Stiefel manifold, and new horizontal space representations under quotient geometries—are developed to obtain our results. The results in this paper deepen our understanding of geometric and algorithmic connections of Riemannian optimization under different Riemannian geometries and provide a few new theoretical insights to unanswered questions in the literature. Funding: X. Li was partially supported by National Key R&D Program of China [Grants 2020YFA0711900, 2020YFA0711901], the National Natural Science Foundation of China [Grants 12271107, 62141407], the Young Elite Scientists Sponsorship Program by CAST [Grant 2019QNRC001], the "Chenguang Program" by the Shanghai Education Development Foundation and Shanghai Municipal Education Commission [Grant 19CG02], the Shanghai Science and Technology Program [21JC1400600]. Y. Luo and A. R. Zhang were partially supported by the National Science Foundation [CAREER-2203741]. [ABSTRACT FROM AUTHOR]

This paper presents a proximal bundle (PB) framework based on a generic bundle update scheme for solving the hybrid convex composite optimization (HCCO) problem and establishes a common iteration-complexity bound for any variant belonging to it. As a consequence, iteration-complexity bounds for three PB variants based on different bundle update schemes are obtained in the HCCO context for the first time and in a unified manner. Although two of the PB variants are universal (i.e., their implementations do not require parameters associated with the HCCO instance), the other newly (as far as the authors are aware) proposed one is not, but has the advantage that it generates simple—namely, one-cut—bundle models. The paper also presents a universal adaptive PB variant (which is not necessarily an instance of the framework) based on one-cut models and shows that its iteration-complexity is the same as the two aforementioned universal PB variants. Funding: Financial support from the Office of Naval Research [N00014-18-1-2077] and the Air Force Office of Scientific Research [Grant FA9550-22-1-0088] is gratefully acknowledged. [ABSTRACT FROM AUTHOR]

Temporal difference learning (TD), coupled with neural networks, is among the most fundamental building blocks of deep reinforcement learning. However, because of the nonlinearity in value function approximation, such a coupling leads to nonconvexity and even divergence in optimization. As a result, the global convergence of neural TD remains unclear. In this paper, we prove for the first time that neural TD converges at a sublinear rate to the global optimum of the mean-squared projected Bellman error for policy evaluation. In particular, we show how such global convergence is enabled by the overparameterization of neural networks, which also plays a vital role in the empirical success of neural TD. We establish the theory for two-layer neural networks in the main paper and extend them to multilayer neural networks in the appendix. Beyond policy evaluation, we establish the global convergence of neural (soft) Q learning. Funding: Z. Yang acknowledges the Theory of Reinforceement Learning program at Simons Institute. J. D. Lee acknowledges support of the ARO under MURI Award W911NF-11-1-0304, the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, ONR Young Investigator Award, and NSF-CAREER under award #2144994. Z. Wang acknowledges National Science Foundation [Awards 2048075, 2008827, 2015568, 1934931], Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports. [ABSTRACT FROM AUTHOR]

Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics, and data analytics. In this paper, based on the augmented Lagrangian function, we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a stationary solution at the rate of o(1/k) , where k is the number of iterations. Moreover, under an additional error bound condition (to be called HVP-EB in the paper) with exponent θ∈(0,1) , we further show the global convergence of NAPP-AL. Additionally, if θ∈(0,12] , then we furthermore show that the convergence rate is in fact linear. Finally, we show that the well-known Kurdyka-Łojasiewicz property and the Hölderian metric subregularity imply the aforementioned HVP-EB condition. We demonstrate that under mild conditions, NAPP-AL can also be interpreted as a variant of the forward-backward operator splitting method in this context. Funding: This work was supported by the National Natural Science Foundation of China [Grant 71871140]. [ABSTRACT FROM AUTHOR]

We consider the canonical revenue management (RM) problem wherein a seller must sell an inventory of some product over a finite horizon via an anonymous, posted price mechanism. Unlike typical models in RM, we assume that customers are forward looking. In particular, customers arrive randomly over time and strategize about their times of purchases. The private valuations of these customers decay over time and the customers incur monitoring costs; both the rates of decay and these monitoring costs are private information. This setting has resisted the design of optimal dynamic mechanisms heretofore. Optimal pricing schemes—an almost necessary mechanism format for practical RM considerations—have been similarly elusive. The present paper proposes a mechanism we dub robust pricing. Robust pricing is guaranteed to achieve expected revenues that are at least within 29% of those under an optimal (not necessarily posted price) dynamic mechanism. We thus provide the first approximation algorithm for this problem. The robust pricing mechanism is practical, since it is an anonymous posted price mechanism and since the seller can compute the robust pricing policy for a problem without any knowledge of the distribution of customer discount factors and monitoring costs. The robust pricing mechanism also enjoys the simple interpretation of solving a dynamic pricing problem for myopic customers with the additional requirement of a novel "restricted sub-martingale constraint" on prices that discourages rapid discounting. We believe this interpretation is attractive to practitioners. Finally, numerical experiments suggest that the robust pricing mechanism is, for all intents, near optimal. [ABSTRACT FROM AUTHOR]

This paper studies the dynamic portfolio choice problem with ambiguous jump risks in a multidimensional jump-diffusion framework.We formulate a continuous-time model of incomplete market with uncertain jumps. We develop an efficient pathwise optimization procedure based on the martingale methods and minimax results to obtain closed-form solutions for the indirect utility function and the probability of the worst scenario. We then introduce an orthogonal decomposition method for the multi-dimensional problem to derive the optimal portfolio strategy explicitly under ambiguity aversion to jump risks. Finally, we calibrate our model to real market data drawn from 10 international indices and illustrate our results by numerical examples. The certainty equivalent losses affirm the importance of jump uncertainty in optimal portfolio choice. [ABSTRACT FROM AUTHOR]

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 Ω ( 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 1 / 2 + ϵ ⁡ log k) for any arbitrarily small ϵ > 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. The online appendix is available at https://doi.org/10.1287/moor.2018.0937. [ABSTRACT FROM AUTHOR]

There is an error in our paper [Paul A, Freund D, Ferber A, Shmoys DB, Williamson DP (2020) Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2):576–590]. In that paper, we consider constrained versions of the prize-collecting traveling salesman and the prize-collecting minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. Rooted variants of the problems have the additional constraint that a given vertex, the root, must be contained in the tour/tree. In our previous paper, we present a 2-approximation algorithm for the rooted and unrooted versions of both the tree and tour variants using a parameterized primal–dual approach. Here, we illustrate an error in the proof of a lemma for the rooted version of the algorithm and show that the algorithm has no finite approximation guarantee for the rooted version of the problem. We also show that the lemma and the approximation guarantee of 2 continue to hold true for the unrooted version. This leaves the best-known approximations for the rooted tour an established (2 + ϵ) -approximation algorithm and for the tree variant a previously published poly-log approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes and develops a new Newton-type algorithm to solve subdifferential inclusions defined by subgradients of extended real-valued prox-regular functions. The proposed algorithm is formulated in terms of the second order subdifferential of such functions that enjoy extensive calculus rules and can be efficiently computed for broad classes of extended real-valued functions. Based on this and on the metric regularity and subregularity properties of subgradient mappings, we establish verifiable conditions ensuring the well-posedness of the proposed algorithm and its local superlinear convergence. The obtained results are also new for the class of equations defined by continuously differentiable functions with Lipschitzian gradients ( C 1 , 1 functions), which is the underlying case of our consideration. The developed algorithms for prox-regular functions and their extension to a structured class of composite functions are formulated in terms of proximal mappings and forward–backward envelopes. Besides numerous illustrative examples and comparison with known algorithms for C 1 , 1 functions and generalized equations, the paper presents applications of the proposed algorithms to regularized least square problems arising in statistics, machine learning, and related disciplines. Funding: Research of P. D. Khanh is funded by Ho Chi Minh City University of Education Foundation for Science and Technology [Grant CS.2022.19.20TD]. Research of B. Mordukhovich and V. T. Phat was partly supported by the U.S. National Science Foundation [Grants DMS-1808978 and DMS-2204519]. The research of B. Mordukhovich was also supported by the Air Force Office of Scientific Research [Grant 15RT0462] and the Australian Research Council under Discovery Project DP-190100555. This work was supported by the Air Force Office of Scientific Research [Grant 15RT0462]. [ABSTRACT FROM AUTHOR]

In this paper, we study the generalized subdifferentials and the Riemannian gradient subconsistency that are the basis for non-Lipschitz optimization on embedded submanifolds of Rn. We then propose a Riemannian smoothing steepest descent method for non-Lipschitz optimization on complete embedded submanifolds of Rn. We prove that any accumulation point of the sequence generated by the Riemannian smoothing steepest descent method is a stationary point associated with the smoothing function employed in the method, which is necessary for the local optimality of the original non-Lipschitz problem. We also prove that any accumulation point of the sequence generated by our method that satisfies the Riemannian gradient subconsistency is a limiting stationary point of the original non-Lipschitz problem. Numerical experiments are conducted to demonstrate the advantages of Riemannian ℓp (0

This paper investigates rationalizable implementation of social choice functions (SCFs) in incomplete information environments. We identify weak interim rationalizable monotonicity (weak IRM) as a novel condition and show it to be a necessary and almost sufficient condition for rationalizable implementation. We show by means of robust examples that interim rationalizable monotonicity (IRM), found in the literature, is strictly stronger than weak IRM and that IRM is not necessary for rationalizable implementation, as had been previously claimed. These examples also demonstrate that Bayesian monotonicity, the key condition for full Bayesian implementation, is not necessary for rationalizable implementation. That is, rationalizable implementation can be more permissive than Bayesian implementation. We revisit well-studied classes of economic environments and show that the SCFs considered there are interim rationalizable implementable. A comprehensive discussion of related issues, including well-behaved mechanisms, mechanisms satisfying the best response property, double implementation, and responsive SCFs is also provided. Funding: This work was supported by Ministry of Education, Singapore [Grant MOE Academic Research Fund Tier 2/MOE-T2EP402A20-0]. [ABSTRACT FROM AUTHOR]

This paper concerns discrete-time infinite-horizon stochastic control systems with Borel state and action spaces and universally measurable policies. We study optimization problems on strategic measures induced by the policies in these systems. The results are then applied to risk-neutral and risk-sensitive Markov decision processes to establish the measurability of the optimal value functions and the existence of universally measurable, randomized or nonrandomized, ϵ-optimal policies, for a variety of average cost criteria and risk criteria. We also extend our analysis to a class of minimax control problems and establish similar optimality results under the axiom of analytic determinacy. Funding: This work was supported by grants from DeepMind, the Alberta Machine Intelligence Institute (AMII), and Alberta Innovates-Technology Futures (AITF). [ABSTRACT FROM AUTHOR]

The progressive hedging algorithm (PHA) is an effective solution method for solving monotone stochastic variational inequalities (SVIs). However, this validity is based on the assumption of global maximal monotonicity. In this paper, we propose a localized PHA for solving nonmonotone SVIs and show that its validity is based on the weaker assumption of locally elicitable maximal monotonicity. Furthermore, we prove that such assumption holds when the mapping involved in the SVI is locally elicitable monotone or locally monotone. The local convergence of the proposed algorithm is established, and it is shown that the localized PHA has the rate of linear convergence under some mild assumptions. Some numerical experiments, including a two-stage orange market problem and randomly generated two-stage piecewise stochastic linear complementarity problems, indicate that the proposed algorithm is efficient. Funding: This work was supported by the National Natural Science Foundation of China [Grant 12171271]. [ABSTRACT FROM AUTHOR]

Optimization problems with uncertainty in the constraints occur in many applications. Particularly, probability functions present a natural form to deal with this situation. Nevertheless, in some cases, the resulting probability functions are nonsmooth, which motivates us to propose a regularization employing the Moreau envelope of a scalar representation of the vector inequality. More precisely, we consider a probability function that covers most of the general classes of probabilistic constraints: φ(x)=P(Φ(x,ξ)∈−K), where K is a convex cone of a Banach space. The conic inclusion Φ(x,ξ)∈−K represents an abstract system of inequalities, and ξ is a random vector. We propose a regularization by applying the Moreau envelope to the scalarization of the function Φ. In this paper, we demonstrate, under mild assumptions, the smoothness of such a regularization and that it satisfies a type of variational convergence to the original probability function. Consequently, when considering an appropriately structured problem involving probabilistic constraints, we can, thus, entail the convergence of the minimizers of the regularized approximate problems to the minimizers of the original problem. Finally, we illustrate our results with examples and applications in the field of (nonsmooth) joint, semidefinite, and probust chance-constrained optimization problems. Funding: P. Pérez-Aros was supported by Centro de Modelamiento Matemático [Grants ACE210010 and FB210005] and BASAL funds for center of excellence and ANID-Chile grant Fondecyt Regular [Grants 1200283 and 1190110] and Fondecyt Exploración [Grant 13220097]. C. Soto was supported by the National Agency for Research and Development (ANID)/Scholarship Program/Doctorado Nacional Chile [Grant 2017-21170428]. E. Vilches was supported by Centro de Modelamiento Matemático [Grants ACE210010 and FB210005] and BASAL funds for center of excellence and Fondecyt Regular [Grant 1200283] and Fondecyt Exploración [Grant 13220097] from ANID-Chile. [ABSTRACT FROM AUTHOR]

Daniilidis and Drusviatskiy, in 2017, extended the celebrated Kurdyka–Łojasiewicz inequality from definable functions to definable multivalued maps by establishing that the coderivative mapping admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process. In this paper, working outside the framework of o-minimal geometry, we characterize the existence of a desingularization for the coderivative in terms of the behavior of the sweeping process orbits and the integrability of the talweg function. These results are close in spirit with the ones in Bolte et al., 2010, in which characterizations for the desingularization of the (sub)gradient of functions is obtained. Funding: A. Daniilidis was supported by the Austrian Science Fund [Grant FWF P-36344N], Fondo Nacional de Desarrollo Científico y Tecnológico [Grant 1211217], and Centro de Modelamiento Matemático [Grant FB210005]. S. Tapia was supported by Agencia Nacional de Investigación y Desarrollo (Chile)-Programa de Fortalecimiento de Capital Humano Académico Doctorado Nacional [Grant 2018-21181905]. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the problem of minimizing the sum of a nonconvex differentiable function and a difference of convex (DC) function, where the differentiable function is not restricted to the global Lipschitz gradient continuity assumption. This problem covers a broad range of applications in machine learning and statistics, such as compressed sensing, signal recovery, sparse dictionary learning, matrix factorization, etc. We first take inspiration from the Nesterov acceleration technique and the DC algorithm to develop a novel algorithm for the considered problem. We then study the subsequential convergence of our algorithm to a critical point. Furthermore, we justify the global convergence of the whole sequence generated by our algorithm to a critical point and establish its convergence rate under the Kurdyka–Łojasiewicz condition. Numerical experiments on the nonnegative matrix completion problem are performed to demonstrate the efficiency of our algorithm and its superiority over well-known methods. [ABSTRACT FROM AUTHOR]

In this paper, we extend previous results on weak approachability in generalized quitting games with vector payoffs to the general case of absorbing games. Specifically, we show that a necessary condition and a different sufficient condition for weak approachability of a convex set, established by Flesch, Laraki, and Perchet, remain valid in the general case. To do so, we extend results on Blackwell approachability to a setup in which stage weights depend on past actions as well as the current action of player 1 (the approaching player). Additionally, we prove that the strategy used to approach the convex set can be defined in blocks of fixed length, and so it has bounded memory and can be implemented by a finite automata. [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. [ABSTRACT FROM AUTHOR]

In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensätze from the late 20th century (e.g., due to Stengle, Putinar, or Schmüdgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellensätze dating back to the early 20th century that only certify positivity of a polynomial globally. More precisely, we show that any inner approximation to the cone of positive homogeneous polynomials that is arbitrarily tight can be turned into a converging hierarchy of lower bounds for general polynomial minimization problems with compact feasible sets. This in particular leads to a semidefinite programming–based hierarchy that relies solely on Artin's solution to Hilbert's 17th problem. We also use a classical result from Pólya on global positivity of even forms to construct an "optimization-free" converging hierarchy for general polynomial minimization problems with compact feasible sets. This hierarchy requires only polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming–based and second-order cone programming–based hierarchies for polynomial minimization problems that rely on the recently introduced concepts of diagonally dominant sum of squares and scaled diagonally dominant sum of squares polynomials. We remark that the scope of this paper is theoretical at this stage, as our hierarchies—though they involve at most two sum of squares constraints or only elementary arithmetic at each level—require the use of bisection and increase the number of variables (respectively, the degree) of the problem by the number of inequality constraints plus three (respectively, by a factor of two). [ABSTRACT FROM AUTHOR]

As one of the most plausible convex optimization methods for sparse data reconstruction, ℓ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 ℓ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 ℓ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 ℓ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 ℓ1-minimization is robustly and weakly stable in recovering sparse data from inaccurate measurements. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm+ (CBA+), a new parameter- and scale-free regret minimizer for general convex compact sets. CBA+ is based on Blackwell approachability and attains O(T) regret. We show how to efficiently instantiate CBA+ for many decision sets of interest, including the simplex, ℓp norm balls, and ellipsoidal confidence regions in the simplex. Based on CBA+ , we introduce SP-CBA+ , a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a O(1/T) ergodic convergence rate. In our simulations, we demonstrate the wide applicability of SP-CBA+ on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, SP-CBA+ achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters. Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361]. [ABSTRACT FROM AUTHOR]

Binary matrix factorization is an essential tool for identifying discrete patterns in binary data. In this paper, we consider the rank-k binary matrix factorization problem (k-BMF) under Boolean arithmetic: we are given an n × m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n × k and k × m, respectively, which minimize the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak linear programming (LP) relaxation, whereas the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times the zero is erroneously covered in a rank-k factorization. For one of the exponential size Ips, we describe a computational approach based on column generation. Experimental results on synthetic and real-world data sets suggest that our integer programming approach is competitive against available methods for k-BMF and provides accurate low-error factorizations. Funding: O. Günlük was partially supported by the Office of Naval Research [Grant N00014-21-1-2575]. R. Á. Kovács was supported by a doctoral scholarship from The Alan Turing Institute under the EPSRC [Grant EP/N510129/1] and the Office for National Statistics. R. A. Hauser was supported by The Alan Turing Institute under the EPSRC [Grant EP/N510129/1]. [ABSTRACT FROM AUTHOR]

The paper investigates quadratic hedging in a semimartingale market that does not necessarily contain a risk-free asset. An equivalence result for hedging with and without numeraire change is established. This permits direct computation of the optimal strategy without choosing a reference asset and/or performing a numeraire change. New explicit expressions for optimal strategies are obtained, featuring the use of oblique projections that provide unified treatment of the case with and without a risk-free asset. The analysis yields a streamlined computation of the efficient frontier for the pure investment problem in terms of three easily interpreted processes. The main result advances our understanding of the efficient frontier formation in the most general case in which a risk-free asset may not be present. Several illustrations of the numeraire-invariant approach are given. [ABSTRACT FROM AUTHOR]

The secretary problem is probably the purest model of decision making under uncertainty. In this paper, we ask which advice we can give the algorithm to improve its success probability. We propose a general model that unifies a broad range of problems: from the classic secretary problem with no advice to the variant where the quality of a secretary is drawn from a known distribution and the algorithm learns each candidate's quality on arrival, more modern versions of advice in the form of samples, and a machine-learning inspired model where a classifier gives us a noisy signal about whether the current secretary is the best on the market. Our main technique is a factor-revealing linear program (LP) that captures all of these problems. We use this LP formulation to gain structural insight into the optimal policy. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and optimal algorithms for a new noisy binary advice model. [ABSTRACT FROM AUTHOR]

This paper studies Nash equilibrium problems that are given by polynomial functions. We formulate efficient polynomial optimization problems for computing Nash equilibria. The Moment-sum-of-squares relaxations are used to solve them. Under generic assumptions, the method can find a Nash equilibrium, if there is one. Moreover, it can find all Nash equilibria if there are finitely many ones of them. The method can also detect nonexistence if there is no Nash equilibrium. Funding: J. Nie was supported by the National Science Foundation [Grant DMS-2110780]. [ABSTRACT FROM AUTHOR]

The k- traveling salesman problem (k-TSP) seeks a tour of minimal length that visits a subset of k≤n points. The traveling repairman problem (TRP) seeks a complete tour with minimal latency. This paper provides constant-factor probabilistic approximations of both problems. We first show that the optimal length of the k-TSP path grows at a rate of Θ(k/nk/(2(k−1))). The proof provides a constant-factor approximation scheme, which solves a TSP in a high-concentration zone, leveraging large deviations of local concentrations. Then, we show that the optimal TRP latency grows at a rate of Θ(nn). This result extends the classic Beardwood–Halton–Hammersley theorem to the TRP. Again, the proof provides a constant-factor approximation scheme, which visits zones by decreasing order of probability density. We discuss practical implications of this result in the design of transportation and logistics systems. Finally, we propose dedicated notions of fairness—randomized population-based fairness for the k-TSP and geographic fairness for the TRP—and give algorithms to balance efficiency and fairness. Funding: This work was partly supported by [Grant ONR N00014-18-1-2122] and the Singapore National Research Foundation through the Singapore–Massachusetts Institute of Technology Alliance for Research and Technology Centre for Future Urban Mobility. Supplemental Material: The e-companion is available at https://doi.org/10.1287/moor.2021.0286. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [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.

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. [ABSTRACT FROM AUTHOR]

After showing, by means of a series of examples, that paradigms alternative to the Bayesian one obtain by simply replacing the notion of approximation associated with the latter, the paper presents a unified framework for theories of decision making and inference. Given a statistical model, the algebra of bounded random variables on the sample space is mapped homomorphically into an algebra of operators on a certain Hilbert space. Then, the choice of a norm or a divergence function on the latter algebra produces a theory of decision making and inference. Examples include models from the Choquet expected utility class, models from robust statistics, the smooth model, maxmin and maxmax (as limiting cases) as well as a novel theory. The paper also contributes to Bayesian theory, which obtains in correspondence to a Hilbert norm. It shows that Bayes' theorem can be derived from the fundamental concept of conditional expectation and that it is the only updating rule for which the operations of updating and of calculating the predictive commute. [ABSTRACT FROM AUTHOR]

Contextual dynamic pricing aims to set personalized prices based on sequential interactions with customers. At each time period, a customer who is interested in purchasing a product comes to the platform. The customer's valuation for the product is a linear function of contexts, including product and customer features, plus some random market noise. The seller does not observe the customer's true valuation, but instead needs to learn the valuation by leveraging contextual information and historic binary purchase feedback. Existing models typically assume full or partial knowledge of the random noise distribution. In this paper, we consider contextual dynamic pricing with unknown random noise in the linear valuation model. Our distribution-free pricing policy learns both the contextual function and the market noise simultaneously. A key ingredient of our method is a novel perturbed linear bandit framework, in which a modified linear upper confidence bound algorithm is proposed to balance the exploration of market noise and the exploitation of the current knowledge for better pricing. We establish the regret upper bound and a matching lower bound of our policy in the perturbed linear bandit framework and prove a sublinear regret bound in the considered pricing problem. Finally, we demonstrate the superior performance of our policy on simulations and a real-life auto loan data set. Funding: Y. Liu and W.W. Sun acknowledge support from the National Science Foundation Division of Social and Economic Sciences [Grant NSF-SES 2217440]. Supplemental Material: The supplementary material is available at https://doi.org/10.1287/moor.2023.1369. [ABSTRACT FROM AUTHOR]

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash social welfare on the Pareto frontier of the set of feasible utilities. The Pareto frontier may contain many such points and, consequently, the outcome of the competitive rule is no longer unique. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive utility profile can be constructed via an explicit formula; each candidate can be checked for competitiveness and the allocation can be reconstructed using a maximum flow computation. Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy. Funding: This work was supported by National Science Foundation (CNS 1518941); Lady Davis Fellowship Trust, Hebrew University of Jerusalem; H2020 European Research Council (740435); Linde Institute at Caltech. [ABSTRACT FROM AUTHOR]

In this paper, we perform a sensitivity analysis for the maximal value function, which is the optimal value function for a parametric maximization problem. Our aim is to study various subdifferentials for the maximal value function. We obtain upper estimates of Fréchet, limiting, and horizon subdifferentials of the maximal value function by using some sensitivity analysis techniques sophisticatedly. The derived upper estimates depend only on the union of all solutions and not on its convex hull or only one solution from the solution set. Finally, we apply the derived results to develop some new necessary optimality conditions for nonconvex minimax problems. In the nonconvex-concave setting, our Wolfe duality approach compares favorably with the first-order approach in that the necessary condition is sharper and the constraint qualification is weaker. Funding: L. Guo was supported by the National Natural Science Foundation of China [Grants 72131007, 72140006, and 12271161] and the Natural Science Foundation of Shanghai [Grant 22ZR1415900]. J. J. Ye was partially supported by the Natural Sciences and Engineering Research Council of Canada. J. Zhang was supported by the National Natural Science Foundation of China [Grant 12222106], the Shenzhen Science and Technology Program [Grant RCYX20200714114700072], and the Guangdong Basic and Applied Basic Research Foundation [Grant 2022B1515020082]. [ABSTRACT FROM AUTHOR]

In this paper, we consider a personalized assortment planning problem under inventory constraints, where each arriving customer type is defined by a primary item of interest. As long as that item is in stock, the customer adds it to the shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with the primary item. This problem is motivated by the new "recommendation at checkout" systems that have been deployed at many online retailers, and it also serves as a framework that unifies many existing problems in online algorithms (e.g., personalized assortment planning, single-leg booking, and online matching with stochastic rewards). In our problem, add-on recommendation opportunities are eluded when primary items go out of stock, which poses additional challenges for the development of an online policy. We overcome these challenges by introducing the notion of an inventory protection level in expectation and derive an algorithm with a 1/4-competitive ratio guarantee under adversarial arrivals. Funding: This work was supported by the Adobe Data Science Research Award and the Alibaba Innovation Research Award. L. Xin was partly supported by the National Science Foundation (NSF) [Award CMMI-1635160], X. Chen was supported by the NSF [CAREER Award IIS-1845444]. W. Ma and D. Simchi-Levi were supported by the Accenture and MIT Alliance in Business Analytics. [ABSTRACT FROM AUTHOR]

In this paper, we consider optimization problems over closed embedded submanifolds of Rn , which are defined by the constraints c(x) = 0. We propose a class of constraint-dissolving approaches for these Riemannian optimization problems. In these proposed approaches, solving a Riemannian optimization problem is transferred into the unconstrained minimization of a constraint-dissolving function (CDF). Different from existing exact penalty functions, the exact gradient and Hessian of CDF are easy to compute. We study the theoretical properties of CDF and prove that the original problem and CDF have the same first-order and second-order stationary points, local minimizers, and Łojasiewicz exponents in a neighborhood of the feasible region. Remarkably, the convergence properties of our proposed constraint-dissolving approaches can be directly inherited from the existing rich results in unconstrained optimization. Therefore, the proposed constraint-dissolving approaches build up short cuts from unconstrained optimization to Riemannian optimization. Several illustrative examples further demonstrate the potential of our proposed constraint-dissolving approaches. Funding: The research of N. Xiao and K.-C. Toh is supported by the Ministry of Education of Singapore Academic Research Fund Tier 3 [Grant MOE-2019-T3-1-010]. The research of X. Liu is supported in part by the National Natural Science Foundation of China [Grants 12125108, 11971466, 12288201, 12021001, and 11991021]; the National Key R&D Program of China [Grants 2020YFA0711900 and 2020YFA0711904]; and the Key Research Program of Frontier Sciences, Chinese Academy of Sciences [Grant ZDBS-LY-7022]. [ABSTRACT FROM AUTHOR]

In this paper, we consider online learning in generalized linear contextual bandits where rewards are not immediately observed. Instead, rewards are available to the decision maker only after some delay, which is unknown and stochastic. Such delayed feedback occurs in several active learning settings, including product recommendation, personalized medical treatment selection, bidding in first-price auctions, and bond trading in over-the-counter markets. We study the performance of two well-known algorithms adapted to this delayed setting: one based on upper confidence bounds and the other based on Thompson sampling. We describe modifications on how these two algorithms should be adapted to handle delays and give regret characterizations for both algorithms. To the best of our knowledge, our regret bounds provide the first theoretical characterizations in generalized linear contextual bandits with large delays. Our results contribute to the broad landscape of contextual bandits literature by establishing that both algorithms can be made to be robust to delays, thereby helping clarify and reaffirm the empirical success of these two algorithms, which are widely deployed in modern recommendation engines. Funding: This work was supported by the National Science Foundation [Grants 2118199, 1915967, and CCF-2106508], the Air Force Office of Scientific Research [Award FA9550-20-1-0397], a Digital Twin research grant from Bain & Company, and a faculty research grant from New York University's Center for Global Economy and Business. [ABSTRACT FROM AUTHOR]

We consider the Brownian "spider process," also known as Walsh Brownian motion, first introduced by J. B. Walsh [Walsh JB (1978) A diffusion with a discontinuous local time. Asterisque 52:37–45]. The paper provides the best constant Cn for the inequality E D τ ≤ C n E τ , where τ is the class of all adapted and integrable stopping times and D denotes the diameter of the spider process measured in terms of the British rail metric. This solves a variant of the long-standing open "spider problem" due to L. E. Dubins. The proof relies on the explicit identification of the value function for the associated optimal stopping problem. Funding: P. A. Ernst thanks the Royal Society Wolfson Fellowship (RSWF\R2\222005) and the U.S. Office of Naval Research (ONR N00014-21-1-2672) for their support of this research. [ABSTRACT FROM AUTHOR]

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P):A⊤x≤u when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two fundamental algorithms for tackling (P) , namely, the simplex and interior-point methods, each of which can be easily implemented in a way that either produces a solution of (P) or proves that (P) is infeasible by producing a solution to the alternative system (Alt):Aλ=0, u⊤λ<0, λ≥0. This paper develops an oblivious ellipsoid algorithm (OEA) that either produces a solution of (P) or produces a solution of (Alt). Depending on the dimensions and other condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when n≪m. This is achieved in the first modified version by proving infeasibility without producing a solution of (Alt) , and in the second version by using more memory. Funding: J. Lamperski and R. M. Freund were supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0240]. [ABSTRACT FROM AUTHOR]

Let T=(V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if T\F contains no cycles (directed). A collection F of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of F. The purpose of this paper is to give a characterization of all tournaments T=(V,A) with the property that, for every nonnegative integral weight function w defined on A, the minimum total weight of a cycle is equal to the maximum size of an FAS packing. Funding: This work was supported by the National Natural Science Foundation of China [Grants 11801266 and 11971228]; the Chinese Academy of Sciences [Grants XDA27000000 and ZDBS-LY-7008]; the Ministry of Science and Technology of China [Grant 2018AAA0101002]; the Research Grants Council of Hong Kong; the Fundamental Research Funds for the Central Universities [Grant 020314380035]. [ABSTRACT FROM AUTHOR]

Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over T rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations, using as a benchmark the best fixed price in hindsight. More precisely, we prove the following tight bounds on the regret: Θ(T) for full-feedback (i.e., direct revelation mechanisms). Θ(T2/3) for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities. Θ(T) for realistic feedback and seller/buyer valuations with bounded densities. Θ(T) for realistic feedback and independent seller/buyer valuations. Θ(T) for the adversarial setting. Funding: This work was partially supported by the European Research Council Advanced [Grant 788893] AMDROMA "Algorithmic and Mechanism Design Research in Online Markets", the Ministero dell'Istruzione, dell'Università e della Ricerca PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets", the AI Interdisciplinary Institute ANITI (funded by the French "Investing for the Future—PIA3" program under the [Grant agreement ANR-19-PI3A-0004], the project BOLD from the French national research agency (ANR), the EU Horizon 2020 ICT-48 research and innovation action ELISE (European Learning and Intelligent Systems Excellence, [Grant agreement 951847]. [ABSTRACT FROM AUTHOR]

We study bankruptcy problems in financial networks in the presence of general bankruptcy laws. The set of clearing payment matrices is shown to be a lattice, which guarantees the existence of a greatest clearing payment and a least clearing payment. Multiplicity of clearing payment matrices is both a theoretical and a practical concern. We present a new condition for uniqueness that generalizes all the existing conditions proposed in the literature. Our condition depends on the decomposition of the financial network into strongly connected components. A strongly connected component that contains more than one agent is called a cycle, and the involved agents are called cyclical agents. If there is a cycle without successors, then one of the agents in such a cycle should have a strictly positive endowment. The division rule used by a cyclical agent with a strictly positive endowment should be positive monotonic, and the rule used by a cyclical agent with a zero endowment should be strictly monotonic. Because division rules involving priorities are not positive monotonic, uniqueness of the clearing payment matrix is a much bigger concern for such division rules than for proportional ones. As a final contribution of the paper, we exhibit the relationship between the uniqueness of clearing payment matrices and the continuity of bankruptcy rules, a property that is very much desired for stability of financial systems. Funding: This research was supported by the Higher Education Institutional Excellence Program 2020 of the Ministry of Innovation and Technology in the framework of the "Financial and Public Services" research project [Grant TKP2020-IKA-02] at Corvinus University of Budapest. P. Csóka received funding from the National Research, Development and Innovation Office [Grants K-120035 and K-138826]. [ABSTRACT FROM AUTHOR]