Back to Events

Seminar Series

September 17

Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry

Chara Podimata

Part Of

4:15P
- 5:15P

Location

32-G449
Refreshments at 4:00pm
Add to Calendar 2024-09-17 16:15:00 2024-09-17 17:15:00 America/New_York Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry Abstract: In this talk I will discuss learning in principal-agent games where there is information asymmetry between what the principal and what the agent know about each other’s chosen actions. I will introduce a generalization of the standard Stackelberg Games (SGs) framework: Calibrated Stackelberg Games (CSGs). In CSGs, a principal repeatedly interacts with an agent who (contrary to standard SGs) does not have direct access to the principal’s action but instead best-responds to calibrated forecasts about it. I will show that in CSGs, the principal can achieve utility that converges to the optimum Stackelberg value of the game (i.e., the value that they could achieve had the agent known the principal’s strategy all along) both in finite and continuous settings, and that no higher utility is achievable. Finally, I will discuss a meta-question: when learning in strategic environments, can agents overcome uncertainty about their preferences to achieve outcomes they could have achieved absent any uncertainty? And can they do this solely through interactions with each other?Based on joint works with Nivasini Ananthakrishnan (UC Berkeley), Nika Haghtalab (UC Berkeley), and Kunhe Yang (UC Berkeley). 32-G449

September 24

Near Optimal Alphabet-Soundness Tradeoff PCPs

Kai Zhe Zheng
MIT Mathematics, CSAIL

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-09-24 16:15:00 2024-09-24 17:15:00 America/New_York Near Optimal Alphabet-Soundness Tradeoff PCPs Refreshments at 4:00 PMAbstract: We show a nearly optimal alphabet-soundness tradeoff for NP-hardness of 2-Prover-1-Round Games (2P1R). More specifically, we show that for all \eps > 0, for sufficiently large M, it is NP-hard to decide whether a 2P1R instance of alphabet size M has value nearly 1 or at most M^{-1+\eps}. 2P1R are equivalent to 2-Query PCP, and are widely used in obtaining hardness of approximation results. As such, our result implies the following: 1) hardness of approximating Quadratic Programming within a factor of nearly log(n), 2) hardness of approximating d-bounded degree 2-CSP within a factor of nearly d/2, and 3) improved hardness of approximation results for various k-vertex connectivity problems. For the first two applications, our results nearly match the performance of the best known algorithms.Joint work with Dor Minzer. 32-G449

October 08

Learning to Defer in Content Moderation: The Human-AI Interplay

Thodoris Lykouris
MIT Sloan

Part Of

4:15P
- 5:15P

Location

32-G449
Add to Calendar 2024-10-08 16:15:00 2024-10-08 17:15:00 America/New_York Learning to Defer in Content Moderation: The Human-AI Interplay Refreshments at 4:00 PMAbstract: Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without jeopardizing non-harmful content. Due to the high-volume nature of online posts, human-only moderation is operationally challenging, and platforms often employ a human-AI collaboration approach. A typical heuristic estimates the expected harmfulness of incoming posts and uses fixed thresholds to decide whether to remove the post and whether to send it for human review. This disregards the uncertainty in the machine learning estimation, the time-varying element of human review capacity and post arrivals, and the selective sampling in the dataset (humans only review posts filtered by the admission algorithm). We introduce a model to capture this human-AI interplay. Our algorithm observes contextual information for posts, makes classification and admission decisions, and schedules posts for human review. Only admitted posts receive human reviews on their harmfulness. These reviews help educate the machine-learning algorithms but are delayed due to congestion in the human review system. We propose a near-optimal learning algorithm that balances the classification loss from a selectively sampled dataset, the idiosyncratic loss of non-reviewed posts, and the delay loss of having congestion in the human review system. To the best of our knowledge, this is the first result for online learning in contextual queueing systems and hence our analytical framework may be of independent interest. This talk is based on joint work with Wentao Weng (Ph.D. student at MIT EECS). A preprint of the corresponding paper can be found here: https://arxiv.org/pdf/2402.12237. This work has been selected as a finalist in the 2024 INFORMS Junior Faculty Interest Group (JFIG) Paper Competition. 32-G449