| paper | d4-conf-wine-2020-0030 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.2
statement extracted from the paper’s text layer
Given finite sets of valuation types \(P,Q\), rational masses summing to one on each side, and static binary values \(v_p(q),v_q(p)\in\{0,1\}\), decide whether there is an infinite schedule of rounds with individual EF1 after every round and maximum welfare in every round. Represent agents by state classes \((p,h)\), where \(h\in\mathbb{N}^{Q}\) records their cumulative counts of matches with each type; each round couples the current state-class masses, gives every mass unit one integral match, and updates histories. The projected type flow \(x(p,q)\) in each round must maximize \(W(x)=\sum_{p,q}x(p,q)(v_p(q)+v_q(p))/2\) among flows with the given type masses; require \(v_p(g-h)\le1\) for every pair of same-side state classes \((p,h),(r,g)\), with the corresponding inequalities on \(Q\).
A nonatomic population with rational mass over complete valuation types, further partitioned by cumulative match history. Round decisions are couplings between history classes whose projection is a maximum-welfare transport; every individual receives one integral match, and EF1 is enforced between individuals represented by all same-side history classes.
The history-state support can grow with time, so the faithful mirror has no demonstrated finite-dimensional compression; this limits the tractability claim but not the question’s fit.
fatal: False
The mirror covers Theorem 4.2’s static binary conflict between individual EF1-over-rounds and per-round maximum welfare. It leaves Theorem 4.1’s dynamic impossibility and the paper’s positive algorithmic results unaddressed.
I would lead with Theorem 4.2, proved in the paper. It says that even for *static* binary valuations, no algorithm can guarantee both EF1-over-rounds and a maximum-weight matching in every round. Its six-agent \(0/1\) example has \(N=\{1,3,5\}\) and \(M=\{2,4,6\}\): every maximum-weight round has weight \(1.5\), but requiring such a round each time eventually forces an EF1 violation. This is an algorithmic impossibility result, not an NP-hardness theorem.
A plausible high-multiplicity setting is a large two-sided platform running repeated assignments among stable cohorts: for example, workers and employers grouped by skill, role, region, and their binary acceptability of counterpart categories. Each type is a complete valuation profile over the other side’s types. There may be millions of agents but only \(\tau\) types, with rational masses \(\mu_p\) and \(\nu_q\). Asymmetry is natural: a worker and an employer need not evaluate a match equally. The paper’s fixed-profile assumption would fit a stable planning period.
Here is the continuous question I would hand to a prover: Max-Welfare EF1 Type-Flow. The input is finite type sets \(P,Q\), positive rational masses summing to one on each side, and static binary valuations \(v_p(q),v_q(p)\in\{0,1\}\). A round is a transport matrix \(x\ge0\) with row sums \(\mu_p\) and column sums \(\nu_q\); \(x_{pq}\) is the fraction of population matched from types \(p,q\). Each mass unit still receives one integral match that round; the matrix records how the population is split among pairs. Round welfare is \(W(x)=\sum_{p,q}x_{pq}(v_p(q)+v_q(p))/2\), and each round must maximize \(W\).
For cumulative type-average bundles, set \(b^t_{p,q}=\sum_{s\le t}x^s_{pq}/\mu_p\), the average number of type-\(q\) matches received per member of type \(p\). Define \(\mathrm{EF1}_{\rm avg}\) by requiring that no type’s average envy of another type’s average bundle exceeds one: for \(p,r\in P\), \(\sum_q v_p(q)(b^t_{r,q}-b^t_{p,q})\le1\), with the analogous inequalities for pairs in \(Q\). The question is whether there is an infinite sequence of maximum-welfare rounds satisfying \(\mathrm{EF1}_{\rm avg}\) after every round. A solution is either a rational stationary transport \(\bar x\) that generates such a schedule when repeated forever, or a certificate that no such schedule exists.
This infinite-horizon question has a direct LP characterization. Let \(W^*\) be the maximum transport welfare. A schedule satisfying \(\mathrm{EF1}_{\rm avg}\) exists exactly when there is a maximum-welfare transport \(\bar x\) whose *per-capita average bundles are envy-free*: each type’s envy gap under \(\bar x\) is at most zero. Repeating such an \(\bar x\) keeps every cumulative gap nonpositive. Conversely, average the first \(T\) transports of any fair infinite schedule. The average remains maximum-welfare, and each envy gap is at most \(1/T\); a convergent subsequence therefore gives a maximum-welfare transport with nonpositive gaps. Thus the mirror is in Class A: the feasibility test is an LP with \(|P||Q|\) variables and polynomially many constraints in the type support and input bit length. It answers the underlying repeated-matching question, rather than merely encoding a one-shot matching problem.
The continuous version preserves the paper’s central tension—cumulative fairness alongside welfare-maximizing matching every round—while making mass splitting available. That makes Theorem 4.2’s integral obstruction a useful test case: its proof relies on individual match counts, whereas the continuous model can balance fractional shares across types. I would not claim from the theorem alone that its particular gadget becomes feasible; the LP decides that. Further questions include which profiles admit a fair maximum-welfare type flow, and how closely finite cohorts can approximate that flow while maintaining individual EF1.
The weakest point is the fairness notion. \(\mathrm{EF1}_{\rm avg}\) compares type-average bundles; it does not guarantee EF1 between almost every pair of individual agents, whose histories may differ even when their valuations agree. Type-level averaging is a reasonable population-scale co-modification here, but the authors might insist that fairness remains individual-level. If so, the stronger mirror must track distributions of individual histories within each type, and the LP characterization above would not settle it. This case covers Theorem 4.2’s static binary efficiency–fairness conflict only; it does not claim to mirror the paper’s dynamic impossibility or its symmetric positive result.
The negative case rests on a mismatch in what Theorem 4.2 calls fair. In the paper, EF1 is checked between individual agents after every round. The proposed LP checks envy between *type-average* bundles. For agents of the same type, its comparison is automatically zero, even when some of them have much worse histories than others. That matters in the theorem’s own example: agents 1 and 3 have identical valuations, and the proof uses their separate envy gaps to show that one eventually envies agent 5 by more than one. Averaging those two agents can erase the violation the theorem establishes.
The proponent’s LP may be a sound characterization of its stated average-fairness question. It does not characterize individual EF1. A faithful continuum model would have to track, within each valuation type, the mass of agents with each cumulative history. At time \(t\), those histories are count vectors of matches; their possible support grows with \(t\), even when the number of valuation types stays fixed. The infinite-horizon problem therefore needs a distribution over evolving histories and matching flows between them. That is a much larger dynamic model than the finite type-flow LP, and the population distribution alone no longer captures the fairness constraints.
This weakens the particular mirror, but it does not rule out every worthwhile one. Large marketplaces can have repeated cohorts with shared valuation profiles, so a high-multiplicity regime is credible. A type-average fairness guarantee could also be useful if the authors accept it as their fairness question. The paper’s six-agent example even includes identical agents, which gives a natural starting point for a population model. There is no honest basis here for claiming that multiplicity is absent, or that continuous prior art has already settled the problem.
So the strongest case against is that the clean, finite LP preserves only average fairness, while preserving the paper’s individual guarantee appears to require unbounded history state and gives up the main compression the proposed mirror promises. That is a substantive reason to doubt this anchor’s fit with the programme. It is not a decisive argument that the history-distribution version would be unworthy of study; that remains the negative case’s weak point.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.