Collapse all | Expand all

Consistency 7

Rule: a / an agreement 5

Prefix: \b

Pattern: a [aeiou]2

240 In a one-shot scenario, the simple serial dictatorship is an appealing
503 iff a unique series of moves down the tree occurs, $m_1,m_2,\ldots

Pattern: an [bcdfghjklmnpqrstvwxz]3

108 thus the usefulness of the platform as a whole. An historic example
308 using an LP. By satisfying the equity criterion, we trivially are
419 infeasible: we cannot solve an LP every time an individual's budget

Rule: can not 0

Prefix: \b
Suffix: \b

Pattern: can not0

No matches

Rule: double words 2

Prefix: \b
Suffix: \b

Pattern: (\w+)\s+\12

292 quickly exhaust the capacity of those on top. In short order, the the
306 We show that when a collection of budgets and and values permits a

Rule: Improper Latinate Express 0

Use e.g. to mean "for example", and i.e. to mean "that is".
Prefix: \b
Suffix: \b

Pattern: i\.e\.0

No matches

Pattern: e\.g\.0

No matches

Pattern: etc\.0

No matches

Formal rules 113

Rule: That / Which 98

Prefix: \b
Suffix: \b

Pattern: \w+ \w+ which3

136 ``buy'' probability shares, giving a bistochastic matrix which can be
312 propose a substitute which we call the ``reverse tontine'' (RT)
540 the $m+1$ case in which we add a new position $v'$ and a new

Pattern: \w+ \w+ that95

61 several attractive properties that make it suitable for
89 inefficient, though there are other works that take alternate views,
98 visibility, and even those that do use prices do not rely solely on
100 ``paid'' results and ``organic'' search results that are not
104 There are several possible answers, but the general explanation is that individual platform member preferences and willingness to pay do
107 example is that selling visibility might undermine the credibility and
110 companies paying DJ's to play certain songs. The platform might worry that those choosing to pay for position might be adversely selected,
129 economic allocation problem, in that the platform has a number of slots that differ in their value and a number of items---people,
158 platforms---has properties that make the standard economic approaches
159 unattractive. One difference is that the economic literature is
166 problem. Let us assume that we have $n$ individuals that we need to
171 stochastic assignment mechanisms, i.e., a mechanisms that will place
179 conditional, i.e., we are assuming that all individuals have identical
188 matrix is identical to that generated by the serial dictatorship.}
191 scenario and our setting is that the economic literature was motivated
199 important. A final difference that is common to many (but not all)
200 two-sided platforms is that the limited capacity of the platform
201 participants suggests that frequent changes in ``merit'' should be
210 creator is likely to generate strong emotions. Whether they perceive it that way or not, the platform creator is implicitely assigning
218 shares. Further, this is plain from the fact that awards should be
219 ``according to merit''; for all men agree that what is just in
231 allocate by a lottery that treats individuals exactly the same (a
236 exhausted. This is actually the only mechanism that is fair and
237 efficient, in the sense that a higher-ranked individual would never
242 same set of individuals, it can easily run afoul of Aristotle's theory that equals should be treated equally, as well as his argument that
243 that equals should be treated equally, as well as his argument that
247 $b_1 = 0.8$ and $b_2 = 0.2$ that must be assigned to two positions that offer value (i.e., visibility) worth $v_1 = 80$ and $v_2 =
263 course means that sometimes the strictly lower-merit individual gets
265 of fairness in expectation. We want the mechanism to capture the notion that likes should be treated alike, which in this case means
266 notion that likes should be treated alike, which in this case means that expected value is continuous in merit. It practically goes
279 effectively zero, which means that every visitor can be shown the
280 ``best'' page without that page being consumed. While this
281 non-rivalrousness is true of web pages, it is not true for many other things that might be returned from search, such as individual buyers
288 dates, knit so many custom sweaters, etc.). The issue is that
295 contacts. This characteristic makes it critical for applied purposes that budgets can be updated in nearly real-time.
306 We show that when a collection of budgets and and values permits a
309 ensured continuity and monotonicity. However, we demonstrate that this
338 ^{2}\,\] To simplify notation, we suppose without loss of generality that $\sum_{i}b_{i}=\sum_{j}v_{j}=1$ and therefore our equity
340 condition is merely that $b_{i}=\sum_{j}p_{ij}v_{j}$ for all $i$. It
341 is obvious that the matrix of marginal probabilities, $P$, should be
356 of Birkhoff \cite{marcus}. The main idea is that if we are given
383 \STATE Let $P^{*}$ be the probability matrix that minimizes $\left\Vert Pv-b\right\Vert _{2}^{2}$.
393 \STATE \COMMENT{By \cite{marcus} it must be the case that $\pi_{ij}=1$
398 \STATE \COMMENT{By \cite{marcus} it must be the case that this reduces the
401 \STATE \COMMENT{At this point we now know that $P^{*}$ is a convex combination
414 algorithm shows that meeting the equity criterion is possible in some
417 gives us continuity in merit. However, in the platform applications that motivated the problem, this approach is likely to prove
425 assignments as they are needed, in the order that they are likely to
446 individuals in that step. The name was chosen because in this
471 Given the description of the Algorithm~\ref{alg:tontine}, one might worry that it would require $n-k$ re-normalizations of the budgets at
475 unattractive. Fortunately, there is a simple and fast algorithm that
493 assigned to that position. We complete the process by moving back up
494 the tree, ``repairing'' the values for each tree to reflect that the
539 continuous. Now, we assume that $x_m(.)$ is continuous and consider
544 immediately and receives $v^* = \max v \cup v'$. Let us denote that
547 get selected in that round, some other individual $k$ is selected,
563 We can see that $x_{m+1}()$ is a finite linear combination of
594 k < n$. We are interested in the probability that the individual
609 Because $b_h > b_l$ and by the assumption that both the high and low
612 S_m(b)^{-1})$, which means that every term of $1-F(k; b_h)$ is less
624 In this section we show that conventional approaches to ordering
640 in search results reflects the merit of the individuals that
641 participate in the results. oDesk is an online labor marketplace that
645 \item Employers can leverage a search interface that allows them to
646 retrieve contractor profiles that are relevant to some
657 contractor visibility and merit estimates. In case of search, the way that oDesk ranks contractors makes them more or less visible to the
659 employers. Thus, the profile views that the contractors receive
660 through clicks on the search results are indicative of the visibility that oDesk provides them. In case of job applications, the email
663 (around 10 applicants) makes it exceeedingly likely that the employer
704 for consecutive positions in search results. In the next paragraph we show that such distribution is not justified by the contractor merit
719 rate, defined as the ratio of his job applications that evolved into
725 the search ranking imposes an artificial boost on visibility that is
727 distrcibutions shows that there are many contractors who have almost
735 In this section we compare the algorithms that we have presented in
737 condition. For our comparison we use synthetic data that capture
739 population. In all of the scenarios we assume that the visibility in
740 different rank positions follow the Zipfian distribution that we
760 section, since our experiments showed that the distribution types have
777 better the algorithm. We observe that tree-based can rank up to $1000$
783 convinced us that it cannot be used in practice. To summarize, the
790 Although we showed that the RT algorithm is fast enough to be applied
795 merit, two properties that are missing from the vanilla assortative
848 ranking yields significantly greater RMSE that the other ranking
849 approaches. Finally, note that the RT ranking yields RMSE that is very
851 for small values of $\alpha$ that yield distributions that were not
852 observed in the oDesk dataset. Thus, we can conclude that the RT
853 algorithm yields visibility that is close to the equitable allocation
865 number of additional criteria for evaluating assignment mechanisms that
866 are relevant in the platform/repeated assignment setting that we are
867 focused on. We show that it is possible to create an assignment that
869 algorithm, but also show that the standard solution is infeasible for
870 web-scale applications. As a substitute, we proposed an algorithm RT that has some nice properties that make it well-suited for
871 that has some nice properties that make it well-suited for
873 criterion. However, we hope that future work might demonstrate how
875 past allocations to yield assignments that are equitable in

Rule: Between / Among 5

Prefix: \b
Suffix: \b

Pattern: (between|among)5

99 them. For example, search engines draw a sharp distinction between
177 difference between this setting the common economic allocation
190 Another important difference between the classic economic allocation
256 the two individuals become in merit, gap between their expected payoff
726 not justified from an individual's merit. The gap between the two

Rule: Fewer / Less 5

Prefix: \b
Suffix: \b

Pattern: (fewer|less)5

181 less. As such, the serial dictatorship and the probabilistic
365 the matrix $(1-t)^{-1}(P-t\Pi)$ has one fewer nonzero entry than
612 S_m(b)^{-1})$, which means that every term of $1-F(k; b_h)$ is less
658 that oDesk ranks contractors makes them more or less visible to the
778 individuals in much less than a second. The tree-based RT achieves

Rule: Sentence End in a Preposition 5

Prefix: \b
Suffix: \.

Pattern: about0

No matches

Pattern: above0

No matches

Pattern: across0

No matches

Pattern: after0

No matches

Pattern: against0

No matches

Pattern: along0

No matches

Pattern: alongside0

No matches

Pattern: amid0

No matches

Pattern: amidst0

No matches

Pattern: among0

No matches

Pattern: amongst0

No matches

Pattern: around0

No matches

Pattern: as0

No matches

Pattern: aside0

No matches

Pattern: at0

No matches

Pattern: athwart0

No matches

Pattern: atop0

No matches

Pattern: barring0

No matches

Pattern: beford0

No matches

Pattern: below0

No matches

Pattern: beneath0

No matches

Pattern: beside0

No matches

Pattern: besides0

No matches

Pattern: between0

No matches

Pattern: beyond0

No matches

Pattern: but0

No matches

Pattern: by0

No matches

Pattern: circa0

No matches

Pattern: concerning0

No matches

Pattern: despite0

No matches

Pattern: down0

No matches

Pattern: during0

No matches

Pattern: except0

No matches

Pattern: failing0

No matches

Pattern: following1

755 The comparison setting is the following. For different sizes $n$ of

Pattern: for0

No matches

Pattern: from0

No matches

Pattern: in0

No matches

Pattern: insi0

No matches

Pattern: like0

No matches

Pattern: minus0

No matches

Pattern: near0

No matches

Pattern: next0

No matches

Pattern: notwithstanding0

No matches

Pattern: of0

No matches

Pattern: off0

No matches

Pattern: on3

187 where they would eat $1/n$, and so on. The resultant bistochastic
427 position and the second position before the third, and so on.
867 focused on. We show that it is possible to create an assignment that

Pattern: onto0

No matches

Pattern: opposite0

No matches

Pattern: out1

149 option until time runs out. \cite{budish2009implementing} gives a

Pattern: outside0

No matches

Pattern: over0

No matches

Pattern: pace0

No matches

Pattern: past0

No matches

Pattern: per0

No matches

Pattern: plus0

No matches

Pattern: regarding0

No matches

Pattern: round0

No matches

Pattern: save0

No matches

Pattern: since0

No matches

Pattern: than0

No matches

Pattern: tthroughout0

No matches

Pattern: till0

No matches

Pattern: times0

No matches

Pattern: to0

No matches

Pattern: toward0

No matches

Pattern: towards0

No matches

Pattern: under0

No matches

Pattern: underneath0

No matches

Pattern: unlike0

No matches

Pattern: until0

No matches

Pattern: up0

No matches

Pattern: upon0

No matches

Pattern: versus0

No matches

Pattern: via0

No matches

Pattern: with0

No matches

Pattern: within0

No matches

Pattern: without0

No matches

Pattern: worth0

No matches

Punctuation 76

Rule: No space before parentheses 28

Pattern: \w\(28

461 $b_i \left(\sum_j b_j\right)^{-1}$.
482 $t$ are $r(t)$ and $l(t)$, respectively. Each node has a value, $|t|$:
484 |l(t_j)| + |r(T_j)|$. If a node is missing children, its value is just
489 number $\gamma \sim U[0,1]$. If $\gamma < \frac{|l(t_0)|}{|l(t_0)| +
490 |r(t_1)|}$, we move to the left child node; otherwise we move to the
508 Pr(b_i) = \frac{|t_1|}{|l(t_0)| + |r(t_0)|} \times
509 \frac{|t_2|}{|l(t_1)| + |r(t_1)|} \times \ldots \times
510 \frac{b_i}{|l(t_{k-1})| + |r(t_{k-1})|}
512 Because $|t_k| = |r(t_k)| + |l(t_k)|$, we can cancel all numerators
514 numerator. This gives us $Pr(b_i) = \frac{b_i}{|l(t_0)| + |r(t_0)|}$,
515 and since $|t_0| = \sum_j b_j$, $Pr(b_i) = \frac{b_i}{\sum_j b_j}$.
519 %The computational complexity is $O(n \log n)$ and the memory
520 %complexity is $O(n)$.
533 with budget $b_i$ when there are $n$ other individuals as $x_n(b_i,
536 $x_2(b_1, \vec{b}, \vec{v}) = b_1v_1 + b_2v_2$ and $x_2(b_2,
539 continuous. Now, we assume that $x_m(.)$ is continuous and consider
558 \left(1- s_{m+1}(i) \right)
575 v_2$ is $\mathbf{E}[u_1] = b_1 \left(v_1 + v_2\right)$ while the
591 $S_m(b)$ as the expected sum of the budgets for the individuals
596 can think of as a cdf, $Pr(q \le k) = F(k; b)$. We can write the
600 1 - F(k; b_l) = \left(1-b_l\right)\left(1-\frac{b_l}{S_1(b_l)}\right)
601 \ldots \left(1 - \frac{b_l}{S_k(b_l)} \right)
605 1 - F(k; b_h) = \left(1-b_h\right)\left(1-\frac{b_h}{S_1(b_h)}\right)
606 \ldots \left(1 - \frac{b_h}{S_k(b_h)} \right)
611 $S_k(b_h) = S_k(b_l)$, and hence $(1-b_h S_m(b_h)^{-1}) < (1-b_l
612 S_m(b)^{-1})$, which means that every term of $1-F(k; b_h)$ is less
613 than every term of $1-F(k; b_k)$ and thus the distribution of outcomes
824 \sqrt{\frac{\sum_{i=1}^n\left(\frac{b_i}{\sum_{j=1}^n

Rule: No Space after period 37

Pattern: \.\w+37

65 \category{J.4}{Social and Behavioral Sciences}{Economics}
66 \category{J.m}{Computer Applications}{Miscellaneous}
169 ``value'' $v$ (i.e., an associated visibility) such that $v_1 > v_2 >
171 stochastic assignment mechanisms, i.e., a mechanisms that will place
179 conditional, i.e., we are assuming that all individuals have identical
225 indivisible, e.g., jobs, unpleasant duties, artwork, custody of
247 $b_1 = 0.8$ and $b_2 = 0.2$ that must be assigned to two positions
248 that offer value (i.e., visibility) worth $v_1 = 80$ and $v_2 =
269 non-decreasing in merit (i.e., an individual should never wish they
273 In situations where search is returning information (e.g., websites,
286 capacity, which is characteristic of many two-sided platforms (e.g.,
335 least-squares sense, i.e. we find marginal probabilities $p_{ij}$ that
354 precisely the matrix $P^{*}$, i.e. that $p_{ij}^{*}=\sum_{k}\alpha_{k}\pi_{ij}^{k}$
359 that $p_{ij}>0$ (i.e. $\Pi$ only has $1$'s in entries whose corresponding
362 i.e. \[
379 the $\alpha_{k}$'s, i.e. $p_{ij}^{*}=\sum_{k}\alpha_{k}\pi_{ij}^{k}$
387 \STATE Let $Q$ be defined by $q_{ij}=\left\lceil p_{ij}\right\rceil $ (i.e.
406 \mathrm{minimize}_{\alpha_{1},\dots,\alpha_{K}}\left\Vert (\alpha_{1}\Pi_{1}+\cdots+\alpha_{K}\Pi_{K})-P^{*}\right\Vert _{2}^{2} & & s.t.\\
426 be needed, i.e., we can learn the first position before the second
586 % http://en.wikipedia.org/wiki/Stochastic_dominance
639 marketplace\footnote{http://www.odesk.com} to study how the visibility
671 % Shape: alpha = 0.2884794
672 % Upper cutoff: B = 8.565862e-05
673 % [ Normalization: C = 557.3199 ]
679 % Observed: 233215 66207.00 19856.00 13163.00 10823.00 8839.00 ...
680 % Expected: 233215 75584.19 26889.86 15340.85 10399.26 7719.41 ...
684 % 59884.04 14 0
686 \includegraphics[width=0.5\columnwidth]{../simulations/results/click_distribution.png}
687 \includegraphics[width=0.5\columnwidth]{../simulations/results/interviewrate_distribution.png}
701 distribution to the data and the estimated exponent is 1.35. Our
709 % \includegraphics[width=0.4\columnwidth]{../simulations/results/interviewrate_distribution.png}
759 $1.35$. We do not report results for other distributions in this
766 \includegraphics[width=0.6\columnwidth]{../simulations/results/performance.png}
811 values for $\alpha$: $100$, $10$, $5$, $1$ and $0.5$. Although
813 distribution with exponent $1.35$ to model the visibility distribution
829 \includegraphics[width=0.6\columnwidth]{../simulations/results/approximation.png}
880 \bibliography{allocating_visibility.bib}

Rule: Multiple spaces after period 10

Pattern: \. +\w+10

57 label proportional equity. We show how to construct allocations
108 thus the usefulness of the platform as a whole. An historic example
118 the platform. For example, craigslist orders results within
168 vector of budgets, $\vec{b}$. Each of the $n$ positions has a
199 important. A final difference that is common to many (but not all)
207 is often not a website or a product but a person. This is a
368 Algorithm \ref{alg:find-equitable}. Since Algorithm \ref{alg:find-equitable} requires that we solve a bipartite matching problem $\mathcal{O}(n^2)$ times, and since the Hungarian algorithm requires $\mathcal{O}(n^3)$ running time \cite{burkard2009assignment}, the overall complexity of Algorithm \ref{alg:find-equitable} is $\mathcal{O}(n^5)$.
594 k < n$. We are interested in the probability that the individual
726 not justified from an individual's merit. The gap between the two
870 web-scale applications. As a substitute, we proposed an algorithm RT

Rule: Serial comma 0

Pattern: , \w+, and0

No matches

Rule: No serial comma 1

Pattern: , \w+ and1

80 In traditional markets, buyers and sellers are responsible for making

Betes noire 0

Rule: Using "different than" or "different to" 0

Prefix: \b
Suffix: \b

Pattern: different (than|to)0

No matches

Rule: He or She for personal pronouns 0

Prefix: \b
Suffix: \b

Pattern: (he|she)0

No matches

Rule: Adverb Start to Sentence 0

Prefix: \b
Suffix: \b

Pattern: [A-Z][a-z]+ly,0

No matches

Rule: Irregardless 0

Prefix: \b
Suffix: \b

Pattern: iregardless0

No matches

Rule: Finalize 0

Prefix: \b
Suffix: \b

Pattern: finalize0

No matches

LaTeX punctuation 19

Rule: No Space Prior to Citation 8

Pattern: \w \\cite8

90 claiming it depends on a number of factors \cite{becker1993simple}.}
238 envy a lower-ranked individual \cite{balinski1999tale}.
356 of Birkhoff \cite{marcus}. The main idea is that if we are given
368 Algorithm \ref{alg:find-equitable}. Since Algorithm \ref{alg:find-equitable} requires that we solve a bipartite matching problem $\mathcal{O}(n^2)$ times, and since the Hungarian algorithm requires $\mathcal{O}(n^3)$ running time \cite{burkard2009assignment}, the overall complexity of Algorithm \ref{alg:find-equitable} is $\mathcal{O}(n^5)$.
391 algorithm \cite{burkard2009assignment} with the matrix $Q$ as an
393 \STATE \COMMENT{By \cite{marcus} it must be the case that $\pi_{ij}=1$
398 \STATE \COMMENT{By \cite{marcus} it must be the case that this reduces the
435 procedural justice \cite{rawls1999theory}, which is concerned with the

Rule: Punctuation mark outside quotation mark 0

Pattern: \w+''[.?,]0

No matches

Rule: Dashes 10

Prefix: \w
Suffix: \w

Pattern: ---10

130 slots that differ in their value and a number of items---people,
157 motivation for this paper---the allocation of visibility on two-sided
158 platforms---has properties that make the standard economic approaches
216 [T]his is the origin of quarrels and complaints---when either equals
315 does better than monotonicity---the distribution of outcomes for a
429 One other desirable feature for the algorithm---a feature not usually
430 seen as an important attribute---is conceptual simplicity, as it will
434 attempting to deliver, is only one kind of justice---there is also
625 platform participants---statically ranking individuals based on some
627 ranking---leads to radically unequal allocations of visibility. We do

Pattern: --- 0

No matches

Pattern: ---0

No matches

Pattern: ---10

130 slots that differ in their value and a number of items---people,
157 motivation for this paper---the allocation of visibility on two-sided
158 platforms---has properties that make the standard economic approaches
216 [T]his is the origin of quarrels and complaints---when either equals
315 does better than monotonicity---the distribution of outcomes for a
429 One other desirable feature for the algorithm---a feature not usually
430 seen as an important attribute---is conceptual simplicity, as it will
434 attempting to deliver, is only one kind of justice---there is also
625 platform participants---statically ranking individuals based on some
627 ranking---leads to radically unequal allocations of visibility. We do

Rule: Improper Quotation Marks 1

Pattern: "1

442 We propose a simple approach we call the ``Reverse Tontine" (RT) that

LaTeX formatting 68

Rule: No space between number and percent symbol 35

Pattern: \%35

2 %\documentclass[prodmode,acmec, draft]{acmsmall}
5 %\usepackage{algorithm}
21 %\usepackage{setspace}
22 %\doublespacing
24 % Document starts
28 % Page heads
518 %\begin{prop}
519 %The computational complexity is $O(n \log n)$ and the memory
520 %complexity is $O(n)$.
521 %\end{prop}
522 %\begin{proof}
523 % TK.
524 %\end{proof}
586 % http://en.wikipedia.org/wiki/Stochastic_dominance
669 %Zipf-Mandelbrot LNRE model.
670 %Parameters:
671 % Shape: alpha = 0.2884794
672 % Upper cutoff: B = 8.565862e-05
673 % [ Normalization: C = 557.3199 ]
674 %Population size: S = Inf
675 %Sampling method: Poisson, with exact calculations.
677 %Parameters estimated from sample of size N = 10465514:
678 % V V1 V2 V3 V4 V5
679 % Observed: 233215 66207.00 19856.00 13163.00 10823.00 8839.00 ...
680 % Expected: 233215 75584.19 26889.86 15340.85 10399.26 7719.41 ...
682 %Goodness-of-fit (multivariate chi-squared test):
683 % X2 df p
684 % 59884.04 14 0
708 %\begin{figure}[t]
709 % \includegraphics[width=0.4\columnwidth]{../simulations/results/interviewrate_distribution.png}
710 % \caption{Interview rate at oDesk over a period of eight months.}
711 % \label{fig:interviewrate}
712 %\end{figure}

Rule: Currency - Close up (7.6) 19

Pattern: \$[0-9]19

186 to eat $1/n$ and then, all at once, all would move to position 2,
187 where they would eat $1/n$, and so on. The resultant bistochastic
258 individual $1$ gets a (proportionally speaking) windfall of $30$ and
259 individual $2$ loses $50$, no matter how small $\epsilon$.
348 problem is $0$ precisely when $P$ satisfies the equity criterion.
359 that $p_{ij}>0$ (i.e. $\Pi$ only has $1$'s in entries whose corresponding
361 minimum value of $P$ whose corresponding entry in $\Pi$ is $1$,
388 $Q$ has a $1$ in it whenever the corresponding entry of $P$ is
593 individual with budget $b$. Choose any position $k$ such that $1 \le
612 S_m(b)^{-1})$, which means that every term of $1-F(k; b_h)$ is less
613 than every term of $1-F(k; b_k)$ and thus the distribution of outcomes
759 $1.35$. We do not report results for other distributions in this
777 better the algorithm. We observe that tree-based can rank up to $1000$
782 than $200$, since the $6$ hours it took to rank $200$ individuals
804 point $1$. That means, that all of the sampled individuals' merits
805 will be almost equal to $1$. As the value of parameter $\alpha$
811 values for $\alpha$: $100$, $10$, $5$, $1$ and $0.5$. Although
813 distribution with exponent $1.35$ to model the visibility distribution
850 close to $0$ for a wide range of $\alpha$ values. The RMSE increases

Rule: Table formatting: (a), (b), (c) or (1), (2), (3) 14

Pattern: \([a-z]\)14

482 $t$ are $r(t)$ and $l(t)$, respectively. Each node has a value, $|t|$:
520 %complexity is $O(n)$.
545 probability as $s_{m+1}(i) = \frac{b_i}{\sum_{b \in \vec{b} \cup b'}
548 with probability $s_{m+1}(k)$. When that $k$ individual is selected,
557 s_{m+1}(i) v^* +
558 \left(1- s_{m+1}(i) \right)
559 \sum_{k=1}^{m} s_{m+1}(k) x_m (b_i, \vec{b} \cup b' \setminus b_k, \vec{v} \cup v' \setminus v^*)
591 $S_m(b)$ as the expected sum of the budgets for the individuals
612 S_m(b)^{-1})$, which means that every term of $1-F(k; b_h)$ is less
688 \caption{(a) Click distribution per rank position in oDesk contractor
689 search. (left)\\ (b) Interview rate at oDesk over a period of eight months. (right)}
696 Figure~\ref{fig:clicks}(a) we plot the click distribution per search
721 Figure~\ref{fig:clicks}(b) we plot the interview rate distribution in
724 By comparing the two Figures~\ref{fig:clicks}(a),(b) we can see how

Pattern: \([0-9]\)0

No matches

Possession (pg112 from OGTS) 15

Rule: 15

Do not use the apostrophe when creating plurals (i.e., Joneses, not Jones's).
Use ' s after singular nouns and indefinite pronouns that do not end and after plural nouns that do not end in s.

Pattern: \w+'s15

84 advertising campaign. Regardless, the market's allocation of
106 not perfectly align with the platform's optimal strategy. One possible
110 companies paying DJ's to play certain songs. The platform might worry
147 individual starting at their preferred position. When an individual's
185 (since this is every individual's first choice). Each would be able
223 We can easily achieve Aristotle's ideal when goods are divisible, but
242 same set of individuals, it can easily run afoul of Aristotle's theory
301 monotonically increasing in an individual's budget and the expected
303 namely that an individual's share of the value from search position
419 infeasible: we cannot solve an LP every time an individual's budget
527 An individual's expected outcome from the RT mechanism is continuous
667 the contractor's merit.
716 constractor's ``success rate'' in seeking jobs. We looked at the job
718 through January 2012) and we calculated each contractor's interview
726 not justified from an individual's merit. The gap between the two

Rule: 0

Use an apostrophe after plural nouns ending in s.

Pattern: \w+s's0

No matches

Rule: 0

Do not use the apostrophe in the possessive pronouns hers, its, ours, yours and theirs.
Prefix: \b
Suffix: \b

Pattern: (her's|hers')0

No matches

Pattern: (their's|theirs')0

No matches

Pattern: (his's|his')0

No matches

Rule: It's vs. Its 0

Prefix: \b
Suffix: \b

Pattern: it's0

No matches

Synonyms 4

Rule: For Because / Why 0

Prefix: \b
Suffix: \b

Pattern: the reason for0

No matches

Pattern: the reason that0

No matches

Pattern: due to the fact that0

No matches

Pattern: owing to the fact that0

No matches

Pattern: in light of the fact that0

No matches

Pattern: considering the fact that0

No matches

Pattern: on the grounds that0

No matches

Pattern: this is why0

No matches

Rule: For although, even though 0

Prefix: \b
Suffix: \b

Pattern: despite the fact that0

No matches

Pattern: regardless of the fact that0

No matches

Pattern: nowithstanding the fact that0

No matches

Rule: For about 0

Prefix: \b
Suffix: \b

Pattern: as regards0

No matches

Pattern: in reference to0

No matches

Pattern: with regard to0

No matches

Pattern: concerning the matter of0

No matches

Pattern: where \w+ is concerned0

No matches

Rule: For may, might, can, could 0

Prefix: \b
Suffix: \b

Pattern: it is possible that0

No matches

Pattern: there is a chance that0

No matches

Pattern: it could happen that0

No matches

Pattern: the possibility exists for0

No matches

Rule: For more, less/fewer, better, worse 4

Prefix: \b

Pattern: increase2

847 distributions are not similar. As $\alpha$ increases the assortative
850 close to $0$ for a wide range of $\alpha$ values. The RMSE increases

Pattern: decrease2

703 \cite{ali2007robust} and indicate dramatic decrease in visibility even
806 decreases, the merit values get spreaded out and finally the Pareto

Rule: For must / should 0

Prefix: \b
Suffix: \b

Pattern: it is crucial that0

No matches

Pattern: it is necessary that0

No matches

Pattern: there is a need0

No matches

Pattern: tthere is a necessity for0

No matches

Pattern: it is important that0

No matches

Pattern: it is incumbent upon0

No matches

Pattern: cannot be avoided0

No matches

Rule: For before, after, as 0

Prefix: \b
Suffix: \b

Pattern: prior to0

No matches

Pattern: in anticipation of0

No matches

Pattern: subsequent to0

No matches

Pattern: following on0

No matches

Pattern: at the same time as0

No matches

Pattern: simultaneously with0

No matches

Rule: For can 0

Prefix: \b
Suffix: \b

Pattern: is able to0

No matches

Pattern: in a position to0

No matches

Pattern: has the capacity to0

No matches

Pattern: has the opportunity to0

No matches

Pattern: has the ability to0

No matches

Nominalizations 184

The subjects of the sentences name the cast of characters.
The verbs that go with those subjects name the crucial actions those characters are part of.

Rule: 184

Prefix: \b
Suffix: \b

Pattern: \w+ion of33

29 \markboth{Horton et al.}{The Allocation of Visibility on Two-Sided
32 \title{The Allocation of Visibility on Two-Sided Platforms}
71 P., Little, G. 2012. The Allocation of Visibility on Two-Sided
84 advertising campaign. Regardless, the market's allocation of
122 \cite{chilton2010task} for a discussion of this phenomena on MTurk.}
124 algorithmic notion of relevancy, such as tf-idf or PageRank
128 The allocation of visibility on a platform has clear analogies to the
157 motivation for this paper---the allocation of visibility on two-sided
164 As we explore the notion of treating different participants
212 visibility according to some notion of justice. This is likely to
290 the top results getting a large fraction of the views and hence
306 We show that when a collection of budgets and and values permits a
315 does better than monotonicity---the distribution of outcomes for a
325 In this section we show how to determine a collection of $n\times
326 n$ permutation matrices $\Pi_{k}$, together with a collection of
334 collection of permutation matrices whose equity is minimized in the
351 we now consider the problem of determining a collection of permutation
355 for all $i,j$. This is a straightforward application of a theorem
401 \STATE \COMMENT{At this point we now know that $P^{*}$ is a convex combination of the matrices $\Pi$ in $\mathtt{Permutations}$; we can merely
471 Given the description of the Algorithm~\ref{alg:tontine}, one might
563 We can see that $x_{m+1}()$ is a finite linear combination of
581 The distribution of outcomes for an individual first order
582 stochastically dominates (FOSD) the distribution of outcomes for any
583 other individual with a lower budget, facing the same collection of
597 probability of an individual being selected after $k$ as a function of their budgets. For $b_h$, we have:
610 individuals face the same collection of individuals, for all $k$,
613 than every term of $1-F(k; b_k)$ and thus the distribution of outcomes
617 A direct implication of Proposition \ref{prop:fosd} is that any
700 (the last position of the first results page). We fitted a Zipfian
736 terms of runtime performance and the satisfaction of the equity
816 For each distribution of merits we ran each of the algorithms $m$
830 \caption{RMSE in the approximation of equitable allocation for the
861 platforms, which is the allocation of visbility to platform

Pattern: \w+ed an1

870 web-scale applications. As a substitute, we proposed an algorithm RT

Pattern: \w+ of (the|a)52

93 by the design choices and policies of the platform. This power to
108 thus the usefulness of the platform as a whole. An historic example
133 absence of a price mechanism goes back to
165 differently, it will be useful to have a more formal statement of the
168 vector of budgets, $\vec{b}$. Each of the $n$ positions has a
175 as well as the distributional properties of the allocation
194 natural focus on the equity of the single realized allocation. In
197 different queries. As such, expected visibility and the properties of the distributio of realized outcomes becomes more interesting and more
200 two-sided platforms is that the limited capacity of the platform
203 continually appear at the top of the search results.
253 values change, the obviousness fairness of the simple serial
278 goods: the effect of the marginal visitor on the remaining visitors is
290 the top results getting a large fraction of the views and hence
298 \subsection{Overview of the paper}
303 namely that an individual's share of the value from search position
330 the $ij$th element of the matrix $\Pi_{k}$) satisfy the equity
355 for all $i,j$. This is a straightforward application of a theorem
378 $P^{*}$ is the marginal probability matrix of the $\Pi_{k}$'s and
401 \STATE \COMMENT{At this point we now know that $P^{*}$ is a convex combination of the matrices $\Pi$ in $\mathtt{Permutations}$; we can merely
403 recover the weighting of the matrices using convex optimization.}
431 make it easier for the individuals subject to the control of the
436 transparency and fairness of the process. Being able to clearly
454 vectors are of the same length. The algorithm returns an assignment
471 Given the description of the Algorithm~\ref{alg:tontine}, one might
472 worry that it would require $n-k$ re-normalizations of the budgets at
479 the parent node a value equal to the sum of the values of its
481 nodes $t \in T$. The right and left children of a non-terminal node
491 right. We then repeat the same procedure, using the values of the new
502 Let $b_i$ be the budget of a particular individual. They are selected
538 linear functions of the respective budgets and hence
550 $b_k$. For each of the $k$ scenarios this generates, this leaves the
590 distributions of the two individuals under RT. First, let us define
591 $S_m(b)$ as the expected sum of the budgets for the individuals
640 in search results reflects the merit of the individuals that
648 to any of the retrieved contractors.
660 through clicks on the search results are indicative of the visibility
664 will view each of the applications and the corresponding
666 an interview invitation or the probability of hiring is indicative of the contractor's merit.
700 (the last position of the first results page). We fitted a Zipfian
736 terms of runtime performance and the satisfaction of the equity
739 population. In all of the scenarios we assume that the visibility in
747 We compare the runtime performance of the EC algorithm
748 (Algorithm~\ref{alg:find-equitable}) and two different variations of the RT algorithm (Algorithm~\ref{alg:tontine}). In the first
757 sampling in the range $[0,1]$ and we set the visibility of each of the
762 we ran all of the three algorithms and we measured the runtime in
767 \caption{Runtime comparison of the three different assignment
780 benefits of the tree structure we use to expedite sampling. As far as
804 point $1$. That means, that all of the sampled individuals' merits
809 values. To evaluate the effect of the different rankings across the
816 For each distribution of merits we ran each of the algorithms $m$
820 allocation}. To evaluate the success of the algorithms in achieving
836 $m=1000$. The x-axis shows the value of the Pareto distribution

Pattern: was \w+en1

446 individuals in that step. The name was chosen because in this

Pattern: were \w+1

851 for small values of $\alpha$ that yield distributions that were not

Pattern: it was \w+1

819 since it was theoretically shown to achieve equitable visibility

Pattern: \w+ly95

53 visibility readily leads to inefficient (and arguably unfair)
58 with all of these properties, but we also show why this is likely to
88 that under a range of plausible assumptions, advertising is socially
91 By comparison, in electronic markets, visibility is inherently
98 visibility, and even those that do use prices do not rely solely on
103 Why do platforms not rely solely on prices to allocate visibility?
106 not perfectly align with the platform's optimal strategy. One possible
111 that those choosing to pay for position might be adversely selected,
116 When a platform entirely forgoes prices, visibility is still
120 (MTurk).\footnote{Not surprisingly, this time-based ordering leads to
140 only ordinal preferences are known. The two main solutions in the
142 serial mechanism. In the serial dictatorship, each person is serially
145 \cite{bogomolnaia2001new}, every individual simultaneously ``eats''
148 current position is totally consumed, they move to their next best
160 generally focused on cases where all individuals should be treated
161 equally, whereas platforms almost always want to give more visibility
165 differently, it will be useful to have a more formal statement of the
170 v_3 \ldots v_n$. In this paper, we will be concerned solely with
176 mechanism. This formalization immediately highlights another important
203 continually appear at the top of the search results.
210 creator is likely to generate strong emotions. Whether they perceive
211 it that way or not, the platform creator is implicitely assigning
212 visibility according to some notion of justice. This is likely to
223 We can easily achieve Aristotle's ideal when goods are divisible, but
229 Pure randomization works well when all should be treated equally, but
231 allocate by a lottery that treats individuals exactly the same (a
236 exhausted. This is actually the only mechanism that is fair and
241 solution, but if done repeatedly, with the same set of choices and the
242 same set of individuals, it can easily run afoul of Aristotle's theory
243 that equals should be treated equally, as well as his argument that
249 20$. The simple serial dictatorship is the only obviously fair
258 individual $1$ gets a (proportionally speaking) windfall of $30$ and
261 Intuitively, as $\epsilon$ gets smaller, the two individuals should
262 each get $v_1$ and $v_2$ in approximately equal proportion. This of
263 course means that sometimes the strictly lower-merit individual gets
267 that expected value is continuous in merit. It practically goes
268 without saying, but expected value should also be monotonically
275 result to every user in response to the same query. This relatively
276 static approach (with updates only made to reflect improved estimates
279 effectively zero, which means that every visitor can be shown the
287 most individuals can only work 40 to 50 hours per week, go on so many
292 quickly exhaust the capacity of those on top. In short order, the the
294 searchers are quickly discouraged by the low response rate to their
296 that budgets can be updated in nearly real-time.
301 monotonically increasing in an individual's budget and the expected
303 namely that an individual's share of the value from search position
308 using an LP. By satisfying the equity criterion, we trivially are
310 implementation is likely to prove computationally infeasible for the
316 higher budget individual first-order stochastically dominates the
318 generated very quickly and has limited memory requirements. It is also
324 \section{Allocating Visibility Equitably}
340 condition is merely that $b_{i}=\sum_{j}p_{ij}v_{j}$ for all $i$. It
344 easily solved using standard convex optimization methods (if desired
348 problem is $0$ precisely when $P$ satisfies the equity criterion.
354 precisely the matrix $P^{*}$, i.e. that $p_{ij}^{*}=\sum_{k}\alpha_{k}\pi_{ij}^{k}$
357 an $n\times n$ doubly stochastic matrix $P$, there must exist an
359 that $p_{ij}>0$ (i.e. $\Pi$ only has $1$'s in entries whose corresponding
364 Clearly if $t=1$ then $P$ is a permutation matrix. If $t<1$ then
366 $P$. We then perform this procedure recursively on the elements of
384 \STATE \COMMENT{This can be found quickly using the method of least-squares.}
402 of the matrices $\Pi$ in $\mathtt{Permutations}$; we can merely
418 that motivated the problem, this approach is likely to prove
423 continuity and monotonicity in merit, and ideally equity. It should be
425 assignments as they are needed, in the order that they are likely to
429 One other desirable feature for the algorithm---a feature not usually
432 algorithm to understand and hopefully support as just the resultant
434 attempting to deliver, is only one kind of justice---there is also
436 transparency and fairness of the process. Being able to clearly
438 way they can understand would be a potentially powerful advantage.
443 is nearly identical to the simple serial dictatorship, except that the
447 mechanism, it is desirable to ``die'' early (unlike an actual
473 step $k$, which combined with the steps needed to actually make the
475 unattractive. Fortunately, there is a simple and fast algorithm that
482 $t$ are $r(t)$ and $l(t)$, respectively. Each node has a value, $|t|$:
544 immediately and receives $v^* = \max v \cup v'$. Let us denote that
552 expected value recursively, as:
582 stochastically dominates (FOSD) the distribution of outcomes for any
589 respectively, with $b_h > b_l$. We want to compare the
625 platform participants---statically ranking individuals based on some
627 ranking---leads to radically unequal allocations of visibility. We do
633 equity criterion, which is only guaranteed by EC.
649 \item Employers may also wait for contractors to apply after they have
662 notification and the typically small number of applicants per job
663 (around 10 applicants) makes it exceeedingly likely that the employer
698 scale. The number of clicks drops from approximately 60K in the first
714 Any constructed measure of merit will be somewhat arbitrary and highly
779 also significantly faster runtime than the naive RT, which shows the
806 decreases, the merit values get spreaded out and finally the Pareto
808 extremely high merit values and many individuals with low merit
818 across the $m$ runs\footnote{We did not actually run the EC algorithm,
819 since it was theoretically shown to achieve equitable visibility
832 randomly sampled from a Pareto distribution with parameter $\alpha$.}
848 ranking yields significantly greater RMSE that the other ranking
849 approaches. Finally, note that the RT ranking yields RMSE that is very
868 satisfied the highly desirable ``equity'' criterion, using our RC

Pattern: for the reason that0

No matches

Pattern: due to the fact that0

No matches

Pattern: owing to the fact that0

No matches

Pattern: in light of the fact that0

No matches

Pattern: considering the fact that0

No matches

Pattern: on the grounds that0

No matches

Pattern: this is why0

No matches

Pattern: the reason for0

No matches

Spelling Concision 59

Rule: Negatives 2

Prefix: \b
Suffix: \b

Pattern: did not allow0

Replace:
prevented
No matches

Pattern: not certain0

Replace:
uncertain
No matches

Pattern: did not remember0

Replace:
forgot
No matches

Pattern: did not2

Replace:
failed to
781 the EC algorithm is concerned, we did not to run it for $n$ greater
818 across the $m$ runs\footnote{We did not actually run the EC algorithm,

Pattern: not many0

Replace:
few
No matches

Pattern: did not accept0

Replace:
rejected
No matches

Pattern: not diferent0

Replace:
alike / similar
No matches

Pattern: does not have0

Replace:
lacks
No matches

Pattern: did not consider0

Replace:
ignored
No matches

Pattern: not clearly0

Replace:
unclearly
No matches

Pattern: not possible0

Replace:
impossible
No matches

Pattern: not the same0

Replace:
difference
No matches

Pattern: did not stay0

Replace:
left
No matches

Pattern: not able0

Replace:
unable
No matches

Pattern: not old enough0

Replace:
too young
No matches

Rule: Pompous Diction 0

Prefix: \b
Suffix: \b

Pattern: cognizant of0

Replace:
aware of
No matches

Pattern: render0

Replace:
make / give
No matches

Pattern: utilization0

Replace:
use
No matches

Pattern: transpire0

Replace:
happen
No matches

Pattern: prior to0

Replace:
before
No matches

Pattern: apprise0

Replace:
inform
No matches

Pattern: eventuate0

Replace:
happen
No matches

Pattern: subsequent to0

Replace:
after
No matches

Pattern: advert to0

Replace:
mention
No matches

Pattern: initiate0

Replace:
begin
No matches

Pattern: deem0

Replace:
think
No matches

Pattern: contingent upon0

Replace:
dependent upon
No matches

Pattern: ascertain0

Replace:
find out
No matches

Pattern: transmit0

Replace:
send
No matches

Pattern: termination0

Replace:
end
No matches

Pattern: endeavor0

Replace:
try
No matches

Pattern: facilitate0

Replace:
help
No matches

Pattern: implement0

Replace:
start / carry out, begin
No matches

Pattern: envisage0

Replace:
think, regard, see
No matches

Rule: Meaningless Modifiers 57

Prefix: \b
Suffix: \b

Pattern: kind of1

434 attempting to deliver, is only one kind of justice---there is also

Pattern: really0

No matches

Pattern: basically0

No matches

Pattern: definitely0

No matches

Pattern: practically1

267 that expected value is continuous in merit. It practically goes

Pattern: actually3

236 exhausted. This is actually the only mechanism that is fair and
473 step $k$, which combined with the steps needed to actually make the
818 across the $m$ runs\footnote{We did not actually run the EC algorithm,

Pattern: virtually0

No matches

Pattern: generally1

160 generally focused on cases where all individuals should be treated

Pattern: certain1

110 companies paying DJ's to play certain songs. The platform might worry

Pattern: particular1

502 Let $b_i$ be the budget of a particular individual. They are selected

Pattern: individual45

86 individual actors.\footnote{There seems to be no consensus on the
105 that individual platform member preferences and willingness to pay do
145 \cite{bogomolnaia2001new}, every individual simultaneously ``eats''
147 individual starting at their preferred position. When an individual's
172 an individual $i$ at position $j$ with probability $p_{ij}$. We
174 individual $i$, which we will call $x^n_i = \sum_{j=1}^n p_{ij}v_j$,
185 (since this is every individual's first choice). Each would be able
234 first-ranked individual gets their first choice, the second gets to
237 efficient, in the sense that a higher-ranked individual would never
238 envy a lower-ranked individual \cite{balinski1999tale}.
250 solution: the higher merit individual gets the higher value
258 individual $1$ gets a (proportionally speaking) windfall of $30$ and
259 individual $2$ loses $50$, no matter how small $\epsilon$.
263 course means that sometimes the strictly lower-merit individual gets
269 non-decreasing in merit (i.e., an individual should never wish they
282 things that might be returned from search, such as individual buyers
301 monotonically increasing in an individual's budget and the expected
303 namely that an individual's share of the value from search position
316 higher budget individual first-order stochastically dominates the
317 outcomes for a lower budget individual. RT allocations can be
419 infeasible: we cannot solve an LP every time an individual's budget
453 $\vec{b}$ of individual budgets shares and $\vec{v}$ of values. Both
460 \STATE Draw an individual $i$ with probability equal to their budget share,
462 \STATE Assign individual $i$ to position $\max \vec
464 \STATE Remove the drawn individual from $\vec b$ and the selected position
487 To sample an individual, we start at the root node, $t_0$. It has a
488 value equal to the sum of all individual budgets. We draw a random
492 nodes children. Once we reach a terminal node, we have the individual
495 selected individual is no longer available for allocation.
502 Let $b_i$ be the budget of a particular individual. They are selected
527 An individual's expected outcome from the RT mechanism is continuous
532 Let us first define notation for the expected value of an individual
541 individual with budget $b'$.
546 b}$, which is continuous in $b_i$. If the individual $i$ does not
547 get selected in that round, some other individual $k$ is selected,
548 with probability $s_{m+1}(k)$. When that $k$ individual is selected,
551 individual $i$ facing an $m$-sized RT scenario. We can write the
581 The distribution of outcomes for an individual first order
583 other individual with a lower budget, facing the same collection of
593 individual with budget $b$. Choose any position $k$ such that $1 \le
594 k < n$. We are interested in the probability that the individual
597 probability of an individual being selected after $k$ as a function
726 not justified from an individual's merit. The gap between the two
751 individuals after each assignment of an individual to a position. In
817 times to obtain the average visibility for each individual $\bar{v_i}$

Pattern: given3

356 of Birkhoff \cite{marcus}. The main idea is that if we are given
471 Given the description of the Algorithm~\ref{alg:tontine}, one might
665 profiles. Given that an employer views a profile, the probability of

Pattern: various0

No matches

Pattern: specific1

83 some specific time and place, or it might require a massive

Pattern: for all intents and purposes0

No matches

Formatting 0

Rule: Spell out ordinals 0

Prefix: \b
Suffix: \b

Pattern: 1st0

No matches

Pattern: 2nd0

No matches

Pattern: 3rd0

No matches

Pattern: [4-9]th0

No matches

Pattern: 10th0

No matches

Rule: Make numbers plural without an apostrophe (7.1.5) 0

Pattern: [0-9]'s\b0

No matches

Acronyms 75

Rule: 75

Prefix: \b
Suffix: \b

Pattern: [A-Z][A-Z]+75

7 \renewcommand{\algorithmcfname}{ALGORITHM}
35 JOHN J. HORTON
37 JOHN GUNNAR CARLSSON
39 IOANNIS ANTONELLIS
41 PANAGIOTIS PAPADIMITRIOU
43 GREG LITTLE
110 companies paying DJ's to play certain songs. The platform might worry
308 using an LP. By satisfying the equity criterion, we trivially are
312 propose a substitute which we call the ``reverse tontine'' (RT)
314 but still ensures continuity and monotonicity in merit. In fact, RT
317 outcomes for a lower budget individual. RT allocations can be
371 \caption{Equity Criterion (EC). This algorithm takes as input a pair
383 \STATE Let $P^{*}$ be the probability matrix that minimizes $\left\Vert Pv-b\right\Vert _{2}^{2}$.
384 \STATE \COMMENT{This can be found quickly using the method of least-squares.}
385 \STATE Set $\bar{P}:=P^{*}$ and $\mathtt{Permutations}:=\emptyset$.
386 \WHILE{$\bar{P}$ has more than $n$ nonzero entries}
387 \STATE Let $Q$ be defined by $q_{ij}=\left\lceil p_{ij}\right\rceil $ (i.e.
390 \STATE Solve a maximum-weight bipartite matching problem using the Hungarian
393 \STATE \COMMENT{By \cite{marcus} it must be the case that $\pi_{ij}=1$
395 \STATE Set $\mathtt{Permutations}:=\mathtt{Permutations}\cup\Pi$.
396 \STATE Set $t=\min_{i,j:\pi_{ij}=1}p_{ij}$.
397 \STATE Set $\bar{P}:=(1-t)^{-1}(\bar{P}-t\Pi)$.
398 \STATE \COMMENT{By \cite{marcus} it must be the case that this reduces the
400 \ENDWHILE
401 \STATE \COMMENT{At this point we now know that $P^{*}$ is a convex combination
404 \STATE Let $K:=\left|\mathtt{Permutations}\right|$. Let $\alpha_{1},\dots,\alpha_{K}$
409 \RETURN $P^{*}$, $\mathtt{Permutations}$, and $\left\{ \alpha_{1},\dots,\alpha_{K}\right\} $.
413 Algorithm \ref{alg:find-equitable}, or the Equitable Criterion (EC)
419 infeasible: we cannot solve an LP every time an individual's budget
442 We propose a simple approach we call the ``Reverse Tontine" (RT) that
452 \caption{Reverse Tontine (RT). This algorithm takes as input vectors
459 \WHILE{there are unassigned individuals}
460 \STATE Draw an individual $i$ with probability equal to their budget share,
462 \STATE Assign individual $i$ to position $\max \vec
464 \STATE Remove the drawn individual from $\vec b$ and the selected position
466 \ENDWHILE
523 % TK.
527 An individual's expected outcome from the RT mechanism is continuous
535 under the RT mechanism, with $b_1 > b_2$ and $v_1 > v_2$, we have
551 individual $i$ facing an $m$-sized RT scenario. We can write the
582 stochastically dominates (FOSD) the distribution of outcomes for any
590 distributions of the two individuals under RT. First, let us define
614 for $b_h$ FOSD $b_l$.
630 (EC and RT) through a series of simulations. We compare the algorithms
632 be used in practice. We also assess how far RT deviates from the
633 equity criterion, which is only guaranteed by EC.
669 %Zipf-Mandelbrot LNRE model.
747 We compare the runtime performance of the EC algorithm
749 the RT algorithm (Algorithm~\ref{alg:tontine}). In the first
750 variation, called \emph{naive} RT, we renormalize the weights of
752 the second variation, called \emph{tree-based} RT, we leverage the
775 tree-based RT, the dashed line looks at the naive RT, and the dotted
776 line looks at the EC algorithm. The closer a line to the x-axis the
778 individuals in much less than a second. The tree-based RT achieves
779 also significantly faster runtime than the naive RT, which shows the
781 the EC algorithm is concerned, we did not to run it for $n$ greater
784 tree-based RT algorithm is much faster than the other algorithms and
790 Although we showed that the RT algorithm is fast enough to be applied
793 yield equitable visibility in the general case as the EC algorithm
794 does. However, the RT algorithm ensures continuity and monotonicity in
799 obtained from the RT and the EC algorithms in terms of their
818 across the $m$ runs\footnote{We did not actually run the EC algorithm,
822 (RMSE) defined as:
830 \caption{RMSE in the approximation of equitable allocation for the
837 parameter and the y-axis shows the RSME. There are three lines in the
839 looks at the RT ranking, the dashed line looks at the assortative
840 ranking and the dotted line looks at the estimated EC ranking. Note
841 that RMSE is 0 for the EC ranking, since the EC algorithm is
843 distribution. The assortative distribution has small RMSE for low
848 ranking yields significantly greater RMSE that the other ranking
849 approaches. Finally, note that the RT ranking yields RMSE that is very
850 close to $0$ for a wide range of $\alpha$ values. The RMSE increases
852 observed in the oDesk dataset. Thus, we can conclude that the RT
868 satisfied the highly desirable ``equity'' criterion, using our RC
870 web-scale applications. As a substitute, we proposed an algorithm RT

Text

3
13
20
23
27
31
33
45 }
46
64
69
73
76
78
102
115
126
138
155
163
189
204
214 Ethics:
228
239
245
260
271
284
297
305
321
322
323
349
362 i.e. \[
369
389 nonzero).
400 \ENDWHILE
421
428
439
450
457
463 v$.
466 \ENDWHILE
469
470
486
496
517
523 % TK.
525
531
542
553
554
561
562
567
579
608
616
620
623
634
637
655
668
676 %
681 %
683 % X2 df p
707
713
723
731
732
742
743
746
754
786
787
796 ranking.
797
815
823 \[
826 \]
856
857
859
877
878
881
882
884