-
作者：Filmus, Yuval; Kawase, Yasushi; Kobayashi, Yusuke; Yamaguchi, Yutaro
作者单位：Technion Israel Institute of Technology; University of Tokyo; Kyoto University; Kyushu University; Kyushu University
摘要：A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight boun...
-
作者：Peck, James; Rampal, Jeevant
作者单位：University System of Ohio; Ohio State University; Indian Institute of Management (IIM System); Indian Institute of Management Ahmedabad
摘要：This paper analyzes a monopoly firm's profit-maximizing mechanism in the following context. There is a continuum of consumers with a unit demand for a good. The distribution of the consumers' valuations is given by one of two possible demand distributions/states. The consumers are uncertain about the demand state, and they update their beliefs after observing their own valuation for the good. The firm is uncertain about the demand state but infers it from the consumers' reported valuations. Th...
-
作者：Simchi-Levi, David; Xu, Yunzong
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider the general (stochastic) contextual bandit problem under the realizability assumption, that is, the expected reward, as a function of contexts and actions, belongs to a general function class F. We design a fast and simple algorithm that achieves the statistically optimal regret with only O(log T) calls to an offline regression oracle across all T rounds. The number of oracle calls can be further reduced to O(log log T) if T is known in advance. Our results provide the first univer...
-
作者：Abdi, Ahmed; Cornuejols, Gerard; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Institute for Basic Science - Korea (IBS)
摘要：Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are combinatorial in nature. In this paper, rendered by the recently developed theory of cuboids, we provide a different class of ideal clutters, one that is geometric in nature. The advantage of this new class of ideal clutters is that it allows for infinitely many ideal minimally nonpack...
-
作者：De Angelis, Tiziano; Gensbittel, Fabien; Villeneuve, Stephane
作者单位：University of Leeds; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：This paper studies a two-player zero-sum Dynkin game arising from pricing an option on an asset whose rate of return is unknown to both players. Using filtering techniques, we first reduce the problem to a zero-sum Dynkin game on a bidimensional diffusion (X,Y). Then we characterize the existence of a Nash equilibrium in pure strategies in which each player stops at the hitting time of (X,Y) to a set with a moving boundary. A detailed description of the stopping sets for the two players is pro...
-
作者：Oliu-Barton, Miquel
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players' behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the val...
-
作者：Zhang, Hui; Dai, Yu-Hong; Guo, Lei; Peng, Wei
作者单位：National University of Defense Technology - China; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; East China University of Science & Technology
摘要：We introduce a unified algorithmic framework, called the proximal-like incremental aggregated gradient (PLIAG) method, for minimizing the sum of a convex function that consists of additive relatively smooth convex components and a proper lower semicontinuous convex regularization function over an abstract feasible set whose geometry can be captured by using the domain of a Legendre function. The PLIAG method includes many existing algorithms in the literature as special cases, such as the prox...
-
作者：Grishchenko, Dmitry; Iutzeler, Franck; Malick, Jerome
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS)
摘要：Many applications in machine learning or signal processing involve nonsmooth optimization problems. This nonsmoothness brings a low-dimensional structure to the optimal solutions. In this paper, we propose a randomized proximal gradient method harnessing this underlying structure. We introduce two key components: (i) a random subspace proximal gradient algorithm; and (ii) an identification-based sampling of the subspaces. Their interplay brings a significant performance improvement on typical ...
-
作者：Duetting, Paul; Kesselheim, Thomas; Tardos, Eva
作者单位：University of London; London School Economics & Political Science; University of Bonn; Cornell University
摘要：Many algorithms that are originally designed without explicitly considering incentive properties are later combined with simple pricing rules and used as mechanisms. A key question is therefore to understand which algorithms, or, more generally, which algorithm design principles, when combined with simple payment rules such as pay your bid, yield mechanisms with a small price of anarchy. Our main result concerns mechanisms that are based on the relax-and-round paradigm. It shows that oblivious...
-
作者：Ye, Heng-Qing; Yao, David D.
作者单位：Hong Kong Polytechnic University; Columbia University
摘要：In a prior study [Ye HQ, Yao DD (2016) Diffusion limit of fair resource control- Stationary and interchange of limits. Math. Oper. Res. 41(4):1161-1207.] focusing on a class of stochastic processing network with fair resource control, we justified the diffusion approximation (in the context of the interchange of limits) provided that the pth moment of the workloads are bounded. To this end, we introduced the so-called bounded workload condition, which requires the workload process be bounded b...
