DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2024.59

Equivocal Blends: Prior Independent Lower Bounds

Authors: Jason Hartline and Aleck Johnsen

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

The prior independent framework for algorithm design considers how well an algorithm that does not know the distribution of its inputs approximates the expected performance of the optimal algorithm for this distribution. This paper gives a method that is agnostic to problem setting for proving lower bounds on the prior independent approximation factor of any algorithm. The method constructs a correlated distribution over inputs that can be described both as a distribution over i.i.d. good-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms distributions. We call these two descriptions equivocal blends. Prior independent algorithms are upper-bounded by the optimal algorithm for the latter distribution even when the true distribution is the former. Thus, the ratio of the expected performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on the prior independent approximation ratio. We apply this framework to give new lower bounds on canonical prior independent mechanism design problems. For one of these problems, we also exhibit a near-tight upper bound. Towards solutions for general problems, we give distinct descriptions of two large classes of correlated-distribution "solutions" for the technique, depending respectively on an order-statistic separability property and a paired inverse-distribution property. We exhibit that equivocal blends do not generally have a Blackwell ordering, which puts this paper outside of standard information design.

Cite as

Jason Hartline and Aleck Johnsen. Equivocal Blends: Prior Independent Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 59:1-59:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hartline_et_al:LIPIcs.ITCS.2024.59,
  author =	{Hartline, Jason and Johnsen, Aleck},
  title =	{{Equivocal Blends: Prior Independent Lower Bounds}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{59:1--59:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.59},
  URN =		{urn:nbn:de:0030-drops-195878},
  doi =		{10.4230/LIPIcs.ITCS.2024.59},
  annote =	{Keywords: prior independent algorithms, lower bounds, correlated decompositions, minimax, equivocal blends, mechanism design, blackwell ordering}
}

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}
}

Search Results

Documents authored by Johnsen, Aleck

Equivocal Blends: Prior Independent Lower Bounds

Abstract

Cite as

Screening with Disadvantaged Agents

Abstract

Cite as

Thanks for your feedback!

Could not send message