We study the trade-off between firm-side fairness and coalition stability in many-to-one matching markets with transferable payments. For a fixed matching $X$, we characterize the largest supportable core factor by a bottleneck financing problem: $\alpha(X)=1/\Phi(X)$, where $\Phi(X)=\min_{z\ge0}\max_i R_i(X,z)$. This yields a polynomial-time linear program and local sensitivity formulas for one-worker reallocations. We then develop a maximum-edge round algorithm and a broader class of mutual-top safe choices. Every safe execution is EF1 and, with $t=\delta(A)$ denoting the minimum positive-edge quality, guarantees $\alpha(X)\ge\max\{t,1/[m-(m-1)t]\}$ and $SW(X)/OPT\geq t+(1-t)/m$. These bounds give finite-firm lower and upper bounds for the EF1--core minimax frontier, with exact results for two firms and for three firms when $\delta\le1/2$; as the number of firms grows, the tight scale-free stability rate is $\delta$. We also extend the financing formulation to stronger $EFX^+$ fairness and capacity-constrained markets.
We initiate the study of $\alpha$-fair prophet inequalities. This interpolates between utilitarian welfare $(\alpha=0)$, Nash welfare $(\alpha=1)$, and Rawlsian max-min fairness $(\alpha\to\infty)$. Given the non-linearity of the objective, it matters when the expectation is applied. For instance, for the Rawlsian obje...
Paul Duetting, Michal Feldman, Mathieu Molina· 0 citations
We study the minimum monetary subsidy required for exact envy-freeness in allocating $m_n$ indivisible goods to $n$ agents. Valuations are additive, item values are i.i.d. from a distribution on $[0,1]$ with density bounded above and away from zero, and all agents value money equally. We consider $n\to\infty$ with $m_n...
The results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier and develop a new offline top-prefix representation that removes path dependence from online decisions.
We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much...
We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In...
We consider the integer version of Alkan--Gale's model on stability in a two-sided market, called the stable generalized allocation one. It is given by a triple $(G,b,C)$, where $G=(V,E)$ is a finite bipartite graph with nonnegative integer capacities $b(e)\in{\mathbb Z}_+$ of edges $e\in E$, and for each vertex (``age...
A. Karzanov· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
