Multi-Unit Bilateral Trade

Matthias Gerstgrasser; Paul W. Goldberg; Bart de Keijzer; Philip Lazos; Alexander Skopalik

Multi-Unit Bilateral Trade

Matthias Gerstgrasser
, Paul W. Goldberg
, Bart de Keijzer
, Philip Lazos
, Alexander Skopalik

Discrete Mathematics and Mathematical Programming

Research output: Working paper

8 Citations (Scopus)

101 Downloads (Pure)

Abstract

We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular.
Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e) approximation mechanism, matching the best known bounds for the single-item setting.

Original language	English
Publisher	ArXiv.org
Number of pages	20
Publication status	Published - 2019

Access to Document

Gerstgrasser2018multi-unitFinal published version, 312 KB

https://arxiv.org/abs/1811.05130v1

Multi-Unit Bilateral Trade
Gerstgrasser, M., Goldberg, P. W., Keijzer, B. D., Lazos, P. & Skopalik, A., 17 Jul 2019, The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI, p. 1973-1980 8 p.
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
110 Downloads (Pure)

Cite this

@techreport{f52a54f372f14ad9aa269e1f86483e74,

title = "Multi-Unit Bilateral Trade",

abstract = "We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e) approximation mechanism, matching the best known bounds for the single-item setting.",

author = "Matthias Gerstgrasser and Goldberg, \{Paul W.\} and \{de Keijzer\}, Bart and Philip Lazos and Alexander Skopalik",

year = "2019",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Multi-Unit Bilateral Trade

AU - Gerstgrasser, Matthias

AU - Goldberg, Paul W.

AU - de Keijzer, Bart

AU - Lazos, Philip

AU - Skopalik, Alexander

PY - 2019

Y1 - 2019

N2 - We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e) approximation mechanism, matching the best known bounds for the single-item setting.

AB - We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1-e) approximation mechanism, matching the best known bounds for the single-item setting.

M3 - Working paper

BT - Multi-Unit Bilateral Trade

PB - ArXiv.org

ER -

Multi-Unit Bilateral Trade

Abstract

Access to Document

Fingerprint

Research output

Multi-Unit Bilateral Trade

Cite this