| paper | Mechanism Design for Multi-Type Housing Markets |
| authors | Sibel Adali, Sujoy Sikdar, Lirong Xia |
| venue | AAAI 2017 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): blocking-coalition existence is decidable in \((L+\tau m^4)^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite item-class sets \(Q_1,Q_2\), a finite set \(T\) of complete agent types, rational masses \(\mu_t\), type-specific endowments \(e_i(t)\), separable lexicographic rankings with common importance order \(1\triangleright2\), and a feasible current mass allocation \(a_{t,b}\) over integral bundles \(b\in Q_1\times Q_2\), decide whether there exists a positive-mass coalition represented by transfers \(z_{t,b,b'}\ge0\) with \(b'\succeq_t b\), \(z_{t,b,b'}\le a_{t,b}\), conservation of every participating item-class mass, and \(\sum_{t,b,b':\,b'\succ_t b}z_{t,b,b'}>0\).
An atomless high-multiplicity exchange economy with agent-type masses \(\mu\), integral bundles, and item-class supplies induced by initial endowments; blocking is optimized by a flow LP over transfers \(z_{t,b,b'}\), maximizing strictly improving mass subject to cohort capacities, preference constraints, and item-class conservation.
The paper's reduction treats every gadget agent and item label as logically distinct, and it does not itself establish that the hardness construction survives when those roles become exchangeable high-multiplicity cohorts.
fatal: False
The mirror covers Theorem 3's strict-core membership problem and leaves MTTC's algorithmic and axiomatic results, the strategy-proofness impossibility results, and Theorem 4 on strict-core nonemptiness untouched.
The strongest positive case is a continuous-population version of the paper’s strict-core membership problem, anchored in Theorem 3.
The paper’s Theorem 3, proved in the paper rather than cited, states: “InStrictCore is co-NPC even when agents have separable lexicographic preferences over \(p\ge 2\) types.” In standard terminology, this is coNP-completeness. InStrictCore receives a finite multi-type housing market, a lexicographic preference profile, and an allocation \(A\), and asks whether \(A\) belongs to the strict core. Equivalently, it asks whether there is no coalition that can redistribute its members’ initial endowments so that every member is weakly better off and at least one is strictly better off. The reduction is from 3-SAT and already uses two item types, a common importance order \(1\triangleright 2\), and separable preferences. Thus the hardness does not rely on complicated CP-net dependencies or heterogeneous importance orders.
I would mirror this as \(\textsc{MassInStrictCore}\).
An instance contains two finite sets of exchangeable item classes \(Q_1\) and \(Q_2\), together with a finite set \(T\) of complete agent types. A type \(t\in T\) specifies:
The society is a rational distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the mass of agents of type \(t\). The supply of item class \(q\in Q_i\) is induced by initial ownership: \(\sigma_i(q)=\sum_{t:e_i(t)=q}\mu_t\).
A feasible allocation is a mass assignment \(a_{t,b}\), where \(b\in Q_1\times Q_2\), satisfying \(\sum_b a_{t,b}=\mu_t\) and the corresponding supply constraints for every item class. This does not give an individual a fractional house or fractional permit. Each infinitesimal agent receives one integral bundle \(b=(b_1,b_2)\); \(a_{t,b}\) merely records what fraction of a homogeneous cohort receives each bundle.
The question is whether the given allocation \(a\) is in the atomless strict core: does there exist a positive-mass coalition and a reassignment of exactly that coalition’s initial endowments such that every participating agent weakly prefers the new bundle to the bundle currently assigned to them, with a positive mass strictly preferring it? A solution to \(\textsc{MassInStrictCore}\) is therefore either a YES answer certifying that no such blocking exchange exists, or a blocking mass-transfer plan.
This is recognisably the authors’ problem. It retains initial endowments, multiple item types, indivisible bundles, ordinal bundle preferences, coalitional blocking, and the strict core. The only change is that repeated agents and repeated item classes are represented by mass. A rational instance has the exact high-multiplicity dictionary: after choosing a common denominator \(N\), create \(N\mu_t\) agents of each type and \(N\sigma_i(q)\) copies of each item class. Conversely, any finite market with repeated preference/endowment roles normalizes to such a distribution.
A plausible regime is a large housing cooperative, university, or municipal allocation system in which thousands of residents each initially hold one room assignment and one parking or storage assignment. Residents fall into a relatively small number of cohorts: the same initial room class, the same initial permit class, and the same lexicographic priorities. Thus \(N\) may be in the tens or hundreds of thousands while \(|T|\), \(|Q_1|\), and \(|Q_2|\) remain modest. This is not a story invented merely to make the mathematics easy: it is exactly the paper’s houses-and-cars interpretation with many exchangeable copies.
I expect this mirror to be Class A. The reason is that the finite coNP-hardness appears to use indivisible coalition selection. In the atomless model, blocking can be expressed directly as a flow LP. Let \(z_{t,b,b'}\) be the mass of type-\(t\) agents currently receiving \(b\) who join the coalition and receive \(b'\). Restrict variables to \(b'\succeq_t b\), impose \(\sum_{b'}z_{t,b,b'}\le a_{t,b}\), and conserve every item class inside the coalition:
\(\sum_{t,b,b':\,b'_i=q}z_{t,b,b'}=\sum_{t:e_i(t)=q}\sum_{b,b'}z_{t,b,b'}\).
Maximize the strictly improving mass
\(\Delta(z)=\sum_{t,b,b':\,b'\succ_t b}z_{t,b,b'}\).
A blocking coalition exists exactly when the optimum is positive. With two item types, \(|Q_1\times Q_2|=|Q_1||Q_2|\), so this LP has polynomial size; separable lexicographic preferences make every comparison \(b'\succeq_t b\) efficiently testable. Hence the natural continuous analogue of the paper’s coNP-complete membership problem is expected to be solvable in polynomial time. The discrete hardness can dissolve because fractional population mass permits partial participation by a cohort, while every participating individual still receives an integral bundle.
The weakest point is that the paper’s reduction uses many gadget-specific agents and item labels. If those labels are genuinely essential rather than exchangeable roles, the high-multiplicity scenario is less faithful. Moreover, the continuous definition deliberately treats only positive-mass coalitions as blocking; a single exceptional individual has measure zero. I think both changes are defensible consequences of continuizing the population, but they are the points a referee would scrutinize.
This case deliberately covers Theorem 3 only. Theorem 4, which proves that \(\textsc{StrictCoreNonEmpty}\) is NP-hard, may also have a continuous analogue, but core existence is a separate equilibrium problem and should not be smuggled into the present claim. Natural follow-up questions are whether continuous strict-core existence is also tractable, whether the result survives for \(p\) varying with the input, and how closely finite markets with large multiplicities converge to the atomless answer.
The strongest negative is an identity objection. Theorem 3’s reduction does not contain repeated social roles: every agent, endowment, and item label is a distinct logical wire in the 3-SAT gadget. The coalition is powerful precisely because it must move those particular endowments through those particular agents. If one retains that identity, each complete type occurs once and the population has no meaningful multiplicity. If one replaces \(j_i\) by an exchangeable item class and duplicates every gadget role, one has changed the market, not merely continuized its population. The variable-consistency gadget is no longer the same object.
The proposed housing-cooperative story does not completely repair this. Residents with the same preferences, initial room class, and permit class can indeed form a high-multiplicity cohort, but that is a new capacitated exchange economy with interchangeable copies. The paper’s formal model treats items as individually named and ranks those names. Nothing in the paper establishes that its core phenomenon survives the symmetry needed to make those items repeat. Thus Theorem 3 itself supplies no evidence that the paper’s computational problem has a natural high-multiplicity regime.
The better defence of the mirror is nevertheless substantial. One can explicitly define a mass allocation \(a_{t,b}\), retain integral bundles for every infinitesimal agent, and let only cohort membership be divisible. Then blocking is captured by variables \(z_{t,b,b'}\), with \(b'\succeq_t b\), capacity constraints, and conservation of the endowment mass of every item class. Maximizing
\[ \sum_{t,b,b':\,b'\succ_t b} z_{t,b,b'} \]
is a polynomial-size LP when there are two finite item-class sets. A positive optimum is exactly a positive-mass blocking coalition. This is not a formal mistake, nor does it improperly continuize the outcome: each individual still receives one integral bundle.
Consequently, I cannot honestly defeat the anchor universally. Theorem 3 is a genuine numbered computational result, and this construction is a recognisable high-multiplicity version of the authors’ problem. Its tractability would be a legitimate Class A result, even if the finite reduction’s hardness disappears. The identity objection shows that the paper does not itself motivate the proposed regime and that the reduction should not be presented as surviving unchanged; it does not show that the continuous question is unworthwhile. On this anchor, the negative case is weak.
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.