쿼리를 이용한 만장일치로 수용 가능한 로터리 학습

Learning Unanimously Acceptable Lotteries via Queries

많은 고위험 인공지능 시스템은 모든 이해관계자가 해당 시스템을 자체 최소 기준에 부합하는 것으로 판단해야만 배포될 수 있습니다. 유한한 옵션 집합에 대한 랜덤화를 사용하는 경우, 이는 실현 가능성 문제가 됩니다. 즉, 모든 이해관계자의 수용 기준을 충족하는 옵션 로터리가 존재하는가입니다. 본 연구에서는 알고리즘이 로터리를 제안하고 이진 형태의 수락/거부 피드백만 받는 쿼리 모델을 사용합니다. 본 연구에서는 만장일치로 수용 가능한 로터리를 찾거나 실현 불가능함을 증명하는 결정론적 및 랜덤 알고리즘을 제시합니다. 적응성을 통해 많은 이해관계자의 제약 조건을 파악하는 것을 피할 수 있으며, 랜덤화를 통해 전체 정보 수집에 비해 예상되는 정보 수집 비용을 더욱 줄일 수 있습니다. 이러한 상한 경계에 더하여, 최악의 경우 하한 경계(특히, 이해관계자 수에 대한 선형 의존성과 정밀도에 대한 로그 의존성은 피할 수 없음)를 제시합니다. 마지막으로, 자연스러운 형태의 조언(예: 제약 조건이 있을 가능성이 높은 이해관계자 또는 유망한 로터리)을 활용하는 학습 기반 알고리즘을 개발하여, 예측이 정확할 때 쿼리 복잡성을 개선하면서도 최악의 경우 보장을 유지합니다.

Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.