2020

最新文章

• On the Existence of Pairwise Stable Weighted Networks AI翻译
  作者：Bich, Philippe; Morhaim, Lisa
  作者单位：Paris School of Economics; Universite Paris-Pantheon-Assas
  摘要：In network theory, Jackson and Wolinsky introduced a now widely used notion of stability for unweighted network formation called pairwise stability. We prove the existence of pairwise stable weighted networks under assumptions on payoffs that are similar to those in Nash's and Glicksberg's existence theorem (continuity and quasi concavity). Then, we extend our result, allowing payoffs to depend not only on the network, but also on some game-theoretic strategies. The proof is not a standard app...
• Multiconstrained Finite-Horizon Piecewise Deterministic Markov Decision Processes with Unbounded Transition Rates AI翻译
  作者：Huang, Yonghui; Guo, Xianping
  作者单位：Sun Yat Sen University
  摘要：This paper studies a multiconstrained problem for piecewise deterministic Markov decision processes (PDMDPs) with unbounded cost and transition rates. The goal is to minimize one type of expected finite-horizon cost over history-dependent policies while keeping some other types of expected finite-horizon costs lower than some tolerable bounds. Using the Dynkin formula for the PDMDPs, we obtain an equivalent characterization of occupancy measures and express the expected finite-horizon costs in...
• Approximate Markov-Nash Equilibria for Discrete-Time Risk-Sensitive Mean-Field Games AI翻译
  作者：Saldi, Naci; Basar, Tamer; Raginsky, Maxim
  作者单位：Ozyegin University; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：In this paper, we study a class of discrete-time mean-field games under the infinite-horizon risk-sensitive optimality criterion. Risk sensitivity is introduced for each agent (player) via an exponential utility function. In this game model, each agent is coupled with the rest of the population through the empirical distribution of the states, which affects both the agent's individual cost and its state dynamics. Under mild assumptions, we establish the existence of a mean-field equilibrium in...
• Stochastic Recursive Inclusions in Two Timescales with Nonadditive Iterate-Dependent Markov Noise AI翻译
  作者：Yaji, Vinayaka G.; Bhatnagar, Shalabh
  作者单位：Indian Institute of Science (IISC) - Bangalore
  摘要：In this paper, we study the asymptotic behavior of a stochastic approximation scheme on two timescales with set-valued drift functions and in the presence of non-additive iterate-dependent Markov noise. We show that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the set-valued drift function in the recursion with respect to a set of measures accounting for both averaging with respect to the stationary distributions of the Markov noise terms an...
• Greed Works-Online Algorithms for Unrelated Machine Stochastic Scheduling AI翻译
  作者：Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin
  作者单位：University of Chicago; Carnegie Mellon University; University of Twente; Massachusetts Institute of Technology (MIT)
  摘要：This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of...
• Acyclic Gambling Games AI翻译
  作者：Laraki, Rida; Renault, Jerome
  作者单位：Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; University of Liverpool; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
  摘要：We consider two-player, zero-sumstochastic games in which each player controls the player's own state variable living in a compact metric space. The terminology comes from gambling problems in which the state of a player represents its wealth in a casino. Under standard assumptions (e.g., continuous running payoff and nonexpansive transitions), we consider for each discount factor the value v(lambda) of the lambda-discounted stochastic game and investigate its limit when lambda goes to zero. W...
• The Computational Complexity of Integer Programming with Alternations AI翻译
  作者：Danny Nguyen; Pak, Igor
  作者单位：University of Michigan System; University of Michigan; University of California System; University of California Los Angeles
  摘要：We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables. This complements earlier results by Lenstra [16] [Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538-5481 and Kannan [13,14] [Kannan R (1990) Test sets for integer programs, for all there exists sentences. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 39-47. Kannan R (1992) Lattice translates of a po...
• Hiring Secretaries over Time: The Benefit of Concurrent Employment AI翻译
  作者：Disser, Yann; Fearnley, John; Gairing, Martin; Goebel, Oliver; Klimm, Max; Schmand, Daniel; Skopalik, Alexander; Toennis, Andreas
  作者单位：Technical University of Darmstadt; University of Liverpool; RWTH Aachen University; Humboldt University of Berlin; Goethe University Frankfurt; University of Twente; University of Bonn
  摘要：We consider a stochastic online problem where n applicants arrive over time, one per time step. Upon the arrival of each applicant, their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable; that is, we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the appli...
• Closing the Gap for Makespan Scheduling via Sparsification Techniques AI翻译
  作者：Jansen, Klaus; Klein, Kim-Manuel; Verschae, Jose
  作者单位：University of Kiel; Universidad de O'Higgins
  摘要：Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a (1 + epsilon)-approximation algorithm with a running time that depends polynomially on 1/epsilon. It has been recently shown that a subexponential running time on 1/epsilon would imply that ...
• General Error Estimates for the Longstaff-Schwartz Least-Squares Monte Carlo Algorithm AI翻译
  作者：Zanger, Daniel Z.
  摘要：We establish error estimates for the Longstaff-Schwartz algorithm, employing just a single set of independent Monte Carlo sample paths that is reused for all exercise time steps. We obtain, within the context of financial derivative payoff functions bounded according to the uniform norm, new bounds on the stochastic part of the error of this algorithm for an approximation architecture that may be any arbitrary set of L-2 functions of finite Vapnik-Chervonenkis (VC) dimension whenever the algor...