Sampath Kannan

A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual\n Bandit Problem

arXiv (Cornell University) · 2018-01-10 · 29 citations

Bandit learning is characterized by the tension between long-term exploration\nand short-term exploitation. However, as has recently been noted, in settings\nin which the choices of the learning algorithm correspond to important\ndecisions about individual people (such as criminal recidivism prediction,\nlending, and sequential drug trials), exploration corresponds to explicitly\nsacrificing the well-being of one individual for the potential future benefit\nof others. This raises a fairness conc…

Graph Reconstruction and Verification

ACM Transactions on Algorithms · 2018-08-09 · 19 citations

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G . In the verification problem, we are given a hypothetical graph Ĝ and want to check whether G is equal to Ĝ . We provide a randomized algorithm for reconstruction using Õ( n 3/2 ) distance queries, based on Voronoi cell decomposition. Next, we…

A Retrospective Look at the Monitoring and Checking (MaC) Framework

Lecture notes in computer science · 2019-01-01 · 3 citations

Fairness in Algorithmic Decision Making

SMARTech Repository (Georgia Institute of Technology) · 2018-10-29 · 3 citations

Presented on October 29, 2018 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E.

Algorithmic Collusion Without Threats

arXiv (Cornell University) · 2024-09-06 · 2 citations

There has been substantial recent concern that pricing algorithms might learn to ``collude.'' Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors who refuse to support high prices, and these strategies can be automatically learned. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to optimize their payo…