10 Search Results for "Beyhaghi, Hedyeh"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.86
The Secretary Problem with Predictions and a Chosen Order

Authors: Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study a learning-augmented variant of the secretary problem, recently introduced by Fujii and Yoshida (2023). In this variant, the decision-maker has access to machine-learned predictions of candidate values in advance. The key challenge is to balance consistency and robustness: when the predictions are accurate, the algorithm should hire a near-best secretary; however, if they are inaccurate, the algorithm should still achieve a bounded competitive ratio. We consider both the standard Random Order Secretary Problem (ROSP), where candidates arrive in a uniform random order, and a more natural model in the learning-augmented setting, where the decision-maker can choose the arrival order based on the predicted candidate values. This model, which we call the Chosen Order Secretary Problem (COSP), can capture scenarios such as an interview schedule that is set by the decision-maker. We propose a novel algorithm that applies to both ROSP and COSP. Building on the approach of Fujii and Yoshida, our method switches from fully trusting predictions to a threshold-based rule when a large deviation of a prediction is observed. Importantly, unlike the algorithm of Fujii and Yoshida, our algorithm uses randomization as part of its decision logic. We show that if ε ∈ [0,1] denotes the maximum multiplicative prediction error, then for ROSP our algorithm achieves competitive ratio max {0.221, (1-ε)/(1+ε)}, improving on a previous bound of max {0.215, (1-ε)/(1+ε)} due to Fujii and Yoshida [Fujii and Yoshida, 2023]. For COSP, our algorithm achieves max {0.262, (1-ε)/(1+ε)}. This surpasses a 0.25 upper bound on the worst-case competitive ratio that applies to the approach of Fujii and Yoshida, and gets closer to the classical secretary benchmark of 1/e ≈ 0.368, which is an upper bound for any algorithm. Our result for COSP highlights the benefit of integrating predictions with arrival-order control in online decision-making.
Cite as

Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, and Cameron Musco. The Secretary Problem with Predictions and a Chosen Order. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 86:1-86:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karisani_et_al:LIPIcs.ITCS.2026.86,
  author =	{Karisani, Helia and Daneshvaramoli, Mohammadreza and Beyhaghi, Hedyeh and Hajiesmaili, Mohammad and Musco, Cameron},
  title =	{{The Secretary Problem with Predictions and a Chosen Order}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{86:1--86:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.86},
  URN =		{urn:nbn:de:0030-drops-253734},
  doi =		{10.4230/LIPIcs.ITCS.2026.86},
  annote =	{Keywords: Secretary problem, learning-augmented algorithms, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.52
Beating Competitive Ratio 4 for Graphic Matroid Secretary

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.
Cite as

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating Competitive Ratio 4 for Graphic Matroid Secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ESA.2025.52,
  author =	{Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Kowalski, Dariusz R. and Krysta, Piotr and Mittal, Danny and Olkowski, Jan},
  title =	{{Beating Competitive Ratio 4 for Graphic Matroid Secretary}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.52},
  URN =		{urn:nbn:de:0030-drops-245205},
  doi =		{10.4230/LIPIcs.ESA.2025.52},
  annote =	{Keywords: online algorithms, graphic matroids, secretary problem}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.26
Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS

Authors: Mads Anker Nielsen, Lars Rohwedder, and Kevin Schewior

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of k-of-n functions: There are independent Boolean random variables x_1,… ,x_n where each variable i has a known probability p_i of taking value 1, and a known cost c_i that can be paid to find out its value. The value of the function is 1 iff there are at least k 1s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of 2 on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of 3/2 for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument.
Cite as

Mads Anker Nielsen, Lars Rohwedder, and Kevin Schewior. Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nielsen_et_al:LIPIcs.APPROX/RANDOM.2025.26,
  author =	{Nielsen, Mads Anker and Rohwedder, Lars and Schewior, Kevin},
  title =	{{Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.26},
  URN =		{urn:nbn:de:0030-drops-243920},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.26},
  annote =	{Keywords: Approximation scheme, Boolean functions, stochastic combinatorial optimization, stochastic function evaluation, sequential testing, adaptivity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.137
Universal Online Contention Resolution with Preselected Order

Authors: Junyao Zhao

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Online contention resolution scheme (OCRS) is a powerful technique for online decision making, which - in the case of matroids - given a matroid and a prior distribution of active elements, selects a subset of active elements that satisfies the matroid constraint in an online fashion. OCRS has been studied mostly for product distributions in the literature. Recently, universal OCRS, that works even for correlated distributions, has gained interest, because it naturally generalizes the classic notion, and its existence in the random-order arrival model turns out to be equivalent to the matroid secretary conjecture. However, currently very little is known about how to design universal OCRSs for any arrival model. In this work, we consider a natural and relatively flexible arrival model, where the OCRS is allowed to preselect (i.e., non-adaptively select) the arrival order of the elements, and within this model, we design simple and optimal universal OCRSs that are computationally efficient. In the course of deriving our OCRSs, we also discover an efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model, answering a question posed in [Dughmi, 2020].
Cite as

Junyao Zhao. Universal Online Contention Resolution with Preselected Order. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 137:1-137:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhao:LIPIcs.ICALP.2025.137,
  author =	{Zhao, Junyao},
  title =	{{Universal Online Contention Resolution with Preselected Order}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{137:1--137:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.137},
  URN =		{urn:nbn:de:0030-drops-235147},
  doi =		{10.4230/LIPIcs.ICALP.2025.137},
  annote =	{Keywords: Matroids, online contention resolution schemes, secretary problems}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.50
Designing Exploration Contracts

Authors: Martin Hoefer, Conrad Schecker, and Kevin Schewior

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study a natural application of contract design in the context of sequential exploration problems. In our principal-agent setting, a search task is delegated to an agent. The agent performs a sequential exploration of n boxes, suffers the exploration cost for each inspected box, and selects the content (called the prize) of one inspected box as outcome. Agent and principal obtain an individual value based on the selected prize. To influence the search, the principal a-priori designs a contract with a non-negative payment to the agent for each potential prize. The goal of the principal is to maximize her expected reward, i.e., value minus payment. Interestingly, this natural contract scenario shares close relations with the Pandora’s Box problem. We show how to compute optimal contracts for the principal in several scenarios. A popular and important subclass is that of linear contracts, and we show how to compute optimal linear contracts in polynomial time. For general contracts, we obtain optimal contracts under the standard assumption that the agent suffers cost but obtains value only from the transfers by the principal. More generally, for general contracts with non-zero agent values for outcomes we show how to compute an optimal contract in two cases: (1) when each box has only one prize with non-zero value for principal and agent, (2) for i.i.d. boxes with a single prize with positive value for the principal.
Cite as

Martin Hoefer, Conrad Schecker, and Kevin Schewior. Designing Exploration Contracts. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoefer_et_al:LIPIcs.STACS.2025.50,
  author =	{Hoefer, Martin and Schecker, Conrad and Schewior, Kevin},
  title =	{{Designing Exploration Contracts}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.50},
  URN =		{urn:nbn:de:0030-drops-228755},
  doi =		{10.4230/LIPIcs.STACS.2025.50},
  annote =	{Keywords: Exploration, Contract Design, Pandora’s Box Problem}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.12
Stable Matching with Interviews

Authors: Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon Gale-Shapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log² n). In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log³ n) interviews to each applicant or position.
Cite as

Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi. Stable Matching with Interviews. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:LIPIcs.ITCS.2025.12,
  author =	{Ashlagi, Itai and Chen, Jiale and Roghani, Mohammad and Saberi, Amin},
  title =	{{Stable Matching with Interviews}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-226402},
  doi =		{10.4230/LIPIcs.ITCS.2025.12},
  annote =	{Keywords: Stable Matching, Gale–Shapley Algorithm, Algorithmic Game Theory}
}
Document
DOI: 10.4230/LIPIcs.FORC.2023.5
Setting Fair Incentives to Maximize Improvement

Authors: Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita

Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)

Abstract
We consider the problem of helping agents improve by setting goals. Given a set of target skill levels, we assume each agent will try to improve from their initial skill level to the closest target level within reach (or do nothing if no target level is within reach). We consider two models: the common improvement capacity model, where agents have the same limit on how much they can improve, and the individualized improvement capacity model, where agents have individualized limits. Our goal is to optimize the target levels for social welfare and fairness objectives, where social welfare is defined as the total amount of improvement, and we consider fairness objectives when the agents belong to different underlying populations. We prove algorithmic, learning, and structural results for each model. A key technical challenge of this problem is the non-monotonicity of social welfare in the set of target levels, i.e., adding a new target level may decrease the total amount of improvement; agents who previously tried hard to reach a distant target now have a closer target to reach and hence improve less. This especially presents a challenge when considering multiple groups because optimizing target levels in isolation for each group and outputting the union may result in arbitrarily low improvement for a group, failing the fairness objective. Considering these properties, we provide algorithms for optimal and near-optimal improvement for both social welfare and fairness objectives. These algorithmic results work for both the common and individualized improvement capacity models. Furthermore, despite the non-monotonicity property and interference of the target levels, we show a placement of target levels exists that is approximately optimal for the social welfare of each group. Unlike the algorithmic results, this structural statement only holds in the common improvement capacity model, and we illustrate counterexamples of this result in the individualized improvement capacity model. Finally, we extend our algorithms to learning settings where we have only sample access to the initial skill levels of agents.
Cite as

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. Setting Fair Incentives to Maximize Improvement. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.FORC.2023.5,
  author =	{Ahmadi, Saba and Beyhaghi, Hedyeh and Blum, Avrim and Naggita, Keziah},
  title =	{{Setting Fair Incentives to Maximize Improvement}},
  booktitle =	{4th Symposium on Foundations of Responsible Computing (FORC 2023)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-272-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{256},
  editor =	{Talwar, Kunal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.5},
  URN =		{urn:nbn:de:0030-drops-179261},
  doi =		{10.4230/LIPIcs.FORC.2023.5},
  annote =	{Keywords: Algorithmic Fairness, Learning for Strategic Behavior, Incentivizing Improvement}
}
Document
DOI: 10.4230/LIPIcs.FORC.2023.6
Screening with Disadvantaged Agents

Authors: Hedyeh Beyhaghi, Modibo K. Camara, Jason Hartline, Aleck Johnsen, and Sheng Long

Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)

Abstract
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 students, but relies on imperfect test scores that reflect both skill and effort. Students are limited by a budget on effort, with disadvantaged students having tighter budgets. This raises a challenge for the principal: among agents with similar test scores, it is difficult to distinguish between students with high skills and students with large budgets. Our main result is an optimal stochastic mechanism that maximizes the gains achieved from admitting "high-skill" students minus the costs incurred from admitting "low-skill" students when considering two skill types and n budget types. Our mechanism makes it possible to give higher probability of admission to a high-skill student than to a low-skill, even when the low-skill student can potentially get higher test-score due to a higher budget. Further, we extend our admission problem to a setting in which students uniformly receive an exogenous subsidy to increase their budget for effort. This extension can only help the school’s admission objective and we show that the optimal mechanism with exogenous subsidies has the same characterization as optimal mechanisms for the original problem.
Cite as

Hedyeh Beyhaghi, Modibo K. Camara, Jason Hartline, Aleck Johnsen, and Sheng Long. Screening with Disadvantaged Agents. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{beyhaghi_et_al:LIPIcs.FORC.2023.6,
  author =	{Beyhaghi, Hedyeh and Camara, Modibo K. and Hartline, Jason and Johnsen, Aleck and Long, Sheng},
  title =	{{Screening with Disadvantaged Agents}},
  booktitle =	{4th Symposium on Foundations of Responsible Computing (FORC 2023)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-272-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{256},
  editor =	{Talwar, Kunal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.6},
  URN =		{urn:nbn:de:0030-drops-179274},
  doi =		{10.4230/LIPIcs.FORC.2023.6},
  annote =	{Keywords: screening, strategic classification, budgeted mechanism design, fairness, effort-incentives, subsidies, school admission}
}
Document
DOI: 10.4230/LIPIcs.FORC.2022.3
On Classification of Strategic Agents Who Can Both Game and Improve

Authors: Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita

Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)

Abstract
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 perceived credit-worthiness and others that also increase their true credit-worthiness. A decision-maker would like to define a classification rule with few false-positives (does not give out many bad loans) while yielding many true positives (giving out many good loans), which includes encouraging agents to improve to become true positives if possible. We consider two models for this problem, a general discrete model and a linear model, and prove algorithmic, learning, and hardness results for each. For the general discrete model, we give an efficient algorithm for the problem of maximizing the number of true positives subject to no false positives, and show how to extend this to a partial-information learning setting. We also show hardness for the problem of maximizing the number of true positives subject to a nonzero bound on the number of false positives, and that this hardness holds even for a finite-point version of our linear model. We also show that maximizing the number of true positives subject to no false positive is NP-hard in our full linear model. We additionally provide an algorithm that determines whether there exists a linear classifier that classifies all agents accurately and causes all improvable agents to become qualified, and give additional results for low-dimensional data.
Cite as

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On Classification of Strategic Agents Who Can Both Game and Improve. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.FORC.2022.3,
  author =	{Ahmadi, Saba and Beyhaghi, Hedyeh and Blum, Avrim and Naggita, Keziah},
  title =	{{On Classification of Strategic Agents Who Can Both Game and Improve}},
  booktitle =	{3rd Symposium on Foundations of Responsible Computing (FORC 2022)},
  pages =	{3:1--3:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-226-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{218},
  editor =	{Celis, L. Elisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.3},
  URN =		{urn:nbn:de:0030-drops-165269},
  doi =		{10.4230/LIPIcs.FORC.2022.3},
  annote =	{Keywords: Strategic Classification, Social Welfare, Learning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.74
Randomness and Fairness in Two-Sided Matching with Limited Interviews

Authors: Hedyeh Beyhaghi and Éva Tardos

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the outcome in a matching market where both sides have limited ability to consider options. For example, in the national residency matching program, doctors are limited to apply to a small set of hospitals, and hospitals are limited by the time required to interview candidates. Our main findings are the following: (1) In markets where jobs can only consider a limited number of candidates for interview, it increases the size of the resulting matching if the system has a limit on the number of applications a candidate can send. (2) The fair system of all applicants being allowed to apply to the exact same number of positions maximizes the expected size of the matching. More particularly, starting from an integer k as the number of applications, the matching size decreases as a few applicants are allowed to apply to one additional position (and then increases again as they are all allowed to apply to k+1). Although it seems natural to expect that the size of the matching would be a monotone increasing and concave function in the number of applications, our results show that neither is true. These results hold even in a market where a-priori all jobs and all candidates are equally likely to be good, and the judgments of different employers and candidates are independent. Our main technical contribution is computing the expected size of the matching found via the deferred acceptance algorithm as a function of the number of interviews and applications in a market where preferences are uniform and independent. Through simulations we confirm that these findings extend to markets where rankings become correlated after the interviews.
Cite as

Hedyeh Beyhaghi and Éva Tardos. Randomness and Fairness in Two-Sided Matching with Limited Interviews. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{beyhaghi_et_al:LIPIcs.ITCS.2021.74,
  author =	{Beyhaghi, Hedyeh and Tardos, \'{E}va},
  title =	{{Randomness and Fairness in Two-Sided Matching with Limited Interviews}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.74},
  URN =		{urn:nbn:de:0030-drops-136139},
  doi =		{10.4230/LIPIcs.ITCS.2021.74},
  annote =	{Keywords: Matching with Short Lists, Stable Matching, Balls in Bins Problem}
}
  • Refine by Type
  • 10 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 2 2023
  • 1 2022
  • 1 2021

  • Refine by Author
  • 5 Beyhaghi, Hedyeh
  • 2 Ahmadi, Saba
  • 2 Blum, Avrim
  • 2 Naggita, Keziah
  • 2 Schewior, Kevin
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Algorithmic mechanism design
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Online algorithms
  • 1 Applied computing → Economics
  • 1 Theory of computation → Algorithmic game theory
  • Show More...

  • Refine by Keyword
  • 2 Stable Matching
  • 2 online algorithms
  • 1 Algorithmic Fairness
  • 1 Algorithmic Game Theory
  • 1 Approximation scheme
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact