Counterbalancing Learning and Strategic Incentives in Allocation Markets
Authors: Jamie Juhee Kang
Faidra Monachou
Moran Koren
Itai Ashlagi
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning
strategic incentives
mechanism design
voting
allocation
markets
healthcare
social learning
herding

Abstract: Motivated by the high discard rate of donated organs in the United States, we study an allocation problem in the presence of learning and strategic incentives. We consider a setting where a benevolent social planner decides whether and how to allocate a single indivisible object to a queue of strategic agents.  The object has a common true quality, good or bad,  which is ex-ante unknown to everyone. Each agent holds an informative, yet noisy, private signal about the quality. To make a correct allocation decision the planner attempts to learn the object quality by truthfully eliciting agents' signals. Under the commonly applied sequential offering mechanism, we show that learning is hampered by the presence of strategic incentives as herding may emerge. This can result in incorrect allocation and welfare loss. To overcome these issues, we propose a novel class of incentive-compatible mechanisms. Our mechanism involves a batch-by-batch, dynamic voting process using a majority rule. We prove that the proposed voting mechanisms improve the probability of correct allocation whenever agents are sufficiently well informed. Particularly, we show that such an improvement can be achieved via a simple greedy algorithm. We quantify the improvement using simulations.

Counterbalancing Learning and Strategic Incentives in Allocation Markets
Jamie Kang Stanford University kangjh0stanf ord. edu
Faidra Monachou
Stanford University
monachou@stanfordd edu
Moran Koren
Itai Ashlagi Stanford University
Harvard University me@mkoren.c org
Abstract
Motivated by the high discard rate of donated organs in the United States, we study an allocation problem in the presence of learning and strategic incentives. We consider setting where benevolent social planner decides whether and how to allocate single indivisible object to a queue of strategic agents. The object has common quality, good bad, which is ex-ante unknown everyone. Each agent holds an informative, yet noisy, private signal about the quality. To make correct allocation decision the planner attempts to learn the object quality by truthfully eliciting agents' signals. Under the commonly applied sequential offering mechanism, show that learning is hampered by the presence of strategic incentives as herding may emerge. This can result in incorrect allocation and welfare loss. To overcome these issues, we propose a novel class of incentive- compatible mechanisms. Our mechanism involves a batch- by-batch, dynamic voting process using a majority rule. We prove that the proposed voting mechanisms improve the probability of correct allocation whenever agents are sufficiently well informed. Particularly, we show that such an improvement can be achieved via a simple greedy algorithm. We quantify the improvement using simulations.
Introduction
This paper contributes to the growing literature in the intersection of learning and mechanism design, by considering a fundamental allocation problem in the presence of learning and strategic agents. In our setting, a planner needs to allocate single indivisible object to at most one among several agents waiting in a queue. The object's 's true quality is either high ("good"") or low ("bad"), but is ex-ante unknown to both the planner and the agents. Agents are privately informed, in the sense that each receives private signal that is informative about the true quality of the object, and strategic since they choose to accept or reject the object based on the action maximizing their expected utility. In this framework, agents thus engage in a social learning process they observe the actions of their predecessors but not their private signals. The planner's 's goal is to design an comppie-- mechanism that optimizes correctness, i.c., maximizes the ex-ante accuracy of allocation.
This problem finds a natural application in the allocation of donated organs to patients on national waitlist. The median waiting time for a first kidney transplant in the U.S. is around 3.6 years [25], whereas the rate at which deceased donor kidneys are offered to patients has been growing steadily [23], exceeding 21 21.2% in 2020 [30]. The reasons leading to high discard rates even of seemingly high-quality organs remain unclear. Clinical studies attribute this increase
eventually discarded
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to herding behavior and inefficiency in allocation mechanisms [11, 29]. Improving the allocation outcome of these markets is undoubtedly crucial as it could save thousands of future lives.
Towards understanding the source of high discard rates, our framework highlights the often overlooked role of social learning. In most cases, when offered an organ, patients not only have access to publicly available data about the organ (e.g.. donor's ' age, organ size) but also consult with their own physicians for private opinions. Each physician may assess the same organ differently based on their prior experience and/or medical expertise, Empirical works [13, 31] have recently proposed an explanation that patients rationally ignore their own private information (e.g.. a physician's 's medical assessment) about the quality of an organ and follow the preceding patients' rejections.
Our proposed model captures this phenomenon and serves as theoretical sandbox for the design and assessment of alternative allocation policies. We theoretically show that sequentially offering the object to agents which is policy commonly used in practice can result in poor correctness, since the rejections by the few initial agents can cause a cascade of rejections by the subsequent agents.
To address this issue, we introduce novel class of incentive-compatible allocation mechanisms characterized by batch-by-batch, dynamic voting process under a simple majority rule. Our proposed greedy mechanism dynamically partitions the list into batches of varying sizes. Then, it sequentially offers the object to each batch until the object is allocated to some agent. The planner privately asks each agent in the current batch to either opt in opt out. If the majority of the current batch vote to opt in, then the planner randomly allocates the object to one of the current agents who opted in. If the mechanism exhausts the list without success, the object is discarded. Interestingly, several Organ Procurement Organizations (OPOs) already offer organs in batches, although no voting is used;" the reasons are both speed up the allocation process and to avoid herding.
In our main result, we show that if private signals are at least as informative as the prior, there always exists an incentive-oompatibe voting mechanism that strictly improves correctness and thus helps avoid unwanted discards. Furthermore, we suggest a simple, greedy algorithm to implement such mechanism. For all other values of private signal precision, we establish that there is no incentive-compatin voting mechanism. Moreover, every voting mechanism results in the same correctness as the sequential offering mechanism.
compaible voting mechanisms have several interesting properties. First, the batch size increases after each failed allocation attempt. The intuition is simple. Failed allocations make the current belief about the object quality more pessimistic. Therefore, the planner increases the batch size to ensure that the object is allocated only if sufficient number of agents receive positive signals while each agent's 's decision remains pivotal. Second, offering to another batch after a failed attempt strictly improves correctness (compared to sequential offering). As our simulations showcase, this improvement is significant and generally becomes larger as the prior and signal precision grow; in fact, voting mechanism with just two batches significantly outperforms sequential offering. Finally, we find that the prior and signal precision have opposite effects on correctness: the correctness tends to decrease the prior increases but the marginal effect of signal precision is positive. An intuitive explanation is as follows. Since the optimal batch size decreases as the prior increases, the probability incorrectly allocate bad object increases. However, the signal precision improves, the magnitude of the error decreases since agents' signals become more reliable.
We highlight the tension between agents' strategic incentives and the planner's learning goal. From the planner's perspective, agents' private signals contain valuable information about the unknown quality of the object. By increasing the number of collected data points, the planner her confidence about the true quality of the object. Agents' strategic incentives, however, impose a constraint the maximum size of the batch that allows the truthful elicitation of agents' signals: as the batch size increases, the chance to be pivotal decreases which in turn reduces the incentive for an agent with negative signal to be truthful. Our proposed voting mechanisms enable the planner to crowdsource agents' private information in a simple, truthful, and effective manner.
improve
Related literature. Our model draws upon seminal social learning papers [7, 8, 28] and their extensions in various game structures [1. 2, 14, 24]. Several empirical studies also examine social learning in organ allocation settings [13, 31J. However, none of these works consider the existence of a planner that controls the flow of information. Furthermore, our proposed mechanism is inspired by the voting literature (e.g., [6, 12]): our notion of correctness is adopted from [3]. Finally, our paper
Based on authors' personal communication. See, e.g., [21] for allocation in batches.

---

is loosely connected to information design (e.g.. [10, 18, 26, 27D) and Bayesian exploration (e.g.. [15-17, 20, 22]). contrast to our model, this literature does generally not consider an underlying social learning process. We include an extended overview of the related literature in Appendix A.
2 Model
We consider a model in which a social planner wishes to allocate a single indivisible object of unknown quality to privately informed agents in a queue.
Object and agents. The object is characterized by a fixed quality w E {G, B}, where G and B denote good and bad quality, respectively. The true quality of the object is ex-ante unknown to both the planner and agents; however, both share a common prior belief = P(w = G) E (0, 1).
Agents are waiting in a queue; we denote by i the agent in position i. Each each agent knows his own position. For simplicity, we assume that the queue consists of an arbitrarily large number I of agents. Each agent has a private binary signal s; E S - {g.b) that is informative about the true quality of the object w. Each 8; is identically and independently distributed conditional on w. Furthermore, each 8, is aligned with w with probability q = P(s, 9 w G) P(s w = B), where the signal precision q E (0.5, 1) is commonly known.
Agents are risk-neutral. The utility of the agent who receives the object is if w G and - if w = B (This symmetry simplifies the exposition and analysis but does not qualitatively change the results.). Any agent who does not receive the object, because he either declines or is never offered, receives a utility of O. As tie-breaking rule we assume that indifferent agents always decline.
Voting mechanisms. report their private signals, and based on their report, decides whether and how to allocate the object. We consider class of voting mechanisms denoted by V. A voting mechanism V V offers the object sequentially to odd-numbered batches of agents, where each batch size may be set dynamically based on the information from previous batches. In any given batch, if the majority of agents vote to opt in, the object is allocated uniformly at random to one of the current agents who opted in.
The planner designs mechanism which potentially asks (a batch of) agents to
Formally, a voting mechanism V(nr)g= is defined by sequence of functions n1: T2: such that for each batch j. the corresponding function πī : [0, 1] - N maps current belief μ about the object quality w to a batch size Kj (we let (40 μt). The mechanism begins with offering to the first batch of agents, who are positions I,.... कi (u)) the object not allocated to batch j 1, it offered to the agents in the next ())))) positions.
When batch j is offered the object, each agent i in batch chooses an action (a vote) 0; E A & [y,n]. where y and n correspond to opting in ("yess") and opting out ("no"), respectively. Y, the number of opt in votes from batch j, constitutes the majority of batch j. i..., Y, 2 ماايما 1, the object is allocated uniformly at random among agents in batch j who opt in. To simplify exposition, we sometimes denote by Kj the ex-post size of batch j (while omitting the dependency on the current belief (1) We assume that the agents in batch as well as the planner observe all the votes of agents in the previous batches j' < j. and this is commonly known. After any batch j and given current prior (1--1, the belief μy shared by the planner and agents is updated recursively in terms of the realized batch size Kj and voting outcome Y,
Mj 19 V3 Ks My 2 PP(w (Jj-1, 13-19 - (1-9) + (1- Y3 -1 95-
(I)
commonly applied voting mechanism is a sequential offering mechanism, which offers the object to one agent at time. Another type of voting mechanism is single-batch voting mechanisms. which offer the object only once; thus, the object is discarded if the majority in the batch choose to opt out.
Let uz (a,; st) denote the expected utility of an agent who receives signal E S and takes action oi E A. voting mechanism V V aicentive-coppatille (IC) if u;(v::) g)) 2 un(n; g) and u. (n b) 2 (y b). Thus, agent gets higher utility from opting in than opting out when he has received signal 5; = g. but prefers to opt out when 8; = b.
"The condition E (0.5, 1) is without loss of generality. The common prior belief and signal precision standard in the social learning literature [7. 8, 28).
3

---

Correctness. The planner's 's goal is to maximize the probability of a correct allocation outcome, or correctness; the allocation outcome is correct if allocates a good object or does not allocate a bad object. Formally, under voting mechanism V E V. the planner's decision whether to allocate the object or not denoted by the random variable Z (0. 1}.
A mechanism V E V achieves correctness c(V) if
c(V) e Ey [I( = G Z 1) [[ B Z =0]
Since we allocate single object, a cascade can only form on the opt out action. Therefore, maximizing correctness is equivalent to maximizing social welfare.
Upper bound on correctness. A natural benchmark on correctness would be the optimal solution in a setting where agents are not strategic and thus are willing to truthfully reveal their private signal to the planner. In the absence of strategic incentives, the planner's optimal solution would be (i) ask all agents in the queue to reveal their private signals, (ii) compute her posterior belief based on the gathered information, and (iii) allocate the object to a random agent if and only if her posterior exceeds 0.5. Equivalently, as we show in Lemma A.1 in Appendix A, the planner allocates the object
if and only if the number of positive signals is least y - 0.5 log --=))
(log (
+ 0.5
where / is the number of agents in the queue. In that case, we can show that correctness equals
P(,, y),
where Xy is Binomial (I, 9) random variable (see also Lemma 3). As I grows, correctness ap- proaches 1. Importantly, this upper bound is not achievable by an incentie-coopptibbe mechanism.
Discussion of modeling assumptions. The model is based on several modeling choices that we diseuss next. First, the assumption that voting outcomes are fully revealed to subsequent batches made for simplicity. Dropping this knowledge complicates the analysis substantially: one should compute a posterior belief of an agent by taking expectations of possible outcomes that led to them being offered object. Second, assuming that batches are always odd-numbered is of technical nature. To attain incentive compatibility, our analysis relies on the monotonic behavior of the upper and lower bounds on the prior. This result depends on probabilistic argument about binomial distributions (Lemma D.2), which fails to hold batches can be both of odd and even sizes." 3 Finally, consider the allocation of just single object rather than setting in which objects arrive and allocated sequentially. In particular we abstract away from dynamic incentives and restrict attention to the learning aspect. We leave the interaction between the two for future work.
3 Herding in the Sequential Offering Mechanism
In this section we analyze the commonly applied sequential offering mechanism, which will serve as benchmark for results. Recall that the sequential offering mechanism, namely VsEo offers the object to each agent one-by-one; the first agent that is offered the object and opts in receives it.
As we establish below, the sequential offering mechanism has two important drawbacks: it is not incentve-cooppttinnn and achieves poor correctness. This is due to a cascade of actions (i.e., herding) that takes place after few decisions. Specifically, cascade of opt out actions begins after couple of initial agents opt out, which ultimately leads the discard of the object. The number of initial opt out actions needed to instigate this cascade-led discard depends the prior The following result formalizes this. A detailed analysis of the benchmark mechanism can be found in Appendix together with the omitted proofs of the section.
Lemma 1. Under VsEa. the object is allocated if and only if: (i) μ > q, (ii) μ E [1/2, q] and either $1 9 $2 = 9. (iii) μ E [1 q, 1/2] and $1 = g. Otherwise, the object is discarded.
direct implication of this result that the outcome of the mechanism is determined in the first two offers. Regardless of the values of p. q and the object's 's true quality, the object is always discarded if it is rejected by the first two agents. Thus the result below follows.
Proposition 1. Under the sequential offering mechanism, Vsno:
(i) At most the two initial agents in the queue determine the allocation outcome: if the first two agents decline, then the object will be always discarded.
This issue can be addressed by introducing random tie-breaking rule with appropriate weights

---

Discarded both agents have 7
Always accupted by agent
Always.discarded discarded
Discarded if agentt 1 his 8,
P
1-q
1/2
Figure I: Allocation outcome of the sequential offer mechanism (VsEo) based on the value of prior (0, 1) with respect signal precision q. For low μu, the object is rejected by all agents, leading to discard. For intermediate μa, the allocation outcome depends on the initial two agents' private signals.
for >
2pq(1 - 2) +
for μ E [1/2, gl
(ii) The correctness equals ef c(Vsno)
=
for μ E [1 - q, 1/2)
1-
for μ 1 - q.
The result qualitatively suggests that the first few agents in the queue have the power to decide whether the object will be allocated. This implies that these few agents can inadvertently undermine the welfare of the rest of the agents. Most importantly, the planner can never learn from the private information of the remaining I - 2 agents make better allocation decisions. In the context of organ transplants, this herding behavior prevents the planner from allocating good-quality organs, leading high discard rate. This may in turn lead to patients' longer waiting times and health deterioration.
4 Voting Mechanisms
Recall from Equation (2) that in the absence of strategic incentives, the planner asks as many agents as possible and makes her allocation decision based these (truthful) private signals. On the other hand, as we have seen with Vsso when agents are strategic, the presence their incentives introduces a constraint for the planner, which in turn sets an upper bound on the number of agents the planner can truthfully learn from. Under the benchmark mechanism Vs for example, the planner can elicit at most two truthful signals, which may prevent her from taking correct allocation decision.
Motivated by these shortcomings, we propose a new class of voting mechanisms and examine the enentive-compatioee mechanisms within this class. We show that there always exists an incentive- compatible voting mechanism that improves correctness as long as private signals are more informa- tive than the common prior belief; otherwise, none of the voting mechanisms are incentive-compatio and achieve correctness equal to that of Vsso. Theorem
our main result.
Theorem 1. For any μ. <. there exists a voting mechanism V E V that is incentive-compatiay and improves correctness compared to the sequential offering mechanism V For μ. Z q, there is no crentive-comppttble voting mechanism and any V E V achieves the same correctness as VsEo-
We prove Theorem 1 in several steps. In Section 4.1, we begin by defining the simplest voting mechanisms, the single-batch voting mechanisms, where the mechanism offers the object to one batch only and terminates afterwards. Specifically, characterize the optimal mechanisms among all incentive-come cicentive-oompatbbee single-batch voting mechanisms. Then in Section 4.2, we utilize these results to develop simple greedy algorithm to construct incentive-compatible correctness- -enecteess-imroviinng voting mechanism with potentially multiple batches.
4.1 Warm up: Optimal Single-batch Voting Mechanisms
As warm up, we begin with the study of one of the simplest voting mechanisms: the single-batch voting mechanisms. With a slight abuse of notation, we use the following definition. Definition 1. Let ViKY E V be the single-batch voting mechanism where the object is offered to only one batch of the initial K agents in the queue.
Unlike VsBo, the single-bater batch voting mechanism V(K) as well as any other voting mechanism, ensures that the object is allocated if and only if the majority of agents (in the batch) opt in. As our
'We have assumed that agents share a constant prior μ. In practice, each agent's prior might be drawn i.i.d. from some common distribution with support (0, 1). Our qualitative insights still extend to this case: a larger but finite number of initial agents determines the allocation outcome and herding still occurs.
5

---

Is
lg
0
M5
14
11
1
Figure 2: Interval of incentive-come coopptile-compatibee prior Ix for different batch sizes K E {1,3,... as described in Lemma 2. The intervals Ik are decreasing (Lemma C.1) with and the consecutive intervals Ix and Ix+2 overlap (Lemma C.2) with each other.
results in this section illustrate, the extent to which this policy incentivizes agents to vote truthfully depends on the values of the prior and batch size K.
In Lemma 2, we identify the necessary and sufficient conditions for ViKy to be incentive-compatible. In Lemma 3, we show its existence conditional on the informativeness of signals and characterize the correctness it achieves. In Proposition we establish that among all dncentive-ooppatioe V(R).
correctness maximized when the incentive compatibility constraint is binding K (()). Finally in Lemma 4, we provide simple comparative statics of this optimal batch size. In the next section, we will extend these results to voting mechanisms possibly with multiple batches.
First, for any batch size K, let
(1
1 1-P X
K+1
q² (1-PP(XR K+1) qp P ((Nx + -1 RP [xx K+1
Ix a
be some interval of prior where Xx Binomial( q). Moreover, let (11) (respectively, K(u)) be the maximum (respectively, minimum) batch size K such that μ E Ix- Then the incentive compatibility of V(к) can be characterized in terms of the interval Ix, equivalently, the batch size bounds (()) and K(μ)):
Lemma 2. V(K) is incentive-compatiie if and only (i) μ E Ik. equivalently (fi) q and K(p) S K S (p)..
The proof of the lemma can be found in Appendix C together with the rest of the proofs in this section. A sketch of the proof is as follows. To show condition (i), for a fixed K, let Gy (respectively, Bx) be the probability that the object gets allocated to some agent in the batch conditional on the true quality being good (respectively, bad). We compute that
GK
Σ K+1
K
K
9rt (1 9)th
x)*-
BR
K Σ K
K
x x-2 9)--1 9
y
Next, we use Gx and Bx to rewrite the incentive compatibility constraints as uq9K (1-w)) p)(1 Bx 20 and μ(1 - 9) - μ)qBx S O. Given that the left-hand sides of both inequalities monotonically increase with μl, there exist some thresholds of prior, namely 15x 10 and "x (0, 1), that solve the indifference conditions: Ax 1-9 Bx and
1-tk
9x
Tg 2 Ex Based on this transformed system of equations, we are able to characterize the 9x feasible region (K) for the prior μ which turns condition (ii), utilize some useful properties of the interval Ix: first, its endpoints are weakly decreasing in K (Lemma C.I), and second, it is overlapping (i.e., Ix n nIx+2 + Φ) (Lemma C.2).
I-Pg
be precisely Ik. To show the equivalent
Condition (ii) in terms of batch size K provides straightforward intuition. Larger batch sizes make agents more confident that, if the object is allocated, it is likely that the quality is good. For the same reason, however, batch size that is too large incentivizes everyone opt in, including those with negative signals. Borrowing the terminology from the voting literature, K (u) is designed to make each agent's decision pivotal: K (1)) is the maximum batch size that guarantees incentive compatibility. On the other hand, if the batch size too small, then the allocation decision depends on learning from sample size that is too small to offer reliable information, making agents with

---

positive signals reluctant to opt in. Thus. K ((4) is the minimum batch size that ensures incentive compatibility. Furthermore, Lemma 2 gives rise to the following observation.
Lemma 3. Suppose μ q. Then, incentive-compatiby V(K) always exists and achieves correct- ness (V(K)) P (Xx* 2 K+1). where Xk Binomiall K,q).
Lemma 3 shows that if each signal is at least as informative as the prior μ4, there is single-batch voting mechanism that elicits information in a truthful manner. Another implication of the lemma is that the correctness of an decentivecooppationn Binomial (K, 9) random variable. This tail distribution can be interpreted as the probability that the majority of votes are aligned with the true quality. Given the definition of correctness, this property is thus particularly intuitive.
ViK} can be expressed as the tail distribution of
An additional observation is that the tail distribution IP (XK 2 K+1) increases with K (see Lemma D.2 in Appendix D). Consequently, given μ4, the upper size limit K (()) maximizes cor- rectness among all possible values of K that conserve the incentive compatibility of V(K). We formalize this property below.
Proposition 2. Suppose μ < q. Then the batch size = R()) maximizes correctness among all incentive-compatible V(KY-
Hence the planner will choose the largest batch size that the agents' incentives allow, As we establish below, the optimal batch size behaves monotonically with respect to the prior p.
Lemma 4. K (1) weakly decreases with μ.
The logic here is simple. If the sentiment around the object quality is optimistic (i.e., Ja is high), then it is harder to keep the agents with negative signals truthful, requiring tighter upper bound on the batch size (lower K (n)). We discuss additional comparative statics through simulations in Section 5,
Finally, note that the results above focused on regimes where μ < q. This a natural setting which guarantees that the signal is least informative as the prior belief. For the complementary where JA 2 we show that there is no incentive-compatible voting mechanism (see Lemma C.3 in Appendix C). Intuitively, the lack of informativeness of the signal induces the agents lose trust in their private signals, and as a result creates no incentives to behave truthfully. In that case, under any V(K), all agents will opt in and thus the object will always be allocated. Notice that this outcome is equivalent to the outcome under Vse in terms of correctness."
4.2 Improving Correctness via Greedy Voting Mechanisms
Next we utilize the results of Section 4.1 to characterize how to dynamically choose batch sizes of a voting mechanism (potentially with multiple batches) improve correctness, while balancing the agents' incentives. Further, we implement this mechanism via a simple greedy algorithm.
The first key technical observation is that, from the perspective of the agents in batch j. the voting mechanism V(xx);= pe is equivalent to a angle-batch voting mechanism V(K,) with realized common belief M4j-1 and batch size K; Hy (pg-1). Naturally, since both the planner and agents observe the voting results from previous batches, no informational asymmetry arises between them.
Lemma 5. A voting mechanism Vi is incentive conpntiiee-ompatbbllee if and only if for any batch j, current belief p-j1 and batch size K2 n, (1z-1),, V(K,) incentive-compatibb
Hence, to ensure the incentive compatibility of V(n,)y,, is sufficient to choose each batch size K₃ myopically by solving a single- batch voting mechanism design problem (with updated belief μ4y-1 instead of p)) This suggests the following greedy scheme.
Definition 2. For any J E N, let V E V be the voting mechanism that offers the object to J batches unless either it is allocated or the list is exhausted. Formally, for each batch j and realized K (μ²-1) for j S for j > J.
belief -1 1:: the batch sizes are chosen as K₁- n (My-1)
'The only difference is that under ViKY, the object is always allocated to an agent in the batch uniformly at random, whereas under Vsso it is always allocated to agent 1.
7

---

Building upon Lemma 5 and results from Section 4.1, we establish three key properties of V Proposition 3. For any μ < q and J, VEREEDY has the following properties:
GREEDY
(i) VeREEnY is incentive-compatine
(ii) Ex-post batch sizes satisfy Ky S for any j' <Jı
(iii) c. (VoReEDy) strictly increases with J.
To understand part (ii), suppose that the object had been offered to batch but was not allocated. Then, the current belief naturally decreases, that is 14, < 11-11. as the majority of batch j has voted to opt out. By Lemma 4, more pessimistic belief about the object quality results in larger optimal batch size (-). Hence, it follows that ( I K(1z). Part (iii) of the proposition suggests that adding an additional batch improves correctness. The intuition is that an additional batch allows the planner to collect and learn from more information about the object. Consequently, the planner would like to keep on offering until either the object is allocated or there are not enough agents left in the queue. We formally define this mechanism below and describe simple algorithm to implement it. Definition 3. Let VOREEDY E be the greedy voting mechanism such that for each batch j and the realized belief p3-1, the batch sizes are chosen as K2 = xz (1zr1 = ((pg-1).
Algorithm 1: Implementation of VGREEDY
Initialize hatch j = 1, belief pro batch size K1 = K (Ho);
while 7 2 K₁ + + K₃ do
Collect votes from the top K2 remaining agents;
Y, 2 + then
Allocate the object uniformly at random among agents in batch j who opted in;
else
Update belief μı using Equation (1) and next batch size K5+1 K (py))
Set.j 4 + 1;
Note that a major advantage of VORFRDY is its design simplicity: the maximum number of batches, J, does not have to be predefined.
Finally, we are ready to prove Theorem 1. The main idea is that using the correctness c(Vsuo) of the sequential offering mechanism from Proposition I, we can show that for every f q, the planner can achieve e (V VOREEDY) that exceeds c(Vseo), ) by appropriately setting J (full proof in Appendix C.3). Furthermore, using Proposition 3 (part (iii),, we establish that the improvement described in Theorem can be also achieved by VAREEDY-
Corollary 1. For any μ q, VOREEDY is incentive-compatiaa (multi- batch) voting mechanism that improves correctness in comparison to the sequential offering mechanism Vsso-
Simulations
In this section we use simulations to complement our theoretical results.
Optimal batch size. In Figure 3, we study the optimal batch size K ((u) (Proposition 2) of the single- batch voting mechanism ViKy by construction, the optimal V(K} is equivalent to Vi In our nu- merical analysis, we examine K (p) for all priors μ E (0, 1) and signal precision q E {0.6, 0.7, 0.83.
We make several observations. First, as guaranteed by Lemma 4, the optimal batch size K K(μ) decreases as the prior μ increases. As we discussed in greater detail in Section 4.1, the incentive compatibility constraint binds at lower values of K(μ). For very high values of μ. that p 2 9. Theorem 1 establishes that it is impossible to achieve incentive compatibility for any batch size, which explains the discontinuity at J = q in each curve.
Second, for lower values of μ (approximately for values μ < 0.5), the marginal effect of q on K (n)) is negative but diminishes as μ grows. Indeed, as Figure 3 illustrates, the signal precision q plays an important role for lower values of μ.. In particular, if µ is low and q is not significantly informative (e.g., = 0.6), the planner has a priori low confidence in the object's 's quality. Similarly, agents have strong incentives to opt out regardless of their signal. Thus, the planner needs larger batch size.
Correctness evaluation and comparison. In Figure 4, we evaluate the correctness c(V) of four different mechanisms V E (Vdenoyy V2 V VsEg, VAL.} for q {0.6, 0.7, 0.8) and μ E (0, 1). For
8

---

Optimal batch size K
150
Figure 3: Via simulations, we compute the optimal incentive-compatinn
100
q
0.6
batch size (()) for all possible priors μa E (0, 1) for three regimes: E {0.6, 0.7, 0.8). In all regimes, K (1) decreases as μ increases. For low values of higher implies lower K (()).
0.7
50
0.8
0.0
0.2
0.4
0.6
0.8
Prior μ
9= 0.6
q= 0.7
q= 0.8
1.0
Correctress c(V)
0.9
VenEsDy
0.8
VEREED
0.7
Vsso
39
VAu
0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0 0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.B
1.0
Prior μr
Prior
Prior
Figure 4: We compare the correctness c( (V) of mechanisms V E (V1 GREEDY: V2
VIREDDY VS VAL in
a setting with population size I = 345. VAL represents the optimal mechanism in the absence of strategic incentives, which achieves near perfect correctness close to (see Equation (2)). The remaining VOREEDY. ViREEDY and Viso assume strategic agents. We compute c(V) for all μ E (0, 1) and three different regimes 9 E {0.6, 0.7, 0.8}. In all regimes, VaREEDY achieves higher correctness than VsE for all < 9/2 + 1 1/4. With one additional batch, V22 VOREED further improves the correctness of V GREEDY and outperforms VsEq for all μ q-
q E (0.6, 0.8), we study the behavior of <(VokuDdY) {1, function of the prior μ.. We observe several interesting properties. First, and y apply two opposite forces on correctness: for both J {1, 2). c(Vort) tends decrease as μ increases but for higher q's this effect is smaller. Intuitively, as the prior μl grows, the batch size becomes smaller (see Figure 3). As the planner learns from fewer signals, the probability to misallocate the object increases. However, as the signal precision improves, the magnitude of misallocation decreases since signals become more reliable.
Second, the comparison between Vl GRFEDY and V2 VOREEDY confirms that additional batch has an important positive effect on correctness. The two-batch mechanism V/2 ViREEDY outperforms the single- batch mechanism VOREEDY- In fact, the gap between their achieved correctness grows as μ increases. Intuitively, if the planner fails to allocate a good object in the first batch, she has another chance to allocate it in the second batch. Since higher y translates to higher probability that the object is of good quality, having two opportunities to allocate the object has positive impact on correctness. This also explains the non-monotonic (but still generally decreasing) trend of c( c(V2 VEREEDY) with respect to μr, which is especially evident for high values of p.
Finally, we are interested in comparing the correctness of voting mechanisms against two natural benchmarks. The first benchmark VsEo is the sequential offering mechanism (see Section 3) in the presence of strategic incentives. As established in Theorem 1, there exists voting mechanism (in this case, VOREEDY) ) which outperforms Vsso for all μ < However, observe that the number of batches is crucial. In contrast to 1/2 V ViREEDY achieves higher correctness than Vsno only for μ < 3 + 1
Comparing V22 ViReeny against VsEg, we observe that the performance gap c( c(V2RFEDY) - c(Vsgo) widens in the region μa E [0, - q] as f grows. This is because the object is always discarded for μ (see Figure 1) which further explains why e( c(Vseg) = - μ (Proposition 1). For μ E (1 - q, 4). the gap remains positive but decreases as μ increases, since the signals of the first two agents affect the outcome of Vsso and thus decrease the chance of misallocation. Note again that, due to Theorem 1, for μ 2 q, any voting mechanism V E V achieves correctness equal to c( c(Vsug).

---

The second benchmark VAL assumees that agents are not strategic (see Equation (2)) and thus achieves the optimal correctness close I. The ratio c( cVV //ceEr) the price of anarchy. We see that incentives put significant cost correctness, especially for higher values of 14 S q. Higher values of g help decrease the price of anarchy. For any q, the maximum price of anarchy e(V ((Vokesn)/cc( is observed around μ g. and equals 1/g in single-batch mechanism.
[1.2], serves as a measure of
Discussion and Conclusion
Recent empirical evidence suggests that significant contributing factor to the high discard rate of donated organs is herding. We propose to amend the current allocation policy by incorporating learning and randomness into the allocation process. We support our recommendations by introducing and analyzing a stylized model through theory and simulations. From a theoretical perspective, our work highlights the tension between learning and incentives and contributes to the understanding of optimal allocation when agents are privately informed and thus susceptible to herding behavior.
make two limiting assumptions: (1) agent utilities are symmetric; (2) agents differ only in the realization their private signals. We believe that our results are qualitatively robust and can be extended to model with variations in agent types and asymmetric utilities. Increasing the relative magnitude accepting "bad" object will make agents more cautious, thus leading larger batches. Introducing heterogeneous agents adds little insight to our qualitative conclusions; therefore, for the sake of brevity, we considered homogeneous agents.
Limitations and extensions. For simplicity.
Nevertheless, we acknowledge that our model is stylized with several abstractions that may not fully reflect the real organ allocation markets. In practice, an organ allocation waitlist might have patients of varying medical characteristics, such as age and blood type, which can give rise to heterogeneous utilities from the same organ. Therefore, our current model, which assumes a common utility function, should be interpreted as restricting attention to patients within the same medical characteristics group. would be an interesting future direction to generalize some of these parts of our model.
Social impact and ethical concerns. Our proposed mechanism is designed to increase the acceptance rate of transplantable donated organs. While designing healthcare policies using insights from theoretical models has been extensively used (see e.g.. [4, 5] for kidney exchange), we emphasize that one must pursue such change in a gradual manner. Furthermore, we note that our mechanism does not constitute Pareto improvement. Patients, who are first in line, may be skipped due to the randomness in allocation. Thus, although our policy has the potential improve the overall system efficiency, its implementation must consider any unintended effects individual patients.
Acknowledgments and Disclosure of Funding
Jamie Kang acknowledges support of the Jerome Kaseherg Doolan Fellowship and Stanford Manage- ment Science & Engineering Graduate Fellowship.
Faidra Monachou acknowledges support from the Stanford Data Science Scholarship, Google Women Techmakers Scholarship. Stanford McCoy Family Center for Ethics in Society Graduate Fellowship, Jerome Kaseberg Doolan Fellowship, and A.G. Leventis Foundation Grant.
Moran Koren acknowledges the support of the Israeli Minestry of Science and Technologi's Shamir scholarship and the support of the Fulbright foundation.
10

---

References
[1] Daron Acemoglu, Asuman Ozdaglar, and Ali Parandchgheibi. Spread of Misinformation in Social Networks. Games and Economic Behavior, 2010.
[2] Itai Arieli and Manuel Mueller-Frank. Multidimensional Social Learning. The Review of Economic Studies, 86(3):913-94) 940, may 2019. doi: 10. 109//resuud/ddy009..... URL https:
// //academic. . ceaaa/esstu//aae /ttp://////rrrlee/////////////// /111//////////111113/212222
[3] Itai Arieli, Moran Koren, and Rann Smorodinsky. The One-Shot Crowdfunding Game. In EC '8: Proceedings of the 2018 ACM Conference on Economics and Computation, pages 213-214. ACM, 2018.
[4] Itai Ashlagi and Alvin E Roth. Free Riding and Participation in Large Scale, Multi-hospital Kidney Exchange. Theoretical Economics, 9(3):117 813-86,,,,, 2014.
[5] Itai Ashlagi and Alvin Roth. Kidney Exchange: An Operations Perspective. Technical report, National Bureau of Economic Research, 2021.
[6] David Austen Sirth and Jeffrey S Banks. Information Aggregation, Rationality, and the Condorcet Jury Theorem. The American Political Science Review, 90(1):pp. 34-45, 1996. ISSN 00030554. URL http: //www//wwwww/// jstor. wwg arrgsstable/2082790
[7] Abhijit V Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, 107(3):797-817, 1992.
[8] Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. A Theory of Fads, Fashion, Custom, and Cultural Change as Informational Cascades. Journal of Political Economy, 10065):92--1026 1992.
[9] Alison Butler, Gretchen Chapman, Jonathan N Johnson, Antonio Amodeo, Jens Böhmer, Manuela Camino, Ryan R Davies, Anne I Dipchand, Justin Godown, Oliver Miera, al. Behavioral economics- a framework for donor organ decision-making in pediatric heart trans- plantation. Pediatric transplantation, (363))e33655, 2020.
[10] Ycon-Koo Che and Johannes Horner. Optimal Design for Social Learning. 2015.
[11] Matthew Cooper, Richard Formica, John Friedewald, Ryutaro Hirose, Kevin O'Connor, Sumit Mohan, Jesse Schold, David Axelrod, and Stephen Pastan. Report of National Kidney Foun- dation Consensus Conference Decrease Kidney Discards. Clinical Transplantation. 33(1):
e13419, 2019.
[12] Nicolas De Condorcet. Essay sur l'application de l'analyse a la probabilite des decisions rendues a la pluralite des voix. Par m. le marquis De Condorcet. de l'imprimerie royale, 1785.
[13] Stephanie De Mel, Kaivan Munshi, Soenje Reiche, and Hamid Sabourian. Herding in Quality Assessment: An Application to Organ Transplantation. Technical report, IFS Working Papers, 2020.
[14] Erik Eyster, Andrea Galeotti, Navin Kartik, and Matthew Rabin. Congested Observational Learning. Games and Economic Behavior, 87(283454):1-32 2013. doi: 1e1016/..eeh.014444 006. URL http: / /xxx doi. pori..org/10 10. 1016/ j geb. 2014. .0..0006666
[15] Jacob Glazer, Ilan Kremer, and Motty Perry. The Wisdom of the Crowd When Acquiring Information Is Costly. Management Science, 2021.
[16] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing Exploration with Unbiased Histories. arXiv preprint arXiv: 000.//...006.... 2018.
[17] Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Bayesian Exploration with Heterogeneous Agents. In The World Wide Web Conference, pages 751-761. ACM, 2019.
[18) Emir Kamenica and Matthew Gentzkow. Bayesian Persuasion. American Economic Review, 101(6):25002213: 2011.

---

[19] Anton Kolotilin, Tymofiy Mylovanov, Andriy Zapechelnyuk, and Ming Li. Persuasion of Privately Informed Receiver. Econometrica, 85(6):1949-196) 2017.
[20] Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "Wisdom of the Crowd". Journal of Political Economy, 122(5):98--012,, 2014.
[21] Michal A Mankowski, Martin Kosztowski, Subramanian Raghavan, Jacqueline M Garonzik- Wang, David Axelrod, Dorry Segev, and Sommer E Gentry. Accelerating kidney allocation: Simultaneously expiring offers. American Journal of Transplantatiin, ((11))3771-3078 2019.
[22] Yishay Mansour, Alcksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian Exploration: Incentivizing Exploration in Bayesian Games, arXiv preprint arXiv:1602.07570, 2016.
[23] Sumit Mohan, Mariana C Chiles, Rachel E Patzer, Stephen O Pastan, S Ali Husain, Dustin Carpenter, Geoffrey K Dube, R John Crew, Lloyd E Ratner, and David J Cohen. Factors Leading the Discard of Deceased Donor Kidneys in the United States. Kidney International, 94(1):
187-198, 2018.
[24] Elchanan Mossel, Allan Sly, and Omer Tamuz. Strategic Learning and the Topology of Social Networks. Econometrica, 1355)11755-1794, 2015. doi: 10.3982/ECTA12058, URL http:///axxvvvooraaaa/ wtt.aa///////.// 5527.
[25] National Kidney Foundation. Organ Donation and Transplantation Statistics, Jan- uary 2016.
URL https://www kidney.orrr. ort/////s//eeeerrr////tttteeeete Organ-Donation and- -rausplattaiioonSSaatt.
[26] Yiangos Papanastasiou, Kostas Bimpikis, and Nicos Savva. Crowdsourcing Exploration. Man- agement Science, 6727)1777) 2017.
[27] Luis Rayo and Ilya Segal. Optimal Information Disclosure. Journal of political Economy, 118 (5):949-987, 2010.
[28] Lones Smith and Peter Sørensen. Pathological Outcomes Observational Learning. Econo- metrica, 68(2):371-398, 2000.
[29] Darren E. Stewart, Victoria C Garcia, John D Rosendale, David K Klassen, and Bob J Carrico. Diagnosing the Decades-long Rise in the Deceased Donor Kidney Discard Rate in the United States. Transplantation, 101():575--57, 2017.
[30] U.S. Department of Health and Human Services. Organ Procurement and Transplantation Network: National Data, April 2021. URL https://optn. transplant wwwaanttttr..aeeaaaaaaaaeee hrsa. hrsa.gov/datal gov/data/ heaa-aatt-rrporttt/mttooooo-----
[31] Juanjuan Zhang. The Sound of Silence: Observational Learning in the U.S. Kidney Market. Marketing Science, 29(2), 2010. doi: 1t2.///ks..100...ooo
12


Reviews:
[{"review_id": "wW5D0NiXSpH", "reviewer": "Reviewer_MQKx", "summary": "The authors study the problem of allocating a single indivisible item to a group of agents, without money. Motivated by kidney exchange, the item can only have two qualities: either good or bad. Every agent (as well as the mechanism designer) agree that the prior probability of the item good is $\\mu = Pr[\\text{item is good}]$. However, each agent i has their own private signal s_i about the item's quality. It is assumed that these signals are iid and depend on the true quality of the item: $q = Pr[s_i \\text{ is good } |\\text{ item is good}] = Pr[s_i \\text{ is bad }|\\text{ item is bad}]$, where this q is the accuracy of their signal. The utility of each agent is +1 upon receiving a good item and -1 for a bad one. The goal is to develop truthful mechanisms that maximize the probability that the item is correctly allocated: i.e., given to an agent if it is good or discarded if it is bad.\n\nThe authors study sequential allocation mechanisms, where the decisions of previous agents might reveal information about the item and affect following choices. This is empirically observed in Kidney Exchange, where if a kidney is rejected early, it is very likely that potential recipients might keep rejecting in, further decreasing the probability that someone will accept it.\n\nThe first result of the authors is to study the sequential offering mechanism. Here, the agents are ordered and the item is offered to each one, stopping and allocating the item the first time an agent accepts it. They show (roughly) that the item is allocated if $\\mu > q$ or if the first two agents receive a good signal and it's never allocated for $\\mu < 1-q$. Also, notice that his mechanism is not truthful. The reason the item might not get allocated is because the agents are actively updating their prior $\\mu$.\n\nThe second (and main result) is the development of a *batched* version of the previous mechanism. In the simplest version, a batch of K agents is selected and asked to report their signals. If the majority considers the item good, then it is allocated at random to one agent reporting a good signal. Depending on $\\mu$ and $q$, the authors show that there exists a range of batch sizes such that the mechanism is truthful. The second step is to greedily combine batches together: starting for a truthful batch size for $\\mu$, if the item is not allocated then the next batch size would be a function of $\\mu'$, the updated prior. Even though the game is sequential, the agents only participate once and only care about their current prior and the size of the batch they participate in.\n\nPutting the two results together, the authors show that for $\\mu > q$ there is no truthful mechanism and every mechanism is at most as good as the sequential one. This makes sense, as in this case the prior is more informative than the private signal. For $\\mu < q$ however, their batched mechanism is incentive compatible and improves the guarantee. Finally, the authors have experiments on synthetic date showing the benefit of using 1 or 2 batches, compared to the sequential mechanism,\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper's model is very clean and in my opinion original (although I am not an expert in social learning). The presentation is excellent, easy to follow and the authors clearly outline the limitations and modelling assumptions of their work (such as the reason every agent has the same $\\mu$ and $q$). \n\n\nThe quality of the exposition and the mathematical rigor is high: although there isn't anything too technical going on, there is clever use of probability and Bayes' theorem to keep the analysis interesting and intuitive. My only recommendation would be to add an analysis for the case where $\\mu$ and $q$ are not precisely known, but only within a confidence interval. I think most results would follow, but it would interesting to see if the new algorithm is robust to such noise. The sequential allocation mechanism performs worse in practice but does not require this information: would the batched mechanism still perform better with a slightly perturbed value of $\\mu$ and $q$?\n\nThe significance of the paper is somewhat subjective: the paper provides a fresh model, with the right abstractions, that explains why there is inefficiency in kidney exchange and how it could be improved. I personally enjoyed it, but I could see why one might consider the technical contribution (and learning aspect) a bit weak.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately explain the limitations and societal impact of their work. Kidney exchange is a very delicate matter and they acknowledge that although their paper is making progress towards the right path, randomization and batching users together might be perceived us unfair and be impractical: for example, imagine one recipient missing out because the rest of his batch voted against.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nnl0MZxefbD", "reviewer": "Reviewer_DTQS", "summary": "The authors study a setting in which a central planner allocates a single indivisible good to agents showing up sequentially. The true quality of the item (good or bad) is unknown to both agents and the mechanism designer. The agents receive a signal about the quality of the item, and the planner aims to leverage those signals to learn the quality of the item and how to allocate it efficiently. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n- The problem is very well and clearly motivated. From a practical point of view, the running example that the authors use is that of organ allocation. There, it is extremely important to ensure that organs are not discarded due to inefficiencies in online decision-making.\n- The aspect studied by the authors is interesting. The point of view taken here is that agents learn from not only their private signals but also from past observations whether the organ is likely to be good or not, and base their willingness to get the item on this knowledge. \n- The naïve sequential mechanism then does not work, because early agents believing the organ is bad lead all subsequent agents to believe the same, leading to the organ being discarded. I like the characterization of Lemma 1 that i) shows exactly when this can happen and ii) shows that this reduces to the beliefs of only the first 2 agents.\n- The characterization of Theorem 1 is tight. If the information received by the agents is precise enough, then the authors develop a voting mechanism that is incentive-compatible and improves outcomes (correctness) compared to the naïve sequential mechanism. When not the case, they show that there is no truthful mechanism that will improve on the sequential one. \n- The mechanism is relatively simple in principle and the idea behind it is natural (divide the population in increasing batch sizes and have them vote to decide on the allocation). It should be not too hard to implement in practice (up to getting the problem parameters right)\n- The experiments complement the theoretical results well, showing that even just 2 batches already improve results significantly compared to the sequential algorithm. \n\nWeaknesses:\n- the model is still simple and first-cut, as acknowledged by the authors. The agents are fully symmetric (before they receive their signals), and all have the same utility/need for an organ.\n- the randomness in the allocation may be undesirable, in the sense that an agent that is first of the remaining list might be skipped.\n- What is the justification for agents having a private signal on the quality of the organ, versus there being a public signal? Why would individuals get different information about the organ in practice? It would be nice to talk about this a bit more. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors acknowledge the limitations of the paper. The current paper is one that could start an important line of work that will lead to relevant social and healthcare impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "l7nXLgxya4Y", "reviewer": "Reviewer_2Yd7", "summary": "This paper presents an idea to improve the correctness of an allocation when the quality of the good must be inferred from agents who learn from each other. The authors set up a problem of allocating one object to a group of agents. The object is either of good or bad quality and each agent has a noisy IID signal of the quality. Together, they have a pretty good estimate of the quality. But each agent may have reasons to withhold their signal in order to avoid getting a bad object or attempt to acquire a good object. With incentives and learning together, the allocation can fail badly using a standard approach of offering the item to each agent sequentially to either accept or reject. The authors prove that, in their simplified model, only the first two agents play a role. If both of the first two agents reject the object, then every agent will reject the object, since they learn about quality from each other. Observing two rejections is enough to update every agents' belief to below threshold. The authors propose instead a clever algorithm. The planner offers the object to a batch of agents at a time. The batch size is calculated to maximize correctness subject to incentive compatibility. If every agent in the first batch rejects the object, the object is offered to a new, larger, batch of agents. The authors prove that, if the signals are more informative than the prior, then their mechanism is incentive compatible and is significantly more correct (has higher social welfare) than the sequential offer mechanism. The authors also prove that if the prior is more informative than the signals, then no mechanism can do better than the sequential offer mechanism.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper provides a clever algorithm to solve a stylized version of an interesting and realistic problem. The authors do a fantastic job of providing explanations and intuition behind their proofs and math. The algorithm is a satisfying solution. The paper is a good illustration of how incentives and learning can collide to interfere with one another, and provides a natural solution that will probably generalize to less stylized cases.\n\nI generally like the paper, but I have several quibbles. First, using organ donation as the primary motivator, highlighted in the first sentence of the abstract, seems like a stretch. The stylized model does not really fit the organ donation example. In organ donation, organs are not just \"good\" and \"bad\" for everyone. The quality of an organ for an agent is highly personalized, according to the level of match with blood type as the highest-order bit and with many other factors. If an organ is not good for one patient, it should mean little for the next patient. Also, patients themselves don't have the best information about the quality of an organ: doctors and hospitals do. Presumably, if the organ is \"bad\", the hospital system will not offer it to anyone. Finally, the organ application seems like it is thrown in just to draw interest: the authors make no attempt to use real data from organ exchanges in the paper and don't really discuss how their stylized model diverges from the application complexities. The paper is a theory paper with simulations: I encourage the authors to be more clear about the strength of fit to applications.\n\nReal estate might be a better application. When a house is on the market for a long time without being sold, buyers may think, \"something must be wrong with the house\". Agents do have information about the house. It's still not perfect, since real estate values are also subjective, and since the real estate market involves prices. In general, I suggest the authors not highlight an application in detail unless some real data is used or care is taken to discuss the fit of theory to reality. Potential applications can be mentioned in the intro, but I wouldn't highlight one of them in the first sentence of the abstract.\n\nSecond, I'd like more discussion of how important key assumptions are to the analysis. In particular, the fact that the true positive rate equals the true negative rate (line 97) seems like a strong and unrealistic assumption.\n\nThird, the simulations don't add a whole lot, in part because the theory is strong. Using some kind of real data would make the paper much stronger than running simulations.\n\nWhy isn't V_GREEDY one of the simulated algorithms? Why are only the 1- and 2-batch algorithms simulated? This seems strange. The main algorithm in the paper is V_GREEDY. I would expect this to be simulated if nothing else. \n\nWhen defining incentive compatibility (line 127), I suggest the authors mention that agents will update u as they learn from other agents.\n\nIn Figure 3, how does V_ALL achieve perfect correctness? Presumably, even V_ALL will allocate incorrectly with some small probability, if, for example, many agents receive an incorrect signal by random chance.\n\nSome minor suggestions:\n\nthousands of future lives.\nthousands of lives.\n\nLine 45: \"the list\" -->\n\"the waiting list\", or \"the list of agents\"\n\n=====\nAfter author response:\n\nI read the authors' response and the other reviews. The authors addressed my concerns well. I don't think it's a slam-dunk paper, but I do think it's worthy of being accepted, especially given the unusual consensus (on ratings) among the reviewers. It was the best submission among those that I reviewed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, although the authors may have overstated the realism of their approach for reducing discards in organ donation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Nw91R56TvXN", "reviewer": "Reviewer_ct3Q", "summary": "This paper studies how to allocate an object with unknown quality (only prior is known) to strategic agents. The strategic agents have their own private signals (drawn i.i.d. from another common prior) about the quality of the object and they would update their beliefs after observing other agents' decisions. \n\nThe authors point out that sequentially offering the object would lead to a cascading effect; in particular, only the first two agents decide the outcome of allocation. In contrast, offering the object to all the agents to elicit their private beliefs all together would lead to an efficient allocation, if without taking strategic behavior into account. The authors propose a novel mechanism, which offers the object to agents batch-by-batch, leading to an improvement in the allocation performance. Their results are supported and validated using simulations.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper is well-written, clear, and easy to follow. The problem studied is nicely motivated by important real world applications. The collection of theoretical results is novel and interesting, which also gives interesting and useful insights to understand the problem. This work also opens many interesting follow-up questions to consider. The reviewer did not check all the proofs but they all look plausible in hindsight. \n\nComments:\n1. It is surprising to see that two agents would determine the outcome in sequential offering mechanisms. The reviewer wonders perhaps this result is mainly due to the i.i.d. assumption. What would happen if the agents are not identical?\n\n2. The reviewer really likes Lemma 2. It is very interesting to see that in order to achieve IC, the batch size cannot be too large or too small.\n\n3. Given that the quality of the object is a binary, possibly the only relevant voting rule is majority. It would be interesting to see how to extend the results to an environment where the quality of the object is no longer a binary; and understand which voting rule could give the best outcome.\n\n4. There is no theoretical guarantee on how the greedy voting mechanism performs. It would be great to figure out whether the greedy voting mechanism is indeed optimal; if no, then understand what approximation does the mechanism give and also find out the optimal mechanism.\n\n5. Figure 3 is confusing. Is V_GREEDY and V_OPT the same? Could we try V_GREEDY^K with K > 2? Is it better than V_GREEDY^2?\n\nMinors:\n*. After reading Lemma 2, the reviewer is curious to see a table or a plot of upper and lower bounds. This is shown in Figure 2 but it might be better to provide a reference to the figure here so that the readers do not need to wonder about the bounds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of this paper is on the i.i.d. assumption for agents. The i.i.d. assumption, to some extent, assume that each agent is identical, which is probably not true in practice. For example, an agent may prefer an object more than another agent due to the level of compatibility. It would be very interesting to extend the results to the case in which the agents' priors are not identical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is an easy and uncontroversial accept.
Decision: Accept (Poster)