# allpay_bidding_games_on_graphs__ffba8012.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

All-Pay Bidding Games on Graphs

Guy Avni,1 Rasmus Ibsen-Jensen,2 Josef Tkadlec1

1IST Austria 2Liverpool University

In this paper we introduce and study all-pay bidding games, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in the graph and assign budgets to the two players. Each turn, each player submits a sealed legal bid (non-negative and below their remaining budget), which is deducted from their budget and the highest bidder moves the token onto an adjacent vertex. The game ends once a sink is reached, and Player 1 pays Player 2 the outcome that is associated with the sink. The players attempt to maximize their expected outcome. Our games model settings where effort (of no inherent value) needs to be invested in an ongoing and stateful manner. On the negative side, we show that even in simple games on DAGs, optimal strategies may require a distribution over bids with inﬁnite support. A central quantity in bidding games is the ratio of the players budgets. On the positive side, we show a simple FPTAS for DAGs, that, for each budget ratio, outputs an approximation for the optimal strategy for that ratio. We also implement it, show that it performs well, and suggests interesting properties of these games. Then, given an outcome c, we show an algorithm for ﬁnding the necessary and sufﬁcient initial ratio for guaranteeing outcome c with probability 1 and a strategy ensuring such. Finally, while the general case has not previously been studied, solving the speciﬁc game in which Player 1 wins iff he wins the ﬁrst two auctions, has been long stated as an open question, which we solve.

1 Introduction Two-player graph games naturally model settings in which decision making is carried out dynamically. Vertices model the possible conﬁgurations and edges model actions. The game proceeds by placing a token on one of the vertices and allowing the players to repeatedly move it. One player models the protagonist for which we are interested in ﬁnding an optimal decision-making strategy, and the other player, the antagonist, models, in an adversarial manner, the other elements of the systems on which we have no control. We focus on quantitative reachability games (Everett 1955) in which the graph has a collection of sink vertices,

Copyright c 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

which we call the leaves, each of which is associated with a weight. The game is a zero-sum game; it ends once a leaf is reached and the weight of the leaf is Player 1 s reward and Player 2 s cost, thus Player 1 aims at maximizing the weight while Player 2 aims at minimizing it. A special case is qualitative reachability games in which each Player i has a target ti and Player i wins iff the game ends in ti. A graph game is equipped with a mechanism that determines how the token is moved; e.g., in turn-based games the players alternate turns in moving the token. Bidding is a mode of moving in which in each turn, we hold an auction to determine which player moves the token. Bidding qualitative-reachability games where studied in (Lazarus et al. 1996; 1999) largely with variants of ﬁrst-price auctions: in each turn both players simultaneously submit bids, where a bid is legal if it does not exceed the available budget, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding (named after David Richman), and to the bank in poorman bidding. The central quantity in these games is the ratio between the players budgets. Each vertex is shown to have a threshold ratio, which is a necessary and sufﬁcient initial ratio that guarantees winning the game. Moreover, optimal strategies are deterministic. We study, for the ﬁrst time, quantitative-reachability allpay bidding games, which are similar to the bidding rules above except that both players pay their bid to the bank. Formally, for i {1, 2}, suppose that Player i s budget is Bi Q>0 and that his bid is bi [0, Bi], then the higher bidder moves the token and Player i s budget is updated to Bi bi. Note that in variants of ﬁrst-price auctions, assuming the winner bids b, the loser s budget is the same for any bid in [0, b). In an all-pay auction, however, the higher the losing bid, the lower the loser s available budget is in the next round. Thus, intuitively, the loser would prefer to bid as close as possible to 0.

Example 1.1. Consider the qualitative reachability game that is depicted in Fig. 1, which we call win twice in a row or Wn R(2), for short. For convenience, ﬁx Player 2 s initial budget to be 1. The solution to the game using a ﬁrst-price auction is trivial: for example, with poorman bidding (in which the winner pays the bank), Player 1 wins iff his budget exceeds 2. Indeed, if his budget is 2 + ϵ, he bids 1 + ϵ/2

0 x + ϵ B2 = 1

2 wins 1 wins

Figure 1: On the left, the bidding game in which Player 1 wins iff he wins two biddings in a row. Assume initial budgets of B1 = 1 + x, for x (0.5, 1), and B2 = 1. A Player 1 strategy that guarantees value 0.5 uniformly bids {x, 1} in the ﬁrst bidding. Player 2 has two optimal counter strategies, and the table on the right depicts the budget in the second bidding in all cases.

in the ﬁrst bidding, moves the token to v1, and, since in ﬁrstprice auctions, the loser does not pay his bid, the budgets in the next round are 1 + ϵ/2 and 1, respectively. Player 1 again bids 1 + ϵ/2, wins the bidding, moves the token to t1, and wins the game. On the other hand, if Player 1 s budget is 2 ϵ, Player 2 can guarantee that the token reaches t2 by bidding 1 in both rounds. The solution to this game with all-pay bidding is much more complicated and was posed as an open question in (Lazarus et al. 1999), which we completely solve. Assuming Player 2 s budget is 1, it is easy to show that when Player 1 s initial budget is either greater than 2 or smaller than 1, there exist a deterministic winning strategy for one of the players. Also, for budgets in between, i.e, in (1, 2), it is not hard to see that optimal strategies require probabilistic choices, which is the source of the difﬁculty and an immediate difference from ﬁrst-price bidding rules. We characterize the value of the game, which is the optimal probability that Player 1 can guarantee winning, as a function of Player 1 s initial budget. In Theorem 5.1, we show that for n IN and x (1/(n+1), 1/n], the value is 1/(n+1) when Player 1 s initial budget is 1+x and Player 2 s initial budget is 1. Fig. 1 gives a ﬂavor of the the solution in the simplest interesting case of x (0.5, 1), where a Player 1 strategy that bids x and 1 each with probability 0.5 guarantees winning with probability 0.5.

Apart from the theoretical interest in all-pay bidding games, we argue that they are useful in practice, and that they address limitations of previously studied models. Allpay auctions are one of the most well-studied auction mechanisms (Michael R. Baye and de Vries 1996). Even though they are described in economic terms, they are often used to model settings in which the agents bids represent the amount of effort they invest in a task such as in rent seeking (Tullock 1980), patent races, e.g., (Baye and Hoppe 2003), or biological auctions (Chatterjee, Reiter, and Nowak 2012). As argued in (Konrad and Kovenock 2009), however, many decision-making settings, including the examples above, are not one-shot in nature, rather they develop dynamically. Dynamic all-pay auctions have been used to analyze, for example, political campaigning in the USA (Klumppa and

K.Polborn 2006), patent races (Harris and Vickers 1985), and (Klumppa and K.Polborn 2006) argue that they appropriately model sport competitions between two teams such as best of 7 in the NBA playoffs. An inherent difference between all-pay repeated auctions and all-pay bidding games is that our model assumes that the players effort has no or negligible inherent value and that it is bounded. The payoff is obtained only from the reward in the leaves. For example, a best of k sport competition between two sport teams can be modelled as an all-pay bidding game as follows. A team s budget models the sum of players strengths. A larger budget represents a fresher team with a deeper bench. Each bidding represents a match between the teams, and the team that bids higher wins the match. The teams only care about winning the tournament and the players strengths have no value after the tournament is over. The closest model in spirit is called Colonel Blotto games, which dates back to (Borel 1921), and has been extensively studied since. In these games, two colonels own armies and compete in n battleﬁelds. Colonel Blotto is a one-shot game: on the day of the battle, the two colonels need to decide how to distribute their armies between the n battleﬁelds, where each battleﬁeld entails a reward to its winner, and in each battleﬁeld, the outnumbering army wins. To the best of our knowledge, all-pay bidding games are the ﬁrst to incorporate a modelling of bounded resource with no value for the players, as in Colonel Blotto games, with a dynamic behavior, as in ongoing auctions. Graph games have been extensively used to model and reason about systems (Clarke et al. 2018) and multi-agent systems (Wooldridge et al. 2016). Bidding games naturally model systems in which the scheduler accepts payment in exchange for priority. Blockchain technology is one such system, where the miners accept payment and have freedom to decide the order of blocks they process based on the proposed transaction fees. Transaction fees are not refundable, thus all-pay bidding is the most appropriate modelling. Manipulating transaction fees is possible and can have dramatic consequences: such a manipulation was used to win a popular game on Ethereum called FOMO3d1. There is thus ample motivation for reasoning and verifying blockchain technology (Chatterjee, Goharshady, and Velner 2018). We show that all-pay bidding games exhibit an involved and interesting mathematical structure. As discussed in Example 1.1, while we show a complete characterization of the value function for the game Wn R(2), it is signiﬁcantly harder than the characterization with ﬁrst-price bidding. The situation becomes worse when we slightly complicate the game and require that Player 1 wins three times in a row, called Wn R(3), for short. We show that there are initial budgets for which an optimal strategy in Wn R(3) requires inﬁnite support. We turn to describe our positive results on general games. First, we study surely-winning in all-pay bidding games, i.e., winning with probability 1. We show a threshold behavior that is similar to ﬁrst-price bidding games: each vertex v in a qualitative all-pay bidding game has a surely-

1https://bit.ly/2wizwjj

winning threshold ratio, denoted STHR(v), such that if Player 1 s ratio exceeds STHR(v), he can guarantee winning the game with probability 1, and if Player 1 s ratio is less than STHR(v), Player 2 can guarantee winning with positive probability. Moreover, we show that surely-winning threshold ratios have the following structure: for every vertex v, we have STHR(v) = STHR(v ) + (1 STHR(v )/STHR(v+)), where v and v+ are the neighbors of v that, respectively, minimize and maximize STHR. This result has computation-complexity implications; namely, we show that in general, the decision-problem counterpart of ﬁnding surely-winning threshold ratios is in PSPACE using the existential theory of the reals (ETR, for short) (Canny 1988), and it is in linear time for DAGs. In the full version, we show that surely-winning threshold ratios can be irrational.

Example 1.2. Tic-tac-toe is a canonical graph game that is played on a DAG. First-price bidding Tic-tac-toe was discussed in a blog post2, where threshold budgets are shown to be surprisingly low: with Richman bidding, Player 1 can guarantee winning when his ratio exceeds 133/123 1.0183 (Develin and Payne 2010) and with poormanbidding, when it exceeds roughly 1.0184. We implement our algorithm and ﬁnd surely-winning threshold ratios in all-pay bidding tic-tac-toe: Player 1 surely wins when his initial ratio is greater than 51/31 1.65 (see Fig. 2). We point to several interesting phenomena. One explanation for the signiﬁcant gap between the thresholds in all-pay and ﬁrst-price bidding is that, unlike Richman and poorman bidding, in the range (31/51, 51/31) neither player surely wins. Second, the threshold ratio for the relaxed Player 1 goal of surely not-losing equals the surelywinning threshold ratio. This is not always the case; e.g., from the conﬁguration with a single O in the middle left position, Player 1 requires a budget of 31/16 for surely winning and 25/13 for surely not-losing. Third, we ﬁnd it surprising that when Player 2 wins the ﬁrst bidding, it is preferable to set an O in one of the corners (as in conﬁguration c2) rather than in the center.

4/3 .= 1.33 3/2 = 1.5 2

51/31 .= 1.65 31/16 .= 1.94 8/3 .= 2.67

5/3 .= 1.67 3

Figure 2: Surely-winning thresholds in tic-tac-toe. For example, the surely-winning threshold budget in c4 is 3 since in order to win the game, Player 1 must win three biddings in a row.

2https://bit.ly/2KUong4

Finally, we devise an FPTAS for the problem of ﬁnding values in DAGs; namely, given a bidding game G that is played on a DAG, an initial vertex, and an ϵ > 0, we ﬁnd, in time polynomial in the size of G and 1/ϵ, an upperand lower-bound on the expected payoff that Player 1 can guarantee with every initial ratio of the form ϵ k. The idea is to discretize the budgets and bids and, using a bottomup approach, repeatedly solve ﬁnite-action zero-sum games. The algorithm gives theoretical bounds on the approximation. It is a simple algorithm that we have implemented and experimented with. Our experiments show that the difference between upperand lower-bounds is small, thus we conclude that the algorithm supplies a good approximation to the value function. The experiments verify our theoretical ﬁndings. In addition, they hint at interesting behavior of all-pay bidding games, which we do not yet understand and believe encourages a further study of this model. Due to lack of space, most proofs appear in the full version (Avni, Ibsen-Jensen, and Tkadlec 2020).

Related work Colonel Blotto games (Borel 1921) have been extensively studied; a handful of papers include (Bellman 1969; Blackett 1954; Hart 2008; Shubik and Weber 1981). They have mostly been studied in the discrete case, i.e., the armies are given as individual soldiers, but, closer to our model, also in the continuous case (see (Roberson 2006) and references therein). The most well-studied objective is maximizing the expected payoff, though recently (Behnezhad et al. 2019) study the objective of maximizing the probability of winning at least k battleﬁelds, which is closer to our model. All-pay bidding games were mentioned brieﬂy in (Lazarus et al. 1999), where it was observed that optimal strategies require probabilistic choices. To the best of our knowledge, all-pay bidding games (Menz, Wang, and Xie 2015) were studied only with discrete-bidding, which signiﬁcantly simpliﬁes the model, and in the Richman setting; namely, both players pay their bids to the other player. First-price bidding games have been well-studied and exhibit interesting mathematical properties. Threshold ratios in reachability Richman-bidding games, and only with these bidding rules, equal values in random-turn based games (Peres et al. 2009), which are stochastic games in which in each round, the player who moves is chosen according to a coin toss. This probabilistic connection was extended and generalized to inﬁnite-duration bidding games with Richman- (Avni, Henzinger, and Chonev 2019), poorman- (Avni, Henzinger, and Ibsen-Jensen 2018), and even taxman-bidding (Avni, Henzinger, and ˇZikeli c 2019), which generalizes both bidding rules. Other orthogonal extensions of the basic model include non-zero-sum bidding games (Meir, Kalai, and Tennenholtz 2018) and discretebidding games that restrict the granularity of the bids (Develin and Payne 2010; Aghajohari, Avni, and Henzinger 2019). There are a number of shallow similarities between allpay games and concurrent stochastic games (Shapley 1953). A key difference between the models is that in all-pay bidding games, the (upper and lower) value depends on the ini-

tial ratio, whereas a stochastic game has one value. We list examples of similarities. In both models players pick actions simultaneously in each turn, and strategies require randomness and inﬁnite memory though in Everett recursive games (Everett 1955), which are closest to our model, only ﬁnite memory is required and in more general stochastic games, the inﬁnite memory requirement comes from remembering the history e.g. (Mertens and Neyman 1981) whereas in allpay bidding games inﬁnite support is already required in the game win 3 times in a row (which has histories of length at most 3). Also, computing the value in stochastic games is in PSPACE using ETR (Etessami et al. 2008), it is in P for DAGs, and there are better results for solving the guaranteed-winning case (Chatterjee and Ibsen-Jensen 2015).

2 Preliminaries

A reachability all-pay bidding game is V, E, L, w , where V is a ﬁnite set of vertices, E V V is a set of directed edges, L V is a set of leaves with no outgoing edges, and w : L Q assigns unique weights to leaves, i.e., for l, l L, we have w(l) = w(l ). We require that every vertex in V \ L has a path to at least two different leaves. A special case is qualitative games, where there are exactly two leaves with weights in {0, 1}. We say that a game is played on a DAG when there are no cycles in the graph. For v V , we denote the neighbors of v as N(v) = {u V : v, u E}. A strategy is a recipe for how to play a game. It is a function that, given a ﬁnite history of the game, prescribes to a player which action to take, where we deﬁne these two notions below. A history in a bidding game is π = v1, b1 1, b2 1 , . . . , vk, b1 k, b2 k , vk+1 (V IR IR) V , where for 1 j k + 1, the token is placed on vertex vj at round j and Player i s bid is bi j, for i {1, 2}. Let BI i be the initial budget of Player i. Player i s budget following π is Bi(π) = BI i

1 j k bi j. A play π that ends in a leaf l L is associated with the payoff w(l). Consider a history π that ends in v V \ L. The set of legal actions following π, denoted A(π), consists of pairs b, u , where b Bi(π) is a bid that does not exceed the available budget and u N(v) is a vertex to move to upon winning. A mixed strategy is a function that takes π and assigns a probability distribution over A(π). The support of a strategy f is supp(f, π) = { b, u : f(π)( v, u ) > 0}. We assume WLog. that each bid is associated with one vertex to proceed to upon winning, thus if b, v , b, v supp(f, π), then v = v . We say that f is pure if, intuitively, it does not make probabilistic choices, thus for every history π, we have |supp(f, π)| = 1.

Deﬁnition 2.1 (Budget Ratio). Let B1, B2 IR be initial budgets for the two players. Player 1 s ratio is B1/B2.3

Let G be an all-pay bidding game. An initial vertex v0, an initial ratio r IR, and two strategies f1 and f2 for the two players give rise to a probability D(v0, r, f1, f2) over

3We ﬁnd this deﬁnition more convenient than B1/(B1 + B2) which is used in previous papers on bidding games.

plays, which is deﬁned inductively as follows. The probability of the play of length 0 is 1. Let π = π v, b1, b2 , u, where π ends in a vertex v. Then, we deﬁne Pr[π] = Pr[π ] f1(π)(b1) f2(π)(b2). Moreover, for i {1, 2}, assuming Player i chooses the successor vertex vi, i.e., bi, vi supp(fi, π ), then u = v1 when b1 b2 and otherwise u = v2. That is, we resolve ties by giving Player 1 the advantage. This choice is arbitrary and does not affect most of our results, and the only affect is discussed in Remark 5.1. Deﬁnition 2.2 (Game Values). The lower value in an allpay game G w.r.t. an initial vertex v0, and an initial ratio r is val (G, v0, r) = supf infg

π D(v0,r,f,g) Pr[π] pay(π). The upper value, denoted val (G, v0, r) is deﬁned dually. It is always the case that val (G, v0, r) val (G, v0, r), and when val (G, v0, r) = val (G, v0, r), we say that the value exists and we denote it by val(G, v0, r).

3 Surely-Winning Thresholds In this section we study the existence and computation of a necessary and sufﬁcient initial budget for Player 1 that guarantees surely winning, namely winning with probability 1. We focus on qualitative games in which each player has a target leaf. Note that the corresponding question in quantitative games is the existence of a budget that sufﬁces to surely guarantee a payoff of some c IR, which reduces to the the surely-winning question on qualitative games by setting Player 1 s target to be the leaves with weight at least c. We deﬁne surely-winning threshold budgets formally as follows. Deﬁnition 3.1 (Surely-Winning Thresholds). Consider a qualitative game G and a vertex v in G. The surely-winning threshold at v, denoted STHR(v), is a budget ratio such that: If Player 1 s ratio exceeds STHR(v), he has a strategy that guarantees winning with probability 1. If Player 1 s ratio is less than STHR(v), Player 2 has a strategy that guarantees winning with positive probability. To show existence of surely-winning threshold ratios, we deﬁne threshold functions, show their existence, and show that they coincide with surely-winning threshold ratios. Deﬁnition 3.2 (Threshold functions). Consider a qualitative game G = V, E, t1, t2 . Let T : V IR 0 be a function. For v V \ {t1, t2}, let v , v+ N(V ) be such that T(v ) T(u) T(v+), for every u N(v). We call T a threshold function if

0 if v = t1 if v = t2 T(v ) + 1 T(v )/T(v+) otherwise.4

We start by making observations on surely-winning threshold ratios and threshold functions. The proof of the following lemma can be found in the full version. Lemma 3.1. Consider a qualitative game G = V, E, t1, t2 , and let T be a threshold function.

4We deﬁne 1/ = 0 and c < , for every c IR.

For v V , if Player 1 s initial ratio exceeds STHR(v), then he has a pure strategy that guarantees winning. For v V \ {t1, t2}, we have STHR(v) 1. We have T(v ) T(v) T(v+) and the inequalities are strict when T(v ) = T(v+).

We ﬁrst show that threshold functions coincide with surely-winning threshold ratios, and then show their existence.

Lemma 3.2. Consider a qualitative game G = V, E, t1, t2 and let T be a threshold function for G. Then, for every vertex v V , we have T(v) STHR(v); namely, Player 1 surely wins from v when his budget exceeds T(v).

Proof. We claim that if Player 1 s ratio is T(v)+ϵ, for ϵ > 0, he can surely-win the game. For t1 and t2, the claim is trivial and vacuous, respectively. We provide a strategy f1 for Player 1 that guarantees that in at most n = |V | steps, either Player 1 has won or he is at some node u V with relative budget T(u) + ϵ + dϵ, where dϵ > 0 is a small ﬁxed positive number. By repeatedly applying this strategy, either Player 1 at some point wins directly, or he accumulates relative budget n and then he can force a win in n steps by simply bidding 1 in each round. Suppose the token is placed on vertex v V \{t1, t2} following 0 i n biddings, let v , v+ N(v) be neighbors of v that achieve the minimal and maximal value of T, respectively. For convenience, set x = T(v ), y = T(v+), and δ = ϵ2. Player 1 bids 1 x/y + δk+1 i. We ﬁrst disregard the supplementary δk+1 i. When Player 1 wins, we consider the worst case of Player 2 bidding 0, thus Player 1 s normalized budget is greater than T(v) (1 x/y) / 1 (1 x/y) = T(v ). On the other hand, when Player 1 loses, Player 2 bids at least as much as Player 1, and Player 1 s normalized budget is greater than T(v) (1 x/y) / 1 2(1 x/y) = T(v+). Upon winning a bidding, Player 1 moves to a neighbor u N(v) with T(u) = T(v ), and when losing, the worst case is when Player 2 moves to a vertex u with T(u) = T(v+). The claim above shows that in both cases Player 1 s budget exceeds T(u). Since T(t2) = , we have established that the strategy guarantees not losing. In the full version, we deﬁne Player 1 s moves precisely, and show how Player 1 uses the surplus δ to guarantee winning.

To obtain the converse, in the full version, we show a strategy for Player 2 that wins with positive probability. We identify an upper bound β in each vertex such that a Player 1 bid that exceeds β exhausts too much of his budget. Then, Player 2 bids 0 with probability 0.5 and the rest of the probability mass is distributed uniformly in [0, β]. This deﬁnition intuitively allows us to reverse the quantiﬁcation and assume Player 1 reveals his strategy before Player 2; that is, when Player 1 bids at least β, we consider the case that Player 2 bids 0, and when Player 1 bids less than β, we consider the case where Player 2 slightly overbids Player 1. Both occur with positive probability.

Lemma 3.3. Consider a qualitative game G = V, E, t1, t2 and let T be a threshold function for G. Then, for every vertex v V , we have T(v) STHR(v); namely, Player 2 wins with positive probability from v when Player 1 s budget is less than T(v). Finally, in the full version, we show existence of threshold functions. We ﬁrst show existence in DAGs, which is a simple backwards-induction argument that we have implemented (see Example 1.2). To obtain existence in a general game G, we ﬁnd threshold functions in games on DAGs of the form Gn, for n IN, in which Player 1 is restricted to win in at most n steps. We tend n to inﬁnity and show that the limit of the threshold functions in the games is a threshold function in G. Lemma 3.4. Every qualitative reachability bidding game has a threshold function. The characterization of surely-winning threshold ratios by means of threshold functions (Lemmas 3.2 and 3.3) have computation complexity consequences on the problem of ﬁnding surely-winning threshold ratios. In DAGs, ﬁnding threshold functions is done in linear time. In general graphs, the characterization implies a reduction to the existential theory of the reals (ETR, for short) by phrasing the constraints in Deﬁnition 3.2 as an input to ETR. It is known that ETR is in PSPACE (Canny 1988). Combining the lemmas above, we have the following. Theorem 3.5. Surely-winning threshold ratios exist in every qualitative reachability game and coincide with threshold functions, and can be irrational. Moreover, given a vertex v and a value c Q, deciding whether STHR(v) c is in PSPACE for general graphs and can be solved in linear time for games on DAGs.

4 Finding Approximated Values In this section, we focus on games on DAGs. The algorithm that we construct is based on a discretization of the budgets; namely, we restrict the granularity of the bids and require Player 1 to bid multiples of some ϵ > 0, similar in spirit to discrete-bidding games (Develin and Payne 2010). We ﬁrst relate the approximated value with the value in G with no restriction on the bids. Then, in Section 6, we experiment with an implementation of the algorithm and show interesting behavior of all-pay bidding games. We deﬁne the approximate value as follows. Deﬁnition 4.1 (Approximate Value Function). Let G be a game on a DAG and ϵ > 0. Let valϵ be the approximatevalue function in G when Player 1 is restricted to choose bids in {ϵ k : k IN} and Player 2 wins ties. Our algorithm is based on the following theorem. Theorem 4.1. Consider a game on a DAG G where each leaf is labeled with a reward. Let v be a vertex in G, B1 IR be an initial budget for Player 1, d(G) be the longest path from a vertex to a leaf in G, and ϵ > 0. Then, we have val(v, B1) valϵ(v, B1 + d(G) ϵ). Theorem 4.1 gives rise to Algorithm 3 that ﬁnds valϵ(B1), for every B1 that is a multiple of ϵ. Note that assuming Player 1 bids only multiples of ϵ, we can assume that

Approx-Values(v, ϵ) if N(v) = then return weight(v) u N(v) call APPROX-VALUES(u, ϵ) for B1 = k ϵ s.t. 0 B1 STHR(v) do // Construct a two-player ﬁnite-action matrix game. A1 = {b1 = i ϵ s.t. 0 b1 B1} A2 = {b2 = j ϵ s.t. 0 b2 1} for b1 A1, b2 A2 do // Player 1 s normalized new budget. B 1 = (B1 b1)/(1 b2) ϵ if b1 > b2 then pay(b1, b2) = maxu N(v) valϵ(u, B 1) else pay(b1, b2) = minu N(v) valϵ(u, B 1) valϵ(v, B1) = SOLVE(A1, A2, pay) return valϵ

Figure 3: An FPTAS for ﬁnding upperand lower-bounds on the values for every initial budget ratio.

Player 2 also bids multiples of ϵ. The algorithm constructs a two-player zero-sum matrix game, which is A1, A2, pay , where, for i {1, 2}, Ai is a ﬁnite set of actions for Player i, and, given ai Ai, the function pay(a1, a2) is the payoff of the game. A solution to the game is the optimal payoff that Player 1 can guarantee with a mixed strategy, and it is found using linear programming. Let STHR(v) denote the threshold budget with which Player 1 can guarantee the highest reward, then valϵ(B1) equals the highest reward, for B1 > STHR(v). To compute STHR(v), we use the lineartime algorithm in the previous section.

5 Win n in a Row Games

In this section we study a simple fragment of qualitative games.

Deﬁnition 5.1 (Win n in a Row Games). For n IN, let Wn R(n) denote the qualitative game in which Player 1 needs to win n biddings in a row and otherwise Player 2 wins. For example, see a depiction of Wn R(2) in Fig. 1.

We start with a positive results and completely solve Wn R(2). Then, we show that optimal strategies require inﬁnite support already in Wn R(3).

A solution to win twice in a row

We start by solving an open question that was posed in (Lazarus et al. 1999) and characterize the value as a function the budget ratio in the win twice in a row game Wn R(2) (see a depiction of the game in Fig. 1).

Theorem 5.1. Consider the all-pay bidding game Wn R(2) in which Player 1 needs to win twice and Player 2 needs to win twice. The value exists for every pair of initial budgets. Moreover, suppose the initial budgets are B1 for Player 1 and 1 for Player 2. Then, if B1 > 2, the value is 1, if B1 < 1, the value is 0, and if B1 (1 + 1 n+1, 1 + 1

n], for n IN, then the value is 1 n+1.

Proof. The cases when B1 > 2 and B1 < 1 are easy. Let 2 n IN such that B1 = 1+1/n+ϵ, where ϵ is such that B1 < 1 + 1/(n 1). We claim that the value of Wn R(2) with initial budgets B1 and B2 = 1 is 1/n. Consider the Player 1 strategy that choses a bid in {k/n : 1 k n} uniformly at random. We claim that no matter how Player 2 bids, one of the choices wins, thus the strategy guarantees winning with probability at least 1/n. Let b2 be a Player 2 bid and let k IN be such that b2 [k/n, (k + 1)/n]. Consider the case where Player 1 bids b1 = (k + 1)/n and wins the ﬁrst bidding. Player 1 s normalized budget in the second bidding is B 1 = B1 b1

1 b2 n+1/n+ϵ (k+1)/n

1 (n k)/n > 1, thus Player 1 wins the second bidding as well. Next, we show that Player 1 s strategy is optimal by showing a Player 2 strategy that guarantees winning with probability at least (n 1)/n. Let ϵ > ϵ such that (n 1) ϵ < 1, which exists since B1 < 1 + 1/(n 1). Player 2 chooses a bid uniformly at random in {k (1/n+ϵ ) : 0 k n 1}. Suppose Player 1 bids b1, and we claim that the bid wins against at most one choice of Player 2. Let b2 be a Player 2 bid. When b2 > b1, Player 2 wins immediately. A simple calculation reveals that when b1 b2 > 1/n + ϵ, then Player 1 s normalized budget in the second bidding is less than 1, thus he loses. It is not hard to see that there are n 1 choices for Player 2 that guarantee winning.

Remark 5.1. Note that the tie-breaking mechanism affects the winner at the end-points of the intervals. For example, if we would have let Player 2 win ties, then the intervals would have changed to [1 + 1 n+1, 1 + 1

Inﬁnite support is required in Wn R(3) We continue to show a negative result already in Wn R(3): there is an initial Player 1 budget for which his optimal strategy requires inﬁnite support, which comes as a contrast to the optimal strategies we develop for Wn R(2), which all have ﬁnite support.

Inﬁnite support is required. The following lemma, whose proof can be found in the full version, shows a condition for the in-optimality of a strategy. Lemma 5.2. Consider a Player 1 strategy f in Wn R(n), for some n IN, that has ﬁnite support b1 > . . . > bm in the ﬁrst bidding. If there is 1 i < m, 1 k i, and bi > x > bi+1 with out(bk, bi) > out(bk, x) and out(x, x) = out(bi, bi), then f is not optimal. Next, we use Lemma 5.2 to show that any strategy with ﬁnite support is not optimal. Theorem 5.3. Consider the game Wn R(3) in which Player 1 needs to win three biddings and Player 2 needs to win once. Suppose the initial budgets are 1.25 for Player 1 and 1 for Player 2. Then, an optimal strategy for Player 1 requires inﬁnite support in the ﬁrst bidding.

6 Experiments We have implemented Algorithm 3 and experiment by running it on qualitative games that are called a race in (Harris and Vickers 1985).

1/3 1/2 2/3 1 1.5 2 3 0.0

Budget ratio, log-scale

Figure 4: Upperand lower-bounds on the values of the games G(1, 3), G(1, 2), G(2, 2), G(2, 1), and G(3, 1).

Deﬁnition 6.1 (Race Games). For n, m IN, let G(n, m) be the qualitative game that consists of at most n + m 1 biddings in which Player 1 wins if he wins n biddings and Player 2 wins if he wins m biddings. Speciﬁcally, we have Wn R(n) = G(n, 1).

The algorithm is implemented in Python and it is run on a personal computer. In our experiments, we choose ϵ = 0.01. In terms of scalability, the running time for for solving the game G(5, 5) is at most 10 minutes. Solutions to smaller games are in the order of seconds to several minutes. Figure 4 depicts some values for ﬁve games as output by the implementation. We make several observations. First, close plots represent the upperand lower-bounds of a game. We ﬁnd it surprising that the difference between the two approximations is very small, and conclude that the output of the algorithm is a good approximation of the real values of the games. Second, the plot of G(2, 1) = Wn R(2) (depicted in red), is an experimental afﬁrmation of Theorem 5.1; namely, the step-wise behavior and the values that are observed in theory are clearly visible in the plot. Third, while a step-wise behavior can be seen for high initial budgets in G(3, 1) (depicted in purple), for lower initial budgets, the behavior seems more involved and possibly continuous. In Theorem 5.3, we show that optimal strategies for initial budgets in this region require inﬁnite support, and the plot afﬁrms the more involved behavior of the value function that is predicted by the theorem. Continuity is more evident in more elaborate games whose values are depicted in Figure 5. Both plots give rise to several interesting open questions, which we elaborate on in the next section.

7 Discussion We study, for the ﬁrst time, all-pay bidding games on graphs. Unlike bidding games that use variants of ﬁrst-price auctions, all-pay bidding games appropriately model decisionmaking settings in which bounded effort with no inherent value needs to be invested dynamically. While our negative results show that all-pay bidding games are signiﬁcantly harder than ﬁrst-price bidding games, our results are mostly

3/5 5/3 1/2 3/4 1 4/3 2 0.0

Budget ratio, log-scale

Figure 5: Upperand lower-bounds on the values of the games G(3, 2), G(3, 3), and G(2, 3).

positive. We are able to regain the threshold-ratio phenomena from ﬁrst-price bidding games by considering surelywinning threshold ratios, and our implementation for games on DAGs solves non-trivial games such as tic-tac-toe. We show a simple FPTAS that ﬁnds upperand lower-bounds on the values for every initial budget ratio, which we have implemented and show that it performs very well. We leave several open questions. The basic question on games, which we leave open, is showing the existence of a value with respect to every initial ratio in every game. We were able to show existence in Wn R(2), and Fig. 5 hints the value exists in more complicated games. Also, while we identify the value function in Wn R(2), we leave open the problem of a better understanding of this function in general. For example, while for Wn R(2) we show that it is a stepwise function, observing Fig. 5 it seems safe to guess that the function can be continuous. Finally, characterizing the function completely, similar to our solution of Wn R(2), in more involved games, is an interesting and challenging open problem.

8 Acknowledments

This research was supported by the Austrian Science Fund (FWF) under grants S11402-N23 (Ri SE/SHi NE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship).

Aghajohari, M.; Avni, G.; and Henzinger, T. A. 2019. Determinacy in discrete-bidding inﬁnite-duration games. In Proc. 30th CONCUR, volume 140 of LIPIcs, 20:1 20:17. Avni, G.; Henzinger, T. A.; and Chonev, V. 2019. Inﬁniteduration bidding games. J. ACM 66(4):31:1 31:29. Avni, G.; Henzinger, T. A.; and Ibsen-Jensen, R. 2018. Inﬁnite-duration poorman-bidding games. In Proc. 14th WINE, volume 11316 of LNCS, 21 36. Springer.

Avni, G.; Henzinger, T. A.; and ˇZikeli c, D. 2019. Bidding

mechanisms in graph games. In In Proc. 44th MFCS, volume 138 of LIPIcs, 11:1 11:13. Avni, G.; Ibsen-Jensen, R.; and Tkadlec, J. 2020. All-pay bidding games on graphs. Co RR abs/1911.08360. https: //arxiv.org/abs/1911.08360. Baye, M. R., and Hoppe, H. C. 2003. The strategic equivalence of rent-seeking, innovation, and patent-race games. Games and Economic Behavior 44(2):217 226. Behnezhad, S.; Blum, A.; Derakhshan, M.; Hajiaghayi, M. T.; Papadimitriou, C. H.; and Seddighin, S. 2019. Optimal strategies of blotto games: Beyond convexity. In Proc. the 20th EC, 597 616. Bellman, R. 1969. On colonel blotto and analogous games. SIAM Rev. 11(1):66 68. Blackett, D. W. 1954. Some blotto games. NRL 1(1):55 60. Borel, E. 1921. La th eorie du jeu les equations int egrales a noyau sym etrique. Comptes Rendus de l Acad emie 173(1304 1308):58. Canny, J. F. 1988. Some algebraic and geometric computations in PSPACE. In Proc. 20th STOC, 460 467. Chatterjee, K., and Ibsen-Jensen, R. 2015. The value 1 problem under ﬁnite-memory strategies for concurrent meanpayoff games. In Proc. 26th SODA, 1018 1029. Chatterjee, K.; Goharshady, A. K.; and Velner, Y. 2018. Quantitative analysis of smart contracts. In Proc. 27th ESOP, 739 767. Chatterjee, K.; Reiter, J. G.; and Nowak, M. A. 2012. Evolutionary dynamics of biological auctions. Theoretical Population Biology 81(1):69 80. Clarke, E. M.; Henzinger, T. A.; Veith, H.; and Bloem, R., eds. 2018. Handbook of Model Checking. Springer. Develin, M., and Payne, S. 2010. Discrete bidding games. The Electronic Journal of Combinatorics 17(1):R85. Etessami, K.; Kwiatkowska, M. Z.; Vardi, M. Y.; and Yannakakis, M. 2008. Multi-objective model checking of markov decision processes. LMCS 4(4). Everett, H. 1955. Recursive games. Annals of Mathematics Studies 3(39):47 78. Harris, C., and Vickers, J. 1985. Perfect equilibrium in a model of a race. The Review of Economic Studies 52(2):193 209. Hart, S. 2008. Discrete colonel blotto and general lotto games. International Journal of Game Theory 36(3):441 460. Klumppa, T., and K.Polborn, M. 2006. Primaries and the new hampshire effect. Journal of Public Economics 90(6 7):1073 1114. Konrad, K. A., and Kovenock, D. 2009. Multi-battle contests. Games and Economic Behavior 66(1):256 274. Lazarus, A. J.; Loeb, D. E.; Propp, J. G.; and Ullman, D. 1996. Richman games. Games of No Chance 29:439 449. Lazarus, A. J.; Loeb, D. E.; Propp, J. G.; Stromquist, W. R.; and Ullman, D. H. 1999. Combinatorial games under auction play. Games and Economic Behavior 27(2):229 264.

Meir, R.; Kalai, G.; and Tennenholtz, M. 2018. Bidding games and efﬁcient allocations. Games and Economic Behavior. Menz, M.; Wang, J.; and Xie, J. 2015. Discrete all-pay bidding games. Co RR abs/1504.02799. Mertens, J., and Neyman, A. 1981. Stochastic games. International Journal of Game Theory 10(2):53 66. Michael R. Baye, D. K., and de Vries, C. G. 1996. The allpay auction with complete information. Economic Theory 8(2):291 305. Peres, Y.; Schramm, O.; Shefﬁeld, S.; and Wilson, D. B. 2009. Tug-of-war and the inﬁnity laplacian. J. Amer. Math. Soc. 22:167 210. Roberson, B. 2006. The colonel blotto game. Economic Theory 29(1):1 24. Shapley, L. S. 1953. Stochastic games. Proceedings of the National Academy of Sciences 39(10):1095 1100. Shubik, M., and Weber, R. J. 1981. Systems defense games: Colonel blotto, command and control. NRL 28(2):281 287. Tullock, G. 1980. Toward a Theory of the Rent Seeking Society. College Station: Texas A&M Press. chapter Efﬁcient rent seeking, 97 112. Wooldridge, M. J.; Gutierrez, J.; Harrenstein, P.; Marchioni, E.; Perelli, G.; and Toumi, A. 2016. Rational veriﬁcation: From model checking to equilibrium checking. In Proc. of the 30th AAAI, 4184 4191.