Better Approximation for Interdependent SOS Valuations
- Resource Type
- Working Paper
- Authors
- Lu, Pinyan; Sun, Enze; Zhou, Chenghan
- Source
- Subject
- Computer Science - Computer Science and Game Theory
- Language
Submodular over signal (SOS) defines a family of interesting functions for which there exist truthful mechanisms with constant approximation to the social welfare for agents with interdependent valuations. The best-known truthful auction is of $4$-approximation and a lower bound of 2 was proved. We propose a new and simple truthful mechanism to achieve an approximation ratio of 3.315.