Research map / Learning theory and algorithms / Submodular and game algorithms
Incentive-Compatible Classification
Yakov Babichenko, Oren Dean, Moshe Tennenholtz
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow agents to issue more reviews, increasing Δ | IC classification mechanisms · α-classification | worst-case coincidence ratio: Q_{\alpha,\Delta}\leq 1-m | Hurt |
| Lower the selected fraction α | IC classification mechanisms · α-classification | worst-case coincidence ratio: 2\alpha-1 | Hurt |
| Use the three-category mechanism when Δ=o(n) | α-classification · α-classification, Δ=o(n) | worst-case coincidence ratio: \alpha-\dfrac{\Delta}{n} | Improved |
| Replace the deterministic borderline decision with independent selection at probability 1/2 | Three-category mechanism · α-classification | expected worst-case coincidence ratio: \alpha-\dfrac{\Delta}{n} | Improved |
| Classify borderline agents by their top-half rank after setting their own reviews to −1 | Three-category mechanism · α-classification, Δ≤min{αn/3,(1−α)n/3} | worst-case coincidence ratio: \alpha-\dfrac{3\Delta}{n} | Improved |
| Permit unbounded review out-degree | IC classification mechanisms · α-classification, α≥1/2 and Δ≥2(1−α)n | worst-case coincidence ratio: Q_{\alpha,\Delta}=2\alpha-1 | Hurt |
| Permit nearly complete review out-degree when α<1/2 | IC classification mechanisms · α-classification, Δ=(1−o(1))n | worst-case coincidence ratio: Q_{\alpha,\Delta}=0 | Hurt |
| Ignore all reviews and classify every agent as worthy | Complete mechanism · α-classification | worst-case coincidence ratio: 2\alpha-1 | Mixed |
| Ignore all reviews and select each agent independently with probability 1/2 | Independent random 1/2 mechanism · α-classification | expected worst-case coincidence ratio: 0 | No clear effect |
| Select only absolutely worthy agents instead of also selecting absolutely unworthy agents and randomizing borderline agents | Three-category probabilistic mechanism · α-classification, Δ≤αn | alternative coincidence measure Q': \alpha-\dfrac{\Delta}{n} | Improved |
Closest papers by meaning
- Impartial Selection with Predictions (NeurIPS 2025 · similarity 0.85)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.84)
- Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification (NeurIPS 2024 · similarity 0.83)
- Mechanism design augmented with output advice (NeurIPS 2024 · similarity 0.83)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.83)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
