Christian Kroer, Alexander Peysakhovich
arXiv 24 Sep 2019 · cs.GT · 5 citations (OpenAlex)
arXiv:1909.10925 · PDF · DOI · OpenAlex · Extracted main text
Allocating multiple scarce items across a set of individuals is an important practical problem. In the case of divisible goods and additive preferences a convex program can be used to find the solution that maximizes Nash welfare (MNW). The MNW solution is equivalent to finding the equilibrium of a market economy (aka. the competitive equilibrium from equal incomes, CEEI) and thus has good properties such as Pareto optimality, envy-freeness, and incentive compatibility in the large. Unfortunately, this equivalence (and nice properties) breaks down for general preference classes. Motivated by real world problems such as course allocation and recommender systems we study the case of additive `at most one' (AMO) preferences - individuals want at most 1 of each item and lotteries are allowed. We show that in this case the MNW solution is still a convex program and importantly is a CEEI solution when the instance gets large but has a `low rank' structure. Thus a polynomial time algorithm can be used to scale CEEI (which is in general PPAD-hard) for AMO preferences. We examine whether the properties guaranteed in the limit hold approximately in finite samples using several real datasets.
appendix boundary found by appendix_command · 51% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Alexander Peysakhovich and Christian Kroer (2019) Fair Division Without Disparate Impact self | 0.928 | 5 | 3 | 80% |
| 2 | Edmund Eisenberg and David Gale (1959) Consensus of subjective probabilities: The pari-mutuel method | 0.843 | 3 | 3 | 100% |
| 3 | Eduardo M Azevedo and Eric Budish (2018) Strategy-proofness in the large | 0.737 | 4 | 2 | 75% |
| 4 | Eric Budish (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes | 0.737 | 3 | 2 | 100% |
| 5 | Eric Budish and Estelle Cantillon (2012) The multi-unit assignment problem: Theory and evidence from course allocation at Harvard | 0.737 | 3 | 2 | 100% |
| 6 | Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman (2016) Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation | 0.737 | 3 | 2 | 100% |
| 7 | Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia… (2016) The unreasonable fairness of maximum Nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM,… | 0.644 | 2 | 2 | 100% |
| 8 | Richard Cole, Nikhil R Devanur, Vasilis Gkatzelis, Kamal Jain, Tung… (2017) Convex program duality, fisher markets, and nash social welfare. In 18th ACM Conference on Economics and Computation, EC 2017. A… | 0.585 | 3 | 1 | 100% |
| 9 | Christian Kroer, Alexander Peysakhovich, Eric Sodomka, and Nicolas E… (2019) Computing large market equilibria using abstractions self | 0.585 | 3 | 1 | 100% |
| 10 | Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijve… (2019) Pacing Equilibrium in First-Price Auction Markets. In Proceedings of the 2019 ACM Conference on Economics and Computation. ACM self | 0.511 | 2 | 2 | 50% |
Showing the top 10 of 31 scored citations.
arXiv econ.EM papers that cite this one, ranked by how heavily they lean on it.
| Citing paper | Intensity | Mentions | Sections | |
|---|---|---|---|---|
| 1 | Statistical Inference for Fisher Market Equilibrium | 0.000 | 1 | 1 |