Paper Reading AI Learner

Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning

2024-02-29 18:16:13
Greg d'Eon, Neil Newman, Kevin Leyton-Brown

Abstract

Iterative combinatorial auctions are widely used in high stakes settings such as spectrum auctions. Such auctions can be hard to understand analytically, making it difficult for bidders to determine how to behave and for designers to optimize auction rules to ensure desirable outcomes such as high revenue or welfare. In this paper, we investigate whether multi-agent reinforcement learning (MARL) algorithms can be used to understand iterative combinatorial auctions, given that these algorithms have recently shown empirical success in several other domains. We find that MARL can indeed benefit auction analysis, but that deploying it effectively is nontrivial. We begin by describing modelling decisions that keep the resulting game tractable without sacrificing important features such as imperfect information or asymmetry between bidders. We also discuss how to navigate pitfalls of various MARL algorithms, how to overcome challenges in verifying convergence, and how to generate and interpret multiple equilibria. We illustrate the promise of our resulting approach by using it to evaluate a specific rule change to a clock auction, finding substantially different auction outcomes due to complex changes in bidders' behavior.

Abstract (translated)

迭代组合拍卖在高风险场景(如频谱拍卖)中得到了广泛应用。这样的拍卖很难用分析方法来理解,使得买家无法确定如何行动,设计师也无法优化拍卖规则以确保实现好的结果(如高收益或福利)。在本文中,我们研究是否可以使用多智能体强化学习(MARL)算法来理解迭代组合拍卖,因为这些算法最近在多个领域取得了经验上的成功。我们发现,MARL确实可以有益于拍卖分析,但有效地部署它并不容易。我们首先描述了保持模型在不牺牲重要特征(如不完美信息或买家的不对称性)的情况下保持游戏可导性的建模决策。我们还讨论了如何应对各种MARL算法的陷阱,如何克服验证收敛的挑战,以及如何生成和解释多个均衡。我们通过使用该方法对一个具体的时钟拍卖规则进行评估,发现由于买家的行为复杂变化,拍卖结果差异很大。

URL

https://arxiv.org/abs/2402.19420

PDF

https://arxiv.org/pdf/2402.19420.pdf


Tags
3D Action Action_Localization Action_Recognition Activity Adversarial Agent Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot