-
作者：Hathcock, Daniel; Zlatin, Michael
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We consider connectivity augmentation problems in the Steiner setting. In the Steiner Augmentation of a Graph problem (k-SAG), we are given a k-edge-connected graph H, which we seek to augment by including links of minimum cost so that the edge connectivity between nodes of H increases by 1. Unlike the standard Connectivity Augmentation Problem, links to Steiner nodes outside H are available for the augmentation. If H is not assumed to be globally k-edge connected but rather Steiner k-edge con...
-
作者：Al-Thani, Hessa; Cui, Yubing; Harris, Blake; Nagarajan, Viswanath
作者单位：University of Michigan; University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
摘要：Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification, and viral marketing. We consider the problem of covering an adaptive submodular function at minimum expected cost, where the random realizations of different items may be correlated. We show that the natural greedy policy has an approximation ratio of 4 center dot (1 + ln Q), where Q is the goal value. We also show that the greedy policy ha...
-
作者：Shaiderman, Dimitry
作者单位：Hebrew University of Jerusalem
摘要：We study a dynamic Bayesian persuasion model called Markovian persuasion, illustrated here with two players: the sender (he) and the receiver (she). In such a model, the belief of the receiver regarding the current state of a Markov chain (X-n)(n >= 1), over a finite state space K, is controlled through signals she obtains from a sender, who observes (X-n)(n >= 1) in real time. At each stage n >= 1, the receiver takes an action based on his current belief, which, together with the realized sta...
-
作者：Bogomolnaia, Anna; Moulin, Herve
作者单位：University of Glasgow; Centre National de la Recherche Scientifique (CNRS)
摘要：We must assign n agents to m posts subject to negative congestion; what assignment is fair and efficient? If congestion is anonymous (each agent adds one unit), it is always possible to assign each agent to one of the agent's top n out of the n x m feasible allocations. This ordinal interpretation of ex ante fairness can be adjusted if congestion is weighted (agent-specific). An assignment is competitive if I don't want to move to an empty post or to an occupied one at its current congestion l...
-
作者：Yang, Lei; Toh, Kim-Chuan
作者单位：Sun Yat Sen University; National University of Singapore
摘要：The Bregman proximal gradient method (BPGM), which uses the Bregman distance as a proximity measure in the iterative scheme, has recently been redeveloped for minimizing convex composite problems without the global Lipschitz gradient continuity assumption. This makes the BPGM appealing for a wide range of applications, and hence, it has received growing attention in recent years. However, most existing convergence results are obtained only under the assumption that the involved subproblems are...
-
作者：Hang, Nguyen Thi Van; Sarabi, Ebrahim
作者单位：Nanyang Technological University; Vietnam Academy of Science & Technology (VAST); University System of Ohio; Miami University
摘要：Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latte...
-
作者：Li, Zanyu; Bao, Chenglong
作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications
摘要：Anderson mixing (AM) method is a popular approach for accelerating fixedpoint iterations by leveraging historical information from previous steps. In this paper, we introduce the Riemannian Anderson mixing (RAM) method, an extension of AM to Riemannian manifolds, and analyze its local linear convergence under reasonable assumptions. Unlike other extrapolation-based algorithms on Riemannian manifolds, RAM does not require computing the inverse retraction or inverse exponential mapping and has a...
-
作者：Dimou, Nikos
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：We prove the almost equivalence of the minimax theorem and the strong duality theorem for a large class of games and conic programs. The previous fundamental results on the equivalence of linear programming and two-player zero-sum games with simplex strategy sets are extended to Banach spaces, and a comprehensive framework unifying two-player zero-sum games and conic linear programs is established. Specifically, we show that, for every zero-sum game with a bilinear payoff function and strategy...
-
作者：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 ...
