Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Interdependent Public Projects
Competitive Revenue Extraction from Time-Discounted Transactions
"Competitive Revenue Extraction from Time-Discounted Transactions" - Yotam Gafni
Abstract: Decentralized cryptocurrencies rely on aligning the incentives of users and miners to operate correctly and offer a high QoS to users.
Recent literature studies the mechanism design problem of the auction serving as a cryptocurrency's Transaction Fee Mechanism (TFM).
We find that a non-myopic modeling of miners falls close to the well-known problem of online buffer management for packet switching. The main difference is that unlike packets, which are of a fixed size throughout their lifetime, in a financial environment user preferences (and therefore revenue extraction) may be time-dependent. We study the competitive ratio guarantees given a certain discount rate and show how existing methods from packet scheduling, which we call ``the undiscounted case'', perform sub-optimally in the more general discounted setting. Most notably, we find a novel, simple, memoryless, and competitively optimal deterministic algorithm for the semi-myopic case, when the discount factor is up to ~0.770018. We also present a randomized algorithm that achieves better performance than the best possible deterministic algorithm, for any discount rate.
"Interdependent Public Projects" - Divyarthi Mohan
Abstract: In the interdependent values (IDV) model introduced by Milgrom and Weber [1982], agents have private signals that capture their information about different social alternatives, and the valuation of every agent is a function of all agent signals. While interdependence has been mainly studied for auctions, it is extremely relevant for a large variety of social choice settings, including the canonical setting of public projects. The IDV model is very challenging relative to standard independent private values, and welfare guarantees have been achieved through two alternative conditions known as single-crossing and submodularity over signals (SOS). In either case, the existing theory falls short of solving the public projects setting. Our main impossibility result is that, in contrast to auctions, no universally truthful mechanism performs better for public projects with SOS valuations than choosing a project at random. Our main positive result applies to excludable public projects with SOS, for which we establish a constant factor approximation similar to auctions. Our results suggest that exclusion may be a key tool for achieving welfare guarantees in the IDV model.
Joint work with Avi Cohen, Michal Feldman and Inbal Talgam-Cohen.