Noticias en español
The value of observability in dynamic pricing.
Abstract: Research on dynamic pricing has been growing during the last four decades due to its use in practice by a variety of companies as well as the several model variants that can be considered. In particular, we consider the pricing problem where a firm wants to sell one item to a single buyer in order to maximize expected revenues. On one hand, the firm commits to a price function over an infinite horizon. On the other, the buyer has a private value for the item and purchases at the time when his utility is maximized. In our model, the buyer is more impatient than the seller. When the...
Read MoreAn efficient symmetry breaking technique for arbitrary groups
Abstract: Symmetries are commonly found in Integer Linear Programs (ILPs) or in some of their substructures. Having many symmetric solutions could make common algorithms as branch-and-bound inefficient, hence breaking symmetries might yield important gains. Given a group of symmetries of an ILP, a Fundamental Domain is a set of R^n that aims to select a unique representative of symmetric vectors, i.e. such that each point in the set is a unique representative under its G-orbit, effectively breaking all symmetries of the group. The canonical Fundamental Domain found in the literature, which...
Read MoreOn the Price of Anarchy for Flows over Time
Abstract: Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. In order to describe the temporal evolution of such systems one has to consider the propagation of flow across the network by tracking the position of each particle along time. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this talk I will discuss dynamic equilibria in the deterministic fluid queuing model in single-source...
Read MoreRobust Revenue Maximization Under Minimal Statistical Information
Abstract: We study the problem of multi-dimensional revenue maximization when selling $m$ items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean $\mu_j$ and an upper bound $\sigma_j$ on the standard deviation of each item’s marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance....
Read MoreOn the Cycle Augmentation Problem: Hardness and Approximation Algorithms.
Abstract: In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum cardinality whose addition to the graph makes it (k+1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k=1 (a.k.a. the Tree Augmentation Problem or TAP) or k=2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, nothing better is known for CacAP (hence for k-Connectivity Augmentation in...
Read MoreREPLICATOR DYNAMICS: OLD AND NEW
Abstract: We introduce the unilateral version associated to the replicator dynamics and describe its connection to on-line learning procedures, in particular tomultiplicative weight algorithm. We show the interest of handling simultaneously discrete and continuous time analysis. We then survey recent results on extensions of this dynamics: regularization function and variable weights. This includes no regret algorithms, time average and link to best reply dynamics in two person games, application to equilibria and variational inequalities, convergence properties in potential and dissipative...
Read More