under what conditions do they work? Vincent Chabault's recent book retraces the history of this company, which has received so much high praise over the years that it has been the object of virulent criticism. Two questions can be asked : one side how the company was able to "absorb" changes in the business environment, and other side at what cost to its original mission ? What working at the FNAC has meant to two generations of the firm's employees ?

Contributing to the times…and then adapting to them

The 1950's saw the emergence of a new middle class that was larger, financially better-off, and better-educated than the previous generation. The valid social aspirations of this rising group differed in various ways from those of their elders. The consumption of cultural products served them both a way of climbing the social ladder and as a sign that they had arrived. The FNAC offered an answer to the aspirations of these future clients and above all of its card-carrying members : young people hungry for distinctive signs of their social status and launched in professional path and way of life, if not new, had not been available to their parents. For them, cultural consumption is a mode of social rising and, both, a sign of it. The goal of the founders of the FNAC was to enhance the access of this new consumer group to cultural products (Chapter 2) into combating rival retailers' abuses in terms of price and quality. In addition to establishing a lowpricing policy, in 1954, Essel and Théret founded Contact, a magazine for members, which published the results of in-house comparative product tests that were conducted in their own laboratory since 1972. Pursuing its low-price purpose, the FNAC established its first discount bookshelf in 1974, a move that upset the delicate balance of publisherbookstore relationships and triggered a lively debate between free-pricing advocates and proponents of fixed-pricing that continued until passage of the so-called "Lang Law" in 1981 (witch fixed-price for books).

In 1980, the FNAC went public and was listed on the Paris stock exchange. Then, in 1985, it was bought by GMF in 1985 before being sold ten years later to François Pinault. From now, the process supplanting the founders' committedness is on with the single-minded pursuit of financial profitability (Chapter 4). Employees hired between 1960 and 1980 for their capacities for personal investment and under labor conditions that were the envy of the business world, were gradually replaced by staff with lower labor status. Tasks were rationalized, margins of employee autonomy vanished, and immediate profitability became the sole priority, while selling won over a focus onoriginality and high quality that had earlier established the company's reputation.

Innovations in personnel management came to an end, and the FNAC was transformed into one among many giant retail distributors, while cashing in on an image that was shaped in an earlier time.

The author sheds light on a segment of the history of the twentieth century middle class by providing a detailed description of two generations of FNAC employees and of the labor conditions under which they worked (Chapters 3 and 6). Through the mid-1980's, the middle class experienced continuous upward growth that provided access to better salaries and improved labor conditions, including increased access to jobs in the cultural sector. Despite continuous increases in educational levels and in the number of specialized degree programs available to them, however, labor conditions for members of the middle class began to deteriorate beginning in the mid-1980's, and work came to hold less interest as employees' margins of autonomy decreased.

A company "not like" the others that became one "among" others

The portraits of Essel and Théret before and after the company was formed shed light on their project and on their plans for implementing it (Chapter 1). Although they were not necessarily pioneers in every area, the sheer scale of their and their successors' concept of the stores and of their approach to fostering customer loyalty (in 1986, the member card became a credit card as well) profoundly altered the marketing of cultural products. The growth strategy of the FNAC began with the opening of stores in Paris, followed by expansion within France -beginning in Lyon in 1972 -and abroad, with the Brussels store opening in 1981. These impressively large facilities brought together a range of products that was unavailable elsewhere, and they made sustained efforts to organize encounters between authors and the public. Success was not long in coming : the number of membership cardholders, a minority of clients with the largest share of sales over the years, spiraled upward from 20,000 in 1955 to 250,00 in 1969, to 400,000 in France and Belgium by 1987, reaching the milestone figure of 1,000,000 in March of 2000.

Expanding the company was expensive, however, and there were lows as well as highs in terms of results. The GMF episode, led by Jean-Louis Pétriat, was of short duration because of investments that placed the company at risk. His tenure was long enough, however, for Pétriat to implement subsidiarization, which ensured that employee benefits obtained in some stores could not be applied to all company employees. He also initiated computerization, which, although obviously necessary, gradually reduced employee autonomy. Beginning in 1996, François Pinault accelerated these changes by centralizing purchasing under "Product Management" (except for books, which accounted for only 40% of centralized purchases in 2003), a step that resulted in significant economies-of-scale and increased profit margins. Innovations under Pinault also included an upper management hiring preference for grandes écoles graduates with well-established intellectual pedigrees instead of in-house promotions to management positions. During the 2000's, a site for on-line sales was established, and by 2008 there were fifty-nine stores outside France, while the number in France was increased to a total in the same year of seventy-eight stores in fifty-six cities, primarily in suburban ringcities intended to counter competition from rival cultural product retailers. The end of the decade has proved difficult, however. Denis Olivennes' recent replacement at the helm of the FNAC by the former CEO of Castorama signals the primacy of profitability over other considerations. The FNAC has no other choice, though, than to uphold its image while it strives to maintain the lead position in the cultural products market (which is very expensive), a position that is its singular strength as well as its weakness as it confronts competitors less burdened by the problems of «image de marque».

From employees of a cultural business to business employees

The FNAC began in 1953 as an association of two individuals and evolved from a small to a modest-sized business as it grew from 22 employees in 1960 to 580 in 1969.

By 2008, the company was a very large corporation that counted 19,357 employees.

Along the way, beginning in 1985, the original management approach had given way to make place of a large specialized retailer that is accountable to stockholders foreign [«outside of» ?] in the cultural market and reduced to the pursuit of short-term profits.

The two generations of FNAC employees who cohabitate today differ in how they were recruited, their work conditions, and how their careers are managed. The older generation experienced labor conditions and a work environment that have now either ceased to exist or are in the process of disappearing. There are radical differences between these group of employees and the younger in terms of their levels of personal investment in their work and in their sense of attachment to the company.

Essel himself recruited the first generation of employees. Those deadn't ask especially for a high degree of autonomy, it was exactly what require management policy.

The intellectual substance of their work enabled their higher educational levels, to be realized through their involvement in advices to the clients in buying decisions which have an real impact on «benefit». The nature of the products on sale further strengthened this feeling of intellectual substance of their work : the contact with legitimate culture and with its practitioners augmented the social status of the sales staff's activities.

Furthermore, possibilities of upward mobility within the company and employee benefits -which have to be win over -enabled every employee to hope for continuous and uninterrupted professional advancement.Associated three "series of indices -the degree of economic security, the capacity for expertise and organizational control of labor, and the possession of cultural capital" (p. 73), the occupation of book seller in FNAC placed these employees firmly within the middle class from 1960 to 1985. Vincent Chabault explains why these employees showed high levels of union membership (the first union affiliation was in 1968, and the first social movement in 1973) that is in direct contrast with unionization levels among employees of other large retail distributors of the period.

Beginning in the mid-1980's, personnel management was refocused on cost reduction (Chapter 5). Although university graduates continued to be recruited because of their disposition towards work and client relations, possibilities for internal promotion diminished. The FNAC's earlier labor environment gave way to deteriorating labor conditions, and a strategy of dividing labor collectives helped deny newer employees the levels of labor protection and job security enjoyed by others employees. Further, the rationalization of work tasks greatly decreased the level of employee autonomy. A high turnover among cashiers and sales staff with little or no job security, and increasing numbers of managers who quit the company to avoid stagnation, became the order of the day. Meanwhile, however, the preferential treatment of "good salespersons" was based on the presence of "expert salespersons" from the the first generation's to combine profits and culture, "expert salespersons" which become increasingly rare . The second generation of employees, as professionally unattached as they are to the company, has tended to join the SUD (Chapter 7) instead of the CGT or the CFDT. Indeed, the primary issue for the most militant employees is no longer about improving labor conditions in a company environment characterized by low job security and diminished interest in the job, resulting in a pronounced sense of detachment. It has become more interesting for these activists to focus their energies on broader social issues related to the labor movement in general. Vincent Chabault's book is far from a mere monograph about the company "that everyone thinks they know." In fact, by reconstructing the history of strategies for corporate growth and by highlighting the role of the two generations of employees in making these strategies operational, the author's principal contribution is to situate the history of the FNAC within the social and economic history of France in the second half of the twentieth century. He achieves this by linking his study of the distribution of cultural products to issues of employment and labor instead of to more classical issues of access, clientele, or practices.

Chabault's documentary sources range from direct observations of labor in the stores to roughly forty in-depth interviews of managers and employees in FNAC stores around Paris. Extended excerpts from these interviews illustrate the diversity of employee profiles, and they make reading the book a pleasant experience, although the author's use of the same excerpts to explore several different topics is a bit surprising. One might also criticize the absence of actual reports of his observations and, above all, of direct quotations from the sources on which he bases his analysis. It is worth noting, however, the presence of a highly useful recapitulative chronology in the appendix.

  The FNAC: A Story of Standardization Reviewed: Vincent Chabault, La FNAC, entre commerce et culture, Paris, Puf, 2010. Frédérique LEBLANC Maîtresse de conférences en sociologie UNIVERSITÉ PARIS OUEST NANTERRE -CSU-CRESPPA How a culturally avant-garde company gradually came little-by-little to be part of Big Business : Vincent Chabault recounts the story of the FNAC, from its Trotskyite origins to the present. What traces remain of the two individuals, both former Trotskyites, who founded the FNAC in 1954? What role did the FNAC play in the commodification of culture, and what remains of the company's original mission? Who are the company's employees, and


Michael A Bender
email: bender@cs.stonybrook.edu

Samuel Mccauley
email: smccauley@cs.stonybrook.edu

Bertrand Simon
email: bertrand.simon@inria.fr

Shikha Singh
email: shiksingh@cs.stonybrook.edu

Frédéric Vivien
email: frederic.vivien@inria.fr

Resource Optimization for Program Committee Members: A Subreview Article *

Keywords: Scheduling, Delegation, Subreviews Digital Object Identifier 10.4230/LIPIcs.FUN.2016

This paper formalizes a resource-allocation problem that is all too familiar to the seasoned program-committee member. For each submission j that the PC member has the honor of reviewing, there is a choice. The PC member can spend the time to review submission j in detail on his/her own at a cost of C i . Alternatively, the PC member can spend the time to identify and contact peers, hoping to recruit them as subreviewers, at a cost of 1 per subreviewer. These potential subreviewers have a certain probability of rejecting each review request, and this probability increases as time goes on. Once the PC member runs out of time or unasked experts, he/she is forced to review the paper without outside assistance.

This paper gives optimal solutions to several variations of the scheduling-reviewers problem. Most of the solutions from this paper are based on an iterated log function of C i . In particular, with k rounds, the optimal solution sends the k-iterated log of C i requests in the first round, the (k -1)-iterated log in the second round, and so forth. One of the contributions of this paper is solving this problem exactly, even when rejection probabilities may increase.

Naturally, PC members must make an integral number of subreview requests. This paper gives, as an intermediate result, a linear-time algorithm to transform the artificial problem in which one can send fractional requests into the less-artificial problem in which one sends an integral number of requests. Finally, this paper considers the case where the PC member knows nothing about the probability that a potential subreviewer agrees to review the paper. This paper gives an approximation algorithm for this case, whose bounds improve as the number of rounds increases.

Introduction

Serving on the program committee (PC) for a flagship theory conference is rewarding for the PC members, but it is intense and time-consuming work. Each submitted manuscript is typically assigned to three or four PC members. As a result, when you serve on a PC, you are given somewhere between 10 and 60 manuscripts to review, depending on the committee. Reviews need to be completed rapidly-on the order of one month. For many of these papers, you have only a casual familiarity, meaning that doing a high-quality review will consume large amounts of time and may be fraught with uncertainty.

Consequently, most PC members rely on subreviewers to provide outside reviews. The subreviewer mechanism works as follows. When you serve on a PC, you decide which manuscripts require outside assistance. Then you scrape the Internet for subreviewers, sending request emails to friends, calling in favors, and searching out new domain experts.

Many of these subreview requests are denied. It is not uncommon that you need to send 3-8 review requests before you find a subreviewer that is not reading the paper for another PC member, already overburdened with reviews from the same conference, also serving on the PC, advising or being advised by one of the paper authors, having a baby, married to one of the paper authors, or just taking a well needed break from responding to email.

Thus, even the administrative process of collecting subreviews is work consuming and worth optimizing. One resource optimization, familiar to seasoned PC members, is the race to send out review requests the moment that the submissions have been meted out to the PC. The longer you wait to ask for a review from someone, the less likely it is that that person will comply. It is common that you miss out on collecting another subreviewer by just a few minutes-someone else's request showed up in the mail queue first.

Another optimization is the use of parallelism: send requests to several potential subreviewers in parallel to increase the probability of a positive answer. But every request takes time, and if multiple people say "yes," this leads to redundant work for the community and the PC member.

This paper studies this class of resource-allocation problem, which overburdened PC members naturally face while discharging their PC duties. Specifically, this paper studies the randomized resource-allocation problem of how to find subreviewers for the minimum expected cost. More generally, this paper explores how to delegate work to outside sources, when delegation has a cost, a nontrivial probability of failing, and the delegator must take this into account in his/her decisions.

Scheduling Model

There are N papers to review, denoted 1, . . . , N . Reviewing paper j yourself costs C j . This cost is paper specific, because some submissions are easier for you to judge yourself, and others are harder. Each attempt to recruit a new subreviewer costs 1. The unit cost models the overhead of searching for email addresses, sending review requests, review reminders, thank you notes, requests for alternative reviewers, and all the other delegation overhead. Without loss of generality, C j > 1; otherwise, it is not cost-effective to recruit subreviewers.

There is a (round-dependent and paper specific) probability of p i,j (0 ≤ p i,j ≤ 1) that at round i the candidate subreviewer declines to review paper j. Probability p i,j is monotonically increasing in i, since as time goes on, any candidate subreviewer is increasingly likely to be reviewing the paper for someone else or already has all of his/her time accounted for.

The reviewing process proceeds in k + 1 rounds. In the first round, you email out a bolus of subreview requests for papers 1, 2, . . . , N . Some of these papers get successfully adopted by subreviewers. For those that do not, you send a second bolus of review requests in the second round, and so forth. In the last round k + 1, you need to review those stray papers that did not find a subreviewer owner in the first k rounds.

The objective is to minimize the total expected cost to review all N papers. Because we are dealing with expected values, we can analyze the subreviewer-finding strategy for each submission in isolation. Henceforth, we focus on the case of a single paper, and the multiple-paper case follows by linearity of expectation. We simplify notation by dropping the subscripts that identify papers, writing C and p i . The main exception is Section 3.3, where a request budget must be distributed among the N papers.

Modeling the process by a series of rounds faithfully captures how many PC members (including the authors on this paper) act when they serve on PCs. Round 1 opens with a flurry of energy and enthusiasm. It ends with a quiescent period filled with hope, despair, gratefulness, and occasional sleep. Round 2, 3, and so forth proceed similarly, as the PC members work up the gumption to renew soliciting reviews, after getting more declines from potential subreviewers.

Although we describe this problem using the colorful language of beating the bushes for subreviewers, this model similarly captures a natural parallel scheduling problem. There are N tasks (the papers). The objective is to schedule all tasks while minimizing the expected cost. A task j can be executed locally (you write the review) or remotely (you assign the review to a subreviewer). A local execution is expensive. A remote execution is cheaper, but even launching a job has a cost and fails with a certain probability.

Results

We first explore the case where the rejection probabilities are known.

For the case of two rounds, we give a closed-form optimal solution for minimizing the expected reviewing cost when the number of requests is not required to be an integer (e.g., we are allowed to send 3/5th of a review request, if we want). We give a closed-form optimal solution for multiple rounds when the number of requests in each round is not required to be an integer. This closed-form solution gives intuition about how requests should be distributed over rounds, and is an important building block for our further results. Using the closed form solution, we construct an optimal algorithm for sending integral requests; the running time is linear in the number of rounds. We then consider the bounded-reviewers case. Specifically, we further generalize to the (common) case where a submission may have only a bounded number R of knowledgeable experts. Once all R experts decline to review the paper, all resources are exhausted and the beleaguered committee member has no choice but to review the submission without help. We give an optimal algorithm if the probabilities remain constant, an approximation algorithm when they are monotonically increasing, and a pseudo-polynomial algorithm when papers have to share a budget R.

We also study the scheduling subreviewer problem for the case where the probability that a subreviewer rejects the subreview request is constant but unknown to the PC member.

We give a two round strategy which is a (4 C/ ln C + 2)-approximation for any subreview cost C ≥ 2. We further generalize to multiple rounds and obtain a k-round strategy that is a k(C 1/k +1)approximation.

Related Work

The problem of optimizing the conference-review process through a careful assignment of papers to PC members has been studied in various guises [START_REF] Benferhat | Conference paper assignment[END_REF][START_REF] Hartvigsen | The conference paper-reviewer assignment problem[END_REF][START_REF] Li | Automatic paper-to-reviewer assignment, based on the matching degree of the reviewers[END_REF][START_REF] Protasiewicz | A support system for selection of reviewers[END_REF]28]. Goldsmith and Sloan [START_REF] Goldsmith | The AI conference paper assignment problem[END_REF] address the problem of assigning papers to PC members in order to minimize "whingeing." Merelo-Guervós et al. [START_REF] Julián | Conference paper assignment using a combined greedy/evolutionary algorithm[END_REF] give evolutionary algorithms to optimize this assignment problem. Assigning conference papers to review has also been studied as a multi-agent fair-allocation problem [START_REF] Lesca | LP solvable models for multiagent fair allocation problems[END_REF]. Data mining and information-retrieval approaches have been used to model a reviewer's interest and build reviewer-recommender systems to assist paper assignment [START_REF] Basu | Recommending papers by mining the web[END_REF][START_REF] Dumais | Automating the assignment of submitted manuscripts to reviewers[END_REF][START_REF] Hettich | Mining for proposal reviewers: lessons learned at the national science foundation[END_REF][START_REF] Mimno | Expertise modeling for matching papers with reviewers[END_REF]. Wang et al. [26,27] present a survey on the various stages of the reviewer-assignment problem consolidating approaches from the areas of artificial intelligence, operations research, information retrieval, and algorithms.

Cormode [START_REF] Cormode | How not to review a paper: The tools and techniques of the adversarial reviewer[END_REF] gives a fun guide on how not to review papers.

Probabilistic Scheduling. In many papers in scheduling and distributed computing, processors randomly choose which task to execute from a pool of tasks. Because multiple processors may choose the same task, there is some probability of wasted work. This is the case in the so-called do-all or write-all literature (among a very large literature, see for instance [START_REF] Alistarh | How to allocate tasks asynchronously[END_REF][START_REF] Chlebus | Cooperative asynchronous update of shared memory[END_REF][START_REF] Dariusz | Writing-all deterministically and optimally using a nontrivial number of asynchronous processors[END_REF][START_REF] Martel | On the complexity of certified write-all algorithms[END_REF]), as well as other contexts where processors randomly choose tasks to execute and may fail to find one that was not already chosen [START_REF] Bender | Scheduling DAGs on asynchronous processors[END_REF][START_REF] Kedem | Efficient program transformation for resilient parallel computation via randomization[END_REF][START_REF] Zvi | Efficient robust parallel computations[END_REF].

Fault tolerance. The subreviewer scheduling problem is related to the problem of executing tasks on failure-prone platforms, and particularly to the work on replication for faulttolerance [START_REF] Casanova | Mapping applications on volatile resources[END_REF][START_REF] Casanova | Using replication for resilience on exascale systems[END_REF]. There is an important difference, however. Most work on fault-tolerance for failure-prone HPC platforms assume that failures are rare [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing[END_REF]; typically the mean time between failures of a component is expressed in tens of years. This means that it is almost always better in practice only to duplicate failed tasks and not be proactive by replicating a priori. Furthermore, the low failure rate allows for first-order approximations [START_REF] Bosilca | Unified Model for Assessing Checkpointing Protocols at Extreme-Scale[END_REF][START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF], which would be invalid in the current context of high rejection (i.e., failure) rates.

Preliminary Notions and Definitions

A strategy S is defined as the vector of requests sent in each round, that is, S = (R 1 , R 2 , . . . , R k ). The probability of rejection is constant if p i = p for all rounds i,

1 ≤ i ≤ k.
The probability of rejection is round-dependent if p i is monotonically increasing with respect to round i, that is, for any rounds i and j such that 1 ≤ i < j ≤ k we have p i ≤ p j . We also consider the case of unknown probability where rejection probabilities are constant but not known to the PC member.

A round i succeeds if at least one request in round i is accepted, that is, some subreviewer in the round agrees to subreview the paper. If a round i succeeds, then no more requests are sent in the later rounds. A round i fails if all requests sent in round i are rejected, that is, none of the subreviewers asked want to subreview the paper. Round i fails with probability p Ri i . If rounds 1 through k fail, the (k + 1)th round is reached. The PC member is then forced to review the paper on their own at a cost of C. We call C the self-reviewing cost.

We devise strategies that send nonnegative integral number of requests, that is, R i ∈ N 0 for 1 ≤ i ≤ k. As an intermediate step, we construct strategies that send nonintegral or real number of requests, that is, R i ∈ R + for 1 ≤ i ≤ k. For example, in round i the PC member could send 3/5ths of a request, meaning that the rejection probability is p 3/5 i . As a shorthand, we call a strategy integral when the number of requests R i for all rounds i is an integer. Otherwise, the strategy is a nonintegral or real strategy.

Finally, we consider bounds on the total number of requests a reviewer can make. First, we consider the setting where the PC member can make an unbounded total number of requests to an arbitrarily large pool of potential subreviewers. Second, we consider the situation where there is a bounded total number R of requests that the PC member can make, which models the situation that there are a limited number of experts capable of reviewing the submission.

Optimal Strategy to Schedule Subreviews

In this section, we give an optimal (k + 1)-round strategy for sending out subreview requests. We consider the case where there is an arbitrary pool of potential subreviewers, that is, there is no upper limit on the total number of requests that the PC member is allowed to make.

As an intermediate step, we give an optimal nonintegral strategy to find a closed-form solution. Then we give a linear-time algorithm that uses the closed-form solution and finds the optimal integral solution.

We start by explaining the high-level idea behind the optimal strategy. Let R i denote the number of requests we send out in round i. Then our total expected cost is the following:

E(R 1 , ..., R k ) = R 1 +p R1 1 R 2 + p R2 2 R 3 + ... R i + p Ri i R i+1 ... + p R k-1 k-1 R k + p R k k C .
Note that the expected reviewing cost conditioned on reaching a particular round i is independent of the past requests R 1 , R 2 , . . . , R i-1 ; call this cost E i .

E i (R i , . . . , R k ) = R i + p Ri i R i+1 + p Ri+1 i+1 . . . p R k-1 k-1 R k + p R k k C .
Thus, we can determine the request sequence R i , R i+1 , . . . , R k that minimizes E i by working backwards from the last round.

Optimal Nonintegral Strategy

The expected reviewing cost conditioned on reaching round k only depends on the selfreviewing cost C. We first compute the optimal number of requests to be made in the last round R k . This is equivalent to devising an optimal two-round strategy.

Lemma 1.

A two-round optimal nonintegral strategy sends R requests, where,

R = 0 if C ≤ 1 ln 1 p ; then the total expected cost is C; R = 1 ln 1 p ln C ln 1 p if C > 1 ln 1 p ; then the total expected cost is 1 ln 1 p 1 + ln C ln 1 p .
We generalize this notion to obtain a complete (k + 1)-round strategy that sends real requests and is optimal. To simplify analysis, we first present the case where the probability of rejection is constant across all rounds.

Theorem 2. An optimal (k + 1)-round strategy for sending real requests when the rejection probability p

i is constant, p i = p, is to send R i requests in round i for 1 ≤ i ≤ k, where, R i = 0 if C ≤ 1 ln(1/p) (no subreview requests) with a total expected cost of E = C. Otherwise, R i = 1 ln 1 p ln 1 + ln 1 + ln 1 + . . . ln 1+ (k -i) times ln C ln 1 p . . . with a total expected cost of E = R 1 + 1 ln(1/p) .
Theorem 2 generalizes to the case with monotonically increasing rejection probabilities.

Theorem 3. Let κ be the largest value in {1, .., k} such that

C ≥ 1 ln 1 pκ (with κ = 0 if C < 1 ln 1 p 1
). Then, when rejection probabilities are monotonically increasing, the optimal (k + 1)-round strategy for sending real requests is to send R i requests in round i where,

             R κ+1 = ... = R k = 0 , R κ = 1 ln 1 pκ ln C ln 1 p κ , R i = 1 ln 1 p i ln E opt i+1 ln 1 pi where E opt i = R i + 1 ln 1 pi for 1 ≤ i < κ . The total expected cost E = C if C < 1 ln 1 p 1 . Otherwise, E = E opt 1 = R 1 + 1/ ln(1/p 1 ), where R 1 = 1 ln 1 p1 ln ln p 1 ln p 2 1 + ln ln p 2 ln p 3 1 + . . . ln ln p κ-1 ln p κ 1+ (κ -1) times ln C ln 1 p κ . . . .

Optimal Integral Strategy

We use Theorem 3 to construct an algorithm to determine an optimal integral (k + 1)-round strategy. We first calculate the real request R i for round i, and then check whether rounding R i up or down leads to a better expected review cost conditioned on having reached round i; see Algorithm 1. Then we work backwards to compute R i-1 through R 1 .

Theorem 4. There exists a linear-time algorithm for finding an optimal (k + 1)-round integral strategy for the case when the rejection probabilities are monotonically increasing.

Algorithm 1: Computes an optimal (k + 1)-round integral strategy.

1 κ ← max i ∈ [1, k] C ≥ 1 ln 1 p i , or κ ← 0 if this set is empty 2 R i ← 0 for all i ∈ [1, k] // R i is the number of requests sent at round i 3 E ← C // E is the current expected cost according to the values of R i 4 for i from κ to 1 do 5 R i ← ln 1 p i (E ln 1 pi ) // R i is rounded down by default 6 if p Ri i E > 1 + p Ri+1 i E then R i ← R i + 1 // Round up R i if beneficial 7 E ← R i + p Ri i E // Update E for the next iteration 8 In each round i, send R i requests. The expected cost is E.

Bounded Number of Requests

A PC member may know only a limited number of experts to ask for a subreview. Let R denote the budget of total number of requests a PC member is allowed to make. In this section, we construct strategies that make a total of at most R requests.

Constant Rejection Probabilities

We give an optimal algorithm for the case when the probability of rejection is constant across rounds, that is,

p i = p for all i (1 ≤ i ≤ k).

Optimal Strategy for Unbounded Rounds

We first consider the case when there is no limit on the number of rounds. Regardless of the bound R on total number of requests, there exists an optimal strategy that never sends more than one request per round; see Algorithm 2. This strategy is also optimal for the case when the number of rounds is limited to k and the budget on total requests R ≤ k.

Theorem 5. When a maximum of R requests can be made over unlimited rounds and the rejection probabilities are constant (p i = p), then the optimal integral strategy is to self-review immediately if C ≤ 1/(1 -p), or make exactly one request per round if C > 1/(1 -p). The optimal expected cost is min(C, 1 1-p ).

Algorithm 2: Optimal strategy when the rejection probabilities are constant and there is no bound on the total number of rounds.

1 if C <

Optimal Algorithm for a Bounded Number of Rounds

We now devise a (k + 1)-round algorithm for the case when we are only allowed to send R requests in total where R > k. (If R ≤ k, then we can use Theorem 5.) For a given self-reviewing cost C, we determine the optimal integral strategy S * (C) that is allowed to make an unbounded number of requests. Let the total number of requests sent by S * (C) be R * . If R * ≤ R, our budget is sufficient and we execute strategy S * (C). If R * > R, there exists an optimal algorithm with budget R that uses all R requests; see Lemma 6. Thus, the challenge is to determine how to distribute R < R * requests across k rounds to minimize the total expected review cost. Lemma 6. For a given self-reviewing cost C, let R * be the total number of requests sent by an optimal integral strategy S * (C) without a budget. When a budget of only R requests is allowed, where R < R * , there exists an optimal strategy S * R (C) that sends exactly R requests. Let R 1 , R 2 , . . . , R k be a partition of the budget R across the k rounds, that is,

n i=1 R i = R. Then the total expected cost is E(R 1 , . . . , R k ) = R 1 + p R1 R 2 + . . . p R1+•••+R k-1 R k + p R C. ( 1
)
Note that the final term, p R C (the expected self-reviewing cost incurred when all requests fail), stays the same regardless of how requests are partitioned among rounds. As long as C is 7:8 Scheduling Subreviewers sufficiently large, further increasing C does not change the optimal partition of R among the k rounds. On the other hand, if C is sufficiently small that the unbounded-request solution does not need more than R requests, we already have a solution-Theorem 4.

With this observation, our goal is to find a self-reviewing cost C R that uses exactly R requests. The partition determined by this solution is exactly what we are looking for.

The proof proceeds as follows. First, we assume that such a C R exists and can be found efficiently. Given this assumption, we show that our algorithm computes an optimal strategy. Then, we complete the proof, that is, we show that an appropriate C R always exists and can be computed efficiently.

Theorem 7.

There exists an algorithm that computes an optimal (k + 1)-round strategy for the case when the total number of requests allowed is bounded by R. At first glance, it may seem immediate that such a C R exists and can be found (perhaps using a binary search). However, the following example illustrates two complications. First, there may be several optimal strategies, each making different total numbers of requests. Second, arbitrarily small perturbations in C R may change the optimal number of requests-in particular, there may only be a single value C R that leads to exactly R requests. Remark 8. An example configuration where several strategies are optimal: let p = 1/2, C = 8 and consider 2 rounds plus the self-reviewing round. The strategies (R 1 , R 2 ) ∈ {(1, 2), (1, 3), (2, 2), (2, 3)} all achieve an expected cost of 3, and use between 3 and 5 requests.

In this example, C = 8 is the only value of C that uses exactly 4 requests. If C = 8 -ε, the optimal strategy uses 3 requests, and if C = 8 + ε it uses 5.

Showing An Appropriate Self-Reviewing Cost Exists. If a strategy is allowed to make nonintegral requests, then showing that an appropriate self-review cost C R exists is straightforward. The total number of requests as a function of the self-review cost C for nonintegral strategies is continuous and increasing; see Theorem 2. Thus, such a C R always exists. Now we show that an appropriate C R exists even for integral strategies. We begin with a structural remark. Lemma 9. When the self reviewing cost increases, the optimal expected cost does not decrease.

The next two structural lemmas focus on a single round i. First, we show that when the self-reviewing cost is increased, the number of requests sent in i (in any optimal solution) cannot decrease. For nonintegral requests, this statement follows directly from Theorem 2. The subtlety here is that the optimal strategy for integer requests, as described in Algorithm 1, performs a rounding to compute each value R i . We prove that our result still holds after this rounding. Lemma 10. Given two integral strategies S C and S D that are optimal for a self-reviewing cost of C and D respectively, with C < D, the number of requests sent in any round i by S C is not larger than the number of requests sent in round i by S D .

Proof. Let R * i (x) denote the (not necessarily integral) optimal number of requests sent at round i with self-reviewing cost x. We know by Theorem 3 that R * i (x) is monotonically increasing in x; in particular, R * i (C) ≤ R * i (D). We show the result by induction on i. First, for i = k, we proceed by contradiction. Assume to obtain a contradiction that S C (resp. S D ) sends A requests (resp. B) at round k, with A > B. By definition, either

A = R * i (C) or A = R * i (C) ; similarly B = R * i (D) or B = R * i (D) . Since R * i (C) ≤ R * i (D) and A > B, we must have A = B + 1.
Recall that, as proved in Theorem 3, R * k (α) is equal to the value of x that minimizes x + p x k α. Then, due to the optimality of A and B with a self-reviewing cost of C and D, respectively, we have (first substituting A = B + 1, then rearranging):

A + p A k C ≤ B + p B k C ⇔ 1 + p k p B k C ≤ p B k C ⇔ C ≥ 1 p B k (1 -p k )
.

Similarly,

B + p B k D ≤ A + p A k D ⇔ p B k D ≤ 1 + p k p B k D ⇔ D ≤ 1 p B k (1 -p k )
.

Since by definition we have C < D, we obtain D ≤ C < D; hence, a contradiction. Now assume this result holds true for any j larger than some i; we will show that it also holds for i. As proved in Theorem 3,

R * i (C) minimizes x + p x i E i+1
, where E i+1 is the optimal expected cost for the rounds after round i. When the self-reviewing cost increases, we know by Lemma 9 that E i+1 is nondecreasing. Then, we can apply the same reasoning as above and complete the induction. Now we show that as C increases, the requests sent at i increase continuously as well.

Lemma 11. Given a round i and an integer q, there exists a self-reviewing cost for which an optimal integral strategy sends exactly q requests at round i.

Proof. We begin with some definitions. We define Ēi (C) as the optimal expected cost, with integral numbers of requests, generated by rounds i through k + 1, conditioned on reaching round i (i.e., all requests at rounds 1 through i -1 failed). To begin, we let Ēk+1 (C) = C to account for the self-reviewing round. We then recursively define E i (x, C) = x + p x i Ēi+1 (C) as the expected cost generated by rounds i through k + 1 (conditioned on reaching round i) when x requests are sent at round i. Therefore, we have Ēi (C) = min x∈N E i (x, C). We finally define R i (C) = arg min x∈N E i (x, C): this is the smallest number of requests that can be sent at round i while retaining optimality.

We want to show that R i (C) spans all integers when C varies. Recall from Theorem 3 that the real value of x minimizing

E i is equal to R * i (C) = ln 1 p i Ēi+1 (C) ln 1 pi .
Then if Ēi+1 is a continuous and strictly increasing function of C, R * i is also a continuous and strictly increasing function of C, and R * i spans all integers (for all q ∈ N there exists a value

C q such that R * i (C q ) = q). From Theorem 4, R i (C) ∈ { R * i (C) , R * i (C) }.
Thus, since R * i spans all integers, R i spans all integers as well (R i (C q ) = q). Therefore, it suffices to show that Ēi (C) is a continuous and (strictly) increasing function of C. We prove this property by induction on i from k + 1 to 1. We begin with the base case i = k + 1. Then Ēk+1 (C) = C, which is continuous and (strictly) increasing.

Suppose now that the inductive hypothesis holds for all j > i: Ēj (C) is continuous and strictly increasing and, thus, R j spans all integers. We must have Ēi (C) ≤ Ēk+1 (C) = C, therefore, R i (C) ≤ C and Ēi (C) = min 0≤x≤C (x + p x i Ēi+1 (C)). Then, Ēi (C) is a continuous and strictly increasing function.

With this structure in mind, we are ready to prove the existence of C R .

Theorem 12. Given an integer number of requests R, there exists a self reviewing cost C R ∈ R such that an optimal strategy uses R requests.

Proof. As the self-reviewing cost increases from 1 to infinity, each R i spans all the integers in increasing order, see Lemmas 10 and 11. Therefore, if C increases by a sufficiently small ε, the number of requests in each round either 1) stays the same, or 2) increases by 1. We refer to these increases as jumps.

If only one R i jumps for each small increase in C, then the theorem is proved. However, it may be that for all ε > 0, there may be two rounds R i and R i that both jump. See Remark 8 for an example. The remainder of the proof handles this case.

Because the expectations E * i (see Lemma 11) are continuous and strictly increasing, for each value S of R i , there exists a unique value C such that both R i = S and R i = S + 1 are optimal. In other words, when R i jumps, there is a value C such that both values of R i are optimal.

For a self-reviewing cost C, let R(C) be the minimum number of requests sent in an optimal solution.

Let C be the largest self-reviewing cost such that R(C) ≤ R, and let S be an optimal strategy using R(C) requests. If R = R(C), we have the result. Otherwise, we let δ = lim ε→0 + R(C + ε) -R(C) be the minimum number of jumps when C increases by any ε. By definition of δ, we have δ ≥ R -R(C).

Recall that at the point where R i jumps, both R i and R i + 1 lead to the same expected cost. Then, there exist δ rounds in which we can add a request in S without modifying the expected cost. Choose R -R(C) of these rounds, and increment the number of requests. We have shown that this retains the (optimal) total expected cost. Thus for any R, we get a C that has an optimal strategy with exactly R requests.

Computing the Appropriate Self-Reviewing Cost. The main idea behind our algorithm for finding C R is to use binary search. However, as mentioned in Remark 8, there may only be a single correct value of C R . In fact, it may not be an integer, or even a rational number. Thus, once we are within 1 of the correct value of C R , our algorithm jumps to the correct C R more directly.

We begin with some definitions. We call a self reviewing cost C a point of discontinuity at round i if there are two optimal strategies for cost C that give a different number of requests in round i. (Note that these are similar to the "jumps" in the proof of Theorem 12.) Let R i (C) (resp. R + i (C)) be the minimum (resp. maximum) number of requests at round i that ensures optimality for a self-reviewing cost of C. Then we formally define R(C) as the sum over all rounds of R i (C), and R + (C) likewise as the sum over R + i (C). Note that these quantities can be computed by Theorem 7.

Our algorithm begins with a binary search, starting with the interval [ 1 1-p , C], and ending on an interval [L, U ] which has R i (U ) -R i (L) ≤ 1 for all rounds i. In particular, we stop here because each round has at most one point of discontinuity in [L, U ].

Then, we refine the search within [L, U ]. The algorithm finds, for each round i, the point of discontinuity within [L, U ] for round i; call it C i . We then update L to be the smallest such C i . We repeat until R + (L) = R, at which point L is the desired value of C R Algorithm 4: Computing a self-reviewing cost C R given R.

1 L ← 1 1-p ; U ← C 0 // Lower and upper bounds on C R 2 while ∃i, R i (U ) -R i (L) ≥ 2 do // binary search 3 x ← 1 2 (L + U ) 4 if R ∈ [R(x), R + (x)] then return x 5 else if R(x) < then L ← x 6 else U ← x 7 while R + (L) < R do 8 I ← {i | R i (U ) = R i (L) + 1} // Value of the expectation before the first discontinuity in [L, U ] 9 E(R 1 , . . . , R k , C) ← R 1 + p R1 R 2 + • • • + p R1+•••+R k C 10 R i ← R i (L) for each i 11 foreach i ∈ I do 12 C i ← solution of E(R 1 , . . . , R i , . . . , R k , C) = E(R 1 , . . . , R i + 1, . . . , R k , C)
// The minimum value corresponds to the first discontinuity 13 L ← min i∈I C i 14 return L Theorem 13. Given a request target R, and a self-reviewing cost C (such that all optimal solutions for C require more than R requests) Algorithm 4 computes an appropriate selfreviewing cost C R which has an optimal solution with exactly R requests.

Proof. First, Theorem 12 ensures the existence of a self-reviewing cost C R for which an optimal strategy with R requests exists.

By Lemma 10, we know that R i (C) and R(C) are nondecreasing. Moreover, by Theorem 5, we know that R( 11-p ) = 0, and our theorem assumes that R(C 0 ) > R. Therefore, throughout the first loop of Algorithm 4, we know that there exists C R ∈ [L, U ]. Then, by Lemma 11, we know that each R i (C) spans every integer, so the first loop terminates. Thus, when the second loop is initiated, [L, U ] is in an interval containing C R , and in which each round has at most one point of discontinuity. Now, we study a given iteration of the second loop. Let j be the index of the round with the first discontinuity in [L, U ]. First, note that a round i encounters a discontinuity at the point C if and only if C meets the requirement of Line 12, where the optimal numbers of requests sent at each round for a self-reviewing cost of C are given by R 1 , . . . , R k . Therefore, C j is indeed the smallest point of discontinuity in [L, U ], i.e., we have R(L) = R(C j ) < R + (C j ), and for every other i, we have R(L) = R(C i ). Thus, during the execution of the second loop, the value of L is increased without skipping any point of discontinuity. This proves the termination and the correctness of this loop.

Finally, we show that this algorithm is efficient, by bounding the number of iterations of the first loop. Note that if a round i has a discontinuity at a self-reviewing cost

C 1 i , the next discontinuity C 2 i satisfies C 2 i ≥ C 1 i /p, see below.
Indeed, this inequality is actually an equality for the last round as the self-reviewing cost that has optimal strategies in which round k sends R k or R k + 1 requests is equal to (1-p) . Then, as the previous rounds increase with a smaller rate, the inequality is proved.

1 p R k
Therefore, the first loop contains O(log 1/p C 0 ) iterations.

Round-Dependent Rejection Probabilities

In this section we consider the case where rejection probabilities are not constant but are monotonically increasing.

The optimal strategy in Section 3.1 for constant rejection probabilities is based on the fact that when only an insufficient budget of R requests is available, then the optimal partition of R across the k rounds is independent of C. However, when the rejection probabilities are monotonically increasing this is no longer true. For rejection probabilities p i for round i, the last term in the expression of expected review cost (Equation 1) becomes p ΣiRi C and thus the optimal review cost depends on the partition R 1 , . . . , R k of the budget R.

For the case of round-dependent rejection probabilities, we give a greedy strategy which achieves a approximation ratio dependent on the number of rounds. Roughly speaking, this strategy sends

R i = OPT i-1 j=1 p Rj j
requests in the ith round, finding the value of OPT through a binary search. Theorem 14. There exists a greedy strategy whose expected cost is at most 1 + (k + 1)OPT where OPT is the cost of the integral optimal strategy using at most R requests and k rounds.

Multiple Papers Sharing a Common Request Budget

In this section we consider the case where the PC member can send a total of at most R requests and these requests have to be distributed among the N papers the PC member has been assigned to review. We first show that there exists a pseudo-polynomial-time algorithm to compute the optimal strategy for one paper using at most R requests. We then extend it to the optimal strategy for N papers, sharing a total budget R, with round-dependent rejection probabilities. Theorem 15. There exists a pseudo-polynomial time algorithm computing an optimal strategy in O(kR 2 ) time for any paper j such that the rejection probabilities with rounds are monotonically increasing and the total number of requests is bounded by R.

Proof. The algorithm uses dynamic programming to build a table

E j [i, r], for 1 ≤ i ≤ k + 1 and 0 ≤ r ≤ R. E j [i,
r] is the optimal expected cost when exactly r requests are spread among the rounds

R i , R i+1 . . . R k . E j [i, r] is constructed using the following equation: ∀i ∈ [1, k], ∀r ∈ [0, R], E j [i, r] = min 0≤x≤r x + p x i,j E j [i + 1, r -x] .
The algorithm proceeds by decreasing the value of round i, starting at round i = k + 1. The table E j is initialized by setting E j [k + 1, r] = C j for all r. For each round and each value of r, the algorithm has a cost of O(R) to update the table E j ; hence, the overall complexity is O(kR 2 ). The space used is O(kR). The optimal strategy is determined by finding the value R that minimizes

E j [1, R] (for 0 ≤ R ≤ R).
We use this result to build a solution for the general case for a total of N papers.

Theorem 16. There exists a pseudo-polynomial time algorithm computing an optimal strategy in O(N kR 2 ) time for sending subreview requests for a total of N different papers such that the rejection probabilities are monotonically increasing with rounds and the total number of requests across the N papers is bounded by R.

Proof. The algorithm uses dynamic programming to build a table E[j, r], for 0 ≤ j ≤ N and 0 ≤ r ≤ R. E[j, r] is the optimal expected cost when exactly r requests are spread among the first j papers. E[j, r] is constructed using the following equation:

∀r ∈ [0, R], E[j, r] = min 0≤x≤r (E j [1, x] + E[j -1, r -x]) ,
where the value of E j [1, x] is given by Theorem 15. The algorithm proceeds by increasing values of j, from 1 to N . The overall complexity is O(N kR 2 ).

Unknown Probability of Rejection

In this section we consider the case in which the probability that a subreviewer rejects a subreview request is constant but unknown to the PC member. We begin with an observation. Suppose we have an unbounded number of rounds for sending requests. Our result for unbounded rounds (see Algorithm 2) states that an optimal algorithm either takes the cost of C immediately, or performs one request per round indefinitely. Even when we do not know the value of p, we can mirror this idea using an approach similar to the classic ski-rental problem (see e.g. [START_REF] Fujiwara | Average-case competitive analyses for ski-rental problems[END_REF]).

Observation 17. Consider a strategy S that makes one subreview request for C rounds then reviews for a self-reviewing cost C. Then, S is a 2-approximation (regardless of the value of the rejection probability p).

Proof. Strategy S has cost at most 2C. If C ≤ 1/(1-p), the optimal strategy is to self-review at cost C and S is a 2-approximation. The cost of S is bounded by 1 + p + . . .

+ p C-1 + p C C ≤ 1/(1 -p) + p C C. Note that p C C = p C + p C + . . . p C ≤ 1 + p 2 + . . . p C ≤ 1/(1 -p).
Thus the total cost is at most 2/(1 -p). So for C > 1/(1 -p), S is also a 2-approximation. Now we consider the case when the total number of rounds used to make subreview requests is bounded. We first give a 2-round strategy (one round of making requests, followed by a self-review if all requests failed) and then generalize to a (k + 1)-round strategy.

Two Rounds. We start with a 2-round strategy that achieves an approximation ratio of (2 √ C + 2). Then we improve the approximation ratio asymptotically; see Theorem 19.

To analyze our strategies we prove the following structural lemma. Roughly speaking, it shows that as long as the optimal cost is not too big, the cost of sending subreview requests is greater than the expected self-reviewing cost.

Lemma 18. Assume the cost of the optimal nonintegral strategy for two rounds with self-reviewing cost

C is OPT ≤ √ C ln C. Then if OPT sends R requests, p R C ≤ R. Proof. By contradiction. Note that OPT ≤ √ C ln C implies that OPT < C since C ≥ 1.
Then by Theorem 2, we have R = log Proof. We compare our algorithm's performance to an optimal strategy S * . To simplify analysis we do not require S * to be integral; however, we do require that S * either sends zero requests, or sends at least one request. This lower bounds the cost of an optimal integral strategy. Let OPT be the cost of S * . We divide the proof into several cases based on the value of OPT. Case 1 (Large OPT): Assume OPT ≥ √ C ln C. Since S has cost at most C/ ln C + C, the approximation ratio is at most

C/ ln C + C √ C ln C ≤ C/ ln C + 1 + C √ C ln C ≤ 1 ln C + 1 √ C ln C + √ C √ ln C ≤ 2 √ C √ ln C +1 for C > 2.
Thus, in this case S is (2 C/ ln C + 1)-competitive. Note that C/ ln C > 1 for all C > 1 and 1/ √ C ln C < 1 when C C > e, which holds for all C ≥ 2. Case 2 (Small OPT):

Assume OPT ≤ C/ ln C. If S * sends R requests, its cost is R + p R C. Since R ≤ OPT ≤ C/ ln C, p R ≥ p √ C/ ln C . Note that p R C ≤ OPT.
(R/C) 1/R ((ln C)/R 2 + (1 -ln R)/R 2 ) ≥ 0 since R ≤ C. Thus (R/C) 1/R is increasing with respect to R; since R < OPT, we obtain p ≤ (R/C) 1/R < (OPT/C) 1/OPT .
Substituting, the approximation ratio is at most

C/ ln C + p √ C/ ln C C OPT ≤ 1 + C ln C + OPT C √ C/ ln C opt C OPT ≤ 2 + C OPT 1- √ C/ ln C opt .
Let x = C/ ln C/OPT, so x ∈ (1/ ln C, 1). Then the ratio is

2 + x √ C ln C 1-x = 2 + e (1-x) ln(x √ C ln C)
Taking the derivative, we get e (1-x) ln(x

√ C ln C) 1 -x x -ln(x √ C ln C) .
This is equal to zero only when 1/x = ln(x √ C ln C) + 1. Substituting into the original equation, we are bounded by:

2 + x √ C ln C 1-x = 2 + √ C ln C ln(x √ C ln C) + 1 1-x ≤ 2 + √ C ln C ln C/ ln C 1-x . Note that ln C ≤ C 1/e for all C. Then C/ ln C ≥ C 1/4 , so 2 + √ C ln C ln C/ ln C 1-x ≤ 2 + 4 C ln C .
Finally, we test the boundary cases. When

x = 1, 2+ x √ C ln C 1-x = 2 < 2+4 C/ ln C. When x = 1/ ln C, then 2 + x √ C ln C 1-x ≤ 2 + C/ ln C.
Thus, the maximum is reached when the derivative is zero and we have the theorem. Multiple Rounds. We generalize k rounds and give a kC 1/k -competitive algorithm. We begin with a useful lemma. Lemma 20. Assume the optimal nonintegral algorithm has total expected cost OPT < C. Then p i i ≤ OPT for all i ≥ OPT.

Proof. The lemma is trivially satisfied if i = OPT, since p opt OPT ≤ OPT. Secondly, note that by Theorem 2, OPT ≥ 1/ ln 1 p . Taking the derivative, we have

d di p i i = p i 1 -i ln 1 p < 0,
where the second inequality follows from the fact that i > OPT ≥ 1/ ln 1 p . Thus, p i i decreases as i increases. In other words, p i i ≤ p opt OPT ≤ OPT. Theorem 21. Let S be a (k + 1)-round strategy with unknown rejection probability p where: self-review immediately if C (i-1)/k > C, or send C (i-1)/k requests at round i. Then S is a k(C 1/k + 1)-approximation strategy.

Proof. If OPT = C, the strategy S sends at most kC requests, and is k-competitive. Now assume OPT < C. We define a variable a which roughly characterizes the performance of OPT in terms of S. Let a be such that C a/k ≤ OPT < C (a+1)/k ; in other words,

7:16

Scheduling Subreviewers a + 1 is the last round where S makes fewer requests than the total cost of OPT. Note that 0 ≤ a ≤ k. The cost of S in rounds 1 to a is bounded by

a i=1 C i/k ≤ a C a/k ≤ a • OPT. Consider round i ≥ a + 1. The cost of S at round i is p i-1 j=1 C j/k C i/k ≤ p C i/k C i/k C 1/k + p C i/k ≤ OPT • C 1/k + 1,
where the final inequality follows from Lemma 20. Thus our algorithm has total cost at most a

• OPT + (k -a)(OPT • C 1/k + 1) ≤ OPT(kC 1/k + k).

Conclusion

Many of structural lemmas in this paper compartmentalize the subreviewer problem into independent tractable subproblems, which are much easier to analyze. For example, we can optimize the subreviewing for each paper independently, thanks to the comforting magic of linearity of expectation. Similarly, we can analyze the later rounds in the reviewing process independently of preceding rounds, thanks to the magic of doing probability theory correctly. Natural open problems abound, generalizing the subreviewer optimization problem from this paper. But in many of these generalizations, this independence and comfortable compartmentalizing gets thrown out the window.

For example, an assiduous PC member may want to obtain two independent subreviews for some controversial submission. Now what happens in later rounds depends on previous rounds, and we cannot immediately apply the "work-backward method" given in Section 2.

Similarly, different papers may share potential subreviewers-a PC member may have ten experts to ask about paper 1 and twelve to ask about paper 2, but five of these experts are the same. Now optimizing the subreviewing for these two papers probably cannot be done independently. We also lose independence if we have a limited pool of subreviewers, and each subreviewer has a paper-dependent and time-dependent rejection probability.

A Omitted Proofs

Proof of Lemma 1. The expected cost when sending a single round of R requests is

E(R) = R + p R C = R + e R ln p C.
Taking the first and second derivatives, we obtain

E (R) = 1 + (ln p)p R C and E (R) = (ln p) 2 p R C.
Thus, E is (strictly) positive, and E is (strictly) increasing. Then, E is zero when R

= 1 ln 1 p ln C ln 1 p . If C ln 1 p ≤ 1, then R ≤ 0.
Because R must be nonnegative and because E is (strictly) increasing then in that case the optimal solution is to send no requests (R = 0) for an expected cost of C. Otherwise, the

optimal expected cost is R + p R C = R + 1 ln 1 p = 1 ln 1 p ln C ln 1 p + 1 ln 1 p .
Proof of Theorem 2. The expression for the total expected review cost can be written as:

E(R 1 , . . . , R k ) = R 1 + p R1 R 2 + • • • + p R1+•••+R k-2 R k-1 + p R1+•••+R k-1 (R k + p R k C). Let E k (R k ) = R k + p R k C. Using Lemma 1, find the optimal value of R k and E k . If C ≤ 1 ln 1 p
, then the optimal value for R k is 0 and thus all the R i s must be 0 and the optimal strategy is to self-review immediately.

For C > 1 ln 1 p , we do an induction on the round i, starting from i = k. The optimal value of R k is the base case. That is,

R k = 1 ln 1 p ln C ln 1 p and E opt k = 1 ln 1 p C ln 1 p + 1 ln 1 p .
Let E j denote the expected cost conditioned on reaching round j, then

E j (R j , ..., R k ) = R j + p Rj R j+1 + • • • + p Rj +•••+R k-1 R k + p Rj +•••+R k C.
Suppose we have determined the optimal values of R i+1 to R k for some value of i. And suppose that for i + 1 ≤ j ≤ k, the expected cost E j (R j , ..., R k ) of an optimal solution is equal to E opt j = R j + 1 ln 1 p . Now consider R i . We rewrite the expression of the overall expected cost:

E(R 1 , . . . , R k ) = R 1 + • • • + p R1+•••+Ri-2 R i-1 + p R1+•••+Ri-1 R i + p Ri R i+1 + • • • + p Ri+1+•••+R k-1 R k + p Ri+1+•••+R k C . = R 1 + • • • + p R1+•••+Ri-2 R i-1 + p R1+•••+Ri-1 R i + p Ri E opt i+1 .
Thus, the optimal value for R i does not depend on the values of R 1 to R i-1 and can be determined by Lemma 1 when substituting E opt i+1 to C. That is,

R i =

7:19

To complete the proof, we use E opt Proof of Theorem 3. We prove the result by induction on i, starting from i = k. The expression for the total expected cost can be written as:

E(R 1 , . . . , R k ) =   R 1 + p R1 1 R 2 + • • • +   k-2 j=1 p Rj j   R k-1   +   k-1 j=1 p Rj j   R k + p R k k C . Let E k (R k ) = R k + p R k k C.
The optimal value for R k and E k from Lemma 1 is:

   R k = 0 and E k = C if C < 1 ln 1 p k R k = 1 ln 1 p k ln C ln 1 p k and E k = E Opt k = R k + 1 ln 1 p k
, otherwise.

If C ≤ 1/(ln 1 p k ), then R k = 0 and using induction the theorem follows for the rounds κ through k (recall that the p i 's are non-decreasing).

Let E j denote the expected cost conditioned on reaching round j. Then

E j (R j , ..., R k ) = R j + p Rj j R j+1 + • • • +   k-1 l=j p R l l   R k +   k l=j p R l l   C.
Similar to the proof of Theorem 2, assume that we have optimal values of R l and E l , for i + 1 ≤ l ≤ κ (and, thus, R κ+1 = ... = R k = 0). Consider R i . Rewriting the expression of the total expected cost we have:

E(R 1 , . . ., R k ) =   R 1 + • • • +   i-2 j=1 p Rj j   R i-1   + i-1 j=1 p Rj j   R i + p Ri i   R i+1 + • • • +   k-1 j=i+1 p Rj j   R k +   k j=i+1 p Rj j   C     = R 1 + • • • +   i-2 j=1 p Rj j   R i-1 +   i-1 j=1 p Rj j   R i + p Ri i E i+1 (R i+1 , ..., R k ) .
Since the values of R i+1 to R κ are optimal, and the optimal value for R i can be determined using Lemma 1 by substituting E opt i+1 to C. Therefore, we obtain the optimal value of R i :

R i = 1 ln 1 pi ln E opt i+1 ln 1 p i = 1 ln 1 pi ln R i+1 + 1 ln 1 pi+1 ln 1 p i = 1 ln 1 pi ln ln p i ln p i+1 + R i+1 ln 1 p i .
We have

E opt i = R i + p Ri E opt i+1 = R i + 1 ln 1 p i
using Lemma 1. Finally, note that the total expected cost of the strategy is

E = E opt 1 .
Proof of Theorem 4. For i > κ, an optimal solution has R i = 0 as in Theorem 3.

7:20

Scheduling Subreviewers

We prove that Algorithm 1 is correct and that at the end of Step 7 E equals Ēi (at iteration i), the optimal expected cost conditioned on reaching round i.

We perform induction on i starting at i = κ similar to the proof of Theorem 3. Let E κ (R κ ) = R κ + p Rκ κ C. We know that the nonintegral optimal value of R κ also minimizes E κ , i.e., R * κ = ln 1 pκ (C ln 1 pκ ). As E κ decreases then increases, the integral optimal value of R κ is either R * κ or R * κ (or both). This proves the result for i = κ. Now, we assume the induction hypothesis for each round l ∈ [i + 1, κ]. Consider R i . We rewrite the expression of E when R l is assigned to its optimal value, for i + 1 ≤ l ≤ k:

E(R 1 , . . . , R i ) = R 1 + • • • +   i-2 j=1 p Rj j   R i-1 +   i-1 j=1 p Rj j   R i + p Ri i Ēi+1 .
Using Lemma 1 the nonintegral optimal value of R i is ln (1/pi) ( Ēi+1 ln 1 pi ). The integral optimal value of R i is one of its closest integers. Thus by induction, E has the value of Ēi+1 at the of Step 7 Algorithm 1 (at iteration i + 1). This proves the correctness for round i. Then, since E is updated to R i + p Ri i Ēi+1 = Ēi , the induction is complete.

Algorithm 3 : 5 C 6 S

 356 Optimal strategy when the rejection probabilities are constant and when requests and rounds are limited. 1 S * (C) ← an optimal strategy for k + 1 rounds and unlimited requests (use Algorithm 1) 2 R * ← number of requests required by S * (C) 3 if R * ≤ R then follow strategy S * (C) 4 else R ← self-reviewing cost for which an optimal strategy sends R requests * (C R ) ← strategy computed using Algorithm 1 for cost C R sending R requests 7 follow strategy S * (C R )

i= 1 p

 1 R i + p Ri E opt i+1 = R i + 1 lnfrom Lemma 1. Finally, note that the total expected cost of the strategy is E = E opt 1 .

  is maximized; thus ln 1 p = e/C is a lower bound on the cost of OPT. Replacing back into the cost of OPT, we have Next, we improve the approximation ratio. Note that for small C (C ≤ e 4 < 55), the warm-up strategy leads to better guarantees. Consider a 2-round strategy S that sends C/ ln C requests. This strategy is a (4 C/ ln C + 2)-approximation for any C ≥ 2.

	√	C ln C ≥ OPT =	ln C ln 1 p ln 1 p	+	1 ln 1 p	≥	2C e	.
	Note that Thus √ C ln C < 2C/e for any C > 1. √ C ln C/C is maximized at C = e (for C > 1), at which point	√	C ln C =< 2C/e.
	Consider the 2-round strategy S that sends	√	C requests in the subreview round. If all
	requests fail, a self-reviewing cost C is incurred in the next round. If the optimal strategy sends more than √ C requests, or sends zero requests and incurs self-reviewing cost C, then S achieves an approximation ratio of √ C + 2 since S has total review cost at most √ C + C. If the optimal strategy sends R < √ C requests, then
	p R C ≤ R < most 2 √ C and the optimal strategy has cost at least 1. √ C by Lemma 18, and we have p √ C C < √ C. Thus, S has total review cost at
	Theorem 19.

1 p (C ln 1 p ), and p R C = 1 ln 1 p . With some algebra, if the lemma statement is false, then we must have ln 1 p < e/C. Note that ln(Cx)/x is minimized when x

  Assume that S * has cost OPT, where C/ ln C < OPT < √ C ln C. By Lemma 18, if S * makes R requests, then p R C ≤ R.Rearranging, we obtain p ≤ e (ln R)/R-(ln C)/R ; taking the derivative with respect to R we get

		√		Then the
	cost of our algorithm is	C/ ln C + p	C/ ln C C ≤	C/ ln C + OPT. Since the optimal
	algorithm has cost at least 1, this results in a 2 C/ ln C + 1 -approximation algorithm.
	Case 3 (Medium OPT):

26

  Fan Wang, Ben Chen, and Zhaowei Miao. A survey on reviewer assignment problem. In New frontiers in applied artificial intelligence, pages 718-727. Springer, 2008. 27 Fan Wang, Ning Shi, and Ben Chen. A comprehensive survey of the reviewer assignment problem. International Journal of Information Technology & Decision Making, 9(04):645-668, 2010. 28 David Yarowsky and Radu Florian. Taking the load off the conference chairs: towards a digital paper-routing assistant. In Proc. of the Joint SIGDAT Conference on Empirical Methods in NLP and Very-Large Corpora, 1999.

* This work was partially supported by NSF Grants CNS 1408695, CCF 1439084, IIS 1247726, IIS 1251137, CCF 1217708, and Sandia National Laboratories. This research was conducted during Shikha Singh's stay at IBISC, University of Evry Val d'Essonne, Evry 91000, France supported by a Chateaubriand Fellowship, and Samuel McCauley's stay at ENS de Lyon, supported by INRIA and a Chateaubriand Fellowship.