Eliciting Thinking Hierarchy without a Prior
Authors: Yuqing Kong
Yunqi Li
Yubo Zhang
Zhihuan Huang
Jinzhao Wu
Venue: NeurIPS 2022 Accept (2022)
Keywords: crowdsourcing
information elicitation
peer prediction
cognitive hierarchy
bounded rationality

Abstract: When we use the wisdom of the crowds, we usually rank the answers according to their popularity, especially when we cannot verify the answers. However, this can be very dangerous when the majority make systematic mistakes. A fundamental question arises: can we build a hierarchy among the answers without any prior where the higher-ranking answers, which may not be supported by the majority, are from more sophisticated people? To address the question, we propose 1) a novel model to describe people's thinking hierarchy; 2) two algorithms to learn the thinking hierarchy without any prior; 3) a novel open-response based crowdsourcing approach based on the above theoretic framework. In addition to theoretic justifications, we conduct four empirical crowdsourcing studies and show that a) the accuracy of the top-ranking answers learned by our approach is much higher than that of plurality voting (In one question, the plurality answer is supported by 74 respondents but the correct answer is only supported by 3 respondents. Our approach ranks the correct answer the highest without any prior); b) our model has a high goodness-of-fit, especially for the questions where our top-ranking answer is correct. To the best of our knowledge, we are the first to propose a thinking hierarchy model with empirical validations in the general problem-solving scenarios; and the first to propose a practical open-response-based crowdsourcing approach that beats plurality voting without any prior. 

Eliciting Thinking Hierarchy without a Prior
Yuqing Kong'
Yungi Lit CFCS and School of EECS
CFCS and School of Computer Science Peking University Begiing.oon@@peee edu. en
Peking University
1 liyunqi@pp @pku herp..uudd...o cn
Yubo Zhang
Zhihuan Huang
CFCS and School of Computer Science Peking University
CFCS and School of Computer Science
Peking University
falsyta@pku. edu.cn
zhihuan. www.uuannuunngpp....kk edu.
Jinzhao Wut
CFCS and School of EECS
Peking University inzhao. wu@pku edu. cn
Abstract
When we use the wisdom of the crowds, we usually rank the answers according to their popularity, especially when cannot verify the answers. However, this be very dangerous when the majority make systematic mistakes. fundamental question arises: where the higher-ranking answers, which may not be supported by the majority, are from more sophisticated people? To address the question, we propose 1) a novel model to describe people's thinking hierarchy; 2) two algorithms to learn the thinking hierarchy without any prior; novel open-response based crowd- sourcing approach based on the above theoretic framework. In addition to theoretic justifications, we conduct four empirical crowdsourcing studies and show that a) the accuracy of the top-ranking answers learned by our approach is much higher than that of plurality voting (In one question, the plurality answer is supported by 74 respondents but the correct answer is only supported by 3 respondents. Our approach ranks the correct answer the highest without any prior); b) our model has high goodness-of-fit, especially for the questions where our top-ranking answer correct. To the best of our knowledge, we are the first to propose a thinking hierarchy model with empirical validations in the general problem-solvingg scenarios; and the first to propose a practical open-response based crowdsoureing approach that beats plurality voting without any prior.
build hierarchy among the answers without any prior
Introduction
The wisdom of the crowds has been proved to lead better decision-making and problem-solving than that of an individual, especially when we do not have sufficient prior knowledge to identify individual experts [26, 2, 28]. Plurality is of the most popular ways aggregate the crowd's opinions. The opinions are usually ranked according to their popularity. However, can be very
"Corresponding Author
This author is currently at Stanford University *This author currently Yale University
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

dangerous when the majority are systematically biased. Here is real-world study we perform. We have asked multiple top university students the following question.
The radius of Circle A is 1/3 the radius of Circle B. Circle A rolls around Circle B one trip back to its starting point. How many times will Circle A revolve in total?
Figure 1: Collected answers of the circle problem
We have collected answers "I (11 people), 2 (8 people), 3 (134 people), 4 (16 people), 6 (27 people), (21 people)". The plurality answer is "3", the ratio between the big circle's 's cireumference and the small circle's. However, the correct answer is "4"* which is only supported by 16 people.
With prior knowledge like the expertise level of each individual respondent, we may be able to identify the correct answer. However, sometimes it's quite expensive and difficult to obtain prior knowledge, especially in new fields.
To address the above issue, Prelec et al. [19] propose an innovative approach, surprisingly popular. They prepare multiple choices, ask the respondents pick one option, and more importantly, predict the distribution over other people's 's choices. They use the predictions to construct a prior distribution the choices, and then select the choice that is more popular than the prior such that the bias corrected. Many other work [11, 6, 20] develop the idea of using the prior or the predictions to correct the bias.
However, first, it's not applicable to employ the previous approaches into the running example, the circle problem, because they require prior knowledge to design the choices. It's also effortful for respondents to report a whole distribution over all choices.
Second, previous works focus on using the predictions to correct bias, while it's intrinsically inter- esting build thinking hierarchy using their predictions. This leads hierarchy among the answers as well. The famous cognitive hierarchy theory (CHT) [24, 25, 3] builds a thinking theory in the scenarios when people play games such that we can learn the actions of players of different sophistication levels. Nevertheless, CHT is designed only for tame-theoretic setting.
We are curious about building thinking theory in general problem-solving scenarios. The key insight is that people of more sophisticated level know the mind of lower levels, but not vice versa [3, 10]. We want apply the insight learn the answers of people of different sophistication levels, called the thinking hierarchy, without any prior.
Key question We aim to build a practical approach to learn the thinking hierarchy without any prior. Based on the thinking hierarchy, can rank the answers such that the higher-ranking answers, which may not be supported by the majority, are from more sophisticated people.
In addition to building thinking theory in the general problem-solving scenarios, in practice, there are multiple reasons why we want the hierarchy rather than only the best. First, for some questions like subjective questions (c.g. why are bar chairs high?), there may be more than one high-quality answer and the full hierarchy provides a richer result. Second, the hierarchy among the answers helps to understand how people think better, which is important especially when try to elicit people's opinions about a policy.
Our approach We follow the framework of asking for answers and predictions simultaneously and extend it to more practical open-response based paradigm. The paradigm asks single open
'Interested readers are referred to https::/mathsstaceeeeee stackexchange.ccoo.. wwt.///ueeooon/1//////11 Aircle-revolutions--oo around- weootter--iirll for explanations.

---

Prediction
Prediction
3
134
20
21
4
16
1
11
0
27
2
0
8
Answer
Answe
134
15
1-
0
11
9-
0
2-
0
1- 0
2
11
(a) Original
(b) Ranked
Figure 2: The empirical results of the circle problem.
response question and asks for both each respondent's answer and prediction for other people's answers, For example, in the circle problem, a respondent can provide: answer: "4", prediction: "3". We then construct an answer-prediction matrix A that records the number of people who report specific answer-predictee pair (e.g. Figure 2(a) shows that 28 people answer "3" and predict other people answer '6".).
To learn the thinking hierarchy, we propose a novel model. Our model describes how people of different sophistication levels answer the question and more importantly, predict other people's answers. The joint distribution over a respondent's 's answer and prediction depends on the latent parameters that describe people's 's thinking hierarchy. We show that given the joint distribution over a respondent's 's answer and prediction, we can infer the latent thinking hierarchy by solving new variant of the non-negative matrix factorization problem, called non-negative congruence triangularization (NCT), which may be of an independent interest. Based on the analysis of NCT, we provide two simple unswer-ranking algorithms and show that with proper assumptions, the algorithms will learn the latent thinking hierarchy given the joint distribution over respondent's 's answer and prediction.
Finally, we show that the enswer-prediction matrix collected by the paradigm is proxy for the joint respondent's answer and prediction. We implement the NCT based answer-ranking distribution answer-predd peweer-preiiction matrix. The default algorithm ranks the answers to maximize the algorithms on the sum of the square of the elements in the upper triangular area of the matrix. allow different answers to have the same sophistication level, the answers are partitioned to compress the matrix. The algorithm maximizes the sum of the square of the upper triangular area of the compressed matrix.
variant version, to
In addition to the above theoretic framework, also empirical studies by asking people questions in various areas including math, Go, general knowledge, and character pronunciation.
Example 1.1 (Empirical results of the circle problem). In the circle problem, have collected the empirical answer-prediction matrix (Figure 2(a)) and ranked it (Figure 2(b)) based on the default algorithum The default ranking algorithm does not any diagonal element. Thus, for ease of illustration, the diagonal elements are modified (i.e,, for all a, Au,a is modified to the number of compare our method the plurality voting visually.
respondents who answer a) such that
More empirical results will be illustrated in Section 3.1. We show the superiority of algorithm by comparing our algorithm to plurality voting by the accuracy of the top-ranking answers. We also test the goodness-of-fit of our model based on the collected data set. To summarize, we provide novel theoretic framework to study people's 's thinking hierarchy in the problem-solving scenarios and a practical apen-response based crowdsourcing approach that outputs a high-quality answer only supported by 16 people when the wrong answer is supported by 134 people (another question is 3 vs. 74) without any prior.
'nllike previous work, the prediction in our model is not a distribution but an answer the respondent thinks other people may answer.

---

1.1 Related work
Information aggregation with the second order information Prelec [18]. Prelec et al. [19] start the framework that asks the respondents both their answers and predictions for the distribution over other people's answers. However, to implement the framework, the requester needs to design a multi-choice question whose choices may require prior knowledge. The effort for distribution report is non-minimal to many respondents and the quality can be issue since most people are not perfect Bayesian. Kong and Schoenebeck [10] study how to clicit thinking hierarchy theoretically by people's predictions and also assumes that more sophisticated people can reason about the mind of less sophisticated people. However, they focus on multi-choice questions, and in their framework, agents either need to perform multiple tasks or report non- mon-minimal distributions. Thus, it's difficult to perform empirical studies using their framework and there is also no empirical validation. Moreover, they assume more sophisticated people can reason about the mind of ALL less sophisticated people while our model allows more sophisticated people cannot reason about some less sophisticated people. Two recent works Hosseini et al. [7], Schoenebeck and Tao [21] study how to aggregate people's votes rank a set of predetermined candidates (e.g. ranking paintings based price [7]. or two presidential candidates [21]) better by using people's predictions. Both of them treat the pairwise comparisons of the candidates as the elicited signals and use people's 's predictions signal quality. In contrast, rather than eliciting ranking based on price or preference, we elicit the thinking hierarchy among people by using people's predictions for other people to determine the hierarchy over the answers. Like Prelec et al. [19], Hosseini et al. [7]. Schoenebeck and Tao [21], there are other works that use people's predictions
improve the
reduce the bias of the collected feedback. For example, Dasgupta et al. [6] use people's s predictions to reduce the bias caused by interactions between users on a social network. Rothschild and Wolfers [20] show that voters' expectations for other people's ' votes are more informative than their intentions. In addition to the discrete setting, recently, a growing literature, including Palley and Soll [16), Martinie et al. [12], Chen al. [4), Wilkening et al. [29], Palley and Satopää [15], Peker [17], aggregate forecasts with additional second order information like each forecaster's s expectation for the average of other forecasters' forecasts.
Peer prediction Starting from Miller et al. [13), series of work (e.g-(13, 18, 5, 22, 11, 9I) focus on eliciting information without a prior by designing incentive-compatille mechanisms. This field is called peer prediction, or information elicitation without prior. In contrast, this work focus how to aggregate information and identify high-quality information without a prior. Liu et al. [11], Prelec al. [19], Hosseini et al. [7], Schoenebeck and Tao [21] focus on information aggregation without prior. However, they do not focus on the problem of learning thinking hierarchy like this work.
Bounded rationality Starting from Simon [23], the term "bounded rationality" describes the decision maker's cognitive limitations. Stahl [24] propose a behavioral model of bounded rationality to predict people's behaviors in strategic games, the level-k theory. Level-k theory assumes that players have different levels of sophistication. Level-0 players play non-strategically, level-1 players play optimal response to level-0 players... A variant of level-k theory is cognitive hierarchy theory [25, 3] where level-k players believe that lower-level players' percentages follow a certain type of distribution. Our Thinking hierarchy model is conceptually similar to level-k but focuses on a non-game setting. Moreover, the level-k theory focus on estimating the average levels of population while we focus on identifying each respondent's 's level.
2 Learning Thinking Hierarchy
We first introduce our model for thinking hierarchy. Tversky and Kahneman [27] propose that people have two systems, a fast and intuitive system, and a slow and logical system. For example, Alice starts to solve the circle problem. When she reads the question, she can run her intuitive system and obtain answer "3", However, when she starts to think carefully, she runs her more careful system 2 to obtain answer "4".
We propose more general model where people can run multiple oracles to approach the question during their thinking process. Conceptually similar to the cognitive hierarchy theory [3], we assume the oracles have different levels. People usually run lower level oracles before the higher level oracles. In the previous example, system is the lower level oracle and system 2 is the higher one. We assume that Alice runs system 2 after system 1. Thus, in our model, people who know the answer is "4" can

---

predict that other people answer "3", which is hypothesized in Kong and Schoenebeck [10]. It's also possible that some people run the most sophisticated oracle directly without running the lower ones. Thus, we design the model such that it does not require the higher-type to be able to predict ALL lower types. We also allow the oracles' outputs to be random.
Section 2.1 introduces the model of thinking hierarchy. Section 2.2 reduces the model inference problem a matrix decomposition problem. Section 2.3 and section 2.4 show how learn the thinking hierarchy.
2.1 Thinking hierarchy
Fixing question y (e.g. the circle problem), T denotes the set of thinking types. A denotes the set of possible answers. Both 7 and A are finite sets. A denotes all possible distributions over A. We sometimes use "prob" as a shorthand for probability.
Generating answers We will describe how people of different thinking types generate answers.
Definition 2.1 (Oracles of thinking types W ). An answer generating oracle maps the question to an (random) answer in A. Each type corresponds to an oracle O₁. The output Og(g) is random variable whose distribution is W, E AA. W denotes a [T] X |A] matrix where each row is Wt-
Each respondent is type with prob pt and E. = 1. A type respondent generates the answer by running the oracle Oz. For all E A, the probability that respondent answers will be Σ, (c). We assume the probability is positive for all E A.
Example 2.2 (A rumning example). There are two types T {0,1). The answer space is (3, 6). On will output '3' with probability 0.8 and '6' with probability 0.2. Or will output '4'
0.8
0
0.2
deterministically. In this example, W =
where the first row is the distribution of 0
0
Og's 's ouiput and the second row is the distribution of O 's outpul.
Generating predictions We then describe how people of different thinking types predict what other people will answer. Here the prediction is not distribution, but an answer other people may report. When a type i respondent makes a prediction, she will run an oracle, which is Oe with probability Pi-+5 where Ee Pi-1' 1. She uses the output of Oμ the prediction g E A.
answer-prediction joint distribution M M denotes |A| |A| matrix where Ma.g is the probability an respondent answers a and predicts g. A denotes a (7) x (T) matrix where Ar, = PePt-st' is the probability respondent is type t and predicts type t!.
Combination:
Example 2.3. In this example, when type 0 respondent makes a prediction, with prob 1, she will run On again. When rype I respondent makes a prediction, with prob 0.5, she will run O₂ again, with prob 0.5, she will run Og. Moreover, respondent is type 0 with prob 0.7, and type with prob 0.3.
PoPo-so PoPo->1 = 0.3 0.5
0.7
0.7 0
0.7
0
Here A-
PIPI-1 PIPI-11
0.3 s 0.5
0.15
0.15
Claim 2.4. Based on the above generating processes, M wWAW.
Proof. For each respondent, the probability she answers and predicts will be
Ma.9 = P.we(()) EP-- we (g) Σ w.(c)ppp-
t,
We sum over all possible types the respondent will be. Given she is type f, she runs oracle O to generate the answer and (a) is the probability that the answer a. We sum over all possible oracles she runs to predict. Given that she runs Op, (e(g)) is the probability the prediction is g. O
Key assumption: upper-triangular never run the oracles of more sophisticated levels. A linear ordering of types {1, T maps a ranking position to a type. For example, T (1) E T is the top-ranking type.
we assume that people of a less sophisticated level can +T
Assumption 2.5. We assume that with a proper ordering of the types, A is upper-trianglla matrix. Formally, there exists a such that Vi > j, Aa(()a triangular is valid thinking hierarchy of the types.
Any n that makes A upper-
5

---

In the running example, the valid thinking hierarchy is T(1) = type 1, x(2) type O. Note that the above assumption does not require vi S J. j.A(())) O. When A a diagonal matrix, types cannot predict each other and are equally sophisticated, thus any ordering is a valid thinking hierarchy.
An algorithm finds the thinking hierarchy when the algorithm is given M which is generated by latent (unknown) W, A, and the algorithm will output a matrix W which equals now-permuted W where the row order is a valid thinking hierarchy. Formally, there exists valid thinking hierarchy such that the : row of W is the (i)) th row of W, i., w Wx()).
2.2 Non-negative Congruence Triangularization (NCT)
With the above model, inferring thinking hierarchy leads to novel matrix decomposition problem, which is similar the symmetric non-negative matrix factorization problem (NMF)". A non-negative matrix is matrix whose elements are non non-negin negative.
Definition 2.6 (Non-negative Congruence" Triangularization (NCT)), Given non-negative matrix M, NCT aims to find non-negative matrices W and non-negative upper-trianular matrix such that M- = W AW. In a Frobenius norm based approximated version, given set of matrices W, NCT aims to find non- neganeate matrices W and non-negative upper-triangulat matrix to minimize
min WEW.A
|M [M-WTAN AWW
and the minimum is defined as the lack-of-fit M regarding W8.
Like NMF, it's impossible to ask for the strict uniqueness of the results. Let PA be the set of permutation matrices such that II AII is still upper-triangular. If (W, A) is a solution, then (II-' 'DW, ID AA 'I) is also solution where D is a diagonal matrix with positive elements and II E PA. We state the uniqueness results as follows and the proof deferred to Appendix C.
Proposition 2.7 (Uniqueness). If [T] I |A| and columns of W consist of a permuted positive diagonal matrix, NCT for M w AW is unique in the sense that then for all W'T A'W' W AW, there exists a positive diagonal matrix D and a [T] x (T' permutation matrix II E PA such that W DDW.
When we restrict W to be "semi-orthogonal" obtain clean format of NCT without searching for optimal A. is the set of all "semi-orthogonal" matrices W where each column of W has and only has non-zero element and WW I. For example, the W in Example 2.2 can be normalized to a semi-orthogonal matrix. The following lemma follows from the expansion of the Frobenius norm and we defer the proof to Appendix C.
Lemma 2.8 (Semi-orthogonal: minimizing F-norm maximizing upper-triangular's sum of the square). For all set of matrices W C I, minwew.A ||M - W AWI? is equivalent to solv- ing maxwew Eis( (WMW Yi and setting A as Up( Sp(WMWT), the upper-triangular area of WMW
2.3 Inferring the thinking hierarchy with answer-prediction joint distribution M
Given M, inferring the thinking hierarchy is equivalent to solving NCT in general. Though we do not have M, later we will show proxy for M. For simplicity of practical use. we introduce two simple ranking algorithms by employing Lemma 2.8. The ranking algorithm takes M as input and outputs linear ordering of answers ग. (1, ... |A] + A that maps ranking position to an answer.
Answer-Ranking Algorithm (Default) AR(M) The algorithm computes
II +- arg NEP
[IMII T
Symmetric NMF: minw |M W W
7 We use congruence here though it not matrix congruence since may not square matrix.
M = W AW, W W has zero lack-of-fit.

---

where P is the set of all |A] X |A| permutation matrices. There is one to one mapping between each permutation matrix II and linear ordering и: =(1) 1, vi. Therefore, the optimal II" leads an optimal rank over answers directly and the default algorithm can be also represented as
arg max π
M (0
To find the optimal rank, we use a dynamic programming based algorithm (see the supplementary materials) which takes 0 |A4 ) In practice, |A] is usually at most or 8. In our empirical study, the default algorithm takes 91 milliseconds to finish the computation of all 152 questions.
The default algorithm implicitly assumes [T] |A| and all oracles are deterministic. To allow [T] < |A| and non-deterministiic oracles, we introduce a variant that generalizes P to a subset of semi-orthogonal matrices Z. Every [2'] x |A| semi-orthogonal W indicates a hard clustering. Each cluster i E 7 contains all answers such that Wr, O. For example, the W in Example 2.2 can be normalized to a semi-orthogonal matrix and indicates a hard clustering {4], ; [6,3]. Therefore, the variant algorithm will partition the answers into multiple clusters and assign hierarchy to the clusters.
Answer-Ranking Algorithm (Variant)
ARt (M, The algorithm computes
W + arg max W
Σ(WMWT).
where W c. I. W is normalized such that every row sums 1. This algorithm does not restrict |2|| = |A| and learns the optimal [2'].
w = Answer rank The output W indicates hard clustering of all answers. We rank all answer as follows: for any < j. the answers in cluster has higher rank than the answers in cluster j. For all i, for any two answers a, a' in the same cluster a is ranked higher than af if W Wi,
Theoretical justification When M perfectly fits the model with the restriction that the latent W is a permutation or hard clustering, we show that our algorithm finds the thinking hierarchy. Otherwise, our algorithm finds the "closest" solution measured by the Frobenius norm.
Theorem 2.9. When there exists Ho P and non-negative upper-triangular matrix Ao such that M = H Ao AR(M) finds the thinking hierarchy 10, In general, A AR(M) will output where IT A Up(IT' MII
a solution to arg min || ITT | The above statement still valid by replacing P by W C I and AR(M) by AR+ (M, W).
Proposition 2.7 and Lemma 2.8 almost directly imply the above theorem. We defer the formal proof to Appendix C.
2.4 A proxy for answer-prediction joint distribution M
In practice, we do not have perfect M. We use the following open-response paradigm to obtain proxy for M.
Answer-prediction paradigm the respondents are asked Q1: What's 's your answer? Answer: Q2: What you think other people will answer:
In the circle example, the possible feedback can be "answer: 4; prediction: 3", "answer: 3; prediction: 6.9.1"... We collect all answers provided by the respondents and denote the set of them by A. In the circle example, A {1, 2, 3, 4, 6, 9}. We also allow respondents to provide no prediction or multiple predictions.
Rank answer in the highest position. 'eee definition in the last paragraph in Section 2.1.
"In practice we set a threshold 6 and collect answers which are provided by at least fraction of the respondents. We allow multiple predictions and also allow people to answer "I do not know". See Section 3 for more details.
7

---

100
Percentage Correct Answers
0.30
Default Variant
0.25
Purality
lack of-ft
0.20
AigorthnmDeteuuli
0:15
Knowledge Pronunciation
Question Type
Accuracy algorithms
(h) Empirieal distribution of lack-of-fit
Figure 3: The results of experiment
Answer-prediction matrix We aggregate the feedback and visualize it by Answer-Prediction matrix. The distinct answers provided by the respondents. Each entry Aa.g: a, g E A is the number of respondents that answer "a" and predict "g".
matrix |A| x |A| square matrix where |A] is the number of
We will show that with proper assumptions, the answer-prediction matrix A expectation is pro- portional M. First, for ease of analysis, assume that each respondent's predictions are i.i.d. samples Second, since we allow people to optionally provide predictions, we need to additionally assume that the number of predictions each respondent willing to provide is independent of her type and answer. We state the formal result as follows and the proof is deferred to Appendix C.
Proposition 2.10. When each respondent's 's predictions are i.i.d samples, and the number of predictions she gives is independent of her type and answer, the answer-prediction matrix A's expectation is proportional to M.
3 Studies
We conduct four studies, study 1 (35 math problems), study 2 (30 Go problems), study 3 (44 general knowledge questions), and study 4 (43 Chinese character pronunciation questions).
Data collection All studies are performed by online questionnaires. recruit respondents by an online announcement or from an online platform that is similar to Amazon Mechanical Turk. We get respondents' consent for using and sharing their data for research. Respondents are asked not to search for the answers to the questions communicate with other people. We allow the respondents to answer do not know" for all questions. Except for Go problems, all questionnaires use flat payment. We illustrate the data collection process in detail in Appendix A. We allow respondents to participate more than one study because our algorithms analyze each question separately and independently.
Data processing We merge answers which are the same, like '0.5' and '50%' We omit the answers that are reported by less than (5) 3% of respondents or one person. The remaining answers, excluding "I do not know". form the answer set A whose size is [A]. We then construct the Answer-Prediction matrix and perform our algorithms. Pseudo-codes are attached Appendix B, Our algorithms do not require any prior the respondents' expertise levels.
3.1 Results
12Thi may be very good assumption since i..dd samples can repeat but respondents usually do repeat their predictions. If we do not want this assumption, we can choose only use first prediction from each respondent (if there exists) to construct the answer-prediction matrix. Many students from top universities in China. See Appendix A for more details.

---

Type
Total
Our Mlgorith((Defaull
Our algorithmi Variant)
Plurality voting
Math
35
29
29
24
Go
30
28
28
23
General knowledge
44
41
41
35
Chinese character
43
36
35
34
Table 1: The number of questions our algorithms/baseline are correct.
Prediction 1:
Prediction
1/5
41
36
0
A/3
34
23
14
% grown
15% BAU
Anewer
35
X
Answer
60.
80
22
10
46
18
0
Monty
18
(a) the Monty Hall problem: you can select one closed door of three. A prize, a car, is behind one of the doors. The other two doors hide goats. After you have made your choice. Monty Hall remaining doors and that it does not contain the prize. He then asks you if you would like to switch your choice to the other unopened door. What the probability to get the prize if you switch?
(h) the Taxicab problem: city are green, the others are blue. A witness sees blue taxi. She is usually correct with probability 80%. What is the probability that taxi saw by the witness blue?
taxis in
will open one
Prediction
Answeer
Answer
67-
(c) Pick move for black such that they can be alive.
(d) Pick for black such that they can be alive by ko.
Prediction
Aprt
Prediction Locito
jani
China
Aprl
15
North Korea
(e) the boundary question: what river forms the boundary between North Korea and China?
(f) the Middle Age New Year question: when the year middle age?
sui j
Prediction
2h1
A
pâng páng
perg:
zhi zhui
Answer
a
+
(g) the pronunciation of
(h) the pronunciation of 39
Figure The ranked answer-prediction matrices

---

We compare our approach to the baseline, the plurality voting, regarding the accuracy of the top- ranking answers. Both of the algorithms beat plurality voting for all studies and the default is slightly better. Among all 152 questions, in 138 questions, the variant algorithm outputs the same hierarchy as the default algorithm. For other questions, the top-ranking type of the variant algorithm may contain more than one answer. The top-ranking answer is the answer supported by more people among all answers in the top-ranking type. In one question the variant is wrong but the default is correct, the variant algorithm assigns both the correct answer and the incorrect plurality answer to the top-ranking type, thus outputting the incorrect answer as the top-ranking answer.
We also compute the lack- index (Definition 2.6) of the algorithms and find that the questions the algorithm outputs the correct answer have smaller lack-of-fit thus fitting the thinking hierarchy model better. Therefore, we can use the lack-of-fit index as a reliability index of the algorithms.
We additionally pick several representative examples for each study (Figure 4) where the matrices are ranked by the default algorithm and the diagonal area modified like Example 1.1. In all of these examples, the plurality is incorrect while our approach is correct. Results of other questions are illustrated at https: //liii/taeiiiioo infonifolllli htt///aassooo///// //. Detailed explanations are illustrated in Appendix D and here we provide some highlights. First, our approach elicits a rich hierarchy, For example, the taxicab problem is borrowed from Kahneman [8] and previous studies show that people usually ignore the base rate and report '80%'. The imagined levels can be 41 41%.. We elicit a much richer level "41 % may fail to predict the least one. In the Taxicab problem, the correct "41%" supporters successfully predict the common wrong answer "80%". However, they fail to predict the surprisingly wrong answers "12%, 20%% which are contrast successfully predicted by "80%" supporters. Our model is sufficiently general to allow this situation. Third, even for problems (like Go) without famous mistakes, our approach still works. Moreover, in the boundary question, we identify the correct answer without any prior when only respondents are correct.
100% 12%%+15%-200
Second, the most sophisticated level
4 Discussion
One future direction is to consider incentives in our paradigm like the literature of information elicitation without verification [13, 18, 5, 22, 9]. We have asked class of students at Peking University: why are bar chairs high? using our paradigm. We cluster the answers by hand. The plurality answer is "the bar counter is high" and our top-ranking answer is "better eye contact with people who stand". Thus, another future diction is to extend our approach to the scenario where people's 's answers are sentences, where we can apply NLP cluster them automatically. In summary, we propose the first empirically validated method to Iearn the thinking hierarchy without any prior in the general mrollem-solving scenarios. Potentially, our paradigm can be used make better decision when we crowd-source opinions in new field with little prior information. Moreover, when we elicit the crowds' opinions for policy, with the thinking hierarchy information, it's i possible to understand the crowds' opinions better. However, regarding the negative impact, it may be easier to implement social media manipulation of public opinion with the full thinking hierarchy of the crowds. One interesting future direction is to explore the impact of the thinking hierarchy information.
Acknowledgement
This research is supported by National Natural Science Foundation of China award number 62002001. We would like to thank Xiaotie Deng, Xiaoming Li, Grant Schoenebeck, and David Parkes for their useful suggestions, and all participants of our studies for their time and efforts.
10

---

References
[1] Joseph Bertrand. Calcul des probabilités. Gauthier-Villars 1889.
[2] David Budescu and Eva Chen. Identifying expertise to extract the wisdom of crowds. Management Science, 61 (2):26677- 2015.
[3] Colin F Camerer, Teck-Hua Ho, and Juin-Kuan Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119())861-888, 2004.
[4] Yi-Chun Chen, Manuel Mueller-Frank, and Mallesh M Pai. The wisdom of the crowd and higher-order beliefs. arXiv preprint arXiv:2102.0 02666, 2021.
[5] Anirban Dasgupta and Arpita Ghosh. Crowdsourced judgement elicitation with endogenous proficiency. Proceedings of the 22nd international conference on World Wide Web, pages 319-330, International World Wide Web Conferences Steering Committee, 2013.
[6] Anirban Dasgupta, Ravi Kumar, and D Sivakumar. Social sampling. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 235-243, 2012.
[7] Hadi Hosseini, Debmalya Mandal, Nisarg Shah, and Kevin Shi. Surprisingly popular voting recovers rankings, surprisingly! arXiv preprint arXiv:210S.09380 2021.
[8] Daniel Kahneman. Thinking, fast and slow. Macmillan, 2011.
[9] Yuqing Kong. Dominantly truthful multi-task peer prediction with constant number of tasks. In Proceedings of the Fourleenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2398-244 2411. SIAM, 2020.
[10] Yuqing Kong and Grant Schoenebeck. Eliciting expertise without verification. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 195-212, 2018.
[11] Y. Liu, J. Wang, and Y. Chen. Surrogate scoring rules. In EC '20: The 2 ACM Conference on Economics and Computation, 2020.
[12] Marcellin Martinie, Tom Wilkening, and Piers DL Howe. Using meta-predictions to identify experts in the crowd when past performance is unknown. Plos one, 15(4):e0232058, 2020.
[13] N. Miller, P. Resnick, and R. Zeckhauser: Eliciting informative feedback: The peer-prediction method. Management Science, pages 1359-1373, 2005.
[14] Martin Müller. Computer go. Artificial Intelligence, 134(1):145-179, 2002. ISSN 0004-3702. doi:
URL htt.:///////.s...eeeeeee. wwtt://wwwwiiieeeeieeeetttt
[15] Asa Palley and Ville Satopää. Boosting the wisdom of crowds within a single judgment problem: Weighted averaging based peer predictions. Available at SSRN 3504286, 2022.
[16] Asa B Palley and Jack B Soll. Extracting the wisdom of crowds when information is shared. Management Science, 65(5):2291-2309) 2019.
[17] Cem Peker, Extracting the collective wisdom in probabilistic judgments. Available at SSRN 4072021, 2022.
[18] D. Prelec. A Bayesian Truth Serum for subjective data. Science, 306(5695) 2004.
[19] Dražen Prelec, H Sebastian Seung, and John McCoy, A solution to the single-question crowd wisdom problem. Nature, 541(6633):322-55, 2017.
[20] David Rothschild and Justin Wolfers. Forecasting elections: Voter intentions versus expecta- tions. Available at SSRN 1884644, 2011.
[21] Grant Schoenebeck and Biaoshuai Tao. Wisdom of the crowd voting: Truthful aggregation of voter information and preferences. Advances Neural Information Processing Systems, 34: 1872-1883, 2021.
11

---

[22] Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes. Informed truthfulness in multi-tast peer prediction. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 179-196. ACM, 2016.
[23] Herbert A Simon. Bounded rationality. In Utility and probability, pages 15-18. Springer, 1990.
[24] Dale O Stahl. Evolution of smartn players. Games and Economic Behavior, 5(4):604-617, 1993.
[25] Dale O Stahl and Paul W Wilson. On players' models of other players: Theory and experimental evidence. Games and Economic Behavior, (0(1):218-254) 1995.
[26] James Surowiecki. The wisdom of crowds. Anchor, 2005.
[27] Amos Tversky and Daniel Kahneman. Judgment under uncertainty: Heuristics and biases. science, 185(4157):124411131 1974.
[28] Susan C Weller. Cultural consensus theory: Applications and frequently asked questions. Field methods, 19(4):339-368 2007.
[29] Tom Wilkening, Marcellin Martinie, and Piers DL Howe. Hidden experts in the crowd: Using meta-predictions leverage expertise in single-question prediction problems. Management Science, 68(1):487-508 2022.
[30] Pauline Yu. Allegory, allegoresis, and the classic of poetry. Harvard Journal of Asiatic Studies, 43(2):377-412, 1983.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
12

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [Yes]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] We obtain the consent forms to use and share the data.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [Yes]
13


Reviews:
[{"review_id": "mQjlDje-Ip1", "reviewer": "Reviewer_93Te", "summary": "This paper argues that in the wisdom-of-the-crowd paradigm, plurality voting may not necessarily yield the correct answer when the majority makes systematic errors. The paper presents a theoretical framework to elicit thinking hierarchy and demonstrates that their method outperforms plurality voting and also demonstrates certain desirable properties. Apart from presenting the theoretical framework, the paper also conducts crowdsourced user studies to demonstrate the practical effectiveness of their framework. ", "questions": "1. How are the questions for the user study selected? ", "limitations": "No negative societal impact is discussed. I do not see any obvious red flags in terms of negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper's motivation is clear and important. If a vast majority displays certain biases, plurality voting would not be very useful. \n2. The paper's writing and organization are good. The examples provided help understanding. \n\nWeaknesses: \n1. The paper can be strengthened by making the user study more elaborate with a clear description of how are the questions selected. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gID0Vxif1FL", "reviewer": "Reviewer_239z", "summary": "The paper proposes a method to aggregate crowdsourcing answers based on a key observation: experts have different expertise levels and experts at a higher level are able to “simulate” the experts at lower levels. The paper aims to find this underlying “thinking hierarchy” —which can be used to find the best answer—by asking people to predict other people’s answers. The paper first proposes a model for this thinking hierarchy. The model assumes that experts have their types, and for each type, there is a thinking oracle that specifies how this type of experts generate their answers. An expert can run the oracles with lower types but never higher types. The paper then develops two algorithms to learn the underlying thinking hierarchy. The algorithms basically generate an answer-prediction matrix based on experts’ answers and predictions and then find a ranking of answers that will reorder the matrix to match the hierarchical structure in the best way. The paper provides theoretical justification for their algorithms. Finally, the paper shows by real-world experiments that their methods outperform plurality voting.\n", "questions": "1. Why not just assume there is an underlying ranking of answers and people with higher-type answers can predict the lower-type answers?\n\n2. How do your algorithms compute the best permutation matrix/the matrix W*? Are they polynomial-time algorithms?\n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are the algorithms and the experiments. The paper proposes novel methods to utilize the underlying thinking hierarchy when aggregating experts’ answers and tests the method through real-world experiments. The algorithms are intuitively reasonable and the experiment results are good. \n\nThe weakness of the paper is the modeling of the thinking hierarchy, which also makes the theoretical justification of the algorithms implausible. The use of thinking oracle seems unreasonable to me. Are these thinking oracles private information or public information? If they are private information, how can the experts of higher types use the lower-type oracles? If they are public information, why can’t the lower-type experts use the higher-type oracles? It is also ungrounded why an expert generates predictions by running thinking oracles of others. The assumption seems crucial for the theoretical analysis, which in my point of view should be more carefully justified. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KcUdT6ehdSj", "reviewer": "Reviewer_SfLf", "summary": "The crux of this paper is that it provides an empirically validated way to use the wisdom of the crowd rather than the default “popular answer”/”plurality voting” paradigm. In the process, the authors show how to obtain the thinking hierarchy of the crowd for the given set of questions. They claim that knowing this (rich) hierarchy helps in areas like policy making. Using mathematical tools and certain assumptions, the paper demonstrates the superiority of their method especially when obtaining a prior distribution from the crowd is prohibitively expensive.\n", "questions": "See above.", "limitations": "The authors discuss technical limitations such as the i.i.d assumption on user predictions. Negative impacts on society are not particularly discussed, but one could think of situations such as political mercenaries or governments collecting information on thinking patterns of a voting population in pursuit of an agenda.\n", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The authors distinguish themselves from previous work by discarding the use of a prior distribution. Further, they claim that their thinking hierarchy learning model captures a richer spectrum of answers. Their method reduces bias like previous work does, with the difference that they do not collect a prediction distribution, rather a single prediction answer. They also differentiate themselves from the game theoretic setting. The concept of the thinking hierarchy is sufficiently novel wrt past work.\n\nQuality: The paper provides mathematical justification, although under certain idealistic assumptions, for every statement it makes. The experiment results have been provided at a URL and are easy to grasp. The authors are upfront about the assumptions that are required and also provide alternatives - for e.g. the i.i.d assumption under which respondents make their predictions is contrasted with picking the first prediction that a respondent makes, due to the fact that i.i.d predictions don’t match with reality.\n\nClarity: The paper is clear with what it aims to achieve and under what conditions it can achieve them. The goal is to: learn the thinking hierarchy among respondents and to do so without collecting prior information. The authors also provide future uses of their work from the ML and scale points of view. The experiments are easy enough for a novice reader to understand, and collect sufficient information.\n\nSignificance: The method described in the paper has significance in that it is applicable to cases where collecting prior information from a crowd is difficult, and plurality voting is not sufficient. One can foresee future applications of systematically obtaining a thought hierarchy as more information on a certain topic or policy can only help with decision making.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HPh0leCp0oD", "reviewer": "Reviewer_J65o", "summary": "The paper proposes a mathematical model for thinking hierarchy of users predictions for their answer and other users’ answers. Given the joint distribution of the answers and predictions of other answers, the authors show that the parameters of the model can be derived using a novel matrix factorization. The authors solve an equivalent Frobenius norm minimization problem for the special case when the $W$ matrix (one of the parameters of the model) is semi-orthogonal. And then the authors propose a brute-force search based algorithm to find the ranking of the answers from the thinking hierarchy. Since the joint distribution of answers and predictions may not be available they use an empirical estimate. Naturally, this works if the samples are i.i.d. ", "questions": "1. Lines 155 to 161 are confusingly written. Are the people predicting other peoples’ answers or their types?\n2. Please write Example 2.3 properly. Since the meaning of $p_t$ and $p_{t \\rightarrow t’}$ has already been explained it would be much easier to understand if the authors just use this notation while showing the construction of $\\Lambda$.\n3. Could the authors comment about what happens if the side information about other people’s predictions is noisy?", "limitations": "I don’t see any mention of the negative impacts of when the proposed algorithms are bad compared to standard algorithms. This discussion is needed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The problem of eliciting thinking hierarchy to come up with the correct ranking over various answers is well-motivated, and is an important problem to study.\n2. The paper seems to be placed well in the recent literature about using additional information about people’s prediction about other answers to get better accuracy for ranking answers.\n3. The theoretical results about the problem are interesting, however somewhat limited.\n\nWeaknesses:\n\n1. The main drawback is that the algorithms proposed in the paper are just brute-force search based algorithms and hence are not efficient for complicated questions.\n2. The theoretical guarantees about eliciting thinking hierarchies hold in fairly restricted settings, which may not hold majority of the times in real-world. Especially, the questions and answers very quickly become complicated, in which case, plurality-voting could be a better method? \n3. Basically, for a complete picture, the complexity of the questions and answers needs to be captured in this framework. In what cases does plurality-voting give better ranking than the algorithms in the proposed framework. I don’t understand when is the side information better?\n4. The writing can be improved (see questions).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept