In this paper, we develop a variant of widely used posted pricing model named bonus-based posted pricing. In this scenario, we consider the following two types of platforms: profile-aware and profile-agnostic platform. We prove that profile-aware posted pricing is equivalent to 0-1 knapsack problem which is known as NP-hard, and propose a constant factor approximation assuming schur-convex and sub-additive property of utility function, which has not been considered before. We secondly reveal that profile-agnostic posted pricing becomes non-convex optimization problem, which is fundamentally hard to find global optimum. In this sense, we assume a correlation between cost and quality of workers and propose polynomial-time algorithm to find global optimum. We also have shown that by adopting bonus-based pricing mechanism, platform is capable of promoting high-quality users even in profile-agnostic manner. In this context, we analyze the price of agnosticity which denotes a fundamental performance gap between two types of platforms. Moreover, we conduct an extensive performance evaluation consists of synthetic simulation. Based on numerical simulation, we verify that our theoretical statement holds and our bounds are highly tight by generating worst-case distribution. Our methodology can practically be applied in many existing platforms directly such as Mturk or CrowdFlower since it does not necessarily require profiling procedure. Moreover, we reveal which situation requires user profiling process highly, and shed bright on the platform designer or crowdsourcer to decide whether or not to adopt profiling process.
본 논문에서는 크라우드 소싱 플랫폼의 사용자들의 퀄리티를 조절하기 위한 메커니즘을 디자인하는 방법을 다룬다. 우리는 널리 사용되는 posted pricing이라는 모델의 변형된 형태를 제안하였다. 이러한 상황에서 사용자들의 개인적인 퀄리티와 코스트를 아는 지 여부에 따라 두 가지 형태의 플랫폼을 다룬다. 사용자들의 개인적인 값을 아는 플랫폼에서 해당 문제는 0-1 배낭 문제로 귀결됨을 밝혔고, 목적 함수의 특정한 형태를 가정하여 근사 알고리즘을 제시하고 분석하였다. 다음으로 사용자들의 개인적인 값을 모르는 플랫폼에서 해당문제가 최적값을 구하는 데 근본적인 어려움이 있는 non-convex 최적화 문제임을 밝혔고, 퀄리티와 코스트의 특정한 관계를 가정하여 최적값을 구하는 다항시간 알고리즘을 제시하고 분석하였다.
또한, 보너스의 도입으로 인해 플랫폼은 사용자들의 개인적인 값을 알지 못하는 상황에서도 사용자들에 대한 조절 자유도가 크게 증가해 도입하지 않는 방법에 비해 플랫폼의 유틸리티가 크게 증가함을 밝혔다. 특히 보너스의 적절한 사용이 가능하다면 사용자들의 개인적인 값을 아는 상황과 모르는 상황에서의 유틸리티 차이가 크지 않음을 밝혔고 이를 이론적으로 분석하였다.
이론적인 알고리즘들의 분석을 바탕으로 시뮬레이션을 통해 알고리즘 및 이론이 실제로 잘 동작함을 확인하였다. 본 논문에서 제시하는 방법론은 Mturk뿐 아니라 존재하는 다양한 플랫폼에 직접적으로 적용될 수 있고, 사용자들의 개인적인 값에 대한 정보가 부족한 상황에서도 유연히 적용할 수 있다. 뿐만 아니라, 우리의 분석을 바탕으로 어떠한 상황에서 사용자들의 개인적인 값에 대한 앎의 유무가 크라우드소싱 과정의 최종적 유틸리티에 크게 관여하는지 미리 확인할 수 있다.
