Algorithms in Strategic or Noisy Environments

Опубликовано 6 марта 2018, 5:09

Algorithms are sometimes used in strategic or noisy environments. These factors can completely change the solutions of the problems.

In this talk, I am going to talk about two projects. In the first one, we study the problem of a seller repeatedly selling goods to a learning buyer. We characterize whether a fully strategic seller can extract additional revenue from a buyer who no-regret learns over time. In the second project, we study the problem of finding top-k items with pairwise comparisons. Motivated by applications like crowdsourcing, we assume the pairwise comparisons are noisy and we evaluate algorithms based both on the number of samples and the number of interactive rounds.

Based on joint work with Mark Braverman, Jon Schneider and Matt Weinberg

See more at microsoft.com/en-us/research/v...