-
作者：Aprile, Manuel; Conforti, Michele; Di Summa, Marco
作者单位：University of Padua
摘要：A binarization of a bounded variable x is obtained via a system of linear inequalities that involve x together with additional variables y(1), ... , y(t) in [0,1] so that the integrality of x is implied by the integrality of y(1), ... , y(t). A binary extended formulation of a mixedinteger linear set is obtained by adding to its original description binarizations of its integer variables. Binary extended formulations are useful in mixed-integer programming as imposing integrality on 0/1 variab...
-
作者：Vazirani, Vijay V.
作者单位：University of California System; University of California Irvine
摘要：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 expo...
-
作者：Cashore, J. Massey; Frazier, Peter I.; Tardos, Eva
作者单位：Cornell University; Cornell University
摘要：Using prices induced by dual variables of a centralized optimization problem induces welfare-optimal equilibria among strategic drivers. We reveal a stark deficiency of such static pricing algorithms: it is possible for them to induce additional equilibria with arbitrarily low social welfare. Moreover, small perturbations to the marketplace, such as those caused by idiosyncratic randomness or model misspecification, can cause the welfare-optimal equilibrium to be Pareto-dominated (in terms of ...
-
作者：Zhang, Chao; Chen, Xiaojun; Ma, Shiqian
作者单位：Beijing Jiaotong University; Hong Kong Polytechnic University; Rice University
摘要：In this paper, we study the generalized subdifferentials and the Riemannian gradient subconsistency that are the basis for non-Lipschitz optimization on embedded sub manifolds of R-n. 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 emp...
-
作者：Beissner, Patrick; Boonen, Tim; Ghossoub, Mario
作者单位：Australian National University; University of Hong Kong; University of Waterloo
摘要：In a pure-exchange economy with no aggregate uncertainty, we characterize in closed form and full generality Pareto-optimal allocations between two agents who maximize (nonconcave) rank-dependent utilities (RDU). We then derive a necessary and sufficient condition for Pareto optima to be no-betting allocations (i.e., deterministic allocations or full insurance allocations). This condition depends only on the probability weighting functions of the two agents and not on their (concave) utility o...
-
作者：van Ackooij, Wim; Perez-Aros, Pedro; Soto, Claudia; Vilches, Emilio
作者单位：Electricite de France (EDF); Universidad de O'Higgins; Universidad de Chile
摘要：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 constr...
-
作者：Bianchi, Pascal; Hachem, Walid; Schechtman, Sholom
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite Gustave-Eiffel; Centre National de la Recherche Scientifique (CNRS)
摘要：In nonsmooth stochastic optimization, we establish the nonconvergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold M, where the function f has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of f is lower-bounded. We require two conditions on f. The first assumption is a Verdier stratification condition, which is a refine...
-
作者：Kunimoto, Takashi; Saran, Rene; Serrano, Roberto
作者单位：Singapore Management University; University System of Ohio; University of Cincinnati; Brown University
摘要：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 rationaliz...
-
作者：Flesch, Janos; Solan, Eilon
作者单位：Maastricht University; Tel Aviv University
摘要：We consider multiplayer stochastic games with finitely many players and actions, and countably many states, in which the payoff of each player is a bounded and Borelmeasurable function of the infinite play. By using a generalization of the technique of Martin [Martin DA (1998) The determinacy of Blackwell games. J. Symb. Log. 63(4):1565-1581] and Maitra and Sudderth [Maitra A, Sudderth W (1998) Finitely additive stochastic games with Borel measurable payoffs. Internat. J. Game Theory 27:257-26...
-
作者：Papadimitriou, Christos; Pollner, Tristan; Saberi, Amin; Wajc, David
作者单位：Columbia University; Stanford University; Alphabet Inc.; Google Incorporated
摘要：The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a prophet who knows the future. An equally natural, though significantly less wellstudied, benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it? M...
