15 papers
On the Power of Deception in Repeated Games
Saba Ahmadi, Avrim Blum, Dimitar Chakarov +1
In repeated games, opponents often predict what we'll do next by looking at what we have done so far. This allows us to deceive them: we can deliberately behave one way for a perio…
A Machine Learning Theory Perspective on Strategic Litigation
Melissa Dutz, Han Shao, Avrim Blum +1
Strategic litigation involves bringing a case to court with the goal of having an impact beyond resolving the particular dispute at hand. In a common law system, one way a case may…
Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
Avrim Blum, Marten Garicano, Kavya Ravichandran +1
The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies,…
Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
Avrim Blum, Daniel Hsu, Cyrus Rashtchian +1
Test-time augmentation, such as Retrieval-Augmented Generation (RAG) or tool use, critically depends on an interplay between a model's parametric knowledge and externally retrieved…
Online Learnability of Chain-of-Thought Verifiers: Soundness and Completeness Trade-offs
Maria-Florina Balcan, Avrim Blum, Kiriaki Fragkia +2
Large Language Models (LLMs) using chain-of-thought reasoning have demonstrated great potential for solving complex reasoning and planning tasks. However, their outputs remain unre…
Revealing Positive and Negative Role Models to Help People Make Good Decisions
Avrim Blum, Keziah Naggita, Matthew R. Walter +1
We consider a setting where agents take action by following their role models in a social network, and study strategies for a social planner to help agents by revealing whether the…