Walrasian pricing in multi-unit auctions

Simina Brânzei; Aris Filos-Ratsikas; Peter Bro Miltersen; Yulong Zeng

doi:10.1016/j.artint.2023.103961

Walrasian pricing in multi-unit auctions

Simina Brânzei^*, Aris Filos-Ratsikas, Peter Bro Miltersen, Yulong Zeng

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

Multi-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency.

Original language	English
Article number	103961
Journal	Artificial Intelligence
Volume	322
Number of pages	17
ISSN	0004-3702
DOIs	https://doi.org/10.1016/j.artint.2023.103961
Publication status	Published - Sept 2023

Keywords

Approximation
Mechanism design
Multi-unit auctions
Revenue
Social welfare

Access to Document

10.1016/j.artint.2023.103961

Cite this

@article{90b43506164443ee8d75eee19a7e67fc,

title = "Walrasian pricing in multi-unit auctions",

abstract = "Multi-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency.",

keywords = "Approximation, Mechanism design, Multi-unit auctions, Revenue, Social welfare",

author = "Simina Br{\^a}nzei and Aris Filos-Ratsikas and Miltersen, {Peter Bro} and Yulong Zeng",

year = "2023",

month = sep,

doi = "10.1016/j.artint.2023.103961",

language = "English",

volume = "322",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Walrasian pricing in multi-unit auctions

AU - Brânzei, Simina

AU - Filos-Ratsikas, Aris

AU - Miltersen, Peter Bro

AU - Zeng, Yulong

PY - 2023/9

Y1 - 2023/9

N2 - Multi-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency.

AB - Multi-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency.

KW - Approximation

KW - Mechanism design

KW - Multi-unit auctions

KW - Revenue

KW - Social welfare

UR - http://www.scopus.com/inward/record.url?scp=85162177692&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2023.103961

DO - 10.1016/j.artint.2023.103961

M3 - Journal article

AN - SCOPUS:85162177692

SN - 0004-3702

VL - 322

JO - Artificial Intelligence

JF - Artificial Intelligence

M1 - 103961

ER -

Walrasian pricing in multi-unit auctions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this