Noticias en español
A Constant Factor Prophet Inequality for Online Combinatorial Auctions.
Abstract: In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research...
Read MoreSingle-choice secretary problems with ordinal advice.
Abstract: We examine variations of the classical secretary problem in a new setting, where the decision-maker (DM) can request one (or more) bits of ordinal information from agents before they arrive. Specifically, each agent has private information (their weight) that is publicly revealed upon arrival. As usual, the DM must irrevocably decide whether to select the agent or not after this step. Additionally, at any given time, the DM can privately ask yes-or-no questions to agents who have not yet arrived, and the agents can only answer ordinal questions based on comparing their private...
Read MoreLearning in scheduling: simple policies for Bayesian scheduling.
Abstract: We consider the problem of scheduling jobs on a single machine, non-preemptively. The goal is to minimize the total completion time of the jobs. It is well known that this problem is solved by scheduling the jobs in order of shortest processing times (SPT) when the jobs’ processing times are known or shortest expected processing times (SEPT), when we have full knowledge on the true expected values. In this talk, we consider the stochastic scheduling problem in which we have additional uncertainty about the parameters of the distribution of the jobs’ processing times. We assume that...
Read MoreLearning to cope with adversaries (in theory) and noise (in practice).
Abstract: Learning theory has burgeoned since 1971 (VC-dimension by Vapnik and Chervonenkis) when the framework was established and the fundamental theorem proved. We extend the framework to model a strategic setting that allows for adversarial behavior during the test phase. As an example consider a situation where students may manipulate their application materials knowing universities’ admissions criteria. We define a new parameter, SVC (Strategic VC dimension) and use it to characterize the statistical and computational learnability of the strategic linear classification problem....
Read MoreOpening Pandora’s Box: the Correlated Case.
Abstract: Pandora’s Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently nothing was known for the case of correlated input. In this talk I will...
Read MoreOpening Pandora’s Box: the Correlated Case.
Abstract: Pandora’s Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently nothing was known for the case of correlated input. In this talk I will...
Read More