-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Tokyo Metropolitan University
摘要：A strongly polynomial algorithm is developed for finding an integer-valued feasible st-flow of a given flow amount, which is decreasingly minimal on a specified subset F of edges in the sense that the largest flow value on F is as small as possible; within this, the second largest flow value on F is as small as possible; within this, the third largest flow value on F is as small as possible, and so on. A characterization of the set of these st-flows gives rise to an algorithm to compute a chea...
-
作者：Drusvyatskiy, Dmitriy; Xiao, Lin
作者单位：University of Washington; University of Washington Seattle; Facebook Inc
摘要：Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision ind...
-
作者：Guo, Xin; Hu, Anran; Xu, Renyuan; Zhang, Junzi
作者单位：University of California System; University of California Berkeley; Amazon.com; University of Southern California; University of Oxford; Stanford University
摘要：This paper presents a general mean-field game (GMFG) framework for simultaneous learning and decision making in stochastic games with a large population. It first establishes the existence of a unique Nash equilibrium to this GMFG, and it demonstrates that naively combining reinforcement learning with the fixed-point approach in classical mean-field games yields unstable algorithms. It then proposes value-based and policy-based reinforcement learning algorithms (GMF-V and GMF-P, respectively) ...
-
作者：Eckstein, Stephan; Nutz, Marcel
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Columbia University
摘要：We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. Sharp rates for general divergences including relative entropy or Lp regularization, general transport costs, and multimarginal problems are obtained. A novel methodology using quantization and martingale couplings is suitable for noncompact marginals and achieves, in particular, the sharp leading-order term of entropically regularized 2-Wasserstein distance for marginals with a finit...
-
作者：Nie, Jiawang; Tang, Xindong
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University
摘要：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.
-
作者：Grand-Clement, Julien; Kroer, Christian
作者单位：Columbia University
摘要：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, lp norm balls, and ellipsoidal c...
-
作者：Jiang, Rujun; Li, Duan
作者单位：Fudan University; City University of Hong Kong
摘要：The extended trust region subproblem (ETRS) of minimizing a quadratic objective over the unit ball with additional linear constraints has attracted a lot of attention in the last few years because of its theoretical significance and wide spectra of applications. Several sufficient conditions to guarantee the exactness of its semidefinite programming (SDP) relaxation have been recently developed in the literature. In this paper, we consider a generalization of the extended trust region subprobl...
-
作者：Nutz, Marcel; Zhang, Yuchong
作者单位：Columbia University; University of Toronto
摘要：We formulate a mean field game where each player stops a privately observed Brownian motion with absorption. Players are ranked according to their level of stopping and rewarded as a function of their relative rank. There is a unique mean field equilibrium, and it is shown to be the limit of associated n-player games. Conversely, the mean field strategy induces n-player epsilon-Nash equilibria for any continuous reward function-but not for discontinuous ones. In a second part, we study the pro...
-
作者：Saunderson, James
作者单位：Monash University
摘要：Every convex homogeneous polynomial (or form) is nonnegative. Blekherman has shown that there exist convex forms that are not sums of squares via a nonconstructive argument. We provide an explicit example of a convex form of degree 4 in 272 variables that is not a sum of squares. The form is related to the Cauchy-Schwarz inequality over the octonions. The proof uses symmetry reduction together with the fact (due to Blekherman) that forms of even degree that are near-constant on the unit sphere...
-
作者：Bogomolnaia, Anna; Moulin, Herve
作者单位：University of Glasgow; Centre National de la Recherche Scientifique (CNRS)
摘要：When dividing a manna Omega of private items (commodities, workloads, land, time slots) between n agents, the individual guarantee is the welfare each agent can secure in the worst case of other agents' preferences and actions. If the manna is nonatomic and utilities are continuous (not necessarily monotone or convex) the minmax utility, that of our agent's best share in the agent's worst partition of the manna, is guaranteed by Kuhn's generalization of divide and choose. The larger maxmin uti...
