nach oben

Autonomous Agents and Multi-Agent Systems

Erschienen in:

01.04.2020

COMBIMA: truthful, budget maintaining, dynamic combinatorial market

verfasst von: Rica Gonen, Ozi Egri

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Current interest in two-sided markets is motivated by examples of successful practical applications of market mechanisms in supply chain markets, online advertising exchanges, and pollution-rights markets. Many of these examples require markets where agents arrive dynamically and can trade multiple commodities. However, the known literature largely focuses on settings with single-commodity unit demand. We present, prove and evaluate a general solution that matches agents in a dynamic, two-sided combinatorial market. Multiple commodities, each with multiple units, are bought and sold in different bundles by agents that arrive over time. Our mechanism, COMBIMA, provides the first dynamic two-sided combinatorial market that allows truthful and individually-rational behavior for all agents, keeps the market budget balanced and approximates social welfare efficiency. We experimentally examine and compare the allocative efficiency of COMBIMA with respect to our proven theoretical bounds and with respect to all known (dynamic and non-dynamic) social-welfare maximizing two-sided markets under variety of distributions of bids, market demands and market size. COMBIMA performs well by all benchmarks and in many cases improves on previous mechanisms.

Vorheriger Artikel Applying Max-sum to asymmetric distributed constraint optimization problems

Nächster Artikel Privacy sensitive environment re-decomposition for junction tree agent organization construction

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

One exception in the literature is a recent work by Feldman et al. [14] that has a single commodity with multiple demand however their market is mediated.

Bredin et al. [6] and Wurman et al. [30] did not provide an approximation guaranty.

Except for the work by Bredin et al. [6] which assumed agents with bounded patience.

If prices increase too quickly then early on the algorithm may encounter buyers with attractive bids who nevertheless cannot afford their desired bundle, i.e., cannot be allocated despite the fact that the allocation has not accumulated high enough SWF to guarantee the desirable approximation bound.

The only previous work on dynamic markets that does not assume a similar assumption on the valuation range, is the work by Bredin et al. [6]. However [6]’s work assumes an alternative assumption: agents with bounded patience, otherwise no reasonable efficiency can be achieved.

Note that the IR property is not affected by the later payments since if units of commodities in \(s_i\) are not sold in the market by its closing time, seller i is left to possess them. Also note that similarly to [6] we could have changed our algorithm to pay the arriving selling agents instantaneously and have the market “hold” the commodities until bought, however such approach will lead to market deficits during the market run as occurs in [6]’s market.

matroid constraints—A matroid is a pair \(({\mathcal {Q}},{\mathcal {Z}})\) where \({\mathcal {Q}}\) is a finite set, \({\mathcal {Z}}\) is a family of subsets of \({\mathcal {Q}}\) and \({\mathcal {Z}}\) has the following properties: 1. \(\emptyset \in {\mathcal {Z}}\), 2. \(\forall Z' \subset Z \subseteq {\mathcal {Q}}\) if \(Z\in {\mathcal {Z}}\) then \(Z'\in {\mathcal {Z}}\), 3. if \(G,R \in {\mathcal {Z}}\) and \(|G|>|R|\) then \(\exists g\in G\) such that \(R \cup \{g\}\in {\mathcal {Z}}\).

Subadditive—roughly speaking, the value of bundle A plus the value of bundle B is greater than the value of their union.

Additive—roughly speaking, the value of bundle A is the sum of the values of the single commodity bundles composing it.

Except for small markets with high theta value, in those, in order to achieve the desired theta , we allow number of sellers \(\,=\, \)number of buyers, while keeping number of each commodity units at \(5^7\).

We say that a market is strong budget balanced (SBB) if the sum of the prices paid by the buying agents is equal to the sum of the prices paid to the selling agents

[6] and [30] did not provide an approximation guaranty.

Bartal, Y., Gonen, R., & Nisan, N. (2003). Incentive compatible multi unit combinatorial auctions. In TARK, (pp. 72–87).

Blum, A., Sandholm, T., & Zinkevich, M. (2002). Online algorithms for market clearing. In SODA (pp. 971–980).

Blumrosen, L., & Dobzinski, S. (2014). Reallocation mechanisms. In EC (pp. 617–640).

Blumrosen, L., & Holenstein, T. (2008). Posted prices vs. negotiations: An asymptotic analysis. In EC.

Blumrosen, L., & Nisan, N. (2009). On the computational power of demand queries. SIAM Journal on Computing, 39(4), 1372–1391.MathSciNetCrossRef

Bredin, J., Parkes, D., & Duong, Q. (2007). Chain: A dynamic double auction framework for matching patient agents. Journal of Artificial Intelligence Research, 30, 133–179.MathSciNetCrossRef

Buchbinder, N., & Gonen, R. (2015). Incentive compatible mulit-unit combinatorial auctions: A primal dual approach. Algorithmica, 72(1), 167–190.MathSciNetCrossRef

Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 2, 17–33.CrossRef

Colini-Baldeschi, R., Goldberg, P., de Keijzer, B., Leonardi, S., Roughgarden, T., & Turchetta, S. (2017). Approximately efficient two-sided combinatorial auctions. In EC (pp. 591–608).

10.

Colini-Baldeschi, R., de Keijzer, B., Leonardi, S., & Turchetta, S. (2016). Approximately efficient double auctions with strong budget balance. In SODA (pp. 1424–1443).

11.

Cramton, P., Shoham, Y., & Steinberg, R. (2006). Combinatorial auctions. Cambridge: MIT Press.MATH

12.

de Vries, S., Schummer, J., & Vohra, R. (2007). On ascending vickery auctions for heterogeneons objects. Journal of Economic Theory, 132, 95–118.MathSciNetCrossRef

13.

Dolgov, D., & Durfee, E. (2005). Computationally-efficient combinatorial auctions for resource allocation in weakly- coupled MDPS. In AAMAS (pp. 657–664).

14.

Feldman, M., & Frim, G., Gonen, R. (2018). Multi-sided advertising markets: Dynamic mechanisms and incremental user compensations. In GameSec.

15.

Gerkey, B. P., & Mataric, M. J. (2002). Sold!: Auction methods for multi robot coordination. IEEE Transactions on Robotics and Automation, 18, 758–768.CrossRef

16.

Gonen, R., & Egri, O. (2017). Dycom: A dynamic truthful budget balanced double-sided combinatorial market. In AAMAS.

17.

Groves, T. (1973). Incentives in teams. Econometrica, 41, 617–631.MathSciNetCrossRef

18.

Guo, M., Markakis, E., Apt, K. R., & Conitzer, V. (2013). Undominated groves mechanisms. Journal of Artificial Intelligence Research (JAIR), 46, 129–163.MathSciNetCrossRef

19.

McAfee, R. P. (1992). Dominant strategy double auction. Journal of Economic Theory, 56, 434–450.MathSciNetCrossRef

20.

Mishra, D., & Parkes, D. C. (2007). Ascending price Vickery auctions for general valuations. Journal of Economic Theory, 132(1), 335–366.MathSciNetCrossRef

21.

Myerson, R. B., & Satterthwaite, M. A. (1983). Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29, 265–281.MathSciNetCrossRef

22.

Parkes, D. C., & Unger, L. H. (2000). Iterative combinatorial auctions:theory and practice. In AAAI (pp. 74–81).

23.

Rassenti, S. J., Smith, V. L., & Bulfin, R. (1982). A combinatorial auction mechanism for airport time slot allocation. The Bell Journal of Economics, 13(2), 402–417.CrossRef

24.

Sandholm, T., & Gilpin, A. (2006). Sequences of take-it-or-leave-it offers: Near-optimal auctions without full valuation revelation. In AAMAS (pp. 73–91).

25.

Song, J., & Regan, A. (2003). Combinatorial auctions for transportation service procurement: The carrier perspective. Transportation Research Record: Journal of the Transportation Research Board, 1833, 40–46.CrossRef

26.

Stonebraker, M., Devine, R., Kornacker, M., Litwin, W., Pfeffer, A., Sah, A., & Staelin, C. (1994). An economic paradigm for query processing and data migration in mariposa. In PDIS (pp. 58–67).

27.

Tovey, C., Lagoudakis, M., & Koenig, S. (2005). The generation of bidding rules for auction-based robot coordination, vol. In Multi-Robot Systems. From Swarms to Intelligent Automata Volume III. Springer.

28.

Vaze, R., & Coupechoux, M. (2016). Online budgeted truthful matching. SIGMETRICS Performance Evaluation Review, 44(3), 3–6.CrossRef

29.

Vickrey, W. (1961). Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16, 8–37.MathSciNetCrossRef

30.

Wurman, P., Walsh, W., & Wellman, M. (1998). Flexible double auctions for electronic commerce: Theory and implementation. Decision Support Systems, 24, 17–27.CrossRef

Titel: COMBIMA: truthful, budget maintaining, dynamic combinatorial market
verfasst von: Rica Gonen
Ozi Egri
Publikationsdatum: 01.04.2020
Verlag: Springer US
Erschienen in: Autonomous Agents and Multi-Agent Systems / Ausgabe 1/2020
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI: https://doi.org/10.1007/s10458-019-09437-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2020

Computing and testing Pareto optimal committees

Stable outcomes in modified fractional hedonic games

Gehrlein stability in committee selection: parameterized hardness and algorithms

Competitive equilibrium for almost all incomes: existence and fairness

Fast core pricing algorithms for path auction

The complexity of bribery and control in group identification

Premium Partner