Market Pricing for Matroid Rank Valuations

[1] B. Berger, A. Eden, and M. Feldman, On the power and limits of dynamic pricing in

combinatorial markets, in Proceedings of the 16th International Conference on Web and

Internet Economics (WINE), Lecture Notes in Comput. Sci. 12495, Springer, 2020, pp. 206-219.

[2] L. Blumrosen and T. Holenstein, Posted prices vs. negotiations: an asymptotic analysis, in

EC'08: Proceedings of the 9th ACM Conference on Electronic Commerce, 2008, 49.

[3] S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan, Multi-parameter mechanism design

and sequential posted pricing, in Proceedings of the Forty-Second ACM Symposium on

Theory of Computing, ACM, New York, 2010, pp. 311--320.

[4] S. Chawla, D. L. Malec, and B. Sivan, The power of randomness in Bayesian optimal

mechanism design, in Proceedings of the 11th ACM Conference on Electronic Commerce,

ACM, New York, 2010, pp. 149--158.

[5] S. Chawla, J. B. Miller, and Y. Teng, Pricing for online resource allocation: Intervals and paths, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2019, pp. 1962--1981, https://doi.org/10.1137/1.

9781611975482.119.

[6] E. H. Clarke, Multipart pricing of public goods, Public Choice, (1971), pp. 17--33.

[7] V. Cohen-Addad, A. Eden, M. Feldman, and A. Fiat, The invisible hand of dynamic market

pricing, in Proceedings of the 2016 ACM Conference on Economics and Computation,

ACM, New York, 2016, pp. 383--400.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Downloaded 02/07/23 to 130.54.130.253 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

MARKET PRICING FOR MATROID RANK VALUATIONS

2677

[8] J. Davies and C. McDiarmid, Disjoint common transversals and exchange structures, J.

London Math. Soc. (2), 2 (1976), pp. 55--62.

\"

[9] P. Dutting,

M. Feldman, T. Kesselheim, and B. Lucier, Prophet Inequalities Made Easy:

Stochastic Optimization by Pricing Non-Stochastic Inputs, preprint, https://arxiv.org/

abs/1612.03161, 2016.

\"

[10] P. Dutting,

M. Feldman, T. Kesselheim, and B. Lucier, Prophet inequalities made easy:

Stochastic optimization by pricing non-stochastic inputs, in Proceedings of the IEEE 58th

Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 540-551.

\"

\'

[11] P. Dutting

and L. A. Vegh.

Private communication, 2017.

[12] A. Eden, U. Feige, and M. Feldman, Max-min greedy matching, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM

2019), LIPIcs. Leibniz Int. Proc. Inform. 145, Schloss Dagstuhl. Leibniz-Zent. Inform.,

Wadern, Germany, 2019, 7.

[13] J. Edmonds, Matroids and the greedy algorithm, Math. Programming, 1 (1971), pp. 127--136.

[14] T. Ezra, M. Feldman, T. Roughgarden, and W. Suksompong, Pricing multi-unit markets,

in Proceedings of the International Conference on Web and Internet Economics, Springer,

2018, pp. 140--153.

[15] M. Feldman, N. Gravin, and B. Lucier, Combinatorial auctions via posted prices, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,

SIAM, Philadelphia, 2014, pp. 123--135, https://doi.org/10.1137/1.9781611973730.10.

[16] M. Feldman, N. Gravin, and B. Lucier, Combinatorial Walrasian equilibrium, SIAM J.

Comput., 45 (2016), pp. 29--48, https://doi.org/10.1137/13094339X.

[17] A. Frank, A weighted matroid intersection algorithm, J. Algorithms, 2 (1981), pp. 328--336.

[18] A. Frank, Generalized polymatroids, in Finite and Infinite Sets, Vols. 1, 2, Colloq. Math. Soc.

J\'

anos Bolyai 37, North-Holland, Amsterdam, 1984, pp. 285--294.

[19] A. Frank, Connections in Combinatorial Optimization, Oxford University Press, Oxford, 2011.

[20] S. Fujishige and Z. Yang, A note on Kelso and Crawford's gross substitutes condition, Math.

Oper. Res., 28 (2003), pp. 463--469.

[21] T. Groves, Incentives in teams, Econometrica, 41 (1973), pp. 617--631.

[22] F. Gul and E. Stacchetti, Walrasian equilibrium with gross substitutes, J. Econom. Theory,

87 (1999), pp. 95--124.

[23] J. Hsu, J. Morgenstern, R. Rogers, A. Roth, and R. Vohra, Do prices coordinate markets?, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 2016, pp. 440--453.

[24] A. S. Kelso, Jr and V. P. Crawford, Job matching, coalition formation, and gross substitutes, Econometrica, 50 (1982), pp. 1483--1504.

[25] S. Krogdahl, A Combinatorial Base for Some Optimal Matroid Intersection Algorithms, Tech.

Report STAN-CS-74-468, Computer Science Department, Stanford University, Stanford,

CA, 1974.

[26] S. Krogdahl, A Combinatorial Proof for a Weighted Matroid Intersection Algorithm, Tech.

Report Computer Science Report 17, Institute of Mathematical and Physical Sciences,

University of Tromso, Tromso, Norway, 1976.

[27] S. Krogdahl, The dependence graph for bases in matroids, Discrete Math., 19 (1977), pp. 47-59.

[28] K. Murota, Discrete Convex Analysis, SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718508.

[29] K. Murota, Discrete convex analysis: A tool for economics and game theory, The Journal of

Mechanism and Institution Design, 1 (2016), pp. 151--273.

[30] K. Murota and A. Shioura, M-convex function on generalized polymatroid, Math. Oper. Res.,

24 (1999), pp. 95--105.

[31] N. Nisan and I. Segal, The communication requirements of efficient allocations and supporting prices, J. Econ. Theory, 129 (2006), pp. 192--224.

[32] H. Nishimura and S. Kuroda, A Lost Mathematician, Takeo Nakasawa: The Forgotten Father

of Matroid Theory, Birkh\"

auser Verlag, Basel, 2009.

[33] J. Oxley, Matroid Theory, Oxford University Press, Oxford, 2011.

[34] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms Combin.

24, Springer-Verlag, Berlin, 2003.

[35] A. Shioura and A. Tamura, Gross substitutes condition and discrete concavity for multi-unit

valuations: a survey, Journal of the Operations Research Society of Japan, 58 (2015),

pp. 61--103.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Downloaded 02/07/23 to 130.54.130.253 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

2678

\'

K. BERCZI,

N. KAKIMURA, AND Y. KOBAYASHI

[36] W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, The Journal of

Finance, 16 (1961), pp. 8--37.

\' ements d'\'

[37] L. Walras, El\'

economie politique pure, ou, Th\'

eorie de la richesse sociale, F. Rouge,

1896.

[38] H. Whitney, On the abstract properties of linear dependence, in Hassler Whitney Collected

Papers, Springer, 1992, pp. 147--171.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

...