Approximation algorithm and mechanism design for bisubmodular welfare maximization problem (Q6971745)

This paper focuses on studying auctions with two-dimensional demand, specifically, buyers have bisubmodular valuations, which have not been explored in previous researchers. Focusing on welfare maximization for efficiency, the authors present a simple greedy algorithm that produces an allocation achieving a 2-approximation when buyers' valuations are public. Furthermore, the authors propose a dominant-strategy incentive compatible (DSIC) mechanism that outputs an allocation achieving an \(O(\sqrt{m})\)-approximation when buyers' valuations are private. The algorithm for the bisubmodular welfare maximization is presented in Section 3. The dominant-strategy incentive compatible mechanism is given in Section 4.