Approximation algorithm and mechanism design for bisubmodular welfare maximization problem
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.
- A characterization of bisubmodular functions
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Approximation algorithms for combinatorial auctions with complement-free bidders
- Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders
- Combinatorial auctions with decreasing marginal utilities
- Computationally manageable combinational auctions
- Directed submodularity, ditroids and directed submodular flows
- Game theory and mechanism design
- Inapproximability results for combinatorial auctions with submodular utility functions
- On some extremal problems in graph theory
- Online mechanism design (randomized rounding on the fly)
- Some optimal inapproximability results
- Truthful randomized mechanisms for combinatorial auctions
- Two Randomized Mechanisms for Combinatorial Auctions
This page was built for publication: Approximation algorithm and mechanism design for bisubmodular welfare maximization problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6971745)
