-
作者：Trobst, Thorben; Vazirani, Vijay V.
作者单位：University of California System; University of California Irvine
摘要：Recent insights have left cardinal-utility matching markets in a state of flux: the celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser (HZ) [Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Polit. Econom. 87(2):293-314.], which had long eluded efficient algorithms, was finally shown to be polynomial parity argument in digraphs (PPAD)-complete (Chen et al. [Chen T, Chen X, Peng B, Yannakakis M (...
-
作者：Csaji, Gergely; Kiratly, Tamas; Takazawa, Kenjiro; Yokoi, Yu
作者单位：Eotvos Lorand University; Eotvos Lorand University; ELTE Centre for Economic & Regional Studies; Eotvos Lorand University; Hosei University; Institute of Science Tokyo
摘要：We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where vertices have preferences over the incident edges. There are two standard models, depending on whether vertices on one or both sides have preferences. A matching M is popular if it does not lose a head-to-head election against any other matching. In our generalized models, one or both sides have matroid constraints, an...
-
作者：Djehiche, Boualem; Dumitrescu, Roxana
作者单位：Royal Institute of Technology; Institut Polytechnique de Paris; Ecole Polytechnique; ENSAE Paris
摘要：We introduce a zero-sum game problem of mean-field type as an extension of the classical zero-sum Dynkin game problem to the case where the payoff processes might depend on the value of the game and its probability law. We establish sufficient conditions under which such a game admits a value and a saddle point. Furthermore, we provide a characterization of the value of the game in terms of a specific class of doubly reflected backward stochastic differential equations of mean-field type, for ...
-
作者：Cohen, Asaf; Zell, Ethan
作者单位：University of Michigan System; University of Michigan
摘要：Mean field games (MFGs) model equilibria in games with a continuum of weakly interacting players as limiting systems of symmetric n-player games. We consider the finiteprove that any solution to the MFG system gives rise to a (C/ ffififfi state, infinite-horizon problem with ergodic cost. Assuming Markovian strategies, we first Vn)-Nash equilibrium in the n-player game. We follow this result by proving the same is true for the strategy profile derived from the master equation. We conclude the ...
-
作者：Khanh, Pham Duy; Khoa, Vu Vinh Huy; Mordukhovich, Boris S.; Phat, Vo Thanh
作者单位：Wayne State University; University of North Dakota Grand Forks
摘要：The paper is devoted to a systematic study and characterizations of notions of local maximal monotonicity and their strong counterparts for set-valued operators that appear in variational analysis, optimization, and their applications. We obtain novel resolvent characterizations of these notions together with efficient conditions for their preservation under summation in broad infinite-dimensional settings. Further characterizations of these notions are derived by using generalized differentia...
-
作者：Ahmadi, Amir Ali; Chaudhry, Abraar; Dibek, Cemil
作者单位：Princeton University; University System of Georgia; Georgia Institute of Technology; Koc University
摘要：We introduce a family of symmetric convex bodies called generalized ellipsoids of degree d (GE-ds), with ellipsoids corresponding to the case of d = 0. Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids. We show that the conditions that the parameters of a GE must satisfy can be checked in strongly polynomial time and that one can search for GEs of a given degree by solving a semidefinite program whose size grows only linearly with dimension...
-
作者：Yang, Shuoguang; Truong, Van-Anh
作者单位：Hong Kong University of Science & Technology; Columbia University
摘要：We propose the analysis of the online learning problem for independent cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censo...
-
作者：Sentenac, Flore; Noiry, Nathan; Lerasle, Matthieu; Perchet, Vianney; Menard, Laurent
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Institut Polytechnique de Paris; ENSAE Paris; Institut Polytechnique de Paris; ENSAE Paris
摘要：We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in practice. Some theoretical support for this practical success has been established in specific classe...
-
作者：Ahn, Dohyun; Zheng, Lewen
作者单位：Chinese University of Hong Kong
摘要：We consider the problem of estimating the expectation over a convex polyhedron specified by a set of linear inequalities. This problem encompasses a multitude of financial applications, including systemic risk quantification, exotic option pricing, and portfolio management. We particularly focus on the case where the target event is rare, which corresponds to extreme systemic failures, deep out-of-the-money options, and high target returns in the aforementioned applications, respectively. This...
-
作者：Tran-Dinh, Quoc; Luo, Yang
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are known as root-finding problems. Our first algorithm is nonaccelerated with constant step sizes and achieves a O(1/k) best-iterate convergence rate on E[& Vert;Gxk & Vert;2] when the underlying operator G is Lipschitz continuous and possesses a weak Minty solution, in which E[] is the expectation and k is the iteration c...
