research-article

Diffusion auction design with transaction costs

Authors:

Dengji ZhaoAuthors Info & Claims

Autonomous Agents and Multi-Agent Systems, Volume 38, Issue 1

https://doi.org/10.1007/s10458-023-09631-8

Published: 06 December 2023 Publication History

Abstract

We study multi-unit auctions powered by intermediated markets, where all transactions are processed by intermediaries and incur certain costs. Each intermediary in the market owns a private set of buyers and all intermediaries are networked with each other. Our goal is to incentivize the intermediaries to share the auction information to individuals they can reach, including their private buyers and neighboring intermediaries, so that more potential buyers are able to participate in the auction. To this end, we build a diffusion-based auction framework to handle the transaction costs and the strategic interactions between intermediaries. The classic Vickrey-Clarke-Groves (VCG) mechanism within the scenario can obtain the maximum social welfare, but it can decrease the seller’s revenue or even lead to a deficit. To overcome the revenue issue, we develop two deficit reduction strategies, based on which a family of diffusion auctions called Critical Neighborhood Auctions (CNA) is identified. The CNA not only maximizes the social welfare, but also eliminates all the seller’s deficits. Moreover, the revenue given by the CNA is no less than the revenue given by the VCG mechanism with/without intermediaries. This is the first set of diffusion auctions with welfare and revenue advantages that can handle multiple items and transaction costs.

References

[1]

Archer, A., Tardos, É (2001). Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 482–491.

[2]

Babaioff, M., Lucier, B., Nisan, N. (2018) Bertrand networks. In: Proceedings of the 14th ACM Conference on Electronic Commerce, pp. 33–34.

[3]

Blume LE, Easley D, and Kleinberg J Éva Tardos: Trading networks with price-setting agents Games and Economic Behavior 2009 67 1 36-50

[4]

Chen, H., Deng, X., Wang, Y., Wu, Y., Zhao, D. (2023). Sybil-proof diffusion auction in social networks. In: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 1379–1387.

[5]

Clarke EH Multipart pricing of public goods Public Choice 1971 11 1 17-33

[6]

Condorelli D, Galeotti A, and Skreta V Selling through referrals Journal of Economics & Management Strategy 2018 27 4 669-685

[7]

Easley, D., Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World, pp. 277–300. Cambridge University Press, Cambridge.

[8]

Emek, Y., Karidi, R., Tennenholtz, M., Zohar, A. (2011). Mechanisms for multi-level marketing. In: Proceedings of the 12th ACM Conference on Electronic Commerce, ACM. pp. 209–218.

[9]

Fang, Y., Zhang, M., Liu, J., Khoussainov, B., Xiao, M. (2023). Multi-unit auction over a social network. In: Proceedings of the 26th European Conference on Artificial Intelligence, pp. 676–683.

[10]

Feigenbaum, J., Shenker, S. (2002). Distributed algorithmic mechanism design: Recent results and future directions. In: Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 1–13.

[11]

Feigenbaum J, Papadimitriou CH, and Shenker S Sharing the cost of multicast transmissions Journal of Computer and System Sciences 2001 63 21-41

[12]

Feldman, J., Mirrokni, V., Muthukrishnan, S., Pai, M.M. (2010). Auctions with intermediaries: Extended abstract. In: Proceedings of the 11th ACM Conference on Electronic Commerce, pp. 23–32.

[13]

Groves T Incentives in teams Econometrica 1973 41 4 617-631

[14]

Guo, Y., Hao, D. (2021). Emerging methods of auction design in social networks. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence, pp. 4434–4441.

[15]

Hu X, Ye D, Zhu T, and Huo H A differentially private auction mechanism in online social networks Journal of Systems Science and Systems Engineering 2021 30 1-14

[16]

Jeong, S.E., Lee, J. (2020). The groupwise-pivotal referral mechanism: Core-selecting referral strategy-proof mechanism. In: Available at SSRN: Https://ssrn.com/abstract=3574093.

[17]

Johnson, D.S., Minkoff, M., Phillips, S. (2000). The prize collecting steiner tree problem: Theory and practice. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 760–769. 0.5555/338219.338637

[18]

Kariv S, Kotowski MH, and Leister CM Liquidity risk in sequential trading networks Games and Economic Behavior 2018 109 565-581

[19]

Kawasaki, T., Barrot, N., Takanashi, S., Todo, T., Yokoo, M. (2020). Strategy-proof and non-wasteful multi-unit auction via social network. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2062–2069.

[20]

Kawasaki, T., Wada, R., Todo, T., Yokoo, M. (2021). Mechanism design for housing markets over social networks. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 692–700.

[21]

Kleinberg, J., Raghavan, P. (2005). Query incentive networks. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 132–141.

[22]

Leskovec, J., Adamic, L.A., Huberman, B.A. (2006). The dynamics of viral marketing. In: Proceedings of the 7th ACM Conference on Electronic Commerce, pp. 228–237.

[23]

Li, B., Hao, D., Zhao, D., Zhou, T. (2018). Customer sharing in economic networks with costs. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 368–374.

[24]

Li, B., Hao, D., Zhao, D., Zhou, T. (2017). Mechanism design in social networks. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 586–592.

[25]

Li, B., Hao, D., Zhao, D. (2020). Incentive-compatible diffusion auctions. In: Proceeding of the 29th Int. Joint Conference on Artificial Intelligence, pp. 231–237.

[26]

Li S Obviously strategy-proof mechanisms American Economic Review 2017 107 11 3257-87

[27]

Li B, Hao D, Gao H, and Zhao D Diffusion auction design Artificial Intelligence 2022 303

[28]

Liu, P., Wang, X., Che, X., Chen, Z., Gu, Y. (2014). Defense against sybil attacks in directed social networks. In: Proc. of the 19th International Conference on Digital Signal Processing, pp. 239–243.

[29]

Liu, X., Wu, W., Li, M., Wang, W. (2021). Budget feasible mechanisms over graphs. In: Proc. of the AAAI Conference on Artificial Intelligence, pp. 5549–5556.

[30]

Manea M Intermediation and resale in networks Journal of Political Economy 2018 126 3 1250-1301

[31]

Moustafa, A., Mishra, P., Daigaku, N.K. (2021) A diffusion mechanism for multi-unit commodity allocation in economic networks. Electronic Commerce Research and Applications, 101078.

[32]

Myerson RB Optimal auction design Mathematics of Operations Research 1981 6 58-73

[33]

Myerson RB and Satterthwaite MA Efficient mechanisms for bilateral trading Journal of Economic Theory 1983 29 2 265-281

[34]

Shi Q and Hao D Social sourcing: Incorporating social networks into crowdsourcing contest design IEEE/ACM Transactions on Networking 2022 12 1-15

[35]

Vickrey W Counterspeculation, auctions, and competitive sealed tenders The Journal of Finance 1961 16 1 8-37

[36]

Viswanath, B., Post, A., Gummadi, K.P., Mislove, A. (2010). An analysis of social network-based sybil defenses. In: Proceedings of the ACM SIGCOMM 2010 Conference, pp. 363–374.

[37]

Xiao, M., Song, Y., Khoussainov, B. (2022). Multi-unit auction in social networks with budgets. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 5228–5235. 0.1609/aaai.v36i5.20458

[38]

Yang, L., Zhu, H., Wang, H., Qian, H., Yang, Y. (2018). Incentive propagation mechanism of computation offloading in fog-enabled d2d networks. In: Proceedings of the IEEE 23rd International Conference on Digital Signal Processing, pp. 1–4.

[39]

Yokoo M, Sakurai Y, and Matsubara S The effect of false-name bids in combinatorial auctions: new fraud in internet auctions Games and Economic Behavior 2004 46 1 174-188

[40]

Zhang, W., Zhang, Y., Zhao, D. (2020). Collaborative data acquisition. In: Proc. of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1629–1637.

[41]

Zhang, Y., Zhang, X., Zhao, D. (2020). Sybil-proof answer querying mechanism. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 422–428.

[42]

Zhang, W., Zhao, D., Zhang, Y. (2020). Incentivize diffusion with fair rewards. In: Proceedings of the 24th European Conference on Artificial Intelligence, pp. 251–258.

[43]

Zhao, D., Li, B., Xu, J., Hao, D., Jennings, N.R. (2018). Selling multiple items via social networks. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 68–76.

[44]

Zhao, D. (2021). Mechanism design powered by social interactions. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 63–67.

[45]

Zhao, D. (2022). Mechanism design powered by social interactions: A call to arms. In: Proc. of the 31st International Joint Conference on Artificial Intelligence, pp. 5831–5835.

Cited By

Li BHao DZhao DDastani MSichman JAlechina NDignum V(2024)Extended Abstract of Diffusion Auction Design with Transaction CostsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663304(2833-2835)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663304

Index Terms

Diffusion auction design with transaction costs
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Index terms have been assigned to the content through auto-classification.

Recommendations

Diffusion auction design
Abstract
This paper studies an auction design problem for a seller to sell a single commodity in a social network, where each individual (the seller or a buyer) can only communicate with her neighbors. The challenge is to design a mechanism to incentivize ...
Extended Abstract of Diffusion Auction Design with Transaction Costs
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

We study multi-unit diffusion auctions powered by intermediated markets, where all transactions are processed by intermediaries and incur certain costs. The classic Vickrey-Clarke-Groves (VCG) mechanism within the scenario can obtain the maximum social ...
False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values

This paper presents a new false-name-proof multi-unit auction protocol called the Greedy ALlocation (GAL) protocol. Internet auctions have become an integral part of Electronic Commerce and a promising field for applying agent and Artificial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Autonomous Agents and Multi-Agent Systems

Autonomous Agents and Multi-Agent Systems Volume 38, Issue 1

Jun 2024

782 pages

Issue’s Table of Contents

© Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 06 December 2023

Accepted: 07 November 2023

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
Science and Technology Commission of Shanghai Municipality

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li BHao DZhao DDastani MSichman JAlechina NDignum V(2024)Extended Abstract of Diffusion Auction Design with Transaction CostsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663304(2833-2835)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663304

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents