5 citations · 10 across the 16 of their papers we have counts for
20 papers
Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi
We study the problem of efficient online proportional sampling from a high-dimensional domain under a -smoothed adversary, where the sampling distribution is induced by a dynami…
Two-Sided Time-Independent Regret for Matching Markets with Limited Interviews
Amirmahdi Mirfakhar, Xuchuang Wang, Mengfan Xu +2
Two-sided matching platforms rely on preferences from both sides, yet participants can evaluate only a small fraction of potential partners. In practice, they use low-cost pre-matc…
The Secretary Problem with Predictions and a Chosen Order
Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi +2
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023), in which the decision-maker has access to machine-learned predictio…
The Active and Noise-Tolerant Strategic Perceptron
Maria-Florina Balcan, Hedyeh Beyhaghi
We initiate the study of active learning algorithms for classifying strategic agents. Active learning is a well-established framework in machine learning in which the learner selec…
CGES: Confidence-Guided Early Stopping for Efficient and Accurate Self-Consistency
Ehsan Aghazadeh, Ahmad Ghasemi, Hedyeh Beyhaghi +1
Large language models (LLMs) are often queried multiple times at test time, with predictions aggregated by majority vote. While effective, this self-consistency (Wang et al., 2023)…
Competitive Algorithms for Multi-Agent Ski-Rental Problems
Xuchuang Wang, Bo Sun, Hedyeh Beyhaghi +3
This paper introduces a novel multi-agent ski-rental problem that generalizes the classical ski-rental dilemma to a group setting where agents incur individual and shared costs. In…
Competition Complexity in Multi-Item Auctions: Beyond VCG and Regularity
Hedyeh Beyhaghi, Linda Cai, Yiding Feng +2
We quantify the value of the monopoly's bargaining power in terms of competition complexity--that is, the number of additional bidders the monopoly must attract in simple auctions…
Recent Developments in Pandora's Box Problem: Variants and Applications
Hedyeh Beyhaghi, Linda Cai
In 1979, Weitzman introduced Pandora's box problem as a framework for sequential search with costly inspections. Recently, there has been a surge of interest in Pandora's box probl…
Screening with Disadvantaged Agents
Hedyeh Beyhaghi, Modibo K. Camara, Jason Hartline +2
Motivated by school admissions, this paper studies screening in a population with both advantaged and disadvantaged agents. A school is interested in admitting the most skilled stu…
New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
Maria-Florina Balcan, Hedyeh Beyhaghi
We advance a recently flourishing line of work at the intersection of learning theory and computational economics by studying the learnability of two classes of mechanisms prominen…
Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS
Hedyeh Beyhaghi, Linda Cai
Weitzman introduced Pandora's box problem as a mathematical model of sequential search with inspection costs, in which a searcher is allowed to select a prize from one of alter…
Setting Fair Incentives to Maximize Improvement
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum +1
We consider the problem of helping agents improve by setting short-term goals. Given a set of target skill levels, we assume each agent will try to improve from their initial skill…
On classification of strategic agents who can both game and improve
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum +1
In this work, we consider classification of agents who can both game and improve. For example, people wishing to get a loan may be able to take some actions that increase their per…
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla +1
Babaioff et al. [BIK2007] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a c…
The Strategic Perceptron
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum +1
The classical Perceptron algorithm provides a simple and elegant procedure for learning a linear classifier. In each step, the algorithm observes the sample's position and label an…
Pandora's Problem with Nonobligatory Inspection
Hedyeh Beyhaghi, Robert Kleinberg
Martin Weitzman's "Pandora's problem" furnishes the mathematical basis for optimal search theory in economics. Nearly 40 years later, Laura Doval introduced a version of the proble…
Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
Hedyeh Beyhaghi, S. Matthew Weinberg
The Competition Complexity of an auction setting refers to the number of additional bidders necessary in order for the (deterministic, prior-independent, dominant strategy truthful…
Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms
Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme +2
We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with buyers and independent but not necessarily identical value di…
Effect of selfish choices in deferred acceptance with short lists
Hedyeh Beyhaghi, Daniela Saban, Eva Tardos
We study the outcome of deferred acceptance when prospective medical residents can only apply to a limited set of hospitals. This limitation requires residents to make a strategic…
Effect of Strategic Grading and Early Offers in Matching Markets
Hedyeh Beyhaghi, Nishanth Dikkala, Eva Tardos
Strategic suppression of grades, as well as early offers and contracts, are well-known phenomena in the matching process where graduating students apply to jobs or further educatio…