Approximation algorithm and mechanism design for bisubmodular welfare maximization problem

DOI10.1016/J.TCS.2025.115302MaRDI QIDQ6971745zbMATH OpenFDO

Authors Yuanyuan Wang, Qingqin Nong, Wenjing Liu, Qizhi Fang

Publication date 13 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115302

zbMATH Keywords

approximation algorithmbisubmodularcombinatorial auctionmechanismwelfare maximization

Mathematics Subject Classification ID

Mechanism design theory (91B03) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites work

• 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)