| paper | d4-conf-ijcai-2017-0537 |
| 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; an exact equilibrium always exists. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite set of types \(T\), blocs \(G\), and item categories \(J\), let each type \(t\) belong to a bloc \(g(t)\), have rational mass \(\mu_t\), and have utility \(u_{tj}\) for category \(j\), with \(\sum_t\mu_t=1\). Category \(j\) has rational per-branch supply \(q_j\), represented by \(Nq_j\) indivisible copies for a population of \(N\) branches. Choose positive-bid masses \(x_{tj}\in[0,\mu_t]\), setting \(x_{tj}=0\) when \(u_{tj}=0\). With \(P_j=\sum_t x_{tj}\), bloc \(g\)’s normalized expected utility is \(U_g(x)=\sum_{j:P_j>0}q_j\frac{\sum_{t:g(t)=g}u_{tj}x_{tj}}{P_j}\), with a zero term when \(P_j=0\). Find a feasible profile \(x\) such that \(U_g(x)\ge U_g(x'_g,x_{-g})\) for every bloc \(g\) and every feasible unilateral change \(x'_g\) to its bid masses.
Types record a branch’s complete utility vector and regional-bloc membership; the society is the distribution \(\mu\) over those types. Each bloc controls its types’ positive-bid masses \(x_{tj}\), and each category’s supply scales per branch as \(q_j\). The objective is to find a pure group equilibrium under the mass version of LIKE’s uniform allocation among positive bidders.
The paper’s equilibrium condition may quantify over a different set of coalitions than the fixed regional blocs in the mirror; the regional motivation supports those blocs but does not establish that the deviation conditions match.
fatal: False
The mirror covers Theorem 3’s computation of group equilibria for LIKE. It leaves aside Theorems 1 and 2, the BALANCED LIKE hardness results, the counting results, and equilibria of the repeated game.
The strongest mirror I believe is for computing group equilibria under LIKE, in a large food bank network. The paper itself motivates group behavior with regional charities that coordinate bids and exchange items after allocation. Make a charity’s type its full utility vector over food categories, together with its region. A network can have many branches but comparatively few such types. If there are \(N\) branches, let \(\mu_t\) be the fraction of branches of type \(t\), and let the supply of category \(j\) be \(Nq_j\) indivisible units. Scaling supplies with the population keeps availability per branch meaningful; the continuous object is still the society.
My anchor is Theorem 3, proved in this paper. It states that with general utilities and LIKE, the problem PURE NASH EQUILIBRIUM is in P. The result concerns computing group pure Nash equilibria: for one item, when a group faces \(k\) positive bidders outside it, the proof finds the group’s best set \(H\) by maximizing
\[
\frac{\sum_{a_i\in H}u_{ij}}{|H|+k}.
\]
Sorting utilities makes this computable, and the paper gives an \(O(n^3m)\) procedure for a profile across \(m\) items. This is a finding problem, rather than a claim about counting every equilibrium.
Here is the continuous problem I would hand to a prover: Mass LIKE Group Equilibrium. The input is a finite set of types \(T\), groups \(G\), item categories \(J\), rational masses \(\mu_t\) summing to \(1\), rational utilities \(u_{tj}\), and rational per-branch supplies \(q_j\). A type belongs to one group and has \(u_{tj}=0\) for categories it dislikes. For each group \(g\), type \(t\), and category \(j\), choose \(x_{tj}\in[0,\mu_t]\), the mass of that type bidding positively on every copy of \(j\). Require \(x_{tj}=0\) when \(u_{tj}=0\). Write \(P_j=\sum_t x_{tj}\). Each copy is allocated uniformly among positive bidders; if \(P_j=0\), it is unallocated. The normalized expected utility of group \(g\) is
\[
U_g(x)=\sum_{j\in J}q_j
\frac{\sum_{t\in g}u_{tj}x_{tj}}{P_j},
\]
with a zero term when \(P_j=0\). The task is to output a mass profile \(x\) such that no group can change its own bid masses and increase \(U_g\). Fractional \(x_{tj}\) means that a continuous cohort splits between positive and zero reports; it does not make an individual item divisible.
I expect this problem to be tractable. For a fixed item and fixed competing mass, the group’s choice is the continuous version of the paper’s ratio optimization: maximize a linear numerator over an affine denominator. Its best response has a utility threshold structure: types above the threshold bid, types below it do not, with a possible split at a tie. Thus the finite-agent subset search becomes a search over finitely many type thresholds and masses. The main proof obligation is to show that these best responses can be assembled into an equilibrium in time polynomial in \(|T|\), \(|G|\), \(|J|\), and the input bit length. This is a plausible Class A result, though Theorem 3 itself does not prove the continuous extension.
I would not make the paper’s counting results the anchor for this mirror. In a mass model, equilibrium profiles are real vectors and may form continua; counting all profiles is not a finite counting problem. Counting extreme points could be a worthwhile separate question, but it would change the paper’s target. This mirror covers Theorem 3’s LIKE group-equilibrium computation, not the paper’s BALANCED LIKE results, its counting results, or its repeated-game equilibria.
The weakest point is the coalition interpretation. The continuous model lets a group coordinate a fractional mass of otherwise identical branches across reports; an individual nonatomic branch has no effect on the aggregate. That is a real modeling choice, but it fits the paper’s regional-charity motivation and its group-equilibrium result. The authors might reject it if they intended only individually strategic agents. The other substantial choice is scaling item supplies with branch count, which is necessary for per-capita allocation to survive the population limit.
Theorem 3 is the right anchor, and the strongest objection is that its group equilibrium may not have the same strategic meaning in a continuum. In the finite model, agents are named and groups can coordinate changes to their bids. The proposed mass game instead fixes a finite set of groups and lets each choose fractions of its types. If the theorem’s equilibrium ranges over arbitrary coalitions, this changes which deviations must be ruled out. Treating a group as a nonatomic population also removes each individual’s effect on the bidder count. Scaling supplies with population preserves per-capita allocation, but does not by itself preserve that equilibrium condition.
The best repair is the one the proponent sketches: treat a few large regional blocs as the strategic players, let each bloc control the bidding choices of its continuum of branches, and scale supplies per branch. That is a coherent computational question, and the theorem’s per-item utility-threshold argument makes a tractable result plausible. It is a weaker mirror if the paper’s result concerns arbitrary coalitions rather than a specified partition, but the paper’s regional-charity motivation makes the repair credible.
So I cannot make a strong case that this anchor fails in every scenario. The paper has a named computational result, and its own application supplies a plausible high-multiplicity regime. The objection is that the proposed model may alter the coalition structure; it does not establish that a worthwhile continuous mirror is absent.
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.