Temporal Information Design in Contests

1 Introduction

Contests are important mechanisms to elicit work (/effort/ideas) from crowds. While contests have been used throughout history (e.g. the British government's 1714 Longitude Prize), they have gained popularity in the current Internet era, and, in particular, in the context of crowdsourcing [Archak and Sundararajan, 2009; DiPalantino and Vojnovic, 2009; Chawla et al., 2012; Liu et al., 2014]. Well known examples include the Netflix prize, Darpa challenges and the Hult prize (hultprize.org), as well as various public platforms that allow requesters to solicit contributions through contests with monetary prizes, such as taskCN (www.taskcn.com), TopCoder (www.topcoder.com) and Kaggle (www.kaggle.com). As such, the study and analysis of contests have become prominent in mechanism design and multi-agent systems literature [Cavallo and Jain, 2013; Ghosh and Kleinberg, 2016; Levy et al., 2017; Sarne and Lepioshkin, 2017]. These include both the analysis and determination of optimal strategies - for the contestants, and methods for the design of effective contests - for the contest's organizer. In this work we concentrate on the latter issue - that of contest design.

Effective contest design has been studied extensively in literature, but most work has focused on how to design the payoffs structure [Moldovanu and Sela, 2001; Luo et al., 2015]. That is, how many and what prizes should be awarded, and to which contestants. When designing a contest, however, the organizer has freedom to structure all aspects of the contest protocol, not only the payoffs, and this entire structure determines the contestants behavior. In particular, the information available to the contestants during the contest has a dramatic impact on their behavior. Hence, by controlling this information the contest organizer can promote its goals.

There are various types of information that can potentially affect prospective contestants' decisions in a contest: information about the protocol/mechanism, information about the other contestants (competence, etc.), and information about the actions of other contestants and their resulting performance so far. Potentially, the contest organizer may try and control the disclosure of any of the above to its benefit (though some may not be under its control). Indeed, recent literature has acknowledged the importance of information design in contests, studying various issues arising from asymmetric information and information disclosure (see following section). Yet, the information considered in the models studied relates to the inherent characteristics of contestants rather than their actions. Furthermore, and perhaps more importantly, in the models used all information is disclosed at the beginning of the contest (or prior to the contest).

In this paper, we study temporal information design, wherein information on the actions of contestants is disclosed during the course of the contest. Importantly, the temporal disclosure of information turns the contest mechanism from a pure parallel game to a semi-sequential one where contestants make their decisions in real-time while new information unfolds.

Contributions The contributions of this paper are threefold. First, the paper formalizes the model of incremental information disclosure, and its resultant temporal nature. Second, it provides a comprehensive characterization of the (subgame perfect) equilibrium strategies of contestants under such a model for two common contest models - the binary contest and the Tullock contest. Finally, the paper demonstrates that partial and incremental information disclosure, as suggested in this paper, may be highly beneficial for the contest organizer, in both of the contest models considered.

2 RelatedWork

Much theoretical work has been devoted to the design of an optimal contest that best serves the organizer's objective function, typically by assuming a specific structure and studying its equilibrium under different assumptions. Common structures are one-stage, where contestants compete simultaneously [Dasgupta and Nti, 1998; Fu and Lu, 2010; Runkel, 2006; Ghosh and Kleinberg, 2016] or multiple rounds consisting of series of contests (most known as a tournament) [Rosen, 1986; Clark and Riis, 1996; Gradstein and Konrad, 1999; Moldovanu and Sela, 2006].

The study of information design in contests is very recent and encompasses various aspects of information providing, such as the contestants' ability to acquire information (e.g., about rivals) [Morath and M¨unster, 2013; Denter et al., 2011], the disclosure of private information either directly or in the form of signaling [Fu et al., 2013; Kovenock et al., 2015], the disclosure of information about contestants' capabilities and types by the organizer in order to influence their behavior [Einy et al., 2017; Ponce, 2018; Kramm, 2018] and the effect of different parameters (e.g., the prize awarded) over the preference of having the contestants knowmore information about their rivals [Denter et al., 2011]. Common to all these works is that the information they consider relates to the types of contestants, i.e., their competence, cost of participation, etc., rather than their actions. Furthermore, and perhaps more importantly, all information is disclosed at the beginning of (or prior to) the contest, thus lacking any temporal aspect. As such, decisions of prospective contestants are made in parallel, as in most contest literature [Dasgupta and Nti, 1998; Moldovanu and Sela, 2006; Liu and Lu, 2014]. Models where contestants' decisions are made sequentially, taking into account information related to the decisions of others were mostly studied with two-period models [Krishna and Morgan, 1998; Amegashie, 2000; Morgan, 2003; Matros, 2006], and rarely with more than two periods [Glazer and Hassin, 2000; Fu and Lu, 2012; Levy et al., 2017]. Moreover, in models of the latter type the process is fully-sequential, i.e., there is only one contestant at a time (according to some pre-defined ordering) deciding on the extent of its participation in the contest and contestants become aware of the performance of all those who engaged before them (e.g., in rhythmic and artistic gymnastics).

Work on temporal information design in contests is very limited, typically by the number of contestants used and the assumptions made. For example, Epstein and Mealem (2013) study the equilibrium in a two-stage two-contestants contest model in which the informed contestant declares its type (or does not declare) in the first stage and in the second stage the two contestants compete according to the information available to them. Gurtler et al. (2013) study sabotage activity in a tournament (i.e., whenever a contestant invests in reducing the effectiveness of a rival's effort), demonstrating that by concealing intermediate information about contestants' performances the incidence of sabotage is mitigated. The most relevant work in the context of this paper is a recent work of Hinnosaar (2018). Considering the Tullock contest in a model essentially identical to ours, Hinnosaar proves that in the case of fully homogeneous agents for which there is no stochastic element associated with their competence or cost, the full information revelation scheme is optimal. However, as we show here, this result is indeed limited to this specific setting, which is rather restrictive. In practice, in most cases the competence of participants is not fully known in advance, and only the distribution thereof is known (or estimated). Indeed, to a great extent, the entire interest in carrying out a contest stems from the uncertainty regarding the contestants competence and costs; if all competences and costs are known then the organizer can simply pay each contestant for its effort separately. Once uncertainty is introduced, the result of Hinnosaar (2018) does not hold, as exhibited in this paper.

3 The General Contest Model

The basic contest model considers a contest organizer and a set A = {A1, ..., Ak} of potential contestants, called "agents" onwards. The agents may be of heterogeneous "types", possibly differing in their competence, cost of engagement, and such. The agents need to decide if and to what extent to engage in the contest (e.g., howmuch effort to exert).

All agents and the organizer are fully-rational and selfinterested. To elicit participation or effort, the organizer offers a prize M > 0 to be awarded to the highest-ranked agent, where the ranking is a function of the performance/effort exerted by the participating agent. Prize allotment may also involve a stochastic element. We assume, as many prior works [DiPalantino and Vojnovic, 2009; Chawla et al., 2012; Levy et al., 2017] that the organizer and the agents are familiar with the prize offered M and the agents' type distributions. The goal of the organizer is to maximize some objective function that takes as input the performance/efforts of the agents and the prize awarded. The goal of each agent is to maximize its own expected profit, defined as the value of the prize it receives minus the cost incurred while engaging in the contest.

3.1 Information Disclosure Schemes

The above contest model encompasses most contest models found in the literature. We now show it can be augmented to support information disclosure. It is assumed that the organizer has access to the acts of the performance levels of the agents, but that other agents do not have direct access to this information. Hence, after some agents have acted, the organizer can (but does not need to) disclose this information to the remaining agents. In principle, there are many possibilities as to what information it chooses to disclose, to whom, and under what circumstances. As a starting point, in this paper, we focus on disclosure schemes of the following type:

Comprehensive: when information on an agent is disclosed, it includes all the information on the agent's act.

Broadcast: whenever information is disclosed, it is all disclosed to all agents.

Set Based: the organizer commits to a family of subsets of agents {S1, . . . , Sn}, Si ⊊ A, such that it reveals all information on Si once all the agents therein have acted.

Truthfullness: The organizer holds by its commitments and discloses only the truth.

Technically, an information disclosure scheme D is simply a family of subsets D = {S1, . . . , Sn}, Si ⊊ A.

3.2 Temporal Behavior

Given the information disclosure commitments of the organizer, agents can benefit from waiting and thus gaining information on the acts of other agents. We thus assume that, given a disclosure scheme D = {S1, . . . , Sn}, any agent Ai waits to act until the information on all sets Sj,Ai ̸∈ Sj are disclosed, and acts immediately thereafter (it cannot wait for a set that includes itself). This results in the following temporal activity structure:

Proposition 1. Given a disclosure scheme D = {S1, ...Sn}, the scheme either results in a deadlock, wherein there are at least two agents each waiting for the other to act, or there exists a series of epochs (E1, . . . ,En) such that for each j, the agents of Ej all act in parallel, and only after all agents of Ej ′ , j ′ < j, have acted.

Proof. First suppose that there are two sets Sj, Sj ′ ∈ D neither of which is contained in the other. So, there exists Aj ∈ Sj - Sj ′ and Aj ′ ∈ Sj ′ - Sj. Agent Aj will wait for Sj ′ to complete its actions, and Aj ′ will wait for Sj to complete its actions, resulting in a deadlock.

Otherwise, the sets of D can be ordered by containments. W.l.o.g. assume that S1 ⊂ S2 ⊂ · · · ⊂ Sn. Then, the claim holds for the epochs defined as E1 = S1 and Ei+1 = Si+1 - Si.

From now on we limit our attention to disclosure schemes that do not result in a deadlock, and consider the resulting epoch structure E = E(D) = (E1, . . . , En).

There are two extreme disclosure schemes: (a) D = ∅, i.e., no information is disclosed, in which case all agents make their decisions independent of the others. We call this the parallel contest; and (b) D = {S1, ..., Sk} where Si = {A1, ...,Ai}. Here, each agent Ai makes its decision only after gaining knowledge of the actions of the previous agents A1, ...,Ai-1. We call this the sequential contest. Between these two extremes there is a multitude of intermediate possible information disclosure structures.

The possible number of information disclosure schemes is combinatorial in the number of agents. In this paper we do not deal with the computational aspects of finding the optimal information disclosure structure. Instead we focus on the equilibrium analysis for a given structure, as our primary goal is to show that temporal information disclosure (as opposed to full or none) can be beneficial for the organizer. In the coming two sections, we provide the equilibrium analysis for the simple/binary contest model (Section 4) and the Tullock contest model (Section 5).

4 Binary Contest

The first contest model we use, which is often termed "simple contest" or "binary contest" applies to a wide spectrum of contests where contestants do not strategize over the quality of their performance, which is a priori set, but rather only decide whether or not to participate in the contest, where participation is costly [Dubey, 2013; Ghosh and Kleinberg, 2016; Levy et al., 2017; Sarne and Lepioshkin, 2017; Levy et al., 2018; Ponce, 2018]. This contest model applies to various real-life settings. For example, consider the case of graduate students applying for a post-doc position. At the time of the contest they cannot influence their performance (as their research has already been carried out and published) and they only have to reason about whether to apply or not. The choice of participation is not trivial, as participation incurs some cost (e.g., time and money spent in getting to an interview). Similar characteristics can be found in beauty pageants, photo contests and many more types of contests.

4.1 Model

Each agent Ai can either participate in the contest, incurring some cost ci, or opt to avoid participating in the contest. If none of the agents participates, the prize is not awarded and the performance as perceived by the organizer is set to some pre-set fall-back performance v0, which, w.l.o.g. we normalize to zero. The performance of an agent Ai is a random variable characterized by some probability distribution function fi(v) (with Fi(v) the associated CDF). The instantiation of the random variable is only determined at the time of actual participation. Here, we focus on continuous distribution. The analysis of the discrete case is analogous. Since the distribution is continuous, the chance of having two agents ranked at the same place is negligible.

The goal of the organizer is to maximize the expected maximum performance obtained by agents in a contest it runs minus the prize M it awards. The goal of each agent is to maximize its own expected profit, defined as the prize awarded to it minus the cost incurred during the contest.

4.2 Strategic Analysis

We use {P, ¬P } to denote the actions available to each agent, where P stands for participate and ¬P for not participate. The strategy of agent Ai is characterized by its participation probability function, pi : R ∪ ∅ → [0, 1], which determines the probability that Ai participates, given that the maximum performance observed in the previous epochs was v (v = ∅ denotes the case where all former agents opted not to participate in the contest).

Consider epoch Et. For E′ ⊆ Et, let FE′ (v, y) denote the probability that the best performance of the agents in subset E′ of epoch Et (for some t ≤ n) is at most y, given that the best performance obtained prior to reaching epoch Et is v. Then,

Similarly, let ¯ FEt (v, y) denote the probability that the best performance in epochs t and on is at most y if reaching epoch Et with best performance v. Denoting ¯ FEn+1 (v, y) = 1 for all y, we inductively have: 1

With FE′(v, y) and ¯ FEt (v, y) we can now express the expected profit of any individual agent Ai ∈ Et from participating in the contest, given the best performance obtained so far v, and the strategies of the other agents S-i = {pj(v)|Aj ∈ A - {Ai}}, denoted BP i (v,S-i):

4.3 Equilibrium

The expected profit of agent Ai if not participating is zero. Therefore in equilibrium it must be that:

We note that it is possible that there is more than one equilibrium solution, though the question of which of those will be used is beyond the scope of the current paper.

As can be observed in (3), the payoff for agent Ai depends only on the actual performance of the agents of previous epochs (as captured by v), not their strategy. This allows us to compute the equilibrium strategy inductively, from the last epoch and back. Specifically, for any epoch Et, given the strategies for agents of epochs Et′ , t′ > t, for any value v, the equilibrium strategy for this epoch's agents is a vector of probabilities pEt (v) = {pi}Ai∈Et , such that (4) holds. For the case of homogeneous agents, i.e., when their performance adheres the same probability distribution function and they all incur the same participation cost, which is actually the assumption made in most prior work [Ghosh and Kleinberg, 2016; Levy and Sarne, 2018], there is a solution wherein all agents of Et have the same strategy, which can be computed as follows. Choose some i ∈ Et.

1. Compute BP i (v,S-i), wherein S-i is the inductively computed strategy for agents of future epochs, and pj(v) = 1 for all other agents of Et. If the resulting BP i (v, S-i) > 0, then set pj(v) = 1 for all Aj ∈ Et.
2. ComputeBP i (v,S-i), whereinS-i is as above, but with pj(v) = 0 for all other agents of Et. If the resulting BP i (v, S-i) < 0, then set pj(v) = 0 for all Aj ∈ Et.
3. Otherwise, find a value p ∈ (0, 1) such that BP i (v,S-i) = 0, wherein Si is as above, but with pj(v) = p for all other agents in Et. Such a value must exists by continuity.

1 Here and in (3), when v = ∅ it is taken as v = -∞.

Monotonicity of pEt

We now show an important characteristic of the equilibrium participation probability functions pi(v), which can aid in the computation thereof. We show that for each epoch Et, the vector pEt (v) does not decrease (in the ℓ∞ norm) as v decreases. That is, as v decreases, it cannot be the case that all the pi(v)'s, Ai ∈ Et, also decrease.

Proof Sketch: For brevity, we provide the proof for the case that fi has full support, for all i. Contrariwise, suppose that pi(v) < pi(v) for all i ∈ Et. Then, by (1), FEt-{Ai}(v, y) > FEt-{Ai}(v, y), for all i ∈ Et. So,

Now, (5) is at least 0, as otherwise pi(v) = 0, and cannot be further decreased. Also, (6) is positive, as all its components are positive. Therefore, in all BP i (v,S-i) > 0. So, by (4), pi(v) = 1, and cannot be less than pi(v). In contradiction.

In particular, for the homogeneous case we get:

Corollary 1. In the homogeneous case pi(v) is nonincreasing in v, for all i.

4.4 Organizer's Profit

The above enables calculating the expected profit of the organizer, denoted Borg :

The calculation considers all possible outcomes (best performances) y (above the default value v0 = 0). The organizer awards the prize M in case at least one of the agents participates, which occurs with probability (1- ∏Ai∈A(1-p(∅))). The organizer thus can calculate the equilibrium for different divisions of the agents into epochs and pick the one that maximizes its expected profit.

4.5 The Benefit of Information Design

Having characterized the equilibrium strategy, we now illustrate the benefit the organizer can obtain from temporal information design. We do so by giving an example wherein, depending on the exact parameters of the problem, the profit of the organizer is maximized using different information disclosure schemes, including at times: the fully parallel, the fully sequential, and a hybrid scheme.

Consider a setting with three homogeneous agents (k = 3) and a prize M = 0.6. The agents are homogeneous in the sense that they have the same underlying performance distribution (f(x) = 1 for 0 ≤ x ≤ 1 and zero otherwise) and cost of participation c. 2 For this setting, we consider the organizer's profit, as a function of the participation cost c, for the four (up to isomorphism) possible epoch schemes:

Figure 1 depicts the graph of the organizer's expected profit for each of these disclosure schemes. In green, the graph for E1, the pure parallel contest. Here, for c < M/3 = 0.2 the equilibrium is that all agents participate, resulting in an expected profit of Borg = 0.15. In the interval 0.2 < c < 0.6 the equilibrium is in mixed strategies. The yellow curve depicts the organizer's profit with E4. Here, the equilibrium dictates the participation of A1, and agents A2 and A3 probability of participation depends on the value v obtained by A1. The blue curve depicts the organizer's profit with E3. Here, A3's strategy is threshold-based (i.e., its best response strategy is to participate if the best performance disclosed is less than some value, and otherwise to not participate). In the interval c < M/3 = 0.23 we obtain an equilibrium (1, 1, r), i.e., agents A1 and A2 necessarily participate, and A3 participates only if the best value received is smaller than r (which value depends on c) and for c > 0.23 the equilibrium is (p(∅), p(∅), r), i.e., agents A1 and A2 use mixed strategy while A3 participates only if the best value received is smaller than r (which once again depends on c). The orange curve depicts the organizer's profit with E2 (the fullysequential contest). In this case we obtain a single equilibrium, where all agents use the same threshold for their participation decisions [Levy et al., 2017].

As can be seen from Figure 1, no one disclosure scheme dominates throughout: for c < 0.22 and c > 0.52, scheme E1 dominates; for 0.22 ≤ c < 0.25, scheme E3 dominates; and for 0.25 ≤ c < 0.52 scheme E2 dominates. So, in all, in order to maximize its profit, the organizer must carefully choose the information disclosure scheme. By limiting to one scheme (e.g., the standard fully parallel scheme) the organizer may be obtaining sub-optimal results, at times severely so, as in the case of c = 0.4, where the profit with E1 is negative, and that of E2 is positive.

2 The homogeneity assumption is only used for ease of exposition in this example. Other, more complex examples with heterogeneous agents can also be obtained.

5 Tullock Contest

The second contest model we consider is the effort-based contest where contestants can influence their probability of winning the prize by the "effort" they exert [Moldovanu and Sela, 2006; Cavallo and Jain, 2013]. Specifically, we consider a generalized Tullock contest wherein contestants' costs of exerting effort are heterogeneous and a priori uncertain.

5.1 Model

We follow the basic Tullock model [Buchanan et al., 1983]. The organizer offers a prize M. Each contestant Ai can participate in the contest by exerting some effort level ei, which is a non-negative real number of its choice. The cost for Ai in exerting effort ei is ci · ei, for some constant ci associated with Ai. Given the sequence e1, . . . , ek of efforts exerted by the agents, the probability of Ai winning the prize is given by: pi(e) = ei/∑kj=1 ej.3 Ai's expected profit is thus Mpi(e) - ciei.

The contestants' cost constants ci may be uncertain, in the sense that only the agent itself knows its true cost, while others only know some distribution gi over the possible values of ci. The gi's are assumed to be known to all agents and the organizer.

The goal of the organizer is to maximize the sum of efforts expended by all agents minus the prize awarded. The goal of each agent is to maximize its own expected profit.

5.2 Strategic Analysis

Note that the strategy of agent Ai ∈ Et may depend on its actual cost ci, and the observed total effort expended in previous epochs, denoted e, but it does not matter how this effort was distributed between the previous agents. So, the effort (/strategy) ei of agent i is a (possibly randomized) function eci i (e).

Fix some strategy e1, . . . , ek of the agents. Consider an epoch Et. For a subset of agents E′ ⊆ Et and total effort e in the previous epochs, let FE′(e, y) be the probability that the total effort exerted by agents in subset E′ is at most y. Denoting by ¯ FEt (e, y) the probability the total effort in epochs from Et and on is at most y, given that the effort in the previous epochs is e, it is inductively obtained:

3 For completeness, if ∑ ej = 0 then pi(e) = 0.

The expected profit of agent Ai ∈ Et from exerting effort eci i (e), given cost ci and total effort previously exerted was e is thus:

(where E is the expectation according to the possibly mixed strategy ei). Taking the derivative of Bi(e, ei, ci) according to ei and equating to zero we obtain the function ei which is the best-response strategy of agent Ai, which in turns, dictates the equilibrium strategy.

The expected profit of the organizer is simply the expected sum of efforts exerted by all agents, minus the prize:

5.3 The Benefit of Information Design

We demonstrate the benefit in temporal information disclosure. Here we use three homogeneous agents, each with two possible costs of exerting effort: c1 = 0.1 with probability 0.12 and c2 = 0.9 with probability 0.88. The prize is M = 1.1. In the pure parallel contest the Nash Equilibrium solution is ec1 i = 1.945 and ec2 i = 0.233, for i = 1, 2, 3, resulting in organizer's expected profit of 0.217. In the fullysequential contest, the equilibrium of the contest is as described in Figure 2. This results in organizer's expected profit of 0.135. When E = ({A1,A2}, {A3}) the equilibrium of the contest is as described in Figure 3, which results in a significantly greater expected profit of 4.114.

6 Conclusions and Open Problems

We analyzed temporal information disclosure in contests, and demonstrated its potential for increasing the organizer's profit, at times dramatically. Indeed, in some cases, incremental information disclosure, as suggested here, can turn an otherwise losing contest into a profitable one (see Figure 1). Furthermore, we have demonstrated that while information disclosure can be beneficial, it is not necessarily the case that disclosing all available information is always the best strategy. Rather, depending on the circumstances, different, at times partial, disclosure schemes are optimal. This finding is in contrast to that of Hinnosaar (2018), which showed that for the Tullock contest full disclosure, resulting in a fully sequential contest, is always optimal. However, it can be shown that this result only holds when there is no uncertainty regarding the contests' competence and costs. In the general case, as we consider here, partial disclosure can be beneficial.

We see this work as a first step towards a cohesive theory of temporal information design in contests, and many questions remain for future research. A major question is developing algorithms and heuristics for determining the optimal disclosure scheme, as the total number of possible disclosure schemes is exponential in the number of contestants. Additionally, if determining the optimal scheme proved to be difficult, it would be interesting to see if one can establish dominance relations between some of the schemes, under various conditions. Another interesting research avenue is in allowing more complex disclosure schemes. Specifically, in our model we have assumed a broadcast setting, where information is either provided to all contestants or to none. However, selective information disclosure, where the organizer discloses information to some of the contestants and not others is also possible, and may further increase its profit. Exploring this possibility is an interesting future direction. Another interesting question concerns the organizer's commitment power; under what circumstances does the organizer have the ability to implement policies that control disclosure of information, and what is the value of this commitment.

Acknowledgments

This research was partially supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1162/17) and the ISFNSFC joint research program (grant No. 2240/15).