| paper | d4-conf-sagt-2021-0018 |
| 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 14
statement extracted from the paper’s text layer
Given a finite type set \(T\), binary-rational masses \(\mu_t\) summing to \(1\), utilities \(u_{ts}\in[0,1]\), and \(\epsilon\in[3/4,1]\), compute a type-symmetric policy \(q\). Each type-\(t\) agent votes herself with probability \(q_{t,\bot}\); otherwise she selects type \(s\) with probability \(q_{ts}\), and a proxy is sampled from that type’s mass. Delegation continues until a self-voting guru is reached, with utility \(u_{ts}\) for a type-\(t\) agent whose guru has type \(s\), and zero if no guru is reached. Require every agent’s expected utility to be at least \(1-\epsilon\) times her best unilateral-deviation utility, and normalized welfare \(\sum_t\mu_t U_t(q)\) to be at least \(1-\epsilon\) times the supremum welfare over measurable delegation policies.
An atomless society with finitely many types and masses , where agents delegate to a type and the platform samples a proxy from that type’s mass. The decision is a type-symmetric mixed policy ; each agent’s utility is determined by the eventual guru, and welfare is the mass-weighted sum of type utilities.
The type-random proxy rule is not forced by taking the population limit: it replaces choosing a named proxy with choosing a class whose member is sampled. The proponent supplies a plausible platform scenario, but no evidence that this is a credible regime for the paper’s game.
fatal: False
The mirror covers Theorem 14’s algorithm for in the stated range. It does not cover the paper’s named-proxy optimal-welfare hardness result, the existence and tightness results for the best approximate equilibrium, or the fixed-point construction requiring an optimal guru set.
The positive case I trust is narrow: Theorem 14, proved in this paper. It says that for every \(\epsilon\in[3/4,1]\), the narcissistic–avaricious algorithm runs in linear time and returns an \(\epsilon\)-Nash equilibrium with welfare at least \((1-\epsilon)\Opt\). Each agent votes for herself with probability \(p=\frac{1+\sqrt{4\epsilon-3}}{2}\); otherwise, she delegates to an agent giving her maximum immediate utility. This is an algorithmic anchor, not a hardness result.
A continuous counterpart is Type-Mass Liquid-Democracy Bicriteria Search. Its input is a finite set \(T\) of \(\tau\) voter types, binary-rational masses \(\mu_t\geq 0\) summing to \(1\), a rational utility table \(u_{ts}\in[0,1]\), and \(\epsilon\in[3/4,1]\). A type completely specifies an agent’s utility for every possible guru type. The society is atomless, with mass \(\mu_t\) of type \(t\). An agent may vote herself or delegate to a type; delegation selects a member of that type uniformly, and the chain continues until someone votes herself. If it never reaches a guru, utility is zero. This preserves optional, transitive delegation and utility from the eventual guru while making proxies within a type interchangeable.
For a type-symmetric mixed policy \(q\), write \(q_{t,\bot}\) for the probability a type-\(t\) agent votes herself, and \(q_{ts}\) for the probability she delegates to type \(s\). The path through these policies is a Markov chain on types with guru states: let \(h_{ts}(q)\) be the probability that a type-\(t\) agent’s chain ends at a guru of type \(s\). Her expected utility is \(U_t(q)=\sum_s h_{ts}(q)u_{ts}\), and normalized welfare is \(W_\mu(q)=\sum_t\mu_t U_t(q)\). Let \(\Opt_\mu\) be the supremum of welfare over all measurable delegation profiles of this society, including profiles that assign different strategies to members of the same type.
The problem is to return a type-symmetric policy \(q\) such that each individual’s utility is at least \(1-\epsilon\) times her best unilateral-deviation utility, and \(W_\mu(q)\geq(1-\epsilon)\Opt_\mu\). The row \(q_t\) is the action variable; mass gives the share of society receiving each type’s expected utility.
The regime is a large online assembly or recurring civic platform with many members but relatively few complete trust-and-utility signatures: \(N\gg\tau\), with many members of each supported type. For example, users might value representation by expertise or affiliation class, and the platform draws a proxy from the chosen class. This is a type-anonymous regime, not a claim about elections where every proxy is valued as a named individual. I think the authors could recognize it as their game in a large-population, interchangeable-proxy setting: the strategic object is still transitive delegation to an eventual guru, and both individual incentives and aggregate welfare remain the questions.
The guarantee carries over directly. Set \(M_t=\max_s u_{ts}\), choose \(s_t\) attaining it, and use \(q_{t,\bot}=p\), \(q_{t,s_t}=1-p\). The immediate event that an agent delegates to \(s_t\) and that this proxy votes herself gives utility at least \(p(1-p)M_t=(1-\epsilon)M_t\). No deviation can yield more than \(M_t\), and \(\Opt_\mu\leq\sum_t\mu_t M_t\). Thus the policy has the stated incentive and welfare guarantees. Scanning the explicit utility table and outputting the sparse type policy takes \(O(\tau^2+L)\) time, where \(L\) is the mass and utility bit length. I expect this mirror to be Class A. Its gain is compression from \(N\) named agents to \(\tau\) types, not a new optimization technique or a claim that mass fractions alone create tractability.
I would not use the paper’s exact-optimum hardness result as a second anchor here. Its directed-dominating-set reduction counts selected guru agents; in an atomless type pool, a positive but arbitrarily small share can act as a potential guru pool. The discrete reduction therefore does not supply a continuous hardness proof. That leaves a worthwhile follow-up: determine the complexity of exact optimal welfare in this type-pool model and whether any form of the reduction survives. Other questions are whether type structure yields guarantees for \(\epsilon<3/4\), and how fast the finite clone game approaches the type-mass model.
The weakest point is the pool semantics. The original game lets an agent target a named proxy; this mirror lets her target an interchangeable type and samples a member of that type. That is a plausible regime for some delegation systems, but it does not cover identity-sensitive trust networks. The case is strongest as a focused mirror of Theorem 14, not as a continuization of the paper’s whole model.
The only computational anchor is Theorem 14, and it qualifies: it gives a linear-time algorithm for an \(\epsilon\)-Nash equilibrium with a welfare guarantee. So the strongest objection has to be about whether the proposed model mirrors that game.
The type-pool model changes what delegation means. In the paper, an agent chooses a particular proxy, whose subsequent choices determine the outcome. In the proposed model, choosing a type draws a random member of it. A utility table \(u_{ts}\) records how type \(t\) values a guru of type \(s\), but it does not make the members of \(s\) interchangeable when their strategies differ. For instance, a proxy who votes herself and one who delegates into a cycle can have the same type and give the same direct utility, yet choosing between them matters in the paper’s game. The stated guarantee is valid for the random-proxy game, but the paper’s named-proxy game has not been carried over.
Keeping named proxies creates a different problem in the atomless limit. A single representative has zero population mass but can still receive everyone’s delegation. For each type \(t\), choose a representative of a type \(s_t\) maximizing \(u_{ts}\); have other members of \(t\) delegate to that representative. The welfare supremum is then \(\sum_t \mu_t\max_s u_{ts}\), since the selected representatives contribute zero mass. That makes the welfare benchmark easy and removes the population-level tradeoff that the finite game’s optimum can have. Adding a positive minimum mass or capacity for gurus could retain that tradeoff, but it would add a constraint absent from the paper.
This leaves a fork: preserving named delegation makes the welfare benchmark collapse; avoiding that collapse by sampling a proxy from a type changes the delegation game. That is the best case against the anchor. It is still limited: a platform that actually delegates to a randomly selected member of an expertise class would make the type-pool model plausible, and the proposed proof appears to establish its guarantee. I cannot honestly conclude that no worthwhile mirror exists in any scenario; the negative case is weak precisely because that class-based setting may be a sensible problem for the authors.
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.