1期

最新文章

• Existence and Complexity of Approximate Equilibria in Weighted Congestion Games AI翻译
  作者：Christodoulou, George; Gairing, Martin; Giannakopoulos, Yiannis; Pocas, Diogo; Waldmann, Clara
  作者单位：Aristotle University of Thessaloniki; University of Liverpool; University of Erlangen Nuremberg; Technical University of Munich
  摘要：We study the existence of approximate pure Nash equilibria (alpha-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously, it was known that d-PNE always exist, whereas nonexistence was established only for small constants, namely, for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have (Theta) over tilde(root d)-PNE, which provides the first superconstant lower bound. Furthermore, we provide a black-...
• Necessary and Sufficient Conditions for Rank-One-Generated Cones AI翻译
  作者：Argue, C. J.; Kilinc-Karzan, Fatma; Wang, Alex L.
  作者单位：Carnegie Mellon University; Carnegie Mellon University; Carnegie Mellon University
  摘要：A closed convex conic subset S of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of S is closely related to the exactness of semidefinite program (SDP) relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to S. We consider the case where S is obtained as the intersection of the PSD cone with finitely many homogeneous linear matrix inequalities and conic constraints...
• Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization AI翻译
  作者：Viet Anh Nguyen; Shafieezadeh-Abadeh, Soroosh; Kuhn, Daniel; Esfahani, Peyman Mohajerin
  作者单位：Stanford University; Carnegie Mellon University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Delft University of Technology
  摘要：We introduce a distributionally robust minimium mean square error estimation model with a Wasserstein ambiguity set to recover an unknown signal from a noisy observation. The proposed model can be viewed as a zero-sum game between a statistician choosing an estimator-that is, a measurable function of the observation-and a fictitious adversary choosing a prior-that is, a pair of signal and noise distributions ranging over independent Wasserstein balls-with the goal to minimize and maximize the ...
• New Constructions of Obviously Strategyproof Mechanisms AI翻译
  作者：Ferraioli, Diodato; Meier, Adrian; Penna, Paolo; Ventre, Carmine
  作者单位：University of Salerno; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of London; King's College London
  摘要：Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategy-proof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the right definition rather than on the construction of these mechanisms. Here, we give the first set of tight results ...
• Power Forward Performance in Semimartingale Markets with Stochastic Integrated Factors AI翻译
  作者：Bo, Lijun; Capponi, Agostino; Zhou, Chao
  作者单位：Xidian University; Columbia University; National University of Singapore; National University of Singapore
  摘要：We study the forward investment performance process (FIPP) in an incomplete semimartingale market model with closed and convex portfolio constraints, when the investor's risk preferences are of the power form. We provide necessary and sufficient conditions for the existence of such a FIPP. In a semimartingale factor model, we show that the FIPP can be recovered as a triplet of processes that admit an integral representation with respect to semimartingales. Using an integrated stochastic factor...
• Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds AI翻译
  作者：Agrawal, Shipra; Jia, Randy
  作者单位：Columbia University
  摘要：We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov decision process (MDP) is communicating with a finite, although unknown, diameter. Our main result is a high probability regret upper bound of (O) over tilde (DS root AT) for any communicating MDP with S states, A actions, and diameter D. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an opti...
• The Big Match with a Clock and a Bit of Memory AI翻译
  作者：Hansen, Kristoffer Arnsfelt; Ibsen-Jensen, Rasmus; Neymanc, Abraham
  作者单位：Aarhus University; University of Liverpool; Hebrew University of Jerusalem
  摘要：The Big Match is a multistage two-player game. In each stage, player 1 hides one or two pebbles in his hand, and his opponent has to guess that number. Player 1 loses a point if player 2 is correct; otherwise, he wins a point. As soon as player 1 hides one pebble, the players cannot change their choices in any future stage. The undiscounted Big Match has been much-studied. Blackwell and Ferguson (1968) give an epsilon-optimal strategy for player 1 that hides, in each stage, one pebble with a p...
• Modelling Multiperiod Carbon Markets Using Singular Forward-Backward SDEs AI翻译
  作者：Chassagneux, Jean-Francois; Chotai, Hinesh; Crisan, Dan
  作者单位：Universite Paris Cite; Imperial College London; Citigroup Incorporated
  摘要：We introduce a model for the evolution of emissions and the price of emissions allowances in a carbon market, such as the European Union Emissions Trading System (EU ETS). The model accounts for multiple trading periods, or phases, with multiple times at which compliance can occur. At the end of each trading period, the participating firms must surrender allowances for their emissions made during that period, and additional allowances can be used for compliance in the following periods. We sho...
• The Edgeworth Conjecture with Small Coalitions and Approximate Equilibria in Large Economies AI翻译
  作者：Barman, Siddharth; Echenique, Federico
  作者单位：Indian Institute of Science (IISC) - Bangalore; California Institute of Technology
  摘要：We revisit the connection between bargaining and equilibrium in exchange economies and study its algorithmic implications. We consider bargaining outcomes to be allocations that cannot be blocked (i.e., profitably retraded) by coalitions of small size, and show that these allocations must be approximate Walrasian equilibria. Our results imply that deciding whether an allocation is approximately Walrasian can be done in polynomial time, even in economies for which finding an equilibrium is know...
• Game on Random Environment, Mean-Field Langevin System, and Neural Networks AI翻译
  作者：Conforti, Giovanni; Kazeykina, Anna; Ren, Zhenjie
  作者单位：Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Universite Paris Saclay; Universite PSL; Universite Paris-Dauphine
  摘要：In this paper, we study a class of games regularized by relative entropy where the players strategies are coupled through a random environment. Besides existence and uniqueness of equilibria for such games, we prove, under different sets of hypotheses that the marginal laws of the corresponding mean-field Langevin systems can converge toward the games equilibria. As an application, we show that dynamic games fall in this framework by considering the time horizon as environment. Concerning appl...