Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Computing Equilibria with Partial Commitment Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Approximating Gains-from-Trade in Bilateral Trading

verfasst von : Liad Blumrosen, Yehonatan Mizrahi

Erschienen in: Web and Internet Economics

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We consider the design of platforms that facilitate trade between a single seller and a single buyer. The most efficient mechanisms for such settings are complex and sometimes even intractable, and we therefore aim to design simple mechanisms that perform approximately well. We devise a mechanism that always guarantees at least 1 / e of the optimal expected gain-from-trade for every set of distributions (assuming monotone hazard rate of the buyer’s distribution). Our main mechanism is extremely simple, and achieves this approximation in Bayes-Nash equilibrium. Moreover, our mechanism approximates the optimal gain-from-trade, which is a strictly harder task than approximating efficiency. Our main impossibility result shows that no Bayes-Nash incentive compatible mechanism can achieve better approximation than 2 / e to the optimal gain from trade. We also bound the power of Bayes-Nash incentive compatible mechanisms for approximating the expected efficiency.

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
Vorheriges Kapitel The Core of the Participatory Budgeting Problem
Nächstes Kapitel Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design
Fußnoten
1
A mechanism is budget balanced if the mechanism does not gain any profit nor requires any subsidies. A mechanism is individually rational if the utility of each player cannot decrease by participating in the mechanism. Formal definitions will be given later in the paper.
 
2
We note that our mechanism satisfies two stronger and desired versions of the above economic properties: it is strongly budget balanced, i.e., the sum of payments is always exactly zero; it is also ex-post individually rational, i.e., agents cannot lose in every instance and not only in expectation.
 
3
Note that the characterization of the “second-best” mechanism by [21] requires that both agents have Myerson-regular distributions, while we require the stronger MHR assumption for the buyer and require nothing for the seller.
 
4
Concavity of the hazard rate is satisfied by some standard distributions (e.g., exponential, Weibull(2,1), etc.), and does not hold for some other distributions (e.g., uniform on [0, 1]).
 
5
We consider the weaker version of interim IR, which makes the proof only harder.
 
6
This follows from \(EFF_M\cdot GFT_{OPT}\ge GFT_M\cdot EFF_{OPT}\) which is equivalent by definition to the inequality \((GFT_M+E[S])\cdot GFT_{OPT}\ge GFT_M\cdot (GFT_{OPT}+E[S])\) that holds by \(GFT_{OPT}\ge GFT_M\).
 
7
Most of the literature assumes a weaker condition, that the \(\varphi \) is non-decreasing. In our paper we often use the inverse function of \(\varphi \), and the notations become much simpler when \(\varphi \) is strictly increasing. Moreover, our main results consider MHR distributions that imply that \(\varphi \) is always strictly increasing.
 
8
We note that \(\overline{\varphi ^{-1}}\left( x\right) \) is defined for every x, even when \(F_b\)’s support is \([\underline{b},\infty )\), since \(\varphi \left( x\right) \) is unbounded from above in that case. This can be seen by noticing that for every \(y\in \mathbb {R}\), choosing \(x>max\{\frac{1}{h\left( \underline{b}\right) }+y+1,\underline{b}\}\) yields \(\varphi \left( x\right) =x-\frac{1}{h\left( x\right) }\ge \frac{1}{h\left( \underline{b}\right) }+y+1-\frac{1}{h\left( \underline{b}\right) }>y\) by the MHR assumption.
 
9
Recall that \(\varphi \) denotes the virtual valuation of the buyer, and the seller use the details of this distribution to determine what price to post.
 
10
This theorem holds for a weaker notion of interim individual rationality (as in [21]); This clearly strengthens the result.
 
Literatur
1.
Ausubel, L., Levin, J., Milgrom, P., Segal, I.: Incentive auction rules option and discussion (2012). Appendix to the FCCs NPRM on Incentive Auctions
2.
Babaioff, M., Immorlica, N., Lucier, B., Weinberg, S.M.: A simple and approximately optimal mechanism for an additive buyer. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 21–30 (2014)
3.
Bhawalkar, K., Roughgarden, T.: Welfare guarantees for combinatorial auctions with item bidding. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 700–709 (2011)
4.
Blumrosen, L., Dobzinski, S.: Reallocation mechanisms. In: The 15th ACM Conference on Economics and Computation, EC 2014, p. 617 (2014)
5.
Blumrosen, L., Dobzinski, S.: (Almost) efficient mechanisms for bilateral trading (2016). Working paper
6.
Blumrosen, L., Holenstein, T.: Posted prices vs. negotiations: an asymptotic analysis. In: ACM Conference on Electronic Commerce (2008)
7.
Blumrosen, L., Nisan, N., Segal, I.: Auctions with severely bounded communications. J. Artif. Intell. Res. 28, 233–266 (2006)MathSciNetMATH
8.
Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 311–320 (2010)
9.
Christodoulou, G., Kovács, A., Schapira, M.: Bayesian combinatorial auctions. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 820–832. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-70575-8_​67 CrossRef
10.
Colini-Baldeschi, R., de Keijzer, B., Leonardi, S., Turchetta, S.: Approximately efficient double auctions with strong budget balance. In: SODA 2016 (2016)
11.
Dhangwatnotai, P., Roughgarden, T., Yan, Q.: Revenue maximization with a single sample. In: The 11th ACM Conference on Electronic Commerce, pp. 129–138 (2010)
12.
Drexl, M., Kleiner, A.: Optimal private good allocation: the case for a balanced budget. Games Econ. Behav. 94, 169–181 (2015)MathSciNetCrossRefMATH
13.
Dutting, P., Roughgarden, T., Talgam-Cohen, I.: Modularity and greed in double auctions. In: EC 2014 (2014)
14.
Fudenberg, D., Mobius, M., Szeidl, A.: Existence of equilibrium in large double auctions. J. Econ. Theory 133(1), 550–567 (2007)MathSciNetCrossRefMATH
15.
Garratt, R., Pycia, M.: Efficient bilateral trade (2015). Working paper
16.
Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: The 10th ACM Conference on Electronic Commerce, EC 2009, pp. 225–234 (2009)
17.
18.
McAfee, P.R.: The gains from trade under fixed price mechanisms. Appl. Econ. Res. Bull. 1, 1–10 (2008)
19.
Milgrom, P., Segal, I.: Deferred-acceptance heuristic auctions (2013). Working paper, Stanford University
20.
21.
22.
Ostrovsky, M., Schwarz, M.: Reserve prices in internet advertising auctions: a field experiment. In: The 12th ACM Conference on Electronic Commerce, pp. 59–60 (2011)
23.
Rustichini, A., Satterthwaite, M.A., Williams, S.R.: Convergence to efficiency in a simple market with incomplete information. Econometrica 62(5), 1041–63 (1994)CrossRefMATH
24.
25.
Syrgkanis, V., Tardos, E.: Composable and efficient mechanisms. In: The 43th Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 211–220 (2013)
26.
Metadaten
Titel
Approximating Gains-from-Trade in Bilateral Trading
verfasst von
Liad Blumrosen
Yehonatan Mizrahi
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Web and Internet Economics

Print ISBN: 978-3-662-54109-8

Electronic ISBN: 978-3-662-54110-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-54110-4_28

Premium Partner

    Bildnachweise