Combinatorial Contracts.

Event Date: Jan 25, 2023 in ACGO, Seminars

Abstract: An emerging frontier in Algorithmic Game Theory is Algorithmic Contract Theory, which studies the classic hidden-action principal-agent problem of contract theory through the computational lens. In this talk, I will present three basic ways in which the problem can be combinatorial and survey both hardness and poly-time (approximation) results. The analysis will uncover some surprising connections (but also fundamental differences) to combinatorial auctions.

Read More

Explainable Affirmative Action.

Event Date: Dec 14, 2022 in ACGO, Seminars

Ver pdf, adjunto.

Read More

Experimentation in Two-Sided Marketplaces: The Impact of Interference.

Event Date: Dec 15, 2022 in ACGO, Seminars

Abstract: Marketplace platforms use experiments (also known as “A/B tests”) as a method for making data-driven decisions about which changes to make on the platform. When platforms consider introducing a new feature, they often first run an experiment to test the feature on a subset of users and then use this data to decide whether to launch the feature platform-wide. However, it is well documented that estimates of the treatment effect arising from these experiments may be biased due to the presence of interference driven by the substitution effects on the demand and supply sides of the...

Read More

Competition and Recall in Selection Problems.

Event Date: Dec 07, 2022 in ACGO, Seminars

Abstract: In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full...

Read More

Generalized formulations for the traveling salesman problem.

Event Date: Nov 30, 2022 in ACGO, Seminars

Abstract:  The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there is a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then, we study the intersection of this family, which we...

Read More

Impartial Selection with Additive Guarantees via Iterated Deletion.

Event Date: Nov 23, 2022 in ACGO, Seminars

Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\gamma})$ nominations, where $\gamma \in [0,1]$. For $\gamma=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized...

Read More