-
作者：Pradhan, Somnath; Yueksel, Serdar
作者单位：Queens University - Canada
摘要：In control theory, typically a nominal model is assumed based on which an optimal control is designed and then applied to an actual (true) system. This gives rise to the problem of performance loss because of the mismatch between the true and assumed models. A robustness problem in this context is to show that the error because of the mismatch between a true and an assumed model decreases to zero as the assumed model approaches the true model. We study this problem when the state dynamics of t...
-
作者：Cesa-Bianchi, Nicolo; Cesari, Tommaso; Colomboni, Roberto; Fusco, Federico; Leonardi, Stefano
作者单位：University of Milan; University of Ottawa; Istituto Italiano di Tecnologia - IIT; Sapienza University Rome
摘要：Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over T rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with diff...
-
作者：Berger, Ben; Ezra, Tomer; Feldman, Michal; Fusco, Federico
作者单位：Harvard University; Tel Aviv University; Sapienza University Rome
摘要：Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper, we initiate the study of Pandora's problem with combinatorial costs, capturing applications where search cost is nonadditive. Weitzman's celebrated algorithm (1979) demonstrates that for additive costs, the optimal search strategy is nonadaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond ad...
-
作者：Brubach, Brian; Grammel, Nathaniel; Ma, Will; Srinivasanb, Aravind
作者单位：Wellesley College; University System of Maryland; University of Maryland College Park; Columbia University; Columbia University
摘要：Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input, which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint...
-
作者：Chatterjee, Krishnendu; Oliu-Barton, Miquel; Saona, Raimundo
作者单位：Institute of Science & Technology - Austria; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the...
-
作者：Hegde, Vishwajit; Menon, Arvind Satish; Prashanth, L. A.; Tagannathan, Krishna
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras
摘要：Utility-based shortfall risk (UBSR) is a risk metric that is increasingly popular in financial applications, owing to certain desirable properties that it enjoys. We consider the problem of estimating UBSR in a recursive setting, in which samples from the underlying loss distribution are available one at a time. We cast the UBSR estimation problem as a root-finding problem and propose stochastic approximation-based estimation schemes. We derive nonasymptotic bounds on the estimation error in t...
-
作者：Zhang, Penghe; Xiu, Naihua; Luo, Ziyan
作者单位：Beijing Jiaotong University
摘要：We consider the problem of minimizing the sum of a smooth function and a composition of a zero-one loss function with a linear operator, namely the zero-one composite optimization problem (0/1-COP). It has a vast body of applications, including the support vector machine (SVM), calcium dynamics fitting (CDF), one-bit compressive sensing (1-bCS), and so on. However, it remains challenging to design a globally convergent algorithm for the original model of 0/1-COP because of the nonconvex and di...
-
作者：Gast, Nicolas; Gaujal, Bruno; Yan, Chen
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); INRAE
摘要：We provide a framework to analyze control policies for the restless Markovian bandit model under both finite and infinite time horizons. We show that when the population of arms goes to infinity, the value of the optimal control policy converges to the solution of a linear program (LP). We provide necessary and sufficient conditions for a generic control policy to be (i) asymptotically optimal, (ii) asymptotically optimal with square root convergence rate, and (iii) asymptotically optimal with...
-
作者：Zhang, Jianfeng; Zhu, Zimu
作者单位：University of Southern California; Hong Kong University of Science & Technology (Guangzhou)
摘要：In this paper, we consider a principal-agent problem where the agent is allowed to quit by incurring a cost. When the current agent quits the job, the principal will hire a new one, possibly with a different type. We characterize the principal's dynamic value function, which could be discontinuous at the boundary, as the (unique) minimal solution of an infinite dimensional system of Hamilton-Jacobi-Bellman equations, parameterized by the agent's type. This dynamic problem is time consistent in...
-
作者：Agrawal, Priyank; Balkanski, Eric; Gkatzelis, Vasilis; Ou, Tingting; Tan, Xizhi
作者单位：Columbia University; Drexel University
摘要：In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in learning augmented algorithms. Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stro...
