# competition_among_pairwise_lottery_contests__2575c9c1.pdf

Competition among Pairwise Lottery Contests

Xiaotie Deng1, Hangxin Gan2, Ningyuan Li1, Weian Li1, Qi Qi3*

1 Center on Frontiers of Computing Studies, School of Computer Science, Peking University, Beijing, China 2 School of Mathematical Science, Nankai University, Tianjin, China 3 Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China {xiaotie, liningyuan, weian li}@pku.edu.cn, hangxin.gan@mail.nankai.edu.cn, qi.qi@ruc.edu.cn

We investigate a two-stage competitive model involving multiple contests. In this model, each contest designer chooses two participants from a pool of candidate contestants and determines the biases. Contestants strategically distribute their efforts across various contests within their budget. We first show the existence of a pure strategy Nash equilibrium (PNE) for the contestants, and propose a fully polynomial-time approximation scheme to compute an approximate PNE. In the scenario where designers simultaneously decide the participants and biases, the subgame perfect equilibrium (SPE) may not exist. Nonetheless, when designers decisions are made in two substages, the existence of SPE is established. In the scenario where designers can hold multiple contests, we show that the SPE always exists under mild conditions and can be computed efficiently.

Introduction Contest theory is a commonly used and classic tool in the field of economics to define competition. In fact, many competitive scenarios can be perceived as contests. These may include political elections, sports events, promotional contests between firms aiming to increase their market share, and so forth. When designing a contest, the objective is to motivate the contestants to put forth greater effort in order to achieve specific goals. This involves determining the prize amount, the number of participants, and the winning rule. Pairwise contests are a type of competition where the number of participants is limited to two. Classic examples of pairwise contests include the Colonel Blotto games (Borel 1921), which depict two players engaged in a battle where the outcome determines the victor. Such contests have numerous real-world applications. For instance, the US presidential election is a well-known example where two candidates compete over all states. Similarly, in competitive sports such as the NBA, two teams compete multiple times to determine the champion. The Internet price war (Li et al. 2019) provides another example, where two e-commerce platforms compete for regional markets by offering discount coupons. The lottery contest is a form of imperfectly discriminatory competition, where the contestant who allocates more

*Corresponding author. Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

effort has a higher probability of winning than one who allocates lesser effort. In real-world scenarios, the lottery contest is highly applicable due to the stochastic factors that may impact the outcome. More specifically, despite allocating greater effort towards a given issue, winning is not always certain due to the unpredictability of such factors. Current research on pairwise and lottery contests tends to center around studying the equilibrium behaviors of contestants or optimizing lottery functions to achieve certain objectives. However, little attention has been paid to investigating competing designers. According to a recent survey on contest theory (Segev 2020), exploring the economy of competitions among designers poses several challenges, particularly in analyzing their equilibrium behavior. In a single contest or a fixed number of contests, the focus is primarily on the strategic behavior of contestants. However, designers also have strategic behavior that needs to be taken into account, including how contestants allocate their efforts and how designers compete with one another. In this paper, we concentrate on the pairwise lottery contests (PLC), where two contestants compete for a prize with a winning probability determined by the lottery rule that is based on their (weighted) effort. Designers are allowed to hold one or several PLCs. Each designer s goal is to maximize the total exerted effort of the participants in all her held contests. Each contestant pursues maximizing the expected prize from the contests she joins. There is a two-stage game in our model: one is among contest designers, who decide the number of held contests and design the configuration (including prize, participants and biases) of held contests. The other is among contestants who decide how to allocate effort.

Our Contributions

Our model introduces several innovative features that enrich the current discourse in contest theory. Firstly, much of the existing literature predominantly concentrates on single contest design or contestants equilibrium analysis within prescribed multi-contest frameworks. In contrast, we cast sight into the case of multiple contests held by different strategic designers. Therefore, the designers strategic behaviors are integrally addressed and analyzed. Secondly, traditional models, exemplified by the Colonel Blotto games, typically focus on pairwise contests involving just two contestants and

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

mainly study equilibrium behaviors of these two contestants. We expand this framework, allowing for n potential participants, thereby granting strategic designers the latitude to select any two from this candidate pool. While this expansion offers a more richer and realistic representation, it increases the analytical difficulty of the model. Our contributions and results can be summarized as follows: Given the configurations of all contests, for the game among contestants (the second stage in our model), we propose a concept called equilibrium multiplier vector (EMV) which represents marginal utilities of contestants in equilibrium, as our main analytical tool characterize the contestant equilibrium. We prove the existence of EMV utilizing Brouwer s fixed-point theorem, and show the uniqueness of EMV leveraging a monotone property. By establishing the connection between the EMV and equilibrium strategy of contestants, we fully characterize the contestant equilibria. Furthermore, we design a polynomial time algorithm to compute an ϵ-approximate contestant equilibrium. For the game of designers (the first stage in our model), when each designer is allowed to hold one contest only, we first show the non-existence of subgame perfect equilibrium (SPE) in certain cases, due to the complicated deviation of the two-dimension strategy (choosing participants and biases simultaneously). However, if designers choose participants and set biases in two separated substages, we can always find an SPE. Specifically, when the participants are fixed, considering the designers strategies to set the biases, we show that it forms an equilibrium when all designers set balancing biases such that every participants in each contest have the same winning probability (i.e., 1/2). Under this situation, the equilibrium effort exerted by a contestant into each contest is proportional to the contest prize. We observe that the designers participants selection is actually equivalent to a variant of weighted congestion game, where a pure Nash equilibrium always exists, implying the existence of a sequential equilibrium in our model. When each designer can divide her budget to hold several contests, although the strategy space of designers seems to become more complicated, surprisingly, we show that an SPE always exists even if the participants and biases are decided simultaneously, under a very mild condition that the maximum total effort of an individual contestant does not exceed the total effort of all other contestants. In this SPE, each contestant s or designer s utility will be proportional to her total effort or prize budget, respectively. All missing proofs appear in the full version (posted in ar Xiv).

Related Works Our paper contributes to the literature in the field of economics and computer science, particularly in topics of multiple contests competition and pairwise contest design. Our work is closely related to the following several studies. (Li

and Zheng 2022) focus on the analysis of pure strategy Nash equilibrium on 2-contestant lottery Colonel Blotto games. However, our paper extends the total number of contestants from 2 to n, which leads to that each contestant may have different opponents in different pairwise contests. In addition, (Fu and Wu 2018) study designing the optimal lottery contest by setting biases in the setting of single contest to achieve different objectives. (Wang, Wu, and Xing 2023) consider a setting of multi-battle contests where the same two contestants battle with each other in every contest and every designer sets biases to attract more effort. Our paper can be viewed as a generalized model of these two papers, where the designer of each contest picks up two contestants from n candidates and sets the biases. Our research focuses on two aspects: equilibrium analysis and contest design. We summarize related works in three fields: lottery contests, Colonel Blotto games, and competition among contests. Lottery Contests The lottery-form contest is introduced by (Skaperdas 1996) and (Clark and Riis 1998), where contestants winning probability is determined by a contest success function (CSF). (Dasgupta and Nti 1998) consider the optimal CSF with n symmetric contestants. (Nti 2004) studies the optimal CSF in two-contestant symmetric contest. When employing a certain form of CSF, lottery contest is classified as a specific type of Tullock contest (Nti 1999; Tullock 2001; Stein 2002). (Clark and Riis 1998) examine the contest performance affected by the different parameters of Tullock CSF. Multiple equilibria in Tullock contest is studied in (Chowdhury and Sheremeta 2011). When there are only two contestants, the optimal contests obtained by optimizing the parameters of Tullock CSF are investigated (Wang 2010; Epstein, Mealem, and Nitzan 2011). (Franke et al. 2013) provide the optimal biases for an n-player Tullock contest. Besides, the lottery contests with multi-prize is discussed in (Fu, Wu, and Zhu 2022). Additionally, the best response dynamics of contestants is investigated by (Ewerhart 2017; Ghosh and Goldberg 2023). Colonel Blotto Games Colonel Blotto Games (Borel 1921) characterize the competition between two players across several contests (aka., battle-fields), which has some similarity to the game among contestants in our model. Many classic papers in this topic mainly focus on the deterministic CSFs, e.g., (Gross and Wagner 1950; Roberson 2006; Macdonell and Mastronardi 2015; Kovenock and Roberson 2021). (Friedman 1958) first introduces lottery CSFs into a two-contestant symmetric Blotto game and shows the uniqueness of equilibrium. (Duffy and Matros 2015) generalize the results to the case with more than two contestants. Some works (Robson et al. 2005; Xu and Zhou 2018) study the two-contestant Blotto game under the general Tullock CSFs. Competition among Contests The topic of competition among contests has received increasing attention in the recent decade. Initially, (Azmat and M oller 2009) examine the two identical Tullock contests setting and investigate the prize structure in different goals. (Di Palantino and Vojnovic 2009) study multiple auction-based crowdsourcing contests and give the contestants equilibrium in symmetric

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

and asymmetric settings. Later, many sutdies (B uy ukboyacı 2016; Azmat and M oller 2018; Juang, Sun, and Yuan 2020) focus on comparing the performance of two parallel contests with different types. Recently, (Deng et al. 2023) investigate that the optimal CSF in the monopolistic setting is also the equilibrium strategy in the competitive setting when designers aim to maximize the total effort. (K orpeo glu, Korpeoglu, and Hafalır 2022) show that when a contestant can join several contests but the output in each contest is affected by an uncertainty variable, increasing the number of contests one contestant participates in improves the utility of contest organizer. (Deng et al. 2022) focus on the environment of parallel contest. They analyze the equilibrium of contestants participation and design the prize policies of contests in different settings.

Model and Preliminaries There are n contestants and m designers. We use the notation i [n] and j [m] to denote a contestant and a designer, respectively. We assume that each contestant i has a limited total effort Ti R>0 to exert in contests and each designer j has a limited budget Bj R>0. In this work, we focus on pairwise general lottery contests, in which the designer invites two contestants as the participants, and sets a multiplicative bias for each participant to incentivize their effort. Each participant s winning probability depends on the product of her bias and her effort exerted into this contest. Formally, a pairwise general lottery contest C is defined as a tuple C = (SC, RC, αC): SC denotes two contestants selected as participants of contest C, satisfying that SC [n] and |SC| = 2; RC R>0 denotes the prize prepared for the winner in the contest; and αC = (αC,i)i SC, where αC,i R>0 denotes the bias selected for the participant i. Suppose SC = {i1, i2}, and let xi1,C and xi2,C be the effort that these two contestants exert in contest C. Each contestant s effort is multiplied by her bias to get αC,i1 xi1,C and αC,i2 xi2,C. The winning probabilities of contestants i1 and i2 are f(αC,i1 xi1,C; αC,i2 xi2,C) and f(αC,i2 xi2,C; αC,i1 xi1,C) respectively, where f is the lottery CSF defined as follows:

( x x+y, if x > 0 y > 0, 1 2, if x = y = 0.

Note that f(x; y) + f(y; x) = 1. We study two models of the designers, varying in whether a designer can divide her budget to hold multiple contests. 1. In the divisible prize model (DPM), each designer j is allowed to distribute her prize budget Bj to hold an arbitrary number of contests, denoted by Cj = {Cj,1, , Cj,Kj}, satisfying that P C Cj RC Bj.

2. In the indivisible prize model (IPM), each designer j can hold only one pairwise general lottery contest, denoted by Cj, and RCj Bj. In this case we define Cj = {Cj}. In both models, each designer j can arbitrarily design the configuration of every contest C Cj, i.e., the invited participants SC, the reward RC, and the bias αC, within

her budget. We call Cj the strategy of designer j and define C = (C1, , Cm) as the strategy profile of designers. Sometimes we use the notation C C to denote that C j [m]Cj. Given designers strategy profile C, for any contestant i, let A(i, C) = {C j [m]Cj : i SC} be the set of contests that i is invited to participate in. Each contestant i decides non-negative amounts of effort to exert in those contests inviting her, denoted by xi = (xi,C)C A(i, C), which satisfies P

C A(i, C) xi,C Ti. We call xi the strategy of contestant i, and x = (x1, , xn) is called the strategy profile of contestants. Sometimes we use C j and x i to denote the strategy profile of all designers except designer j and the strategy profile of all contestants except contestant i, respectively. Given C and x, for any contestant i and any contest C A(i, C), let OPi,C denote her opponent in contest C, that is, SC = {i, OPi,C}. Then, her winning probability in C is denoted by

pi,C( x) = f(αC,i xi,C; αC,OPi,C x OPi,C,C).

The utility of contestant i is defined as her expected total prize, u Contestant i ( C, x) = P

C A(i, C) RC pi,C( x). And the utility of a designer is the total effort exerted by the participants in her all contests, u Designer j ( C, x) = P C Cj P i SC xi,C. With these definitions, we study a two-stage game model of the competition among pairwise lottery contests. Definition 1 An instance of Pairwise Lottery Contest Competition Game (PLCCG) is defined as the tuple (n, m, (Ti)i [n], (Bj)j [m]). The game has two stages: 1. In the first stage (called the stage of designers), all designers simultaneously select their strategies. In other words, each designer j [m] decides the number Kj = |Cj| (under the indivisible prize model, Kj always equals to 1.) of contests to hold, and the configuration of each contest C Cj, within her total budget Bj. 2. In the second stage (called the stage of contestants), having observed C1, , Cm, all contestants simultaneously select their strategies, i.e., each contestant i [n] decides her effort xi = (xi,C)C A(i,C), within her total effort Ti. Our work mainly focuses on the sequential equilibrium, i.e., subgame perfect equilibrium (SPE), of PLCCG. Before giving the definition of SPE, we first define the contestant equilibrium, i.e., the pure Nash equilibrium among contestants in the second stage, when a strategy profile C of designers is given.

Definition 2 Given designers strategy profile C, we say a contestant strategy profile x is a contestant equilibrium under C , if for any i [n] and any feasible strategy x i, it holds that

u Contestant i ( C, x) u Contestant i ( C, (x i, x i)).

Define E C as the set of all contestant equilibria under C.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Next, we define the subgame perfect equilibrium and designer equilibrium.

Definition 3 ( C, x) is a subgame perfect equilibrium, if the following two conditions hold:

1. x is a contestant equilibrium under C, i.e., x E C. 2. For any designer j, any feasible strategy C j and any x E(C j, C j), it holds that 1

udesigner j ( C, x) udesigner j ((C j, C j), x ).

We say C is a designer equilibrium if there is some x E C such that ( C, x) is a subgame perfect equilibrium.

Contestant Equilibrium In this section, we study the equilibrium behavior of contestants in the contestants stage of PLCCG, i.e., the contestant equilibrium, when the designers strategy profile is given. In subsection , as a key tool for analyzing and characterizing contestant equilibrium, we propose a concept called equilibrium multiplier vector (EMV), which represents each contestant s equilibrium strategy by a multiplier variable, indicating the contestant s marginal utility under the contestant equilibrium. We also show the close connection between contestant equilibrium and EMV. This simplifies the contestant s multi-dimensional strategy into a single-dimensional number. In subsection , we prove the existence and uniqueness of equilibrium multiplier vector, which enables us to fully characterize the set of all contestant equilibria. Additionally, in subsection , we show that an ϵ-approximate contestant equilibrium can be found in polynomial time through an iterative updating process of the multiplier vector, which draws inspiration from the tˆatonnement algorithm used in the field of market equilibrium. Given any designers strategy profile C, since the contestants do not care about the holder of each contest, we can simplify some notions. We use the notation C = j [m]Cj to denote the set of all contests, and define A(i, C) = {C C : i SC} and ui(C, x) = P C A(i,C) RC pi,C( x). W.l.o.g, we assume that for any contestant i [n], A(i, C) = .

Equilibrium Multiplier Vector In this subsection, we propose equilibrium multiplier vector as a representation of contestant equilibrium. We first give the motivation and definition of EMV by Lemma 1 and Definition 4. Then we characterize the contestant equilibrium with the help of EMV. We derive a necessary and sufficient condition for a vector being an EMV in Theorem 1, and then characterize the set of all contestant equilibria corresponding to an EMV as shown in Theorem 2. Combining Theorem 2

1Note that this definition is slightly stronger than the standard definition of SPE since it requires that for any designer j, x is better for the best x E(C j, C j), while the standard definition only

requires that x is better for some x E(C j, C j). However, this is not an essential difference since the contestant equilibrium will be unique in some sense as shown later.

and the uniqueness of EMV proved in the next subsection, we can fully characterize the set of all contestant equilibrium. If x is a contestant equilibrium, for each contestant i, xi is a best response to x i. In other words, xi is an optimal solution to the following optimization problem:

max xi,C 0 for C A(i,C)

C A(i,C) RC pi,C(xi, x i), (1)

C A(i,C) xi,C Ti.

Intuitively, if we use the Lagrange multiplier method, there will be a Lagrange multiplier λi 0 so that xi maximizes the Lagrangian function P C A(i,C) RC pi,C(xi, x i) λi(Ti P C A(i,C) xi,C). However, due to the discontinuity of pi,C(xi, x i) at the point with xi,C = x OPi,C,C = 0, the Lagrange multiplier method cannot be applied directly. Thus, we establish the existence of such λi for each contestant i through some analysis, to obtain the following lemma.

Lemma 1 If x is a contestant equilibrium under strategy profile C, there exist λ1, , λn R 0 such that, for any contestant i and any contest C A(i, C), RC pi,C( x)

xi,C λi, where the equation holds when xi,C > 0.

By Lemma 1, we know that every contestant equilibrium x corresponds to a vector λ = (λ1, , λn), which can be viewed as the vector of contestants Lagrange multipliers in Optimization 1. We refer to such λ as an EMV.

Definition 4 A vector λ = (λ1, , λn) Rn 0 is an equilibrium multiplier vector, if there exists a contestant equilibrium x such that x and λ satisfies the conditions in Lemma 1. We call x a contestant equilibrium corresponding to λ.

First, we present a necessary and sufficient condition to decide whether a vector λ is an EMV. We say a vector λ Rn 0 is valid if for any contest C C, it holds P i SC λi > 0. Then, for any valid vector λ Rn 0, we define

ˆxi,C( λ) = RC αC,iαC,OPi,CλOPi,C (αC,OPi,Cλi + αC,iλOPi,C)2

for any contestant i and any contest C A(i, C). For any contestant i, we also define ˆTi( λ) = P C A(i,C) ˆxi,C( λ), which can be viewed as the demand of contestant i s effort induced by λ. Before giving the characterization of EMV, we first give a lemma to show that ˆxi,C( λ) is the lowest exerted effort in a contestant equilibrium corresponding to λ.

Lemma 2 If x is a contestant equilibrium corresponding to an equilibrium multiplier vector λ, for any contestant i [n] and any contest C A(i, C), it holds that xi,C ˆxi,C( λ), where the equation holds when λi > 0.

Now, we can give a necessary and sufficient condition for a vector λ to be an EMV, which enables us to identify an EMV directly.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Theorem 1 For any λ Rn 0, λ is an equilibrium multiplier vector if and only if the following statements hold:

1. λ is valid; 2. For any contest i with λi > 0, Ti = ˆTi( λ); 3. For any contest i with λi = 0, Ti ˆTi( λ).

Next, we show that, when given an EMV λ, the set of all contestant equilibria corresponding to λ is also uniquely determined.

Theorem 2 If λ is an equilibrium multiplier vector, then a contestant strategy profile x is a contestant equilibrium corresponding to λ if and only if x X( λ), where

X( λ) = {(xi,C)i [n],C A(i,C) :

C A(i,C) xi,C Ti

C A(i, C), xi,C ˆxi,C( λ)}.

It is notable that in the next subsection, we will prove that for any C, there always exists a unique EMV λ. Combined with this, Theorem 2 fully characterizes the set of all contestant equilibria, which is exactly X( λ).

Existence and Uniqueness

In this subsection, we mainly discuss the existence and uniqueness of EMV. We prove that EMV always exists (Theorem 3) and is unique (Theorem 4) for any strategy profile of designers. Although the existence of contestant equilibrium follows immediately, there may exist multiple contestant equilibria. Nonetheless, as mentioned before, the set of all contestant equilibria is fully characterized by the unique EMV through Theorem 2. A conventional approach to prove the existence of a contestant equilibrium is to consider the best response updating process of the strategy profile x and show the existence of a fixed point by Kakutani fixed-point theorem (Kakutani 1941). However, due to the discontinuity of the lottery CSF f(x; y) at the point x = y = 0, the set of contestant i s best response is sometimes empty and the condition of Kakutani fixed-point theorem is not satisfied. To address this problem, we turn to the space of multiplier vectors. We carefully design a continuous mapping of the multiplier vector λ such that the fixed point is an EMV, and prove the existence of such a fixed point by Brouwer s fixed-point theorem.

Theorem 3 For any designers strategy profile C, there exists an equilibrium multiplier vector λ.

Next, we prove the uniqueness of EMV. Recall that, for any valid λ, ˆTi( λ) can be viewed as the demand of contestant i s effort induced by λ, and the conditions in Theorem 1 can be interpreted as a complementary-slackness condition for the demands ˆT1( λ), , ˆTn( λ). We view these demands as a vector function ˆT( λ) = ( ˆT1( λ), , ˆTn( λ)). An important observation is that, ˆT( λ) satisfies a monotone property in λ.

Lemma 3 For any two valid multiplier vectors λ and λ , it holds that n X

i=1 (λ i λi)( ˆTi( λ ) ˆTi( λ)) 0.

Moreover, the strict inequality holds when there exists some i such that λ i = λi and max C A(i,C) max{λOPi,C, λ OPi,C} > 0.

With this monotone property, we can prove that the EMV is unique 2. Intuitively, if there are two distinct EMVs, λ and λ , by Lemma 3 they will induce different demand of efforts, i.e., ˆT( λ) = ˆT( λ ), which will contradict with Theorem 1.

Theorem 4 Given any designers strategy profile C, there is a unique equilibrium multiplier vector.

Computation of Contestant Equilibrium In this subsection, we study the computation of the contestant equilibrium. We design an algorithm which computes an ϵ-contestant equilibrium in polynomial time given any strategy profile of designers C. Lemma 3 provides the insight that, we can roughly adjust ˆT( λ) towards some direction by adjusting λ in the the opposing direction. Building upon this, we firstly find an approximate EMV through an iterative updating process inspired by the tˆatonnement algorithm, and then construct an approximate contestant equilibrium based on this approximate EMV. Definition 5 A strategy profile x is an ϵ-approximate contestant equilibrium, if for any i and any feasible strategy x i, u Contestant i ( C, x) (1 ϵ)u Contestant i ( C, (x i, x i)) holds.

Theorem 5 Given any strategy profile C, for any ϵ > 0, there exists an algorithm to compute an ϵ-approximate contestant equilibrium in polynomial time in 1

ϵ and the input sizes, namely n, m, and | j [m] Cj|.

Indivisible Prize Model Starting from this section, we investigate the equilibrium behavior of designers. We study the indivisible prize model (IPM) in this section and the divisible prize model (DPM) in Section . In this section, we first show that the designer equilibrium (defined in Definition 3) may not exist in some instances of IPM. Thus, we consider a weaker concept called weak designer equilibrium (WDE), based on a setting where the stage of designers is divided into two substages. By analyzing the equilibrium of two substages in reverse order, we prove that WDE always exists, in which all designers will adopt balancing biases such that both sides of any contest have an equal winning probability of 1/2 under a contestant equilibrium.

2We remark that the uniqueness of EMV relies on the assumption that for any contestant i, A(i, C) = . When there is some contestant i with A(i, C) = , it means that contestant i does not participate in any contest, and we can assume that λi can take arbitrary value. In this case, however, for any other contestant with A(i, C) = , the equilibrium multiplier is still unique.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Weak Designer Equilibrium We first use a counterexample to show that the SPE may not exist under IPM, even in a very simple instance with 3 identical contestants and 2 identical designers. Theorem 6 In some instances of indivisible prize model, the designer equilibrium does not exist. Roughly speaking, the main reason of the nonexistence of SPE is that modifying the choice of participants in some contest can cause significant change in the optimal choice of biases, which again leads to another better choice of participants. Therefore, we relax the requirement of designer equilibrium by separating the stage of designers into two substages3: in the first substage, each designer decides the amount of prize and participants of her contest; and in the second stage, each designer decides the biases of her contest. Now we provide the definition of WDE formally. For each designer j, we call (RCj, SCj) her first-stage strategy, and (αCj,i)i SCj her second-stage strategy. Let Bias Dev(Cj) = {C j : RC j = RCj SC j = SCj} denote all strategies of designer j whose first-stage strategy is the same as that of Cj. The WDE can be defined as follows.

Definition 6 In the IPM, we say a strategy profile C is a second-substage equilibrium, if there exists x E C such that, for any designer j, any C j Bias Dev(Cj) and for any x E(C j, C j), it holds that udesigner j ( C; x)

udesigner j ((C j, C j); x ). We say a strategy profile C is a first-substage equilibrium, if the following holds:

1. C is a second-substage equilibrium. 2. There exists x E C such that, for any designer j and any strategy C j, there is C j such that C j Bias Dev(Cj ) for any j = j,

C = (C j, C j) is a second-substage equilibrium,

udesigner j ( C; x) udesigner j ( C ; x ) for all x E C .

A strategy profile C is called a weak designer equilibrium if it is a first-substage equilibrium. It is not hard to find that WDE is a weaker concept than designer equilibrium, since any beneficial deviation in either substage leads to a beneficial deviation in the original designer stage.

Equilibrium in the Second Substage To analyze the weak designer equilibrium, we firstly study the second-substage equilibrium, i.e., how the designers set the biases when their first-stage strategies are fixed. We extend an approach from the previous works to our model, which considers the winning probability of a participant under contestant equilibrium as designer s decision

3This setting is justified by the common fact that the list of participants is often announced before the contest beginning, and modifying the judging criteria for contestants performance is relatively less costly than withdrawing the invitation to participants.

variable, instead of directly deciding the biases in the contest. We establish the validity of this approach in our model by Lemma 5. Although existing literature suggests that a designer s dominate strategy is to set a balancing bias which results in her participants having an equal winning probability of 1/2, we show that this claim does not unconditionally hold in our model in Theorem 7. Nonetheless, in Theorem 8 we prove that it still forms an second-substage equilibrium when all designers are using the balancing biases. Firstly we show that the winning probability is uniquely determined by the designers strategy profile.

Lemma 4 Given the strategy profile C, let λ be the unique equilibrium multiplier vector with respect to C. For any contest C and any contestant i SC, define ˆpi,C( λ) = αC,iλOPi,C αC,iλOPi,C +αC,OPi,C λi . Then, for any contestant equilib-

rium x, it holds that pi,C( x) = ˆpi,C( λ).

The following technical lemma shows that the designers are able to manipulate the equilibrium winning probabilities in their contests by adjusting the biases. This allows us to consider the winning probability in a contest as the designer s decision variable in the second substage.

Lemma 5 Suppose the set of all contests is partitioned as C = Cfix Cvar, such that every C Cfix s configuration is fixed, while every C Cvar only has fixed SC and RC, and the biases αC need to be assigned. Given any target of winning probabilities for these contests ( pi,C)C Cvar,i SC satisfying that pi,C (0, 1) and P i SC pi,C = 1, there exists an assignment of biases (αC,i)C Cvar,i SC, under which it holds for all C Cvar and i SC that ˆpi,C( λ) = pi,C, where λ is the EMV under C after assigning the biases to contests in Cvar. Moreover, such assignment of bias is unique when normalized such that α C,i + α C,OPi,C = 1.

Viewing ˆpi,C( λ) as the decision varaible is an effective approach, since it affects the contestants effort exertion more directly. Define QC( λ) = ˆpi,C( λ) ˆp OPi,C,C( λ) = ˆpi,C( λ)(1 ˆpi,C( λ)) for arbitrary i SC. Recall the definition of ˆxi,C( λ) in Section , for any contestant i with λi > 0, we can find that for any contest C A(i, C),

ˆxi,C( λ) = RCQC( λ)

λi . Observe that QC( λ) is maximized

when the bias is adjusted such that ˆpi,C( λ) = 1 2 for both contestants i SC, which we call the balancing bias. Consequently, using the balancing bias in C intuitively maximizes xi,C as long as the indirect influence on λi is limited. Previous works (Wang, Wu, and Xing 2023) also suggest that, when there are only two candidate contestants, i.e., n = 2, the optimal choice for a designer under any strategies of the other designers is to use the balancing bias. However, surprisingly, this is not a dominant strategy in the second substage of designers in our model.

Theorem 7 In some instances of IPM, setting the balancing bias may not be the best response strategy for a designer in the second substage of designers.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

Nonetheless, we can prove that, when all designers simultaneously use the balancing biases, it forms an equilibrium. Therefore, it is still reasonable to assume that all designers will use the balancing biases.

Theorem 8 In the IPM, for a strategy profile C, let λ be the unique equilibrium multiplier vector. If it holds that ˆpi,Cj( λ) = 1

2 for any contest Cj and any contestant i SCj, the biases of all contests in C form an equilibrium in the second substage of designers.

Equilibrium in the First Substage Assuming that all designers use the balancing biases in the second substage, with a little calculation, we can find that the contestants efforts are distributed in proportion to the prizes of contests. Consequently the first substage of designers is strategically equivalent to a variant of weighted congestion game (Bhawalkar, Gairing, and Roughgarden 2014), which has a pure Nash equilibrium. Therefore, we can guarantee the existence of WDE in the IPM.

Theorem 9 In the IPM, there exists at least one weak designer equilibrium.

Divisible Reward Model In this section, we concentrate on DPM, in which each designer is allowed to divide her budget to hold multiple contests. Compared to IPM, the strategy space of a designer under DPM is more complicated due to the involvement of multiple contests, but at the same time, it also become more flexible since the prize amount can be continuously adjusted across different contests to achieve some balanced state. Consequently, our result on DPM is two-fold: On the one hand, we show by an counterexample that Theorem 8 cannot be extended to DPM (Theorem 10), which means that using the balancing bias is sometimes no longer the best choice, even if all other designers do so. On the other hand, in contrast to IPM, we establish the existence of the designer equilibrium in DPM (Theorem 11 & 12), under a mild condition that maxi [n] Ti 1

2 P i [n] Ti. We first show that Theorem 8 cannot be extended to the DPM. That is, even when all designers use balancing bias simultaneously, it may not be an second-substage equilibrium.

Theorem 10 In some instances of DPM, there exists some strategy profile C such that:

Suppose λ is the EMV, it holds that ˆpi,C( λ) = 1

2, for any contest C j [m]Cj and any participant i SC, However, there is some designer who has the incentive to change the biases of her contests.

However, interestingly, if every designer distributes her budget of prize proportional to the total effort of each participant and sets the balancing bias in each contest, it will be a designer equilibrium.

Theorem 11 In the DPM, given designers strategy profile C, let λ be the EMV under C. If the following two conditions hold:

1. For any designer j and contestant i, it holds that P C A(i,Cj) RC = 2Bj Ti P

2. For any contest C j [m]Cj and any participant i SC, it holds that ˆpi,C( λ) = 1

then C is a designer equilibrium. Under the mild condition that the maximum effort of an individual contestant is not too large, we can show the existence of a designer equilibrium by constructing a strategy profile satisfying the condition of Theorem 11. Theorem 12 In the DPM, if maxi [n] Ti 1 2 P i [n] Ti, there exists a designer equilibrium.

It s worth noting that, the designer equilibrium C shown in Theorem 12 and its corresponding contestant equilibrium x exhibits a kind of balance: each contestant gets a utility proportional to her total effort, and each designer gets a utility proportional to her budget. Formally, it holds that

ucontestant j ( C; x) = Ti P i [n] Ti

udesigner j ( C; x) = Bj P j [m] Bj

for all contestants i [n] and all designers j [m].

Conclusion and Future Work This paper examines the competitive environment of multiple pairwise lottery contests, focusing on the equilibrium behavior of contest designers and contestants. Designers determine the prize amount, participants, and biases of their contests, while contestants allocate their effort across contests. We fully characterize the contestant equilibrium using the equilibrium multiplier vector. When designers can hold one or multiple contests, we demonstrate the designer equilibrium under mild conditions. We suggest two directions for future research. The first is to extend our results to the general Tullock model with a more complex contest success function. The second is to analyze the equilibrium strategy of contestants and designers when there are more than two participants in a contest.

Acknowledgments This research was partially supported by the National Natural Science Foundation of China (NSFC) (No.62172012), and Beijing Outstanding Young Scientist Program No.BJJWZYJH012019100020098, the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China No.22XNKJ07, and Major Innovation & Planning Interdisciplinary Platform for the Double-First Class Initiative, Renmin University of China.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)

References Azmat, G.; and M oller, M. 2009. Competition among contests. The RAND Journal of Economics, 40(4): 743 768. Azmat, G.; and M oller, M. 2018. The distribution of talent across contests. The economic journal, 128(609): 471 509. Bhawalkar, K.; Gairing, M.; and Roughgarden, T. 2014. Weighted congestion games: the price of anarchy, universal worst-case examples, and tightness. ACM Transactions on Economics and Computation (TEAC), 2(4): 1 23. Borel, E. 1921. La th eorie du jeu et les equations int egralesa noyau sym etrique. Comptes rendus de l Acad emie des Sciences, 173(1304-1308): 58. B uy ukboyacı, M. 2016. A Designer S Choice between Single-Prize and Parallel Tournaments. Economic Inquiry, 54(4): 1774 1789. Chowdhury, S. M.; and Sheremeta, R. M. 2011. Multiple equilibria in Tullock contests. Economics Letters, 112(2): 216 219. Clark, D. J.; and Riis, C. 1998. Contest success functions: an extension. Economic Theory, 201 204. Dasgupta, A.; and Nti, K. O. 1998. Designing an optimal contest. European Journal of Political Economy, 14(4): 587 603. Deng, X.; Gafni, Y.; Lavi, R.; Lin, T.; and Ling, H. 2023. From Monopoly to Competition: Optimal Contests Prevail. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37(5), 5608 5615. Deng, X.; Li, N.; Li, W.; and Qi, Q. 2022. Competition Among Parallel Contests. In Web and Internet Economics: 18th International Conference, WINE 2022, Troy, NY, USA, December 12 15, 2022, Proceedings, volume 13778, 357. Springer Nature. Di Palantino, D.; and Vojnovic, M. 2009. Crowdsourcing and all-pay auctions. In Proceedings of the 10th ACM conference on Electronic commerce, 119 128. Duffy, J.; and Matros, A. 2015. Stochastic asymmetric Blotto games: Some new results. Economics Letters, 134: 4 8. Epstein, G. S.; Mealem, Y.; and Nitzan, S. 2011. Political culture and discrimination in contests. Journal of Public Economics, 95(1-2): 88 93. Ewerhart, C. 2017. The lottery contest is a best-response potential game. Economics Letters, 155: 168 171. Franke, J.; Kanzow, C.; Leininger, W.; and Schwartz, A. 2013. Effort maximization in asymmetric contest games with heterogeneous contestants. Economic Theory, 52: 589 630. Friedman, L. 1958. Game-theory models in the allocation of advertising expenditures. Operations research, 6(5): 699 709. Fu, Q.; and Wu, Z. 2018. On the optimal design of lottery contests. Available at SSRN 3291874. Fu, Q.; Wu, Z.; and Zhu, Y. 2022. On equilibrium existence in generalized multi-prize nested lottery contests. Journal of Economic Theory, 200: 105377.

Ghosh, A.; and Goldberg, P. W. 2023. Best-Response Dynamics in Lottery Contests. ar Xiv preprint ar Xiv:2305.10881. Gross, O.; and Wagner, R. 1950. A continuous Colonel Blotto game. Technical report, Rand Project Air Force Santa Monica Ca. Juang, W.-T.; Sun, G.-Z.; and Yuan, K.-C. 2020. A model of parallel contests. International Journal of Game Theory, 49(2): 651 672. Kakutani, S. 1941. A generalization of Brouwer s fixed point theorem. K orpeo glu, E.; Korpeoglu, C. G.; and Hafalır, I. E. 2022. Parallel innovation contests. Operations Research, 70(3): 1506 1530. Kovenock, D.; and Roberson, B. 2021. Generalizations of the general lotto and colonel blotto games. Economic Theory, 71: 997 1032. Li, C.; Yan, X.; Deng, X.; Qi, Y.; Chu, W.; Song, L.; Qiao, J.; He, J.; and Xiong, J. 2019. Latent dirichlet allocation for internet price war. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33(01), 639 646. Li, X.; and Zheng, J. 2022. Pure strategy Nash Equilibrium in 2-contestant generalized lottery Colonel Blotto games. Journal of Mathematical Economics, 103: 102771. Macdonell, S. T.; and Mastronardi, N. 2015. Waging simple wars: a complete characterization of two-battlefield Blotto equilibria. Economic Theory, 58(1): 183 216. Nti, K. O. 1999. Rent-seeking with asymmetric valuations. Public Choice, 98(3-4): 415 430. Nti, K. O. 2004. Maximum efforts in contests with asymmetric valuations. European journal of political economy, 20(4): 1059 1066. Roberson, B. 2006. The colonel blotto game. Economic Theory, 29(1): 1 24. Robson, A. R.; et al. 2005. Multi-item contests. Segev, E. 2020. Crowdsourcing contests. European Journal of Operational Research, 281(2): 241 255. Skaperdas, S. 1996. Contest success functions. Economic theory, 7: 283 290. Stein, W. E. 2002. Asymmetric rent-seeking with more than two contestants. Public Choice, 113(3-4): 325 336. Tullock, G. 2001. Efficient rent seeking. Efficient rentseeking: Chronicle of an intellectual quagmire, 3 16. Wang, Z. 2010. The optimal accuracy level in asymmetric contests. The BE Journal of Theoretical Economics, 10(1). Wang, Z.; Wu, Z.; and Xing, Z. 2023. Multi-battle Contests with Competing Battlefields. Working Paper. Xu, J.; and Zhou, J. 2018. Discriminatory power and pure strategy Nash equilibrium in the lottery Blotto game. Operations Research Letters, 46(4): 424 429.

The Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)