Optimal allocation in combinatorial auctions with quadratic utility functions

DOI10.1007/978-3-642-20877-5_15MaRDI QIDQ3010396zbMATH OpenOpenAlexFDO

Authors Akiyoshi Shioura, Shunya Suzuki

Publication date 1 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20877-5_15

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Utility theory (91B16) Auctions, bargaining, bidding and selling, and other market models (91B26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Optimal allocation problem with quadratic utility functions and its relationship with graph cut problem
• Inapproximability results for combinatorial auctions with submodular utility functions
• Combinatorial auctions with decreasing marginal utilities
• Combinatorial auctions
• Bidder optimal assignments for general utilities

Cites work

• \(M\)-convex functions and tree metrics
• A Note on Kelso and Crawford's Gross Substitutes Condition
• Algorithm for optimal winner determination in combinatorial auctions
• An o(n^3 )-Time Maximum-Flow Algorithm
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation Algorithms for Graph Homomorphism Problems
• Bundling equilibrium in combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• Inapproximability results for combinatorial auctions with submodular utility functions
• Job Matching, Coalition Formation, and Gross Substitutes
• Multiagent resource allocation in k-additive domains: preference representation and complexity
• Network flows. Theory, algorithms, and applications.
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Submodular functions and optimization.
• The Complexity of Multiterminal Cuts
• The ellipsoid method and its consequences in combinatorial optimization
• Verifying gross substitutability.
• Walrasian equilibrium with gross substitutes

Cited in

(4)

• Allocative efficiency in simulated multiple-unit combinatorial auctions with quantity support
• On the optimal allocation of prizes in best-of-three all-pay auctions
• Optimal allocation problem with quadratic utility functions and its relationship with graph cut problem
• Quadratic core-selecting payment rules for combinatorial auctions

This page was built for publication: Optimal allocation in combinatorial auctions with quadratic utility functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010396)