-
作者：von Stengel, Bernhard
作者单位：University of London; London School Economics & Political Science
摘要：The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig is known to be incomplete. We explain and combine classical theorems about solv-ing linear equations with nonnegative variables to give a correct alternative proof more directly than Adler. We also extend Dantzig's game so that any max-min strategy gives either an optimal LP solution or shows that none exists
-
作者：Emek, Yuval; Lavi, Ron; Niazadeh, Rad; Shi, Yangguang
作者单位：Technion Israel Institute of Technology; University of Bath; University of Chicago; Shandong University
摘要：An online problem called dynamic resource allocation with capacity constraints (DRACC) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. Because existing online learning techniques do not yield vanishing regret for this problem, we develop a novel online learning framework over deterministic Markov dec...
-
作者：Qin, Junjie; Vardi, Shai; Wierman, Adam
作者单位：Purdue University System; Purdue University; California Institute of Technology
摘要：We consider a minimization variant on the classical prophet inequality with monomial cost functions. A firm would like to procure some fixed amount of a divisible commodity from sellers that arrive sequentially. Whenever a seller arrives, the seller's cost function is revealed, and the firm chooses how much of the commodity to buy. We first show that if one restricts the set of distributions for the coefficients to a family of natural distributions that include, for example, the uniform and tr...
-
作者：Hu, Hao; Li, Xinxin; Im, Haesol; Wolkowicz, Henry
作者单位：Clemson University; University of Waterloo; Jilin University
摘要：We study a semismooth Newton-type method for the nearest doubly stochastic matrix problem where the nonsingularity of the Jacobian can fail. The optimality conditions for this problem are formulated as a system of strongly semismooth functions. We show that the nonsingularity of the Jacobian does not hold for this system. By exploiting the problem structure, we construct a modified two step semismooth Newton method that guarantees a nonsingular Jacobian matrix at each iteration, and that conve...
-
作者：Luo, Yuetian; Li, Xudong; Zhang, Anru R.
作者单位：University of Chicago; Fudan University; Duke University; Duke University; Duke University; Duke University
摘要：In this paper, we propose a general procedure for establishing the geometric land-scape 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 stat...
-
作者：Ankirchner, Stefan; Kazi-Tani, Nabil; Wendt, Julian; Zhou, Chao
作者单位：Friedrich Schiller University of Jena; Universite de Lorraine; National University of Singapore; National University of Singapore
摘要：We consider a symmetric stochastic differential game where each player can control the diffusion intensity of an individual dynamic state process, and the players whose states at a deterministic finite time horizon are among the best alpha is an element of (0, 1)of all states receive a fixed prize. Within the mean field limit version of the game, we compute an explicit equilibrium, a threshold strategy that consists of choosing the maximal fluctuation intensity when the state is below a given ...
-
作者：Kushnir, Alexey; Krishnamoorthy, Vinod
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We prove that supply correspondences are characterized by two properties: the law of supply and being homogeneous of degree zero.
-
作者：Fujii, Kaito; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be hig...
-
作者：Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Goethe University Frankfurt; Max Planck Society
摘要：We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not...
-
作者：Gunluk, Oktay; Hauser, Raphael Andreas; Kovacs, Reka Agnes
作者单位：Cornell University; University of Oxford; Alan Turing Institute
摘要：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 (kBMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x 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 tw...
