2 Search Results for "Bahrani, Maryam"

Document
DOI: 10.4230/LIPIcs.AFT.2023.21
When Bidders Are DAOs

Authors: Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
In a typical decentralized autonomous organization (DAO), people organize themselves into a group that is programmatically managed. DAOs can act as bidders in auctions (with ConstitutionDAO being one notable example), with a DAO’s bid typically treated by the auctioneer as if it had been submitted by an individual, without regard to any details of the internal DAO dynamics. The goal of this paper is to study auctions in which the bidders are DAOs. More precisely, we consider the design of two-level auctions in which the "participants" are groups of bidders rather than individuals. Bidders form DAOs to pool resources, but must then also negotiate the terms by which the DAO’s winnings are shared. We model the outcome of a DAO’s negotiations through an aggregation function (which aggregates DAO members' bids into a single group bid) and a budget-balanced cost-sharing mechanism (that determines DAO members' access to the DAO’s allocation and distributes the aggregate payment demanded from the DAO to its members). DAOs' bids are processed by a direct-revelation mechanism that has no knowledge of the DAO structure (and thus treats each DAO as an individual). Within this framework, we pursue two-level mechanisms that are incentive-compatible (with truthful bidding a dominant strategy for each member of each DAO) and approximately welfare-optimal. We prove that, even in the case of a single-item auction, the DAO dynamics hidden from the outer mechanism preclude incentive-compatible welfare maximization: No matter what the outer mechanism and the cost-sharing mechanisms used by DAOs, the welfare of the resulting two-level mechanism can be a ≈ ln n factor less than the optimal welfare (in the worst case over DAOs and valuation profiles). We complement this lower bound with a natural two-level mechanism that achieves a matching approximate welfare guarantee. This upper bound also extends to multi-item auctions in which individuals have additive valuations. Finally, we show that our positive results cannot be extended much further: Even in multi-item settings in which bidders have unit-demand valuations, truthful two-level mechanisms form a highly restricted class and as a consequence cannot guarantee any non-trivial approximation of the maximum social welfare.
Cite as

Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. When Bidders Are DAOs. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bahrani_et_al:LIPIcs.AFT.2023.21,
  author =	{Bahrani, Maryam and Garimidi, Pranav and Roughgarden, Tim},
  title =	{{When Bidders Are DAOs}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.21},
  URN =		{urn:nbn:de:0030-drops-192108},
  doi =		{10.4230/LIPIcs.AFT.2023.21},
  annote =	{Keywords: Auctions, DAOs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.8
Asynchronous Majority Dynamics in Preferential Attachment Trees

Authors: Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, and S. Matthew Weinberg

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

Abstract
We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability 1/2+δ. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model [Barabási and Albert, 1999], with high probability, the process stabilizes in a correct majority within O(n log n/log log n) rounds. We extend our results to other tree structures, including balanced M-ary trees for any M.
Cite as

Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, and S. Matthew Weinberg. Asynchronous Majority Dynamics in Preferential Attachment Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bahrani_et_al:LIPIcs.ICALP.2020.8,
  author =	{Bahrani, Maryam and Immorlica, Nicole and Mohan, Divyarthi and Weinberg, S. Matthew},
  title =	{{Asynchronous Majority Dynamics in Preferential Attachment Trees}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{8:1--8:14},
  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.8},
  URN =		{urn:nbn:de:0030-drops-124156},
  doi =		{10.4230/LIPIcs.ICALP.2020.8},
  annote =	{Keywords: Opinion Dynamics, Information Cascades, Preferential Attachment, Majority Dynamics, non-Bayesian Asynchronous Learning, Stochastic Processes}
}
  • Refine by Author
  • 2 Bahrani, Maryam
  • 1 Garimidi, Pranav
  • 1 Immorlica, Nicole
  • 1 Mohan, Divyarthi
  • 1 Roughgarden, Tim
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Online auctions
  • 1 Networks → Network dynamics
  • 1 Theory of computation → Algorithmic game theory and mechanism design

  • Refine by Keyword
  • 1 Auctions
  • 1 DAOs
  • 1 Information Cascades
  • 1 Majority Dynamics
  • 1 Opinion Dynamics
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 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