-
作者：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...
-
作者：Jin, Chi; Liu, Qinghua; Wang, Yuanhao; Yu, Tiancheng
作者单位：Princeton University; Princeton University; Massachusetts Institute of Technology (MIT)
摘要：A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms, even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms-V-learning, which provably learns Nash equilibria ...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：Liang, Ling; Sun, Defeng; Toh, Kim-Chuan
作者单位：University System of Maryland; University of Maryland College Park; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore
摘要：This paper proposes a squared smoothing Newton method via the Huber smoothing function for solving semidefinite programming problems (SDPs). We first study the fundamental properties of the matrix-valued mapping defined upon the Huber function. Using these results and existing ones in the literature, we then conduct rigorous convergence analysis and establish convergence properties for the proposed algorithm. In particular, we show that the proposed method is well-defined and admits global con...
-
作者：Vera, Alberto; Arlotto, Alessandro; Gurvich, Itai; Levin, Eli
作者单位：Cornell University; Duke University
摘要：We study a family of dynamic resource allocation problems, wherein requests of different types arrive over time and are accepted or rejected. Each request type is characterized by its reward, arrival probability, and resource consumption. An upper bound for the collected reward is given by a linear optimization problem with a random righthand side. This type of problem, known as packing linear program (LP), is ubiquitous in resource allocation. We provide a detailed characterization of the par...
