| paper | d4-conf-ijcai-2022-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Such a decentralized Thompson-sampling policy exists under the stated exact public-matrix model. It satisfies the stronger regret upper bound $R_p(T)\le O(m^2+L+\log(\tau+1)+\log(1/\Delta))$ with the required polynomial per-employer, per-round computation. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finite employer and worker type sets \(P,A\), rational employer masses \((\alpha_p)_{p\in P}\) summing to \(1\), per-capita worker supplies \((\beta_a)_{a\in A}\) with total supply at least \(1\), known worker-type priorities over employer types, and fixed but policy-unknown Bernoulli reward means \((\mu_{p,a})\) with positive minimum gap \(\Delta\), consider atomless employers who learn from their own feedback and face priority-based acceptance at each round. Is there a decentralized Thompson-sampling policy, with per-employer computation polynomial in \(|P|,|A|,L,1/\Delta\), whose expected regret for every employer type \(p\)—measured against its minimum per-capita payoff over stable mass assignments, multiplied by \(T\)—is \(O(\operatorname{poly}(|P|,|A|,L,1/\Delta)\log^2 T)\), uniformly in the absolute population size?
A repeated atomless hiring market with rational employer-type masses and per-capita worker-type supplies. Employers of each base type share reward means and learn independently from private histories; worker types apply their known priorities to incoming mass. The market state includes the distribution of posterior histories within each base type, and regret is measured against the type’s least-favorable stable mass assignment.
Preserving decentralized learning requires tracking a horizon-growing distribution of private posterior histories; the proposed flow structure does not show how to compress or efficiently analyze that distribution.
fatal: False
Covers Theorem 1’s player-pessimal stable-regret guarantee for CA-TS; leaves the experiments and the paper’s discussion of player-optimal stable regret untouched.
The strongest honest case is one anchor: Theorem 1, proved in this paper. It is the paper’s named guarantee for CA-TS; the paper gives no comparable named hardness result to anchor instead.
Theorem 1 concerns \(N\) players and \(K\) arms, with \(N\le K\). Each player has unknown rewards \(\mu_{i,j}\), each arm has a known ranking of the players, and rejected players receive zero reward. CA-TS uses Beta posteriors and its conflict-avoidance and delay steps. Regret is measured against the player-pessimal stable matching: \(R_i(T)=T\mu_{i,m_i}-\mathbb{E}[\sum_{t=1}^{T}X_{i,A_i(t)}(t)]\), where \(m_i\) is player \(i\)’s least-favourite arm among stable matchings. With \(\rho=\lambda^{N-1}(1-\lambda)\), minimum nonzero reward gap \(\Delta\), and \(\Delta_{i,\max}=\mu_{i,m_i}\), Theorem 1 gives each player a regret bound of order
\[
O\!\left(\frac{N^5K^2\log^2 T}{\rho N^4\Delta^2}\,\Delta_{i,\max}\right).
\]
It also gives an explicit bound depending on any \(\varepsilon\) with \(\Delta-2\varepsilon>0\), including a universal constant \(C\) and a term involving \(1/\varepsilon^6\). The result is a regret guarantee, not a worst-case complexity classification.
My lead mirror is Continuous CA-TS Stable-Regret Learning. Consider a repeated hiring market with finitely many employer types \(P\) and worker types \(A\). Employer types have rational masses \(\alpha_p\) summing to one; worker types have rational supplies \(\beta_a\) with total supply at least one. A type is the complete preference-and-capacity profile used by the market: employers of type \(p\) share unknown reward means \(\mu_{p,a}\) over worker types, while each worker type \(a\) has a known priority ranking over employer types. Assume Bernoulli rewards and a positive minimum gap \(\Delta\). The regime is many employers and workers but relatively few distinct types—for example, recurring cohorts of similar job postings and applicants with similar credentials.
Each infinitesimal employer independently runs the paper’s Thompson-sampling policy from its own observations and posterior. Employers choose worker types; worker capacity is allocated by priority, with ties within a type split atomlessly. Accepted employers receive rewards; rejected employers receive zero. The market’s state is the distribution of individual posterior histories within each preference type. Thus the mass model retains private learning and blocking rather than pooling observations and instantly revealing a type’s reward means. Its benchmark is a player-pessimal stable flow of mass, and its per-type regret is the benchmark payoff per unit of employer mass times \(T\), minus expected reward mass collected over \(T\) rounds.
The question to hand a prover is: given these rational type masses, supplies, reward means, priorities, a gap bound, and horizon \(T\), can a decentralized policy with polynomial per-agent work in \(|A|\) achieve per-type stable regret bounded by \(\mathrm{poly}(|P|,|A|,L,1/\Delta)\log^2 T\), with no dependence on the absolute number of agents? A solution is a policy and a proof of a uniform bound for every employer type, or a lower bound showing why such a guarantee is impossible. My forecast is tractable (Class A) for fixed finite type support: the type-level allocation and stable benchmark have a flow structure, and the population limit gives a natural setting for analyzing aggregate blocking. Theorem 1 does not establish that forecast.
The authors could plausibly recognize this as their problem at scale. It keeps the unknown employer preferences, decentralized repeated choices, worker-side priorities, rejection feedback, stable benchmark, and regret objective. Mass is the natural description when the market consists of large cohorts sharing the same problem-relevant profile. The mirror covers Theorem 1’s player-pessimal stable-regret result; it does not extend the claim to player-optimal regret, which the paper identifies as unresolved.
The weakest point is substantial: Theorem 1’s \(\rho\) is the probability that a particular player explores while all \(N-1\) others delay, and \(\rho\) shrinks exponentially with \(N\). In an atomless population with independent delays, the event that every other agent delays has probability zero. So the finite-market proof cannot simply be normalized or sent to a limit. A new aggregate analysis—or a policy redesign—would be needed. There is also a fit question for ChoCo: the anchor studies regret and learning, rather than the static worst-case complexity questions most central to the programme. The mirror remains a credible positive case because it poses a precise population-scale version of the paper’s own algorithmic objective, but its tractability is an open target, not a consequence of the theorem.
Theorem 1 is the only strong anchor. It proves a regret bound for CA-TS, but it does not classify the complexity of a computational problem: it says how regret grows with the horizon, gap, and market size. The paper gives no runtime bound or finite-input optimization problem whose complexity could be mirrored. Its central contribution is statistical analysis of a decentralized learning process.
A recurring hiring market with a few employer and worker profiles is a credible high-multiplicity regime. The individual-identity objection does not defeat the mirror either: the benchmark and regret can be averaged by employer type. The difficulty is that a faithful continuum model cannot describe each exogenous type by a single mass. Employers of that type acquire different private posterior histories and make different randomized choices. Preserve those histories, and the model needs a distribution over endogenous learning states that evolves over time; its state complexity can grow with the horizon. Pool observations within each type to keep a small state, and the agents no longer run the paper’s decentralized Thompson-sampling process.
That leaves a legitimate continuous-population question, but its object is a mean-field learning dynamic over posterior states. The per-agent policy is local; the central challenge is how congestion and private learning shape aggregate regret. Computing a stable mass flow would capture the static allocation, but would not capture Theorem 1’s learning guarantee. Nor is there an evident role for the programme’s central machinery—complexity classifications and continuous optimization over mass transfers. The mirror therefore appears to belong more naturally to mean-field bandit learning than to ChoCo’s computational-complexity programme.
The theorem’s factor \(\rho=\lambda^{N-1}(1-\lambda)\) tending to zero as the market grows is not, by itself, an objection: a changed or failed bound could be a worthwhile result. It does show, though, that a continuum analysis would need to study a different aggregate event structure, rather than translate the paper’s finite-market guarantee into masses.
This is a case against the mirror’s fit with ChoCo, not proof that no useful continuous-population study exists. The cohort model is sensible, and the resulting learning question could matter in its own field. The negative case is strongest when “worthwhile” means a contribution to ChoCo’s stated computational programme; the universal claim that no scenario could yield a worthwhile mirror is harder to sustain.
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.