Loading...

Designing Machine-Learning based Efficient Combinatorial Auctions

Jamshidi, Arash | 2024

179 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 57235 (19)
  4. University: Sharif University of Technology
  5. Department: Computer Engineering
  6. Advisor(s): Jafari Siavoshani, Mahdi
  7. Abstract:
  8. The aim of this research is to use machine learning methods in the design of Combinatorial Auctions. In particular, in this study, we first examine the relationship between Differential Privacy and combinatorial auctions. We propose a method based on Differential Privacy that, under certain assumptions, can transform any combinatorial auction based on machine learning methods into a Truthful auction using the Exponential Mechanism, such that all participants in the auction have no reason to misreport their Valuation Function. We also prove that in this case, using this method when the number of items is much less than the number of participants does not significantly impact the social welfare of the algorithm's output, and with high probability, we will see a maximum reduction in social welfare by an amount of O(√((2^m mlog⁡n)/n)) where n is the number of participants and m is the number of items. In the subsequent sections, we explore the use of submodular functions' properties in the design of machine learning-based combinatorial auctions. Specifically, in this section, we use the family of Deep Submodular Functions and a new family of set functions called Extended Deep Submodular Functions in the auction design. We also examine the theoretical properties of this family using some properties of the polymatroids of these functions. We assess the practical results of using these functions on learning complex set functions such as Coverage Functions and Cut Functions and show that Extended Deep Submodular Functions have significantly higher accuracy than Deep Submodular Functions in learning these functions. Additionally, in the auction design problem using these two families, we observe that the social welfare of the output allocation is significantly higher when using Extended Deep Submodular Functions as the base model compared to when the base model is chosen from the family of Deep Submodular Functions.
  9. Keywords:
  10. Auction ; Social Welfare ; Differential Privacy ; Submodular Functions ; Machine Learning ; Neural Network

 Digital Object List

 Bookmark

...see more