Noticias en español
Auctions with Intermediaries.
Abstract: In many markets, buyers do not bid directly in the auction, but instead, they are represented by intermediaries. This includes ad auctions, where some of the buyers might be represented by intermediaries like Ad agencies, Aggregators (e.g. Home Advisor), or Ad networks participating in an Ad Exchange. The presence of intermediaries creates the potential for collusion across buyers. Also, intermediaries have their own goals that depend on the contract between buyers and the intermediary, and will behave according to the incentives induced by their goals. We will talk about the...
Read MoreSome discrete optimization problems in matching markets.
Abstract: In the classical stable marriage problem, we are given two sets of agents – students and schools – with each student and school having a total order of agents from the opposite set. The goal is to form disjoint pairs of students and schools so that the resulting matching satisfies a fairness property known as stability. In their fundamental work, Gale and Shapley showed that a stable matching always exists and gave a fast algorithm to find one. These strong structural and algorithmic results propelled the application of the stable marriage model in several contexts,...
Read MoreStability in Matrix Games.
Abstract: We consider the simplest game, Matrix Games, and basic stability questions on the value and strategies upon perturbations on the payoff matrix. Considering polynomial perturbations, we design polynomial-time algorithms for the following tasks: (a) ensuring that, for every sufficiently small error, there is a strategy to guarantee that the value is at least the value of the error-free case; (b) ensuring that there is a fixed strategy to guarantee that, for every sufficiently small error, the value is at least the value of the error-free case; and (c) computing the analytical form...
Read MorePopular Branchings and Their Dual Certificates.
Abstract: Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient...
Read MoreImproved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More.
Abstract: In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+eps<1.89 and there is a (3/2+eps)-approximation algorithm if we are allowed to rotate items by 90 degrees. In this talk, I will present a (4/3+eps)-approximation algorithms in polynomial time for both cases, assuming that all input data are...
Read MoreNon-Euclidean Differentially Private Stochastic Convex Optimization.
Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t.~the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter....
Read More