AI Paper Atlas

Research map / Learning theory and algorithms / Submodular and game algorithms

Learning Lotteries with Minimal Violations from Membership Queries

Paul W Goldberg, Nicholas Teh

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Fair division of indivisible goods

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 changedWhereMeasuredEffect
increase sample size from k=30 to k=120 (ablation)exact minimization on sample · Separated, n=500extra rejection rate (%): 6.81 -> 1.67Improved
increase sample size from k=120 to k=480 (ablation)exact minimization on sample · Separated, n=500extra rejection rate (%): 1.67 -> 0.43Improved
raise LP margin eta from 0.02 to 0.05 (ablation)LP · Separated, k=120extra rejection rate (%): 1.96 -> 0.53Improved
raise LP margin eta from 0.02 to 0.05 (ablation)LP · Near-threshold, k=120extra rejection rate (%): 3.60 -> 9.20Hurt
use LP with eta=0.05 instead of exact minimization on 120 samplesLP · Separatedextra rejection rate (%): 1.67 -> 0.53Improved
use all 500 agents instead of 120 sampled for LP (ablation)LP eta=0.02 · Near-thresholdextra rejection rate (%): 3.60 -> 1.86Improved
query a fixed set of K agents instead of random samplingdeterministic algorithms · worst-case profile, m>=3additive gap: n-KHurt
choose K=100 agents uniformly at randomsampling algorithm · random instances n=500additive gap (agents): 8.46 vs worst case 400Improved
sample 169 alternatives instead of full lottery when all agents have margin >= etasampled lottery · n=1000, m=500new rejections: 0 new rejections in 480 trialsImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy