Market pricing for matroid rank valuations

DOI10.1137/20M1386335zbMATH Open1478.91080arXiv2007.08759OpenAlexW3214667065MaRDI QIDQ5013570FDOQ5013570

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)

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.

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

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?

zbMATH Keywords

Walrasian equilibriumpricing schemegross substitutes valuationmatroid rank function

Mathematics Subject Classification ID

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

Cites Work

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

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

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)