A constant factor approximation for Nash social welfare with subadditive valuations.
Shahar DobzinskiWenzheng LiAviad RubinsteinJan VondrákPublished in: CoRR (2023)
Keyphrases
- social welfare
- constant factor approximation
- combinatorial auctions
- approximation algorithms
- mechanism design
- np hard
- optimal allocation
- bargaining solution
- worst case
- special case
- resource allocation
- bidding strategies
- auction mechanisms
- search algorithm
- coalition formation
- optimal solution
- greedy algorithm
- incomplete information
- decision problems
- np complete
- scheduling problem
- closest string
- lower bound