-
作者：Babaioff, Moshe; Nisan, Noam; Taigam-Cohen, Inbal
作者单位：Hebrew University of Jerusalem; Technion Israel Institute of Technology
摘要：Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods (Foley 1967, Varian 1974). Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible even in the simple two-agent, single-item market. Yet it is easy to see that, once the two budgets are slightly perturbed (made generic), a co...
-
作者：Altschuler, Jason M.; Talwar, Kunal
作者单位：Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
摘要：This paper studies the value of switching actions in the Prediction From Experts problem (PFE) and Adversarial Multiarmed Bandits problem (MAB). First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms achieve the minimax optimal order for both regret and switches in expectation; however, high probability guarantees are an open problem. We present the first algorithms that achieve this optimal order for both quantities with high probabil...
-
作者：Bomze, Immanuel M.; Kahr, Michael; Leitner, Markus
作者单位：University of Vienna; University of Vienna; University of Vienna; Vrije Universiteit Amsterdam
摘要：We consider the robust standard quadratic optimization problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is optimized over the standard simplex. Following most approaches, we model the uncertainty sets by balls, polyhedra, or spectrahedra, more generally, by ellipsoids or order intervals intersected with subcones of the copositive matrix cone. We show that the copositive relaxation gap of the RStQP equals the minimax gap under some mild assumptions on the curvature of...
-
作者：Bistritz, Ilai; Leshem, Amir
作者单位：Stanford University; Bar Ilan University
摘要：We consider an N-player multiarmed bandit game in which each player chooses one out of M arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed or Markovian. When two or more players choose the same arm, they all receive zero reward. Performance is measured using the expected sum of regrets compared with optimal assignment of arms to players that maximizes the sum of expected rewards. We assume that e...
-
作者：Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
作者单位：Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan
摘要：We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identicalmachines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated m...
-
作者：Crespi, Giovanni Paolo; Hamel, Andreas H.; Rocca, Matteo; Schrage, Carola
作者单位：Universita Carlo Cattaneo - Liuc; Free University of Bozen-Bolzano; University of Insubria
摘要：Via a family of monotone scalar functions, a preorder on a set is extended to its power set and then used to construct a hull operator and a corresponding complete lattice of sets. Functions mapping into the preordered set are extended to complete lattice-valued ones, and concepts for exact and approximate solutions for corresponding set optimization problems are introduced and existence results are given. Well-posedness for complete lattice-valued problems is introduced and characterized. The...
-
作者：Harks, Tobias; Hoefer, Martin; Schedel, Anja; Surek, Manuel
作者单位：University of Augsburg; Goethe University Frankfurt
摘要：In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing protocol determines cost shares that are budget-balanced, separable, and guarantee existence of pure Nash equilibria (PNE). We provide black-box reductions reducing the design of such a protocol to the design of an approximation algorithm for...
