6 Search Results for "Dughmi, Shaddin"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.51
On Sparsification of Stochastic Packing Problems

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems more generally. Specifically, we consider packing problems where elements are independently active with a given probability p, and ask whether one can (non-adaptively) compute a "sparse" set of elements guaranteed to contain an approximately optimal solution to the realized (active) subproblem. We seek structural and algorithmic results of broad applicability to such problems. Our focus is on computing sparse sets containing on the order of d feasible solutions to the packing problem, where d is linear or at most polynomial in 1/p. Crucially, we require d to be independent of the number of elements, or any parameter related to the "size" of the packing problem. We refer to d as the "degree" of the sparsifier, as is consistent with graph theoretic degree in the special case of matching. First, we exhibit a generic sparsifier of degree 1/p based on contention resolution. This sparsifier’s approximation ratio matches the best contention resolution scheme (CRS) for any packing problem for additive objectives, and approximately matches the best monotone CRS for submodular objectives. Second, we embark on outperforming this generic sparsifier for additive optimization over matroids and their intersections, as well as weighted matching. These improved sparsifiers feature different algorithmic and analytic approaches, and have degree linear in 1/p. In the case of a single matroid, our sparsifier tends to the optimal solution. In the case of weighted matching, we combine our contention-resolution-based sparsifier with technical approaches of prior work to improve the state of the art ratio from 0.501 to 0.536. Third, we examine packing problems with submodular objectives. We show that even the simplest such problems do not admit sparsifiers approaching optimality. We then outperform our generic sparsifier for some special cases with submodular objectives.
Cite as

Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. On Sparsification of Stochastic Packing Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ICALP.2023.51,
  author =	{Dughmi, Shaddin and Kalayci, Yusuf Hakan and Patel, Neel},
  title =	{{On Sparsification of Stochastic Packing Problems}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.51},
  URN =		{urn:nbn:de:0030-drops-181036},
  doi =		{10.4230/LIPIcs.ICALP.2023.51},
  annote =	{Keywords: Stochastic packing, sparsification, matroid}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.11
Multi-Channel Bayesian Persuasion

Authors: Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We propose a model that smoothly interpolates between the two, by introducing a natural multi-channel communication structure in which each receiver observes a subset of the sender’s communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable. Our main result is a complete characterization specifying when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure M₁ is (weakly) better than M₂ if and only if every information-dominating pair of receivers in M₁ is also such in M₂. This result holds in the most general model of Bayesian persuasion in which receivers may have externalities - that is, the receivers' actions affect each other. The proof is cryptographic-inspired and it has a close conceptual connection to secret sharing protocols. As a surprising consequence of the main result, the sender can implement private Bayesian persuasion (which is the best communication structure for the sender) for k receivers using only O(log k) communication channels, rather than k channels in the naive implementation. We provide an implementation that matches the information-theoretical lower bound on the number of channels - not only asymptotically, but exactly. Moreover, the main result immediately implies some results of [Kerman and Tenev, 2021] on persuading receivers arranged in a network such that each receiver observes both the signals sent to him and to his neighbours in the network. We further provide an additive FPTAS for an optimal sender’s signaling scheme when the number of states of nature is constant, the sender has an additive utility function and the graph of the information-dominating pairs of receivers is a directed forest. We focus on a constant number of states, as even for the special case of public persuasion and additive sender’s utility, it was shown by [Shaddin Dughmi and Haifeng Xu, 2017] that one can achieve neither an additive PTAS nor a polynomial-time constant-factor optimal sender’s utility approximation (unless P=NP). We leave for future research studying exact tractability of forest communication structures, as well as generalizing our result to more families of sender’s utility functions and communication structures. Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is computationally hard for a general family of sender’s utility functions - separable supermajority functions, which are specified by choosing a partition of the set of receivers and summing supermajority functions corresponding to different elements of the partition, multiplied by some non-negative constants. Note that one can easily deduce from [Emir Kamenica and Matthew Gentzkow, 2011] and [Itai Arieli and Yakov Babichenko, 2019] that finding an optimal signaling scheme for such utility functions is computationally tractable for both public and private persuasion. This difference illustrates both the conceptual and the computational hardness of general multi-channel persuasion.
Cite as

Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Multi-Channel Bayesian Persuasion. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babichenko_et_al:LIPIcs.ITCS.2022.11,
  author =	{Babichenko, Yakov and Talgam-Cohen, Inbal and Xu, Haifeng and Zabarnyi, Konstantin},
  title =	{{Multi-Channel Bayesian Persuasion}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{11:1--11:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.11},
  URN =		{urn:nbn:de:0030-drops-156072},
  doi =		{10.4230/LIPIcs.ITCS.2022.11},
  annote =	{Keywords: Algorithmic game theory, Bayesian persuasion, Private Bayesian persuasion, Public Bayesian persuasion, Secret sharing, Networks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.58
Matroid Secretary Is Equivalent to Contention Resolution

Authors: Shaddin Dughmi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is true if and only if every matroid admits an online random-order contention resolution scheme which, given an arbitrary (possibly correlated) prior distribution over subsets of the ground set, matches the balance ratio of the best offline scheme for that distribution up to a constant. We refer to such a scheme as universal. Our result indicates that the core challenge of the matroid secretary problem lies in resolving contention for positively correlated inputs, in particular when the positive correlation is benign in as much as offline contention resolution is concerned. Our result builds on our previous work which establishes one direction of this equivalence, namely that the secretary conjecture implies universal random-order contention resolution, as well as a weak converse, which derives a matroid secretary algorithm from a random-order contention resolution scheme with only partial knowledge of the distribution. It is this weak converse that we strengthen in this paper: We show that universal random-order contention resolution for matroids, in the usual setting of a fully known prior distribution, suffices to resolve the matroid secretary conjecture in the affirmative.
Cite as

Shaddin Dughmi. Matroid Secretary Is Equivalent to Contention Resolution. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dughmi:LIPIcs.ITCS.2022.58,
  author =	{Dughmi, Shaddin},
  title =	{{Matroid Secretary Is Equivalent to Contention Resolution}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{58:1--58:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.58},
  URN =		{urn:nbn:de:0030-drops-156540},
  doi =		{10.4230/LIPIcs.ITCS.2022.58},
  annote =	{Keywords: Contention Resolution, Secretary Problems, Matroids}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.37
Delegated Stochastic Probing

Authors: Curtis Bechtel and Shaddin Dughmi

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

Abstract
Delegation covers a broad class of problems in which a principal doesn't have the resources or expertise necessary to complete a task by themselves, so they delegate the task to an agent whose interests may not be aligned with their own. Stochastic probing describes problems in which we are tasked with maximizing expected utility by "probing" known distributions for acceptable solutions subject to certain constraints. In this work, we combine the concepts of delegation and stochastic probing into a single mechanism design framework which we term delegated stochastic probing. We study how much a principal loses by delegating a stochastic probing problem, compared to their utility in the non-delegated solution. Our model and results are heavily inspired by the work of Kleinberg and Kleinberg in "Delegated Search Approximates Efficient Search." Building on their work, we show that there exists a connection between delegated stochastic probing and generalized prophet inequalities, which provides us with constant-factor deterministic mechanisms for a large class of delegated stochastic probing problems. We also explore randomized mechanisms in a simple delegated probing setting, and show that they outperform deterministic mechanisms in some instances but not in the worst case.
Cite as

Curtis Bechtel and Shaddin Dughmi. Delegated Stochastic Probing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bechtel_et_al:LIPIcs.ITCS.2021.37,
  author =	{Bechtel, Curtis and Dughmi, Shaddin},
  title =	{{Delegated Stochastic Probing}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{37:1--37:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.37},
  URN =		{urn:nbn:de:0030-drops-135763},
  doi =		{10.4230/LIPIcs.ITCS.2021.37},
  annote =	{Keywords: Delegation, Mechanism Design, Algorithmic Game Theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.42
The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem

Authors: Shaddin Dughmi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Contention resolution schemes have proven to be a useful and unifying abstraction for a variety of constrained optimization problems, in both offline and online arrival models. Much of prior work restricts attention to product distributions for the input set of elements, and studies contention resolution for increasingly general packing constraints, both offline and online. In this paper, we instead focus on generalizing the input distribution, restricting attention to matroid constraints in both the offline and online random arrival models. In particular, we study contention resolution when the input set is arbitrarily distributed, and may exhibit positive and/or negative correlations between elements. We characterize the distributions for which offline contention resolution is possible, and establish some of their basic closure properties. Our characterization can be interpreted as a distributional generalization of the matroid covering theorem. For the online random arrival model, we show that contention resolution is intimately tied to the secretary problem via two results. First, we show that a competitive algorithm for the matroid secretary problem implies that online contention resolution is essentially as powerful as offline contention resolution for matroids, so long as the algorithm is given the input distribution. Second, we reduce the matroid secretary problem to the design of an online contention resolution scheme of a particular form.
Cite as

Shaddin Dughmi. The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dughmi:LIPIcs.ICALP.2020.42,
  author =	{Dughmi, Shaddin},
  title =	{{The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.42},
  URN =		{urn:nbn:de:0030-drops-124496},
  doi =		{10.4230/LIPIcs.ICALP.2020.42},
  annote =	{Keywords: Contention Resolution, Secretary Problems, Matroids}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.31
Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice

Authors: Shaddin Dughmi, David Kempe, and Ruixin Qiang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
To select a subset of samples or "winners" from a population of candidates, order sampling [Rosén, 1997] and the k-unit Myerson auction [Myerson, 1981] share a common scheme: assign a (random) score to each candidate, then select the k candidates with the highest scores. We study a generalization of both order sampling and Myerson's allocation rule, called winner-selecting dice. The setting for winner-selecting dice is similar to auctions with feasibility constraints: candidates have random types drawn from independent prior distributions, and the winner set must be feasible subject to certain constraints. Dice (distributions over scores) are assigned to each type, and winners are selected to maximize the sum of the dice rolls, subject to the feasibility constraints. We examine the existence of winner-selecting dice that implement prescribed probabilities of winning (i.e., an interim rule) for all types. Our first result shows that when the feasibility constraint is a matroid, then for any feasible interim rule, there always exist winner-selecting dice that implement it. Unfortunately, our proof does not yield an efficient algorithm for constructing the dice. In the special case of a 1-uniform matroid, i.e., only one winner can be selected, we give an efficient algorithm that constructs winner-selecting dice for any feasible interim rule. Furthermore, when the types of the candidates are drawn in an i.i.d. manner and the interim rule is symmetric across candidates, unsurprisingly, an algorithm can efficiently construct symmetric dice that only depend on the type but not the identity of the candidate. One may ask whether we can extend our result to "second-order" interim rules, which not only specify the winning probability of a type, but also the winning probability conditioning on each other candidate's type. We show that our result does not extend, by exhibiting an instance of Bayesian persuasion whose optimal scheme is equivalent to a second-order interim rule, but which does not admit any dice-based implementation.
Cite as

Shaddin Dughmi, David Kempe, and Ruixin Qiang. Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ITCS.2019.31,
  author =	{Dughmi, Shaddin and Kempe, David and Qiang, Ruixin},
  title =	{{Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.31},
  URN =		{urn:nbn:de:0030-drops-101248},
  doi =		{10.4230/LIPIcs.ITCS.2019.31},
  annote =	{Keywords: Interim rule, order sampling, virtual value function, Border's theorem}
}
  • Refine by Author
  • 5 Dughmi, Shaddin
  • 1 Babichenko, Yakov
  • 1 Bechtel, Curtis
  • 1 Kalayci, Yusuf Hakan
  • 1 Kempe, David
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 2 Contention Resolution
  • 2 Matroids
  • 2 Secretary Problems
  • 1 Algorithmic Game Theory
  • 1 Algorithmic game theory
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2022
  • 1 2019
  • 1 2020
  • 1 2021
  • 1 2023

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 Imprint Privacy Contact