Metric Distortion of Social Welfare Functions

의사결정의 세계에서, 새로운 직원을 채용하는 것부터 그룹의 영화 관람을 위해 영화를 고르는 것에 이르기까지, 우리는 종종 사람들의 선호도를 순위로 매기는 것에 의존합니다. 우리는 "누가 가장 마음에 드나요?" 또는 "당신의 첫 번째 선택은 무엇인가요?"라고 묻고, 그 답변을 사용하여 집단적인 결정을 내립니다. 수십 년 동안 연구자들은 사람들이 각 옵션을 얼마나 가치 있게 여기는지 정확히 모를 때, 이러한 순위가 얼마나 잘 결과로 이어지는지를 연구해 왔습니다. 그들은 개인의 감정의 정확한 강도를 알지 못하더라도, 단지 선호하는 순서만 아는 것으로도 놀라울 정도로 공정한 결과를 도출할 수 있다는 것을 발견했습니다. 그러나 이 작업의 대부분은 대통령이나 최고의 후보자와 같이 단 한 명의 승자를 뽑는 데 집중되었습니다. 실제 삶은 종종 더 복잡합니다. 우리는 대학 입시 대기 명단이나 제품 추천 피드처럼, 모든 항목을 첫 번째부터 마지막까지 순위별로 나열하는 전체 목록을 만들어야 할 때가 많습니다. 이러한 시나리오에서는 순위의 위치가 중요합니다. 첫 번째로 선정되는 것은 매우 중요할 수 있지만, 열 번째로 선정되는 것은 마지막과 거의 차이가 없을 수도 있습니다. 문제는, 사람들이 첫 번째 자리와 두 번째 자리 사이의 차이를 얼마나 중요하게 여기는지 모르는 상태에서, 오직 사람들이 선호하는 순서만을 알고 있을 때, 어떻게 하면 모두를 만족시키는 완전한 목록을 구성할 수 있는가 하는 것입니다.

한 연구팀은 이제 이 구체적인 과제에 도전하여, 투표자들이 각 위치에 대해 서로 다른 중요도를 가질 때 어떻게 완전한 순위를 구축할 수 있는지 탐구했습니다. 그들은 모든 사람이 숨겨진 가치 척도를 가지고 있어, 상위권과 하위권을 얼마나 중요하게 여길지 결정하는 시나리오를 가정했습니다. 어떤 사람들은 오직 첫 번째 추천에만 관심을 가질 수도 있고, 다른 사람들은 적절한 것을 찾기 위해 여러 옵션을 훑어볼 수도 있습니다. 연구자들은 투표 시스템이 이러한 숨겨진 척도를 보지 않고도 어떻게 공정하고 고품질의 순위를 만들 수 있는지 알고 싶어 했습니다. 그들은 그 답이 시스템이 어떤 정보를 사용할 수 있는지에 전적으로 달려 있다는 것을 발견했습니다. 만약 시스템이 각 사람이 각 위치를 얼마나 가치 있게 여기는지 정확히 안다면, 가능한 최선의 품질을 가진 순위를 구축하여 3이라는 최적의 왜곡(distortion)을 달eric할 수 있습니다. 만약 시스템이 가치는 모르지만 모든 사람이 동일한 숨겨진 척도를 공유한다는 것을 안다면, 여전히 매우 잘 수행할 수 있으며, 결과의 품질은 그 공유된 척도가 얼마나 변하는지에 따라 달라집니다.

가장 어려운 상황은 시스템이 가중치에 대해 아무것도 모르고, 모든 사람이 자신만의 고유하고 숨겨진 척도를 가지고 있을 때 발생합니다. 이 경우, 연구자들은 아무리 영리한 투표 규칙이라 할지라도 결과의 품질이 필연적으로 저하될 것임을 증명했습니다. 그들은 순위를 매기는 후보자의 수가 늘어남에 따라 결과의 오류가 선형적으로 증가한다는 것을 보여주었습니다. 간단히 말해, 소규모 그룹의 순위를 매길 때는 시스템이 괜찮은 일을 할 수 있지만, 많은 수의 후보자를 순위 매길 때는 위치에 대한 중요도를 사람들이 얼마나 중요하게 여기는지에 대한 정보 부족으로 인해 좋은 결과를 보장하는 것이 불가능하다는 것입니다. 이 발견은 근본적인 한계를 강조합니다: 투표자들이 목록의 각 자리를 어떻게 가중치 있게 생각하는지 모른다면, 대규모 그룹을 위한 완벽한 순위는 손에 닿지 않는 곳에 있습니다.

연구자들은 이러한 순위를 만들기 위해 단계별 방법을 구축하여 자신들의 아이디어를 테스트했습니다. 목록을 위에서부터 한 자리씩 채워 나가는 과정을 상상해 보십시오. 각 단계에서 시스템은 현재의 선호도를 바탕으로 해당 특정 위치를 위한 최적의 후보를 선택합니다. 그들은 만약 시스템이 가중치를 알고 있다면, 이 단순한 단계별 접근 방식이 최적으로 작동하여 3이라는 최적의 왜곡을 달성한다는 것을 발견했습니다. 그들은 각 단계에서 승자를 뽑기 위해 특정하고 정교한 방법을 사용했으며, 이를 통해 최종 목록이 이러한 제약 조건 하에서 이론적으로 가능한 최선의 목록만큼 좋을 것임을 증명할 수 있었습니다. 이는 완전한 목록을 만드는 것이 단 한 명의 승자를 뽑는 것과 비교했을 때, 적절한 정보가 있다면 품질을 희생하지 않고도 가능하다는 것을 보여주었기에 중요한 발견이었습니다.

가중치가 숨겨져 있지만 모두에게 공유되는 경우, 연구자들은 동일한 단계별 방법이 여전히 작동하지만 결과의 품질은 공유된 척도의 형태에 따라 달라진다는 것을 발견했습니다. 만약 모든 사람이 모든 위치를 거의 비슷하게 가치 있게 여긴다면, 시스템은 1의 왜곡을 달성하며, 이는 결과가 최적의 사회적 후생(social welfare)과 완벽하게 일치함을 의미합니다. 만약 모두가 오직 첫 번째 자리만을 중요하게 여긴다면, 시스템은 단 한 명의 승자를 뽑을 때와 똑같이 수행합니다. 성능은 이 두 극단 사이를 부드럽게 이동합니다. 이는 구체적인 숫자를 알지 못하더라도, 그룹이 목록에 대해 생각하는 방식이 균일하다면 시스템이 매우 효과적인 순위를 만들어낼 수 있음을 의미합니다. 연구자들은 이 성능에 대한 정확한 공식을 제공하여, 그룹의 변동성이 최종 결과에 어떻게 영향을 미치는지 정확히 보여주었습니다.

그러나 가중치가 숨겨져 있고 사람마다 다를 때는 이야기가 완전히 달라집니다. 연구자들은 이 혼란스러운 환경에서 시스템이 품질의 상당한 손실을 피할 수 없음을 입증했습니다. 그들은 가중치를 모르는 상태에서 어떤 투표 규칙도 만들어낼 수 없는 것보다 훨씬 우월한 최적의 순위가 존재하는 구체적인 사례들을 구축했습니다. 그들은 결과의 차이가 후보자의 수에 직접적으로 비례하여 증가한다는 것을 증명했습니다. 후보자가 10명일 때는 오류가 작지만, 100명일 때는 오류가 훨씬 커집니다. 이 결과는 더 많은 정보 없이 영리한 알고리즘이 문제를 해결할 수 있다는 희망을 일축합니다. 이는 명확한 경계선을 설정합니다: 대규모 그룹을 위한 고품질의 순위를 얻으려면, 당신은 위치를 어떻게 가중치 있게 생각하는지 알거나, 아니면 결과가 불완전할 것임을 받아들여야 합니다.

연구는 또한 사람들이 가치를 정규화(normalize)하는 두 가지 다른 방식도 살펴보았습니다. 한 시나리오에서는 모든 사람이 전체 목록에 걸쳐 고정된 양의 가치를 배분합니다(예: 1달러를 모든 위치에 나누어 주는 것과 같습니다). 다른 시나리오에서는 모든 사람이 나머지 위치를 어떻게 가치 있게 여기든 상관없이 첫 번째 자리에 고정된 값인 1을 부여합니다. 연구자들은 이 두 가지 현실적인 시나리오 모두에서, 숨겨지고 서로 다른 가중치의 문제가 동일한 선형적 오류 증가로 이어진다는 것을 발견했습니다. 투표자들이 내부적인 척도를 어떻게 구조화하든, 만약 시스템이 이를 볼 수 없고 그것들이 사람마다 다르다면, 순위의 품질은 목록이 길어짐에 따라 저하될 것입니다. 이는 추천 시스템 설계자나 채용 위원회에 명확한 경고를 제공합니다: 만약 당신이 다양한 우선순위를 가진 다양한 집단을 다루고 있다면, 더 구체적인 선호도 데이터를 수집하지 않고는 단순한 순위 매기기 방법만으로 완벽한 목록을 만들어낼 수 있다고 기대해서는 안 됩니다.

궁극적으로, 이 연구는 제한된 정보로 우리가 무엇을 달성할 수 있는지에 대한 한계를 명확히 합니다. 좋은 집단적 결정을 내리는 경로는 가용 정보의 구조에 크게 달려 있음을 보여줍니다. 가중치를 알 때, 우리는 3의 최적의 왜곡을 달성할 수 있습니다. 가중치가 모두에게 동일하다는 것을 알 때, 가중치가 균일하면 1의 왜곡을 달성할 수 있고, 그렇지 않으면 단일 승자 경계와 1 사이를 보간(interpolate)하는 결과를 얻을 수 있습니다. 하지만 가중치가 숨겨져 있고 서로 다르다면, 우리는 그룹의 크기가 결과의 품질을 결정하는 벽에 부딪히게 됩니다. 연구자들은 단순히 새로운 투표 방식을 제안한 것이 아니라, 정보가 누락되었을 때 공정성과 효율성의 규칙이 어디서 무너지는지를 보여줌으로써 무엇이 가능한지의 경계를 그려냈습니다. 그들의 발견은 완전한 순위를 위해 선호도를 집계하려는 모든 이들에게 실질적인 가이드를 제공하며, 사람들의 다양성이 커질수록 과업의 복잡성도 커진다는 점을 상기시켜 줍니다.