{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibwo4hk53dulmvlznqdizx5eim6wbtroko3zqzdw5j4gynzo4y5tu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmnyrffcfed2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.23408v1",
  "publishedAt": "2026-05-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sander Borst",
    "Max Springer"
  ],
  "textContent": "**Authors:** Sander Borst, Max Springer\n\nOnline bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to online advertising. When agents belong to classes such as demographic groups or geographic regions, fairness demands equitable treatment across these groups. Recent work introduced class envy-freeness (CEF), a natural extension of the classical fair division notion: an algorithm is $α$-CEF if each class receives value at least an $α$ fraction of what it could extract from any other class's bundle. However, all known algorithms achieving constant-factor CEF guarantees attain utilitarian social welfare (total matching value) of at most $\\frac{1}{2}$ times the optimum, far below the $1-\\frac{1}{e} \\approx 0.632$ achievable without fairness constraints. We resolve the open question of whether fairness necessitates this efficiency loss, by introducing threshold-based algorithms parameterized by $γ\\in [0,1]$ that equalize allocations across classes until threshold $γ$, then maximize efficiency. For divisible matching, this yields simultaneous $(1-e^{-γ})$-CEF and $(1 - \\frac{e^{γ-1}}{γ+1})$-USW guarantees; for indivisible matching, $\\fracγ{2}$-CEF with the same USW. Setting $γ> 0$ produces the first algorithms beating $\\frac{1}{2}$-USW while maintaining constant CEF. We complement this with a novel upper bound construction, proving no non-wasteful $α$-CEF algorithm can exceed $\\frac{1 +α- e^{α-1}}{1+α}$-USW and correcting prior bounds that were vacuous for $α< 0.58$. Our upper bound nearly matches our algorithms' performance, giving the first substantive characterization of the price of fairness in online class matching.",
  "title": "Beyond the Half-Approximation: Fair and Efficient Online Class Matching"
}