Hedyeh Beyhaghi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Hedyeh Beyhaghi has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Linda Cai
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA, USA
1 shared publication - Robert Kleinberg
Cornell University
1 shared publication - S. Matthew Weinberg
Princeton University
1 shared publication - Yiding Feng
Hong Kong University of Science and Technology, Hong Kong, Hong Kong
1 shared publication - Yingkai Li
National University of Singapore, Singapore, Singapore
1 shared publication
Latest Publications
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 89
Competition Complexity in Multi-item Auctions: Beyond VCG and Regularity
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 89
Open AccessCompetition Complexity in Multi-item Auctions: Beyond VCG and Regularity
- Open Access
- 17 June 2019
- Published by Association for Computing Machinery (ACM)
- p. 131-132
Pandora's Problem with Nonobligatory Inspection
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 problem in which the searcher is not obligated to pay the cost of inspecting an alternative's value before selecting it. Unlike the original Pandora's problem, the version with nonobligatory inspection cannot be solved optimally by any simple ranking-based policy, and it is unknown whether there exists any polynomial-time algorithm to compute the optimal policy. This motivates the study of approximately optimal policies that are simple and computationally efficient. In this work we provide the first non-trivial approximation guarantees for this problem. We introduce a family of "committing policies" such that it is computationally easy to find and implement the optimal committing policy. We prove that the optimal committing policy is guaranteed to approximate the fully optimal policy within a 1-1/e = 0.63... factor, and for the special case of two boxes we improve this factor to 4/5 and show that this approximation is tight for the class of committing policies.
- 17 June 2019
- Published by Association for Computing Machinery (ACM)
- p. 131-132
Open AccessPandora's Problem with Nonobligatory Inspection
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 problem in which the searcher is not obligated to pay the cost of inspecting an alternative's value before selecting it. Unlike the original Pandora's problem, the version with nonobligatory inspection cannot be solved optimally by any simple ranking-based policy, and it is unknown whether there exists any polynomial-time algorithm to compute the optimal policy. This motivates the study of approximately optimal policies that are simple and computationally efficient. In this work we provide the first non-trivial approximation guarantees for this problem. We introduce a family of "committing policies" such that it is computationally easy to find and implement the optimal committing policy. We prove that the optimal committing policy is guaranteed to approximate the fully optimal policy within a 1-1/e = 0.63... factor, and for the special case of two boxes we improve this factor to 4/5 and show that this approximation is tight for the class of committing policies.