A simple and approximately optimal mechanism for an additive buyer

M Babaioff, N Immorlica, B Lucier… - Journal of the ACM …, 2020 - dl.acm.org
We consider a monopolist seller with n heterogeneous items, facing a single buyer. The
buyer has a value for each item drawn independently according to (non-identical) …

Approximately efficient bilateral trade

Y Deng, J Mao, B Sivan, K Wang - Proceedings of the 54th Annual ACM …, 2022 - dl.acm.org
We study bilateral trade between two strategic agents. The celebrated result of Myerson and
Satterthwaite states that in general, no incentive-compatible, individually rational and weakly …

The distortion of binomial voting defies expectation

YA Gonczarowski, G Kehne… - Advances in …, 2024 - proceedings.neurips.cc
In computational social choice, the distortion of a voting rule quantifies the degree to which
the rule overcomes limited preference information to select a socially desirable outcome …

Efficient two-sided markets with limited information

P Dütting, F Fusco, P Lazos, S Leonardi… - Proceedings of the 53rd …, 2021 - dl.acm.org
A celebrated impossibility result by Myerson and Satterthwaite (1983) shows that any truthful
mechanism for two-sided markets that maximizes social welfare must run a deficit, resulting …

Approximately efficient two-sided combinatorial auctions

R Colini-Baldeschi, PW Goldberg, B Keijzer… - ACM Transactions on …, 2020 - dl.acm.org
We develop and extend a line of recent work on the design of mechanisms for two-sided
markets. The markets we consider consist of buyers and sellers of a number of items, and …

Fixed-price approximations in bilateral trade

ZY Kang, F Pernice, J Vondrák - Proceedings of the 2022 Annual ACM-SIAM …, 2022 - SIAM
We consider the bilateral trade problem, in which two agents trade a single indivisible item. It
is known that the only dominant-strategy truthful mechanism is the fixed-price mechanism …

Mechanism Design for ZK-Rollup Prover Markets

W Wang, L Zhou, A Yaish, F Zhang, B Fisch… - arXiv preprint arXiv …, 2024 - arxiv.org
In ZK-Rollups, provers spend significant computational resources to generate validity proofs.
Their costs should be compensated properly, so a sustainable prover market can form over …

Dynamic double auctions: Toward first best

SR Balseiro, V Mirrokni, RP Leme… - Operations …, 2022 - pubsonline.informs.org
We study the problem of designing dynamic double auctions for two-sided markets in which
a platform intermediates the trade between one seller offering independent items to multiple …

Bulow-klemperer-style results for welfare maximization in two-sided markets

M Babaioff, K Goldner, YA Gonczarowski - Proceedings of the Fourteenth …, 2020 - SIAM
We consider the problem of welfare (and gains-from-trade) maximization in two-sided
markets using simple mechanisms that are prior-independent. The seminal impossibility …

Interactive communication in bilateral trade

J Mao, RP Leme, K Wang - arXiv preprint arXiv:2106.02150, 2021 - arxiv.org
We define a model of interactive communication where two agents with private types can
exchange information before a game is played. The model contains Bayesian persuasion as …