-
作者：Akrami, Hannaneh; Chaudhury, Bhaskar Ray; Hoefer, Martin; Mehlhorn, Kurt; Schmalhofer, Marco; Shahkarami, Golnoosh; Varricchio, Giovanna; Vermande, Quentin; van Wijland, Ernest
作者单位：Max Planck Society; University of Bonn; Saarland University; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; RWTH Aachen University; Goethe University Frankfurt; Saarland University; University of Calabria; Universite Cote d'Azur; Universite Paris Cite
摘要：We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either 1 or psq for some fixed coprime numbers p,q E N such that 1 <= q <= p. Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends ...
-
作者：Nguyen, Thai; Stadje, Mitja
作者单位：Laval University; Ulm University; Ulm University
摘要：We study the expected utility maximization problem of a large investor who is allowed to make transactions on tradable assets in an incomplete financial market with endogenous permanent market impacts. The asset prices are assumed to follow a nonlinear price curve quoted in the market as the utility indifference curve of a representative liquidity supplier. Using generalized subgradients, we show that optimality can be fully characterized via a system of coupled forward-backward stochastic dif...
-
作者：Wei, Jiaqin; Xia, Jianming; Zhao, Qian
作者单位：East China Normal University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Shanghai University of International Business & Economics
摘要：We investigate the portfolio selection problem for an agent with rank-dependent utility, for which the investment strategy is constrained to take values in a closed convex set. For a constant coefficient market and constant relative risk-aversion utilities, we characterize the deterministic strict equilibrium strategies. For the case of time-invariant probability weighting functions, we provide a comprehensive characterization of the deterministic strict equilibrium strategy. The unique nonzer...
-
作者：Davies, Sami; Moseley, Benjamin; Newman, Heather
作者单位：University of California System; University of California Berkeley; Carnegie Mellon University; Vassar College
摘要：We design the first purely combinatorial O(1)-factor algorithms for correlation clustering with respect to the fp-norm of the disagreement vector. Our main technical contribution is the construction of a novel semimetric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The power of the correlation metric allows us to design an algorithm that outputs a single clustering solution that i...
-
作者：Li, Shukai; Mehrotra, Sanjay
作者单位：Northwestern University
摘要：This paper develops a new method for computing the stationary distribution and steady-state performance measures of stochastic systems that can be described as a continuous-state Markov chain supported on R. The balance equations are solved by constructing a proxy Markov chain with finite states. We show the consistency of an approximate solution and provide deterministic nonasymptotic error bounds under the supremum norm. Our method is near optimal among all approximation methods using discre...
-
作者：Ahn, Hyun-Soo; Ryan, Christopher Thomas; Uichanco, Joline; Zhang, Mengzhenyu
作者单位：University of Michigan System; University of Michigan; University of British Columbia; University of London; University College London
摘要：When underlying demand follows a complex stochastic process, pricing problems are difficult to solve. In such cases, certainty equivalent (CE) policies, based on the solution to the deterministic relaxation of the stochastic pricing problem, can be used as practical alternatives. CE policies have lighter computational and informational requirements compared with solving the problem to optimality. Although the effectiveness of CE pricing policies has been theoretically studied when demands are ...
