8 Search Results for "Oren, Sigal"


Document
Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

Authors: Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg

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


Abstract
Roughgarden [Roughgarden, 2020] initiates the study of Transaction Fee Mechanisms (TFMs), and posits that the on-chain game of a "good" TFM should be on-chain simple (OnC-S), i.e., incentive compatible for both the users and the miner. Recent work of Ganesh, Thomas an Weinberg [Ganesh et al., 2024] posit that they should additionally be Off-Chain Influence-Proof (OffC-IP), which means that the miner cannot achieve any additional revenue by separately conducting an off-chain auction to determine on-chain inclusion. They observe that a cryptographic second-price auction satisfies both properties, but leave open the question of whether other mechanisms (such as those not dependent on cryptography) satisfy these properties. In this paper, we characterize OffC-IP TFMs: They are those satisfying a burn identity relating the burn rule to the allocation rule. In particular, we show that auction is OffC-IP if and only if its (induced direct-revelation) allocation rule X̄(⋅) and burn rule B̅(⋅) (both of which take as input users' values v₁, … , v_n) are truthful when viewing (X̄(⋅), B̅(⋅)) as the allocation and pricing rule of a multi-item auction for a single additive buyer with values (φ(v₁),…, φ(v_n)) equal to the users' virtual values. Building on this burn identity, we characterize OffC-IP and OnC-S TFMs that are deterministic and do not use cryptography: They are posted-price mechanisms with specially-tuned burns. As a corollary, we show that such TFMs can only exist with infinite supply and prior-dependence. However, we show that for randomized TFMs, there are additional OnC-S and OffC-IP auctions that do not use cryptography (even when there is {finite} supply, under prior-dependence with a bounded prior distribution). Holistically, our results show that while OffC-IP is a fairly stringent requirement, families of OffC-IP mechanisms can be found for a variety of settings.

Cite as

Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg. Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 65:1-65:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ITCS.2026.65,
  author =	{Ganesh, Aadityan and Thomas, Clayton and Weinberg, S. Matthew},
  title =	{{Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{65:1--65:23},
  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.65},
  URN =		{urn:nbn:de:0030-drops-253527},
  doi =		{10.4230/LIPIcs.ITCS.2026.65},
  annote =	{Keywords: Transaction Fee Mechanism Design, Off-Chain Influence Proofness, Blockchain, Decentralized Finance, Simple Auctions}
}
Document
APPROX
Optimal Competitive Ratio for Optimization Problems with Congestion Effects

Authors: Miriam Fischer, Dario Paccagnan, and Cosimo Vinci

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


Abstract
In this work we study online optimization problems with congestion effects. These are problems where tasks arrive online and a decision maker is required to allocate them on the fly to available resources in order to minimize the cost suffered, which grows with the amount of resources used. This class of problems corresponds to the online counterpart of well-known studied problems, including optimization problems with diseconomies of scale [Konstantin Makarychev and Maxim Sviridenko, 2018], minimum cost in congestion games [Gairing and Paccagnan, 2023], and load balancing problems [Baruch Awerbuch et al., 1995]. Within this setting, our work settles the problem of designing online algorithms with optimal competitive ratio, i.e., algorithms whose incurred cost is as close as possible to that of an oracle with complete knowledge of the future instance ahead of time. We provide three contributions underpinning this result. First, we show that no online algorithm can achieve a competitive ratio below a given factor depending solely on the resource costs. Second, we show that, when guided by carefully modified cost functions, the greedy algorithm achieves a competitive ratio matching this lower bound and thus is optimal. Finally, we show how to compute such modified cost functions in polynomial time.

Cite as

Miriam Fischer, Dario Paccagnan, and Cosimo Vinci. Optimal Competitive Ratio for Optimization Problems with Congestion Effects. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.APPROX/RANDOM.2025.9,
  author =	{Fischer, Miriam and Paccagnan, Dario and Vinci, Cosimo},
  title =	{{Optimal Competitive Ratio for Optimization Problems with Congestion Effects}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{9:1--9:24},
  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.9},
  URN =		{urn:nbn:de:0030-drops-243754},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  annote =	{Keywords: Online Algorithms, Competitive Ratio, Algorithmic Game Theory, Greedy Algorithms, Congestion Games}
}
Document
OWA for Bipartite Assignments

Authors: Jabari Hastings, Sigal Oren, and Omer Reingold

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)


Abstract
In resource allocation problems, a central planner often strives to have a fair assignment. A challenge they might face, however, is that there are several objectives that could be argued to be fair, such as the max-min and maximum social welfare. In this work, we study bipartite assignment problems involving the optimization of a class of functions that is sensitive to the relative utilities derived by individuals in allocation and captures these traditional objectives. We introduce and study a subclass of evaluation functions that targets the average welfare attained within some interval of the economic ladder (e.g., the bottom 10%, middle 50%, or top 80%). We provide an efficient algorithm that can be used to optimize the welfare for an arbitrary interval and also show how the approach can be used to approximate more general evaluation functions. We also study a subclass of evaluation functions consisting of the "fair" ordered weighted averages (OWA) introduced by Lesca et al. (Algorithmica 2019), which are most sensitive to the utilities received by the worst-off individuals. We provide a simple proof that optimizing this objective belongs to the class XP.

Cite as

Jabari Hastings, Sigal Oren, and Omer Reingold. OWA for Bipartite Assignments. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{hastings_et_al:LIPIcs.FORC.2025.21,
  author =	{Hastings, Jabari and Oren, Sigal and Reingold, Omer},
  title =	{{OWA for Bipartite Assignments}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.21},
  URN =		{urn:nbn:de:0030-drops-231482},
  doi =		{10.4230/LIPIcs.FORC.2025.21},
  annote =	{Keywords: fairness, matchings, approximation algorithms}
}
Document
Quantum Communication Complexity of Classical Auctions

Authors: Aviad Rubinstein and Zixin Zhou

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


Abstract
We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the buyer and the seller. Specifically, we ask whether using quantum communication can be more efficient than classical communication. We have two sets of results, revealing a surprisingly rich landscape - which looks quite different from both quantum communication in non-strategic parties, and classical communication in mechanism design. We first study the expected communication complexity of approximately optimal auctions. We give quantum auction protocols for buyers with unit-demand or combinatorial valuations that obtain an arbitrarily good approximation of the optimal revenue while running in exponentially more efficient communication compared to classical approximately optimal auctions. However, these auctions come with the caveat that they may require the seller to charge exponentially large payments from a deviating buyer. We show that this caveat is necessary - we give an exponential lower bound on the product of the expected quantum communication and the maximum payment. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting: additive buyer’s valuations over two items. We show the following separations: - There exists a prior where the optimal classical auction protocol requires infinitely many bits, but a one-way message of 1 qubit and 2 classical bits suffices. - There exists a prior where no finite one-way quantum auction protocol can obtain the optimal revenue. However, there is a barely-interactive revenue-optimal quantum auction protocol with the following simple structure: the seller prepares a pair of qubits in the EPR state, sends one of them to the buyer, and then the buyer sends 1 qubit and 2 classical bits. - There exists a prior where no multi-round quantum auction protocol with a finite bound on communication complexity can obtain the optimal revenue.

Cite as

Aviad Rubinstein and Zixin Zhou. Quantum Communication Complexity of Classical Auctions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 84:1-84:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2025.84,
  author =	{Rubinstein, Aviad and Zhou, Zixin},
  title =	{{Quantum Communication Complexity of Classical Auctions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{84:1--84:27},
  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.84},
  URN =		{urn:nbn:de:0030-drops-227124},
  doi =		{10.4230/LIPIcs.ITCS.2025.84},
  annote =	{Keywords: Mechanism design, Communication complexity, Quantum computing}
}
Document
Track A: Algorithms, Complexity and Games
Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games

Authors: Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand, and Giovanna Varricchio

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger’s Hiking Problem": Consider a group of n people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between 1 and n. Is it possible to efficiently assign the n people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an O(n⁵) time algorithm for Woeginger’s Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games.

Cite as

Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand, and Giovanna Varricchio. Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.ICALP.2024.48,
  author =	{Constantinescu, Andrei and Lenzner, Pascal and Reiffenh\"{a}user, Rebecca and Schmand, Daniel and Varricchio, Giovanna},
  title =	{{Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.48},
  URN =		{urn:nbn:de:0030-drops-201910},
  doi =		{10.4230/LIPIcs.ICALP.2024.48},
  annote =	{Keywords: Algorithmic Game Theory, Dynamic Programming, Anonymous Hedonic Games, Single-Peaked Preferences, Social Optimum, Wonderful Partitions}
}
Document
Track A: Algorithms, Complexity and Games
A Characterization of Complexity in Public Goods Games

Authors: Matan Gilboa

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We complete the characterization of the computational complexity of equilibrium in public goods games on graphs. In this model, each vertex represents an agent deciding whether to produce a public good, with utility defined by a "best-response pattern" determining the best response to any number of productive neighbors. We prove that the equilibrium problem is NP-complete for every finite non-monotone best-response pattern. This answers the open problem of [Gilboa and Nisan, 2022], and completes the answer to a question raised by [Papadimitriou and Peng, 2021], for all finite best-response patterns.

Cite as

Matan Gilboa. A Characterization of Complexity in Public Goods Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{gilboa:LIPIcs.ICALP.2024.73,
  author =	{Gilboa, Matan},
  title =	{{A Characterization of Complexity in Public Goods Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{73:1--73:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.73},
  URN =		{urn:nbn:de:0030-drops-202164},
  doi =		{10.4230/LIPIcs.ICALP.2024.73},
  annote =	{Keywords: Nash Equilibrium, Public Goods, Computational Complexity}
}
Document
Computational Social Dynamics (Dagstuhl Seminar 22452)

Authors: Martin Hoefer, Sigal Oren, Roger Wattenhofer, and Giovanna Varricchio

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)


Abstract
This report documents the program and outcomes of Dagstuhl Seminar 22452 "Computational Social Dynamics". The seminar addressed social and dynamic problems in the field of algorithmic game theory, and their implications in numerous applications, such as fair division, financial networks, or behavioral game theory. We summarize organizational aspects of the seminar, the talk abstracts, and the problems that were discussed in the open problem sessions.

Cite as

Martin Hoefer, Sigal Oren, Roger Wattenhofer, and Giovanna Varricchio. Computational Social Dynamics (Dagstuhl Seminar 22452). In Dagstuhl Reports, Volume 12, Issue 11, pp. 28-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{hoefer_et_al:DagRep.12.11.28,
  author =	{Hoefer, Martin and Oren, Sigal and Wattenhofer, Roger and Varricchio, Giovanna},
  title =	{{Computational Social Dynamics (Dagstuhl Seminar 22452)}},
  pages =	{28--44},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Hoefer, Martin and Oren, Sigal and Wattenhofer, Roger and Varricchio, Giovanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.28},
  URN =		{urn:nbn:de:0030-drops-178346},
  doi =		{10.4230/DagRep.12.11.28},
  annote =	{Keywords: algorithmic game theory, behavioral economics, fair division, financial networks, social networks}
}
Document
Mechanism Design with Moral Bidders

Authors: Shahar Dobzinski and Sigal Oren

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


Abstract
A rapidly growing literature on lying in behavioral economics and psychology shows that individuals often do not lie even when lying maximizes their utility. In this work, we attempt to incorporate these findings into the theory of mechanism design. We consider players that have a preference for truth-telling and will only lie if their benefit from lying is sufficiently larger than the loss of the others. To accommodate such players, we introduce α-moral mechanisms, in which the gain of a player from misreporting his true value, comparing to truth-telling, is at most α times the loss that the others incur due to misreporting. Note that a 0-moral mechanism is a truthful mechanism. We develop a theory of moral mechanisms in the canonical setting of single-item auctions within the "reasonable" range of α, 0 ≤ α ≤ 1. We identify similarities and disparities to the standard theory of truthful mechanisms. In particular, we show that the allocation function does not uniquely determine the payments and is unlikely to admit a simple characterization. In contrast, recall that monotonicity characterizes the allocation function of truthful mechanisms. Our main technical effort is invested in determining whether the auctioneer can exploit the preference for truth-telling of the players to extract more revenue comparing to truthful mechanisms. We show that the auctioneer can indeed extract more revenue when the values of the players are correlated, even when there are only two players. However, we show that truthful mechanisms are revenue-maximizing even among moral ones when the values of the players are independently drawn from certain identical distributions (e.g., the uniform and exponential distributions). A by-product of our proof that optimal moral mechanisms are truthful is an alternative proof to Myerson’s optimal truthful mechanism characterization in the settings that we consider. We flesh out this approach by providing an alternative proof that does not involve moral mechanisms to Myerson’s characterization of optimal truthful mechanisms to all settings in which the values are independently drawn from regular distributions (not necessarily identical).

Cite as

Shahar Dobzinski and Sigal Oren. Mechanism Design with Moral Bidders. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dobzinski_et_al:LIPIcs.ITCS.2022.55,
  author =	{Dobzinski, Shahar and Oren, Sigal},
  title =	{{Mechanism Design with Moral Bidders}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{55:1--55:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.55},
  URN =		{urn:nbn:de:0030-drops-156513},
  doi =		{10.4230/LIPIcs.ITCS.2022.55},
  annote =	{Keywords: Mechanism Design, Cognitive Biases, Revenue Maximization}
}
  • Refine by Type
  • 8 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 2 2024
  • 1 2023
  • 1 2022

  • Refine by Author
  • 3 Oren, Sigal
  • 2 Varricchio, Giovanna
  • 1 Constantinescu, Andrei
  • 1 Dobzinski, Shahar
  • 1 Fischer, Miriam
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 3 Theory of computation → Algorithmic game theory
  • 3 Theory of computation → Algorithmic game theory and mechanism design
  • 2 Theory of computation → Algorithmic mechanism design
  • 1 Applied computing → Online auctions
  • 1 Information systems → Social networks
  • Show More...

  • Refine by Keyword
  • 2 Algorithmic Game Theory
  • 1 Anonymous Hedonic Games
  • 1 Blockchain
  • 1 Cognitive Biases
  • 1 Communication complexity
  • 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