Noticias en español
A sequential Stackelberg game for dynamic inspection problems.
Abstract: This talk considers a game where an inspection authority must verify that a set of operators adhere to a certain rule. The inspector has time to inspect only a few operators, and this must be done sequentially. The operators disclose the sequence of inspections as they occur. We will discuss variants of this sequential game. The talk focuses on the mathematical structure of the set of equilibria of this inspection game, where the inspector is a Stackelberg leader and is capable of performing exactly two inspections. A static and dynamic version of the game are analyzed. In the...
Read MoreAttention is Turing Complete.
Abstract: Alternatives to recurrent neural networks, in particular, architectures based on self-attention, are gaining momentum for processing input sequences. In spite of their relevance, the computational properties of such networks have not yet been fully explored. We study the computational power of the Transformer, one of the most paradigmatic architectures exemplifying self-attention. We show that the Transformer with hard-attention is Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. Our study also reveals some...
Read MoreProphet Inequalities Require Only a Constant Number of Samples.
Abstract: In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as a reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. Because of its connections with resource allocation and posted-price mechanisms, this problem has been intensively studied, and several variants have been introduced. While most of the literature assumes that distributions are known to the gambler, recent work has...
Read MoreAggregating opinions — do we need (Kolmogorov) complexity?
Abstract: Imagine a group of people that need each day to make some collective decision (for the entire group), choosing one of two options A and B. Some people prefer A, some prefer B, and others are OK with any of the two options. (The next day the preferences may change arbitrarily, and a new group choice is made.) The group management needs to choose A or B, in both cases making some people unhappy. This cannot be avoided completely (if someone wants A and someone else wants B, one of them will be unhappy), so the goal is more modest: each person should not be unhappy too many times....
Read MoreTariff Zone Assignment: Complexity Results ans Solution Approaches.
Abstract: In the Tariff Zone Assignment problem, an operator is tasked with partitioning a transport network (i.e., a graph) into tariff zones in order to maximize revenue under a linear pricing model. In this model, customers pay a price proportional to the number of zones traveled through, up to some maximum accepted price. If this price gets exceeded, customers drop out of the model and thus generate no revenue at all. In this talk, first we will look at the complexity of this problem and show APX-hardness on star graphs and strong NP-hardness on paths. These complexity results motivate...
Read MoreOracle-Augmented Prophet Inequalities.
Abstract: In the top-1-of-k prophet inequality setting, a gambler is given a sequence of n random variables X_1, …, X_n, taken from known distributions, observes their values in an adversarial order, and selects up to k of them, immediately after they are observed, so that the top value selected is as high as possible, comparing against a prophet who always selects the maximum realization. For k = 1, one recovers the classical prophet inequality, and thus this model serves as a generalization. In this talk, we look at a new approach to solve the top-1-of-k model. We generalize the...
Read More