Benny Lehmann

Title: Benny Lehmann

Main Research Question: How do submodular valuations, which exhibit no complementarities, affect the allocation problem in combinatorial auctions?

Methodology: The researchers used combinatorial auctions as a case study to explore the implications of submodular valuations, which exhibit no complementarities. They developed an efficient greedy 2-approximation algorithm for this case and generalized it to the case of limited complementarities.

Results: The researchers found that the allocation problem among submodular valuations is NP-hard. However, they presented an efficient greedy 2-approximation algorithm for this case and generalized it to the case of limited complementarities. They also showed that valuations satisfying the gross substitutes property form a zero-measure subset of the submodular valuations that have positive measure.

Implications: The results of this study have implications for the design and implementation of combinatorial auctions. The efficient greedy 2-approximation algorithm developed by the researchers can be used to solve the allocation problem among submodular valuations, which is a significant contribution to the field. The generalization of the algorithm to the case of limited complementarities also provides a useful tool for dealing with more complex scenarios. The study also contributes to the understanding of strategic aspects of combinatorial auctions among players with decreasing marginal utilities.

Link to Article: https://arxiv.org/abs/0202015v2 Authors: arXiv ID: 0202015v2