Research map / Learning theory and algorithms / Submodular and game algorithms
Learning Lotteries with Minimal Violations from Membership Queries
Paul W Goldberg, Nicholas Teh
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies learning a lottery over m alternatives for n agents with unknown linear halfspace acceptance sets using only binary membership queries, minimizing the number of rejecting agents.
Problem
Choosing a lottery over alternatives that is acceptable to many agents when each agent's acceptable lotteries form an unknown linear halfspace of the simplex and only accept/reject membership queries are available; prior work requires a lottery accepted by all agents, which may not exist.
Approach
Relaxes the goal from finding a lottery accepted by every agent to one that minimizes the number of rejecting agents, and studies query-efficient learning of such near-universally-acceptable lotteries from membership queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase sample size from k=30 to k=120 (ablation) | exact minimization on sample · Separated, n=500 | extra rejection rate (%): 6.81 -> 1.67 | Improved |
| increase sample size from k=120 to k=480 (ablation) | exact minimization on sample · Separated, n=500 | extra rejection rate (%): 1.67 -> 0.43 | Improved |
| raise LP margin eta from 0.02 to 0.05 (ablation) | LP · Separated, k=120 | extra rejection rate (%): 1.96 -> 0.53 | Improved |
| raise LP margin eta from 0.02 to 0.05 (ablation) | LP · Near-threshold, k=120 | extra rejection rate (%): 3.60 -> 9.20 | Hurt |
| use LP with eta=0.05 instead of exact minimization on 120 samples | LP · Separated | extra rejection rate (%): 1.67 -> 0.53 | Improved |
| use all 500 agents instead of 120 sampled for LP (ablation) | LP eta=0.02 · Near-threshold | extra rejection rate (%): 3.60 -> 1.86 | Improved |
| query a fixed set of K agents instead of random sampling | deterministic algorithms · worst-case profile, m>=3 | additive gap: n-K | Hurt |
| choose K=100 agents uniformly at random | sampling algorithm · random instances n=500 | additive gap (agents): 8.46 vs worst case 400 | Improved |
| sample 169 alternatives instead of full lottery when all agents have margin >= eta | sampled lottery · n=1000, m=500 | new rejections: 0 new rejections in 480 trials | Improved |
Closest papers by meaning
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.86)
- Online Fair Division Meets Reordering Buffers (NeurIPS 2026 · similarity 0.85)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.85)
- Smooth Partial Lotteries for Stable Randomized Selection (NeurIPS 2026 · similarity 0.85)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.85)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.84)
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.
