| paper | d4-conf-aaai-2018-0184 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given rational resident-type masses \(\mu_t\), room-class supplies \(\lambda_a\) with each summing to one, values \(v_{ta}\), budgets \(b_t\), per-capita rent \(R\), and rational linear objectives \(\ell_s\), decide whether there are prices \(p_a\) and assignment masses \(x_{ta}\ge 0\) such that \(\sum_a x_{ta}=\mu_t\), \(\sum_t x_{ta}=\lambda_a\), and \(\sum_a\lambda_a p_a=R\). For every \(x_{ta}>0\), require \(p_a\le b_t\) and \(v_{ta}-p_a\ge v_{tb}-p_b\) for every room class \(b\); then, if feasible, maximize \(\min_s\ell_s(u)\), where \(u_t=v_{ta}-p_a\) for any class assigned positive mass to type \(t\). Determine whether this can be done in time polynomial in the number of types, room classes, and input bit length.
A pooled rent market with a distribution \(\mu\) over complete resident types, room-class supplies \(\lambda\), per-room prices \(p\), and assignment masses \(x\). Each unit of resident mass receives one integral room; \(x\) records aggregate assignments, prices balance the per-capita rent, and assigned rooms must be affordable and envy-free. The objective selects among feasible allocations using the type utilities \(u\).
The paper motivates efficiency across many mostly small, separate apartments; it does not establish that a single large market with a shared rent pool is an important use case.
fatal: False
The mirrors cover Theorem 1’s budget-feasible optimization and Theorem 4’s minimum-violation extension. They leave the utility-uniqueness and equitable-solution results, as well as the strategic discussion, outside the mirror.
The strongest case is a large pooled housing market that retains the paper’s central question: can rent be divided so that every resident prefers their assigned room at its price, while respecting budgets and selecting a fair allocation? The paper has no named hardness result for this problem, so its polynomial-time anchors are the right ones to use.
Suppose a housing authority manages many rooms and residents. Residents have a small set \(T\) of recurring profiles, each specifying a value \(v_{ta}\) for every room class \(a\) and a budget \(b_t\). Rooms are grouped into classes \(A\) that have identical values for every resident type. Let \(\mu_t\) be the population share of type \(t\), and \(\lambda_a\) the share of rooms in class \(a\), with \(\sum_t\mu_t=\sum_a\lambda_a=1\). The regime of interest has many residents and rooms, but relatively few types and room classes.
A solution includes prices \(p_a\) and an assignment mass \(x_{ta}\). Each resident gets one room; \(x_{ta}\) records how much of type \(t\) receives class \(a\), with row sums \(\mu_t\) and column sums \(\lambda_a\). Rent balances per capita: \(\sum_a\lambda_a p_a=R\), where \(R\) is total rent divided by the number of residents. Whenever \(x_{ta}>0\), that room must be affordable to type \(t\), and \(v_{ta}-p_a\ge v_{tb}-p_b\) for every room class \(b\). This preserves the paper’s envy test, including comparisons with rooms a resident could not afford. All residents of a type using rooms in positive mass have the same utility \(u_t\).
This is a deliberate extension of the paper’s single-apartment setting: room supplies scale with the population and rents are pooled across a large development. It preserves one room per resident, quasi-linear values, budget constraints, envy-freeness, and fair selection among allocations. In a finite market with \(N\) residents and rooms, \(\mu_t=n_t/N\), \(\lambda_a=q_a/N\), and \(R=r/N\) recover the corresponding shares and per-capita rent. The flow \(x\) is an aggregate assignment, not a fractional room bundle. For fixed prices, the allowed type-to-room assignments form a bipartite flow network; after clearing rational denominators, its integral flow property supports exact finite-clone realizations.
Lead anchor — Theorem 1, proved in this paper. For an economy \(e=(N,A,v,r)\), budgets \(b\), and a polynomial number \(t\) of linear functions \(f_s\) of the agents’ utility vector, the theorem gives a polynomial-time algorithm that decides whether any envy-free allocation satisfies the budgets. If one exists, it outputs an allocation maximizing the minimum of those \(t\) functions over all envy-free, budget-feasible allocations.
Mass Budget-Constrained Envy-Free Rent Division is the corresponding continuous problem. Its input is the rational type masses \(\mu\), room supplies \(\lambda\), values \(v_{ta}\), budgets \(b_t\), per-capita rent \(R\), and an explicit family of rational linear objectives \(\ell_s\) on the type-utility vector. It asks whether there are \(x,p\) satisfying the mass balance, rent balance, envy, and budget conditions above; if so, return an allocation maximizing \(\min_s\ell_s(u)\). The direct maximin version takes \(\ell_t(u)=u_t\), so it maximizes the minimum utility of any resident.
I expect this mirror to be Class A, tractable, through a support-compressed version of the paper’s envy-graph and component decomposition, using capacitated flows and linear optimization. That is a research expectation, not a consequence already proved by Theorem 1. The central question is whether the algorithm can run in time polynomial in the number of resident types, room classes, and input bit length.
Theorem 4, stated here with its proof deferred to the full version. The authors give a polynomial-time algorithm that, for the same economy, budget vector, and polynomial family of linear utility objectives, outputs an envy-free allocation that first minimizes the maximum budget violation and then maximizes the minimum objective value among allocations with that minimum violation.
Mass Minimum-Violation Envy-Free Rent Division uses the same instance and constraints except that budgets need not be satisfied outright. Define the violation of a mass allocation by
\[
\Delta(x,p)=\max_{(t,a):\,x_{ta}>0}\max\{0,p_a-b_t\}.
\]
The problem asks for an envy-free, rent-balanced \(x,p\) minimizing \(\Delta(x,p)\), then maximizing \(\min_s\ell_s(u)\) among allocations attaining that minimum. I also expect Class A, by adapting the paper’s decomposition while optimizing the violation threshold. A proof would need to show that the price and assignment choices still admit a support-sized algorithm.
The weakest point is the bit complexity. The paper’s polynomial bounds use the explicitly represented number of agents. Clearing the denominators of binary rational masses can create a finite clone population exponentially large in the encoded input, so those bounds alone do not establish a polynomial algorithm in support size and bit length. The scenario is credible and the aggregate assignment remains faithful to indivisible rooms, but the required compression of the authors’ algorithm remains open.
The first mirror generates the question whether the budget-feasible algorithm can be compressed to resident types and room classes, with polynomial bit lengths for prices and flows. It also invites checking whether the paper’s maximin utility uniqueness and maximin-versus-equitable results survive in the mass model. The second asks whether minimum violation admits the same support-sized compression and how its optimal value behaves as finite populations approximate the rational mass distribution.
These mirrors cover the paper’s budget-constrained allocation algorithm and its minimum-violation extension. They do not claim to continuize the paper’s other structural results.
The strongest case against these mirrors is a mismatch between the paper’s setting and the regime that motivates it. The paper studies one apartment, with one room per agent, and says its practical concern is the cost of processing many instances; most real instances have at most four agents. Repeating those small apartments does not make one high-multiplicity society. Envy is assessed within each apartment, and each apartment has its own fixed rent. Pooling their residents and rooms would introduce cross-apartment comparisons and a shared rent constraint that the paper does not study.
That objection applies to both anchors. Theorem 1’s budget-feasible, envy-free allocation and Theorem 4’s minimum-violation allocation are computational results, but their practical motivation does not point to a large population inside a single instance. For Theorem 4 in particular, a continuous maximum violation would be sensitive to any positive mass, however small; an exceptional individual whose population share vanishes would disappear from the limit. That may be an appropriate population-level fairness criterion, but it need not preserve the paper’s worst-individual guarantee.
A stronger mirror, though, is hard to dismiss: a large dormitory or housing co-op that assigns many residents to many rooms under one rent pool, with recurring resident profiles and room classes. Then a mass assignment \(x_{ta}\) can represent residents of type \(t\) receiving rooms of class \(a\). Rational masses can be scaled to a finite assignment, while a support-sized algorithm could avoid processing an enormous clone population. Theorem 1 gives a clear question about whether its algorithm compresses to type and room-class counts; Theorem 4 has a natural analogue using the maximum violation over positively assigned type-room pairs. Neither question is answered by the paper’s polynomial-time bounds in the number of named agents.
So the negative case is real but limited: the paper’s own application does not establish a compelling high-multiplicity regime, and the proposed pooled-market scenario changes the setting from one apartment to a larger housing allocation system. But that system is plausible, and the resulting computational questions are well-posed. I cannot honestly defeat both anchors in every scenario; the case against a worthwhile mirror is weaker than the case for one.
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.