Market pricing for matroid rank valuations

DOI10.1137/20M1386335MaRDI QIDQ5013570zbMATH OpenOpenAlexFDO

Authors Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi

Publication date 1 December 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.08759

zbMATH Keywords

gross substitutes valuationmatroid rank functionpricing schemeWalrasian equilibrium

Mathematics Subject Classification ID

Welfare economics (91B15) Microeconomic theory (price theory and economic markets) (91B24) Special types of economic equilibria (91B52)

Abstract: In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a simple partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by D"uetting and V'egh in 2017. We further formalize a weighted variant of the conjecture of D"uetting and V'egh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M${}^{a}tural$-concave functions, or equivalently, gross substitutes functions.

Recommendations

• Combinatorial Walrasian equilibrium
• Combinatorial Walrasian equilibrium
• Pricing to maximize revenue and welfare simultaneously in large markets
• Optimal item pricing in online combinatorial auctions
• Do prices coordinate markets?

Cites work

• \(M\)-convex function on generalized polymatroid
• A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
• A Note on Kelso and Crawford's Gross Substitutes Condition
• A weighted matroid intersection algorithm
• Combinatorial auctions via posted prices
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial Walrasian equilibrium
• Connections in combinatorial optimization
• Discrete Convex Analysis
• Disjoint Common Transversals and Exchange Structures
• Do prices coordinate markets?
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• scientific article; zbMATH DE number 3906513 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Incentives in Teams
• Job Matching, Coalition Formation, and Gross Substitutes
• Matroids and the greedy algorithm
• Multi-parameter mechanism design and sequential posted pricing
• On the power and limits of dynamic pricing in combinatorial markets
• Pricing for Online Resource Allocation: Intervals and Paths
• Pricing multi-unit markets
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• The communication requirements of efficient allocations and supporting prices
• The dependence graph for bases in matroids
• The power of randomness in Bayesian optimal mechanism design
• Walrasian equilibrium with gross substitutes

Cited in

(3)

• Inverse optimization problems with multiple weight functions
• The finite matroid-based valuation conjecture is false
• A Dual Approach for Dynamic Pricing in Multidemand Markets

Describes a project that uses

Uses Software

• Sociodynamica

This page was built for publication: Market pricing for matroid rank valuations

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