Search Results

Documents authored by Mansour, Yishay

Document
DOI: 10.4230/LIPIcs.ITCS.2025.39
Data Reconstruction: When You See It and When You Don't

Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia

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

Abstract
We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically, - We introduce a new definitional paradigm - Narcissus Resiliency - to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes. - We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful.
Cite as

Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Data Reconstruction: When You See It and When You Don't. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2025.39,
  author =	{Cohen, Edith and Kaplan, Haim and Mansour, Yishay and Moran, Shay and Nissim, Kobbi and Stemmer, Uri and Tsfadia, Eliad},
  title =	{{Data Reconstruction: When You See It and When You Don't}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{39:1--39:23},
  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.39},
  URN =		{urn:nbn:de:0030-drops-226674},
  doi =		{10.4230/LIPIcs.ITCS.2025.39},
  annote =	{Keywords: differential privacy, reconstruction}
}
Document
DOI: 10.4230/LIPIcs.FORC.2020.1
Efficient Candidate Screening Under Multiple Tests and Implications for Fairness

Authors: Lee Cohen, Zachary C. Lipton, and Yishay Mansour

Published in: LIPIcs, Volume 156, 1st Symposium on Foundations of Responsible Computing (FORC 2020)

Abstract
When recruiting job candidates, employers rarely observe their underlying skill level directly. Instead, they must administer a series of interviews and/or collate other noisy signals in order to estimate the worker’s skill. Traditional economics papers address screening models where employers access worker skill via a single noisy signal. In this paper, we extend this theoretical analysis to a multi-test setting, considering both Bernoulli and Gaussian models. We analyze the optimal employer policy both when the employer sets a fixed number of tests per candidate and when the employer can set a dynamic policy, assigning further tests adaptively based on results from the previous tests. To start, we characterize the optimal policy when employees constitute a single group, demonstrating some interesting trade-offs. Subsequently, we address the multi-group setting, demonstrating that when the noise levels vary across groups, a fundamental impossibility emerges whereby we cannot administer the same number of tests, subject candidates to the same decision rule, and yet realize the same outcomes in both groups. We show that by subjecting members of noisier groups to more tests, we can equalize the confusion matrix entries across groups, seemingly eliminating any disparate impact concerning outcomes.
Cite as

Lee Cohen, Zachary C. Lipton, and Yishay Mansour. Efficient Candidate Screening Under Multiple Tests and Implications for Fairness. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 156, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.FORC.2020.1,
  author =	{Cohen, Lee and Lipton, Zachary C. and Mansour, Yishay},
  title =	{{Efficient Candidate Screening Under Multiple Tests and Implications for Fairness}},
  booktitle =	{1st Symposium on Foundations of Responsible Computing (FORC 2020)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-142-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{156},
  editor =	{Roth, Aaron},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2020.1},
  URN =		{urn:nbn:de:0030-drops-120179},
  doi =		{10.4230/LIPIcs.FORC.2020.1},
  annote =	{Keywords: algorithmic fairness, random walk, inference}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.16
On Price versus Quality

Authors: Avrim Blum and Yishay Mansour

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
In this work we propose a model where the value of a buyer for some product (like a slice of pizza) is a combination of their personal desire for the product (how hungry they are for pizza) and the quality of the product (how good the pizza is). Sellers in this setting have a two-dimensional optimization problem of determining both the quality level at which to make their product (how expensive ingredients to use) and the price at which to sell it. We analyze optimal seller strategies as well as analogs of Walrasian equilibria in this setting. A key question we are interested in is: to what extent will the price of a good be a reliable indicator of the good's quality? One result we show is that indeed in this model, price will be a surprisingly robust signal for quality under optimal seller behavior. In particular, while the specific quality and price that a seller should choose will depend highly on the specific distribution of buyers, for optimal sellers, price and quality will be linearly related, independent of that distribution. We also show that for the case of multiple buyers and sellers, an analog of Walrasian equilibrium exists in this setting, and can be found via a natural tatonnement process. Finally, we analyze markets with a combination of "locals" (who know the quality of each good) and "tourists" (who do not) and analyze under what conditions the market will become a tourist trap, setting quality to zero while keeping prices high.
Cite as

Avrim Blum and Yishay Mansour. On Price versus Quality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blum_et_al:LIPIcs.ITCS.2018.16,
  author =	{Blum, Avrim and Mansour, Yishay},
  title =	{{On Price versus Quality}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.16},
  URN =		{urn:nbn:de:0030-drops-83264},
  doi =		{10.4230/LIPIcs.ITCS.2018.16},
  annote =	{Keywords: Algorithmic game theory, pricing, Cobb-Douglas valuations}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.48
Competing Bandits: Learning Under Competition

Authors: Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition--how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems. In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen. We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the "competition vs. innovation" relationship, a well-studied theme in economics.
Cite as

Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu. Competing Bandits: Learning Under Competition. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 48:1-48:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mansour_et_al:LIPIcs.ITCS.2018.48,
  author =	{Mansour, Yishay and Slivkins, Aleksandrs and Wu, Zhiwei Steven},
  title =	{{Competing Bandits: Learning Under Competition}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{48:1--48:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.48},
  URN =		{urn:nbn:de:0030-drops-83341},
  doi =		{10.4230/LIPIcs.ITCS.2018.48},
  annote =	{Keywords: machine learning, game theory, competition, exploration, rationality}
}
Document
DOI: 10.4230/DagRep.7.6.68
Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251)

Authors: Paul W. Goldberg, Yishay Mansour, and Paul Dütting

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)

Abstract
his report documents the program and the outcomes of Dagstuhl Seminar 17251 "Game Theory Meets Computational Learning Theory". While there have been many Dagstuhl seminars on various aspects of Algorithmic Game Theory, this was the first one to focus on the emerging field of its intersection with computational learning theory.
Cite as

Paul W. Goldberg, Yishay Mansour, and Paul Dütting. Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251). In Dagstuhl Reports, Volume 7, Issue 6, pp. 68-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{goldberg_et_al:DagRep.7.6.68,
  author =	{Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul},
  title =	{{Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251)}},
  pages =	{68--85},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.6.68},
  URN =		{urn:nbn:de:0030-drops-82876},
  doi =		{10.4230/DagRep.7.6.68},
  annote =	{Keywords: Algorithmic Game Theory, Computational Learning Theory, Economics}
}
Document
DOI: 10.4230/DagRep.3.11.58
Electronic Markets and Auctions (Dagstuhl Seminar 13461)

Authors: Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking

Published in: Dagstuhl Reports, Volume 3, Issue 11 (2014)

Abstract
The main goal of this workshop was to study topics related to electronic markets and auctions both from the computational perspective and from a game-theoretic and economic one. From the computer science perspective, with the advent of the Internet, there has been a significant amount of work in Algorithmic Game Theory focusing on computational aspects of electronic markets and on algorithmic aspects of mechanism design. Economics have been traditionally interested in markets in general and designing efficient markets mechanisms (such as auctions) in particular. The recent emergence of electronic markets and auctions has only reemphasized the importance of this topic.
Cite as

Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking. Electronic Markets and Auctions (Dagstuhl Seminar 13461). In Dagstuhl Reports, Volume 3, Issue 11, pp. 58-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{mansour_et_al:DagRep.3.11.58,
  author =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  title =	{{Electronic Markets and Auctions (Dagstuhl Seminar 13461)}},
  pages =	{58--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{11},
  editor =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.11.58},
  URN =		{urn:nbn:de:0030-drops-44379},
  doi =		{10.4230/DagRep.3.11.58},
  annote =	{Keywords: Algorithmic game theory, mechanism design, economics, electronic markets}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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