Top

Published in:

2021 | OriginalPaper | Chapter

Ascending-Price Mechanism for General Multi-sided Markets

Authors : Dvir Gilor, Rica Gonen, Erel Segal-Halevi

Published in: Multi-Agent Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present an ascending-price mechanism for a multi-sided market with a variety of participants, such as manufacturers, logistics agents, insurance providers, and assemblers. Each deal in the market may consist of a combination of agents from separate categories, and different such combinations are simultaneously allowed. This flexibility lets multiple intersecting markets be resolved as a single global market. Our mechanism is obviously-truthful, strongly budget-balanced, individually rational, and attains almost the optimal gain-from-trade when the market is sufficiently large. We evaluate the performance of the suggested mechanism with experiments on real stock market data and synthetically produced data.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Governing Black-Box Agents in Competitive Multi-Agent Systems

We define the categories that receives payments as negative values so we can sum the deal values to calculate the gain from trade.

In the terminology of Li [12], a mechanism is OT if and only if, for all agents, replying truthfully to all queries is an obviously-dominant strategy. Note that Li [12] defines games with actions and not with queries, so in his model, the notion of truthfulness is irrelevant. He defines a mechanism as obviously strategy-proof if and only if it has an equilibrium in obviously-dominant strategies..

This simplifies Algorithm 2.

In all our examples, the opposite is also true: each path corresponds to a recipe. But it is not necessary to make this assumption explicitly: if some path does not correspond to a recipe in R, then the category corresponding to the leaf of that path can be removed from the market, since it does not participate in any other recipe. This can be repeated until all remaining paths correspond to recipes.

Note that the tree structure is not unique. For example, if R contains a single recipe, then every category can be considered as the root. For our purposes, it is sufficient to fix a single tree and a single root, and consider them as the input to the algorithms (instead of the set R).

The code used for the experiments and the experiment results are available at https://github.com/dvirg/auctions.

Babaioff, M., Nisan, N.: Concurrent auctions across the supply chain. J. Artif. Intell. Res. (JAIR) 21, 595–629 (2004). https://doi.org/10.1613/jair.1316MathSciNetCrossRefMATH

Babaioff, M., Walsh, W.E.: Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Decis. Support Syst. 39(1), 123–149 (2005). https://doi.org/10.1016/j.dss.2004.08.008. ISSN 01679236

Blumrosen, L., Mizrahi, Y.: Approximating gains-from-trade in bilateral trading. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 400–413. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-54110-4_28CrossRef

Colini-Baldeschi, R., Goldberg, P.W., de Keijzer, B., Leonardi, S., Roughgarden, T., Turchetta, S.: Approximately efficient two-sided combinatorial auctions. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 591–608. ACM (2017)

Feldman, M., Gonen, R.: Removal and threshold pricing: truthful two-sided markets with multi-dimensional participants. In: Deng, X. (ed.) SAGT 2018. LNCS, vol. 11059, pp. 163–175. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99660-8_15CrossRef

Feldman, M., Frim, G., Gonen, R.: Multi-sided advertising markets: dynamic mechanisms and incremental user compensations. In: Bushnell, L., Poovendran, R., Başar, T. (eds.) GameSec 2018. LNCS, vol. 11199, pp. 227–247. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01554-1_13CrossRef

Gerstgrasser, M., Goldberg, P.W., de Keijzer, B., Lazos, P., Skopalik, A.: Multi-unit bilateral trade. In: Proceedings of the AAAI 2019, vol. 33, pp. 1973–1980 (2019). arXiv preprint arXiv:1811.05130

Gilor, D., Gonen, R., Segal-Halevi, E.: Ascending-price mechanism for general multi-sided markets. In: EUMAS (2021). The full version of the paper is at https://bit.ly/3oY1dZO

Gonen, M., Gonen, R., Elan, P.: Generalized trade reduction mechanisms. In: Proceedings of EC 2007, pp. 20–29 (2007)

10.

Gonen, R., Egri, O.: COMBIMA: truthful, budget maintaining, dynamic combinatorial market. Auton. Agents Multi Agent Syst. 34(1), 14 (2020)CrossRef

11.

Gonen, R., Segal-Halevi, E.: Strongly budget balanced auctions for multi-sided markets. In: AAAI, pp. 1998–2005 (2020)

12.

Li, S.: Obviously strategy-proof mechanisms. Am. Econ. Rev. 107(11), 3257–3287 (2017)CrossRef

13.

McAfee, R.P.: A dominant strategy double auction. J. Econ. Theory 56(2), 434–450 (1992). ISSN 00220531MathSciNetCrossRef

14.

McAfee, R.P.: The gains from trade under fixed price mechanisms. Appl. Econ. Res. Bull. 1, 1–10 (2008)

15.

Myerson, R.B., Satterthwaite, M.A.: Efficient mechanisms for bilateral trading. J. Econ. Theory 29(2), 265–281 (1983). ISSN 00220531MathSciNetCrossRef

16.

Nisan, N.: Introduction to mechanism design (for computer scientists). In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, pp. 209–241. Cambridge University Press (2007). ISBN 978-0521872829

17.

Segal-Halevi, E., Hassidim, A., Aumann, Y.: SBBA: a strongly-budget-balanced double-auction mechanism. In: Gairing, M., Savani, R. (eds.) SAGT 2016. LNCS, vol. 9928, pp. 260–272. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53354-3_21CrossRef

18.

Segal-Halevi, E., Hassidim, A., Aumann, Y.: MUDA: a truthful multi-unit double-auction mechanism. In: Proceedings of AAAI 2018. AAAI Press, February 2018. arXiv preprint arXiv:1712.06848

19.

Segal-Halevi, E., Hassidim, A., Aumann, Y.: Double auctions in markets for multiple kinds of goods. In: Proceedings of IJCAI 2018. AAAI Press, July 2018. Previous name: “MIDA: A Multi Item-type Double-Auction Mechanism”. arXiv preprint arXiv:1604.06210

20.

Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finan. 16(1), 8–37 (1961)MathSciNetCrossRef

Title: Ascending-Price Mechanism for General Multi-sided Markets
Authors: Dvir Gilor
Rica Gonen
Erel Segal-Halevi
Publisher: Springer International Publishing
Book: Multi-Agent Systems
Print ISBN: 978-3-030-82253-8

Electronic ISBN: 978-3-030-82254-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-82254-5_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner