An Isotonic Mechanism for Overlapping Ownership

Motivation

• Around 10,000 full-paper submissions at major conferences reflect nearly tenfold growth over a decade, while reviewer capacity and experience lag, contributing to inconsistent peer review.NeurIPS experiments reported 49.5% and 50.6% inconsistency probabilities in 2014 and 2021, respectively.Source: §1 · p. 1
• Overlapping ownership makes naive owner-specific score adjustment strategically unsafe because co-owners’ rankings can affect items outside an owner’s portfolio.The paper therefore seeks a mechanism that elicits useful self-evaluations despite these incentive interactions.Source: §1 · pp. 2, 4

Method

• The Isotonic Mechanism partitions ownership structures into blocks with common owners, then uses within-block item rankings to calibrate pre-given review scores.It targets relative rankings because they can be less noisy than absolute owner-provided scores.Source: §1 · pp. 3–4

Mechanism guarantees

• Truthfully reporting rankings by all owners forms a Nash equilibrium, extending earlier single-owner truthfulness results to overlapping ownership.The mechanism’s proof uses majorization, and the truthful equilibrium is payoff dominant.Source: §1 · pp. 4–5
• Within personalized-partition isotonic mechanisms, every truthful design has an equivalent global-partition representation, so truthful mechanisms cannot exploit cross-block ordering information in this class.The result is a within-class reduction and does not rule out truthful mechanisms outside the studied class.Source: §1 · p. 5

Partition optimization

• Partition selection trades off informativeness against robustness because larger blocks can reduce the number of jointly ranking owners.The paper frames informativeness as an objective and robustness as a constraint for statistical-efficiency optimization.Source: §1 · p. 5
• A nearly linear-time greedy algorithm finds a partition that is near-optimal for every criterion in the considered class, although exact optimization is NP-hard.The algorithm achieves constant-ratio approximation simultaneously across the criteria.Source: §1 · p. 5

Experiments

• Synthetic and ICLR review experiments show that the proposed mechanism improves estimation performance relative to original review scores across varied settings.The application is designed to supplement reviewer scores and help allocate scarce reviewing attention.Source: §1 · pp. 2, 6

Problem Formulation

• The model contains many owners and items with overlapping ownership, represented by item-owner incidence relations in a bipartite graph.Owners may share items, and the abstract owner/item model also covers project, proposal, and creative-work review settings.Source: §2 · p. 6
• The calibration mechanism combines noisy review scores with rankings elicited from owners to improve estimates of ground-truth item evaluations.In conference review, ground-truth scores represent community mean evaluations, while raw scores are noisy estimates produced by sampled experts.Source: §2 · p. 6
• Each owner reports a full ranking of her owned items before reviews are realized, after which the mechanism outputs adjusted review scores.If an owner does not report, the mechanism uses a uniformly random ranking.Source: §2 · p. 7
• Truthfulness is defined through Bayes-Nash equilibrium, requiring truthful reporting to be optimal for every owner given the other owners’ reports.The framework focuses on unilateral deviations and restricts attention to truthful mechanisms using a revelation-principle argument.Source: §2 · p. 7
• The theoretical analysis assumes informed owners know their items’ ground-truth ranking, exchangeable review noise, and additive non-decreasing convex owner utility.The informed-owner assumption is an idealized benchmark; the paper discusses a single-owner relaxation and limitations of the assumptions later.Source: §2 · pp. 7–8

3 An Isotonic Mechanism for Completely Overlapping Ownership

• Isotonic regression produces scores consistent with an owner’s ranking while minimizing squared distance from the raw review scores.The estimator solves a convex program using the reported ordering and the raw score vector.Source: §3 · p. 8
• The mechanism elicits each owner’s ranking, computes ranking-calibrated scores, and can weight owners according to expertise, reputation, or track record.Equal weights are possible, while personalized owner credentials are left to the practitioner.Source: §3 · p. 8

3.1 Truthfulness under Completely Overlapping Ownership

• Under completely overlapping ownership, truthful reporting forms a Bayes-Nash equilibrium and is payoff-dominant under Assumptions 1, 2, and 3.Every owner receives at least as much utility at the truthful equilibrium as at any other Nash equilibrium.Source: §3.1 · p. 9
• Behavioral-game-theory evidence connects the truthful outcome to common-interest games, where people often select the payoff-dominant action profile.The paper relates this behavior to empirical human preferences, self-reinforcing expectations, and team reasoning.Source: §3.1 · pp. 9–10

3.2 Non-truthfulness Beyond Completely Overlapping Ownership

• The partial-overlap failure motivates a different aggregation approach rather than simply reweighting owners’ contributions.A sole owner may fully determine one item but cannot fully determine another shared item without ignoring other owners or raw review scores.Source: §3.2 · pp. 10–11
• Averaging owner-specific calibrated scores under partial overlap is not truthful because owners can exploit uneven influence across their items.In the example, an owner promotes a weak item by using the reputation of a strong item; reweighting cannot fully resolve the mismatch without weakening owner information.Source: §3.2 · p. 10

4 Restoring Truthfulness via Partitioning

• Mechanism 2 forms a Bayes-Nash equilibrium for truthful within-block rankings under any partition and parameter choice.Each block elicits rankings only from owners who completely own it, and score estimates are independent across blocks.Source: §4 · p. 12

4.1 Reduction from Personalized Partition to Global Partition

• Within the personalized-partition isotonic class, every truthful mechanism can be replaced by a truthful global-partition mechanism preserving all truthfully elicited pairwise comparisons.This characterization does not rule out truthful mechanisms outside the studied class.Source: §4.1 · pp. 13–14

4.2 Partition Optimization and Its Hardness

• Larger blocks improve informativeness, while more owners per non-singleton block improve robustness when perception noise creates conflicting rankings, creating a statistical tradeoff for partition design.Risk is measured by expected squared estimation error; an L-strong partition requires at least L shared owners for every non-singleton block.Source: §4.2 · pp. 14–16
• Partition optimization is NP-hard for maximizing the size-focused objective subject to 1-strongness.Any L-strongness constraint can first be reduced to 1-strongness on a transformed ownership instance.Source: §4.2 · pp. 16–17

4.3 Fast Greedy Partition with Robust Approximation Guarantees

• The greedy 1-strong partition algorithm repeatedly selects the largest residual ownership set, adds it as a block, and removes its items from further consideration.It initializes an empty partition and continues until all items are selected.Source: §4.3 · p. 17
• The greedy procedure iteratively selects the largest residual item set owned by an owner, requiring almost-linear input time and being essentially as fast as possible up to a log(m) factor.The algorithm is agnostic to the partition objective while retaining robust quality across the wellness-function class.Source: §4.3 · p. 17
• The method and its constant approximation guarantees extend via Proposition 3 to finding optimal L-strong partitions in O time.The supplied passage truncates the full runtime expression after O.Source: §4.3 · p. 17
• Algorithm 4 runs in O(N log m) time, outputs a 1-strong partition, and simultaneously achieves a c(w)-approximation for every monotone convex wellness function w.Here N is the total number of owner-item pairs; the guarantee is formalized by Theorem 3.Source: §4.3 · pp. 17–18
• The greedy partition guarantees at least 1/2 of both comparison-focused and size-focused optima, and a 1/α fraction for polynomial wellness functions w(x) = x^α.These ratios are objective-agnostic and tight for every monomial objective f(S) = Σ_k=1^K |S_k|^α with α > 1.Source: §4.3 · p. 18

5.1 Experiment Setups: Datasets, Baselines and Metrics

• ICLR experiments use publicly available 2021–2023 ownership and review data with surrogate ground truth, while ICML uses a separate one-shot evaluation with observed author rankings.The two datasets’ numerical results are not directly comparable because their evaluation designs differ.Source: §5.1 · p. 19
• The mechanism is evaluated against raw scores, randomized and greedy partitions, and an information-rich oracle all-owner benchmark using MSE and top-30% accuracy.The oracle uses all eligible owners’ rankings but is not incentive compatible under partial overlap.Source: §5.1 · p. 19
• Real-data experiments use L = 1 because requiring L = 2 leaves substantially fewer calibrated papers and pairwise comparisons.The broader L tradeoff is therefore studied in controlled synthetic ownership structures.Source: §5.1 · pp. 19–20, §5.2 · p. 20

5.2 Experiment Results

• Across three ICLR years and seven noise levels, the greedy method reduces MSE by 21–33% relative to raw scores and recovers 16–21% of surrogate top-30% papers missed by raw selection.It consistently outperforms randomized partitions and remains close to the oracle all-owner benchmark.Source: §5.2 · p. 20, Figure 5 · p. 21
• Synthetic binary-tree experiments show that larger blocks work better under low perception noise, whereas smaller blocks can work better under high perception noise.At intermediate noise, the best block size balances informativeness from pairwise comparisons against robustness from more authors per block.Source: §5.2 · p. 21, Figure 6 · p. 22
• Both partition schemes reduce MSE relative to the baseline in the one-shot ICML 2023 evaluation using observed author rankings.The evaluation uses the least-confident review as the raw score and higher-confidence reviews as the surrogate ground truth.Source: §5.2 · p. 21, Table 5 · p. 22

• The Isotonic Mechanism has a polynomial-time ownership-set partitioning algorithm with a constant-factor approximation to the hard-to-compute optimal partition.This supports practical implementation of the mechanism.Source: §6 · p. 22
• Randomized partitions use rankings from more eligible owners but produce less informative partitions than the deterministic greedy partition on ICLR 2021–2023 ownership graphs.The comparison identifies owner reach and informativeness as a design trade-off.Source: §6 · p. 23, Table 6 · p. 23
• Maximizing owner reach can substantially reduce informativeness: in the constructed example, the reduction factor is n/2.The single-block partition maximizes informativeness but reaches only 1/(K + 1) owners, whereas pair blocks maximize owner reach.Source: §6 · p. 23
• Exact truthfulness assumes owners know the ground-truth ranking of their items, while ranking elicitation is presented as a compromise between risky fine-grained scores and overly coarse information.The assumption does not require owners to know precise ground-truth scores.Source: §6 · p. 23
• With noisy owner perceptions, a single owner’s perceived ranking is optimal under conditional exchangeability of review-score errors relative to perceived scores.This condition is not implied merely by additive exchangeable perception noise, and conflicting co-owner perceptions can break equilibrium reporting of perceived rankings.Source: §6 · p. 24
• The model’s exchangeable-noise and convex-utility assumptions have practical motivation but remain scope boundaries, including limited treatment of concave upper-score utilities, heterogeneous values, ownership manipulation, and group collusion.The paper positions practice-oriented deployment and further real-world experiments as future work.Source: §6 · pp. 25–26

• For almost every information realization, any measurable ranking report is no better than a ranking consistent with the owner’s perceived scores.The proof fixes the information realization, applies exchangeability to the conditional noise distribution, and uses the finite report space.Source: A Proof of Proposition 5 · p. 31
• Randomized deviations cannot improve conditional expected utility because they are mixtures of deterministic reports.Taking expectations yields the corresponding ex-ante optimality result.Source: A Proof of Proposition 5 · p. 31

• Under this induced utility, the owner’s expected total payoff is non-decreasing and convex, so the truthful Nash-equilibrium result applies to the clipped threshold model.The payoff is separable across items under the stated noise structure.Source: B A Microfoundation for Assumption 3 · pp. 31–32
• A clipped threshold payoff induces non-decreasing convex utility in adjusted scores when the area-chair noise CDF is concave on the relevant threshold interval.The same property extends to non-negative step functions of multiple decision thresholds.Source: B A Microfoundation for Assumption 3 · p. 31
• If the base payoff is already non-decreasing and convex, area-chair noise preserves both properties without requiring a specific noise distribution.This complementary observation applies under the stated independence and integrability conditions.Source: B A Microfoundation for Assumption 3 · p. 32
• For bounded uniform area-chair noise with c ≥7 on the [0, 10] score range, the induced utility is non-decreasing and weakly convex across the full calibration range.The sufficient bound keeps the utility linear throughout the range, although it is not necessary for convexity.Source: B A Microfoundation for Assumption 3 · p. 33
• The reduced-form score-based utility bridges outcome rewards and calibrated scores but does not claim global convexity; richer intermediate-convex and upper-score-concave utilities remain future work.The paper also discusses rating-scale redesign as a way to encourage convexity near the acceptance margin.Source: B A Microfoundation for Assumption 3 · pp. 33–34
• Figure 7 shows oral-acceptance probability is approximately convex in review score, while overall acceptance is not globally convex and expected utility follows a convex-then-concave pattern.The evidence supports Assumption 3 mainly on the score region below acceptance thresholds.Source: B A Microfoundation for Assumption 3 · pp. 33–34, Figure 7 · p. 34

• Majorization and the Hardy–Littlewood–Pólya inequality convert isotonic-score ordering into utility comparisons for convex functions.The proof uses lemmas showing that aligned score and noise orderings majorize permuted alternatives.Source: C Proof of Theorem 1 · p. 35
• With other owners truthful, exchangeable review noise and isotonic projection inequalities show that an owner cannot improve utility by misreporting her ranking.The comparison is established pointwise in the noise vector before taking expectations.Source: C Proof of Theorem 1 · pp. 35–37
• The truthful strategy profile is a Bayes-Nash equilibrium because each owner’s truthful report is a best response when the other owners report truthfully.The argument applies the single-owner truthfulness result within the multi-owner mechanism.Source: C Proof of Theorem 1 · p. 36
• Truthful equilibrium gives every owner at least as much expected utility as any other equilibrium, with the proof using Jensen’s inequality, averaging, and the single-owner theorem.The comparison extends over mixed strategy profiles.Source: C Proof of Theorem 1 · p. 37
• The payoff-dominance argument is stronger than equilibrium comparison, but truthful reporting is not necessarily a dominant strategy or a unique equilibrium.These conclusions concern strategy profiles beyond unilateral best responses to arbitrary co-owner reports.Source: C Proof of Theorem 1 · pp. 37–38

D Proof of Proposition 1

• Isotonic regression on a block of size s has squared-error risk σ2H_s, where H_s = ∑_{k=1}^s 1/k.The risk follows from the block cone's statistical dimension.Source: D Proof of Proposition 1 · p. 38
• For block sizes (s_1, . . . , s_K), total squared-error risk is additive as σ2∑_{k=1}^K H_{s_k}.The blockwise risk identity underlies the partition comparison.Source: D Proof of Proposition 1 · p. 38
• The wellness function is w(s)=σ2(s−H_s), with w(0)=w(1)=0 and strictly increasing, strictly convex increments for s≥1.Its increments are positive and strictly increasing on the non-negative integers.Source: D Proof of Proposition 1 · p. 38
• Wellness is Schur-convex in block sizes and is maximized by the most unequal split.Transferring size from a smaller block to a larger block increases total wellness.Source: D Proof of Proposition 1 · p. 38
• An equal two-block split has risk ratio 2H_{n/2}/H_n → 2, so inverse-risk statistical efficiency is asymptotically halved.Splitting a single block of size n into n/2 and n/2 therefore substantially increases risk.Source: D Proof of Proposition 1 · p. 39

E Proof of Proposition 2

• Risk for L averaged isotonic estimates is non-increasing in L, with strict decrease when perception noise produces distinct estimates with positive probability.The bias term is independent of L, while the variance term scales with averaging.Source: E Proof of Proposition 2 · p. 39
• Under Assumption 1, owners report π⋆ with probability one, making the conditional isotonic estimate deterministic and eliminating the variance term.Thus the strict-decrease condition from perception noise is not met under truthful reporting.Source: E Proof of Proposition 2 · p. 39

F Proof of Proposition 3

• For any L-strong partition in an ownership graph, the proof constructs a transformed graph whose owners are all L-element subsets of the original owners.The transformed edges connect an item to a subset-owner when every member of that subset owns the item.Source: F Proof of Proposition 3 · p. 39
• The transformed graph preserves each L-strong partition as an equivalent 1-strong greedy partition.The proof verifies that corresponding blocks are unchanged under the construction.Source: F Proof of Proposition 3 · p. 39

G Proof of Proposition 4

• With weight w(x)=max{x,1}−1, any partition with K blocks has objective obj(S)=n−K.The optimization therefore favors partitions using fewer blocks.Source: G Proof of Proposition 4 · p. 39
• Optimizing this objective is at least as hard as finding a minimum set cover.The reduction maps set-cover instances to bipartite ownership graphs.Source: G Proof of Proposition 4 · p. 40
• For a set-cover instance, the construction uses items as one vertex class, subsets as the other, and edges for item membership.A partition with K* blocks corresponds to a set cover of size K*, and vice versa.Source: G Proof of Proposition 4 · p. 40
• Selecting one owner vertex from each partition block yields K* subsets covering all n items.This supplies the reverse direction of the reduction from an optimal partition to a set cover.Source: G Proof of Proposition 4 · p. 40

H Proof of Theorem 2

• Mechanism 3 is truthful only under partition conditions requiring balanced owner influence within blocks and compatible weights across overlapping blocks.The proof establishes equivalence between the two conditions and shows unbalanced influence creates a profitable ranking misreport.Source: H Proof of Theorem 2 · pp. 40, 41, 43
• The resulting Mechanism 2 elicits at least as much ranking information as the original Mechanism 3 and therefore has no worse statistical efficiency.After merging and removing zero-weight blocks, the procedures coincide with Mechanism 2 except that all owners fully owning each block participate.Source: H Proof of Theorem 2 · pp. 41–42
• The MERGE operator combines unnecessarily isolated blocks while preserving valid parameters and strictly increasing the ranking information elicited.Merged-block orderings are incorporated into calibration, so the process terminates with a partition suitable for Mechanism 2.Source: H Proof of Theorem 2 · p. 41

I Proof of Theorem 3

• The ownership relation is modeled as a bipartite graph whose item-owner edges encode ownership, while each partition block’s complete neighboring owner set defines a 1-strong mechanism block.Blocks with at most one item or no complete owner are assigned raw review scores.Source: I Proof of Theorem 3 · pp. 43–44
• The greedy algorithm repeatedly selects the largest residual item set owned by one owner, producing a 1-strong partition whose approximation guarantee is proved by induction on the number of owners.The proof compares the greedy first choice with an optimal partition and reduces the remaining instance by deleting the selected owner and adjacent items.Source: I Proof of Theorem 3 · p. 44
• When every block’s optimal-partition value is at most 1, convexity implies every 1-strong partition is at least as good as the optimum, making the greedy algorithm optimal.This special case handles the otherwise potentially unbounded term in the approximation analysis.Source: I Proof of Theorem 3 · p. 45
• The approximation-ratio lower bound invokes the mediant inequality together with Technical Lemma 6 for p ≥2.The supplied passage indicates this argument applies for k ≥2.Source: I Proof of Theorem 3 · p. 45
• Algorithm 4 runs in O(|E| log m) time using red-black trees to maintain maximum residual item sets and update affected owners.Each round removes at least one owner’s residual item set, and tree operations take O(log m).Source: I Proof of Theorem 3 · p. 45
• Lemma 6 relies on convexity of w and its left derivative, together with w(p) > 0 and w(0) = 0.The convexity argument establishes the stated derivative-based inequality for any k.Source: I Proof of Theorem 3 · pp. 45–46

• For α-th degree polynomial weights, the guarantee approaches 1/α as M tends to infinity, matching the worst-case approximation guarantee.Source: §I.1 · pp. 46–47
• The greedy algorithm’s α-approximation guarantee is provably tight for every weight in the monomial class.Source: §I.1 · pp. 46–47
• The worst-case construction uses M disjoint owner item sets plus L overlapping owners arranged so greedy selects the overlapping sets first.Source: §I.1 · p. 46
• Greedy ordering follows successive largest remaining item sets, with the first M owners selected only after the overlapping owners’ residual sets shrink.Source: §I.1 · p. 46
• Comparing the greedy objective with the partition selecting only the first M owners yields the approximation-ratio bound used in the tightness argument.Source: §I.1 · pp. 46–47
• Although optimal partitioning is NP-hard for a size-focused objective, the hardness of finding an optimum under the α-th degree polynomial objective remains open.Source: §I.1 · p. 47

• The greedy partition generally improves top-1.5% and top-5% accuracy over baseline and randomized methods under varying ICLR review noise.Source: J Additional Experiments · p. 47, Figure 9 · p. 48