marketplace platform designers

Abstract: We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good at a price she sets, and each buyer chooses a utility-maximizing bundle subject to her budget. We consider both the rivalrous setting, such as markets for physical goods, and the non-rivalrous setting, such as markets for datasets. Pure Nash equilibria often fail to exist in this game. However, Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates, whereas in practice, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that buyers' purchases (among their optimal choices) change continuously with prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor of at most $b_{\mathrm{avg}}/b_{\min}$, the ratio of the average budget to the minimum budget. Our proof uses two nested applications of the KKM lemma. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating, and show that it reaches an approximate RARE, with additive error $δ$, within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. The main results of this paper are formally verified in the Lean 4 proof assistant (https://github.com/sharmaeklavya2/dm-rare).

Abstract: Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for $n = 2$ agents, they left open whether the same holds for $n > 2$ agents. We resolve this open question in the affirmative: for any fixed number of agents $n$ and any number of items $m$ divisible by $n$, an envy-free allocation exists with probability $1 - o(1)$ as $m \to \infty$. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.

Abstract: How much social welfare must a market lose because values are private? We determine the sharp ratio of second-best to first-best welfare under independent nonnegative types, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. The ratio is approximately $0.8882516903$ for arbitrary priors and $0.9113893681$ when buyers have monotone hazard rates and sellers are unrestricted. The arbitrary-prior guarantee holds for every downward-closed family of feasible matchings; the MHR guarantee holds when every matching of a compatibility graph is feasible. Both constants are \revise{attained}{sharp} already in bilateral trade. The proof keeps the sellers' initial endowment inside the budget Lagrangian. For arbitrary priors, a common threshold decomposition reduces the problem to three-parameter power-law distributions. For monotone hazards, common transformations of buyer and seller scores reduce it to shifted capped exponential buyers; a typewise allocation certificate and an explicit worst-case seller satisfy the same boundary equation. The bilateral-to-matching framework, with a welfare endowment charge and an MHR-preserving packing argument, transfers these affine inequalities without loss. We give exact variational characterizations of both constants and reproducible interval certificates for their numerical evaluation. Unrestricted signed transfers also permit pointwise strong budget balance.

Abstract: We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

Abstract: The maximin share (MMS) guarantee is a central fairness benchmark for allocating indivisible items. Since Kurokawa, Procaccia and Wang [EC'14, JACM'18] showed that exact MMS allocations need not exist, much work has studied existence and computation of approximate MMS allocations. In contrast, a basic complexity question posed more than a decade ago by Bouveret and Lemaître [JAAMAS'16] has remained unresolved: how hard is it to decide whether an exact MMS allocation exists? For additive valuations, Lonc and Truszczynski [JAIR'20] showed membership in $Δ_2^P$ (also known as $P^{NP}$), but no hardness result was known. For the more general class of 2-additive valuations, Bouveret and Lemaître established NP-hardness, leaving a substantial gap to the $Δ_2^P$ upper bound. Moreover, the (precise) complexity of MMS existence in additive and $k$-additive settings was posed as an open question. We make progress on all of these fronts: (1) For additive goods, we prove that deciding MMS existence is $D^P$-hard, giving the first hardness result for this longstanding problem. (2) For 2-additive valuations, we close the complexity gap by proving $Δ_2^P$-completeness on a class of instances of monotone submodular goods. To the best of our knowledge this is the first result of this kind. We also prove weak coNP-hardness for three agents, thereby establishing a precise dichotomy with the known existence guarantee for two agents; and strong coNP-hardness when the number of agents is unrestricted. Moreover, the strong hardness construction produces an inverse-polynomial gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio unless P=NP. Finally, we show that all these results for goods extend to the chores setting through a polynomial-time transformation that preserves MMS existence.

Abstract: We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.