Noticias en español
Learning 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 MoreLifting Apportionment Methods to Weighted Fair Division.
Abstract: We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. This setting (known as weighted fair division) constitutes a generalization of the well-studied apportionment problem, and we present two approaches for lifting apportionment methods to weighted fair division. In the first part of the talk, we focus on additive valuations and show that picking sequences derived from divisor methods provide natural envy-freeness,...
Read MorePercolation games.
Abstract: Inspired by first-passage percolation models, we consider zero-sum games on Z^d and study their limit behavior when the game duration tends to infinity. After reviewing several fundamental results in this literature, we present a generalization and discuss connections with long-term behavior of Hamilton-Jacobi equations.
Read MoreDecomposition of Probability Marginals for Security Games in Abstract Networks and Ideal Clutters.
Abstract: Consider a set system on a finite ground set E, where each set P in the system is equipped with a required hitting probability r(P) and each element e of E has a probability marginal p(e). We study the question whether the marginals can be decomposed into a distribution over all subsets of E such that the resulting random set intersects each set P from the system with probability at least r(P). A simple necessary condition is that for every set P in the system, the sum of the marginals of elements in P is at least r(P). Extending a result by Dahan, Amin, and Jaillet (Mathematics of...
Read More