Computing Threshold Budgets in Discrete-Bidding Games_2

2025-04-27 0 0 590.12KB 45 页 10玖币

侵权投诉

1/ 45 2025:5

Computing Threshold

Budgets in

Discrete-Bidding Games

Received Jan 4, 2024

Revised Sep 27, 2024

Accepted Nov 23, 2024

Published Jan 22, 2025

Key words and phrases

Discrete bidding games, Richman

games, parity games, reachability

games

Guy Avnia

Suman Sadhukhana

aUniversity of Haifa, Israel

ABSTRACT. In a two-player zero-sum graph game, the players move a token throughout a

graph to produce an inﬁnite play, which determines the winner of the game. Bidding games are

graph games in which in each turn, an auction (bidding) determines which player moves the

token: the players have budgets, and in each turn, both players simultaneously submit bids

that do not exceed their available budgets, the higher bidder moves the token, and pays the bid

to the lower bidder (called Richman bidding). We focus on discrete-bidding games, in which,

motivated by practical applications, the granularity of the players’ bids is restricted, e.g., bids

must be given in cents.

A central quantity in bidding games is threshold budgets: a necessary and sucient initial

budget for winning the game. Previously, thresholds were shown to exist in parity games,

but their structure was only understood for reachability games. Moreover, the previously-

known algorithms have a worst-case exponential running time for both reachability and parity

objectives, and output strategies that use exponential memory. We describe two algorithms for

ﬁnding threshold budgets in parity discrete-bidding games. The ﬁrst is a ﬁxed-point algorithm.

It reveals, for the ﬁrst time, the structure of threshold budgets in parity discrete-bidding games.

Based on this structure, we develop a second algorithm that shows that the problem of ﬁnding

threshold budgets is in NP and coNP for both reachability and parity objectives. Moreover, our

algorithm constructs strategies that use only linear memory.

This research was supported in part by ISF grant no. 1679/21. A preliminary version of this article appeared at FSTTCS 22

[14].

Cite as Guy Avni, Suman Sadhukhan. Computing Threshold Budgets in

Discrete-Bidding Games. TheoretiCS, Volume 4 (2025), Article 5, 1-45.

https://theoretics.episciences.org

DOI 10.46298/theoretics.25.5

2/ 45 G. Avni, S. Sadhukhan

1. Introduction

Two-player zero-sum graph games are a central class of games. A graph game proceeds as

follows. A token is placed on a vertex and the players move it throughout the graph to produce

an inﬁnite play, which determines the winner of the game. The central algorithmic problem in

graph games is to identify the winner and to construct winning strategies. One key application of

graph games is reactive synthesis [29], in which the goal is to synthesize a reactive system, namely

a policy for interacting with an adversarial environment, that satisﬁes a given speciﬁcation no

matter how the environment behaves.

Two orthogonal classiﬁcations of graphs games are according to the mode of moving

the token and according to the players’ objectives. For the latter, we focus on two canonical

qualitative objectives. In reachability games, there is a set of target vertices and Player 1wins if

a target vertex is reached. In parity games, each vertex is labeled with a parity index and an

inﬁnite path is winning for Player 1i the highest parity index that is visited inﬁnitely often is

odd. The simplest and most studied mode of moving is turn-based: the players alternate turns

in moving the token. We note that reactive synthesis reduces to solving a turn-based parity

game. Examples of other modes of moving are concurrent and probabilistic moves (see [4]).

We study bidding graph games [25,24], which apply the following mode of moving: both

players have budgets, and in each turn, an auction (bidding) determines which player moves

the token. Concretely, we focus on Richman bidding (named after David Richman): in each turn,

both players simultaneously submit bids that do not exceed their available budget, the higher

bidder moves the token, and pays his bid to the lower bidder. Note that the sum of budgets

stays constant throughout the game. We distinguish between continuous- and discrete-bidding,

where in the latter, the granularity of the players’ bids is restricted. The central questions in

bidding games revolve around the threshold budgets, namely a necessary and sucient initial

budget for winning the game.

Continuous-bidding games. This paper focuses on discrete-bidding. We brieﬂy survey the

relevant literature on continuous-bidding games, which have been more extensively studied

that their discrete-bidding counterparts. Bidding games were introduced in [25,24]. The

objective that was considered is a variant of reachability, which we call double reachability:

each player has a target and a player wins if his target is reached (unlike reachability games in

which Player 2’s goal is to prevent Player 1from reaching his target). The targets are assumed

to be distinct, thus the game is zero sum. Note that apriori, it is possible that a play results in

a tie if no target is visited. It was shown, however, that in continuous-bidding games, a target

is necessarily reached, thus double-reachability games essentially coincide with reachability

games continuous-bidding games.

3/ 45 Computing Threshold Budgets in Discrete-Bidding Games

Threshold budgets were shown to exist; namely, each vertex

𝑣

has a value

Th(𝑣)

such that

if Player 1’s budget is strictly greater than

Th(𝑣)

, he wins the game from

𝑣

, and if his budget

is strictly less than

Th(𝑣)

, Player 2wins the game. Moreover, it was shown that the threshold

function

is the unique function that satisﬁes the following property, which we call the average

property. Suppose that the sum of budgets is 1, and

𝑡𝑖

is Player

𝑖

’s target, for

𝑖∈ {

}

. Then,

assigns a value in

[

]

to each vertex such that at the “end points”, we have

Th(𝑡1)=

0and

Th(𝑡2)=1, and the threshold at every other vertex is the average of two of its neighbors.

Uniqueness implies that the problem of ﬁnding threshold budgets

is in NP and coNP.

Moreover, an intriguing equivalence was observed between reachability continuous-bidding

games and a class of stochastic game [19]called random-turn games [28]. Intricate equivalences

between mean-payo continuous-bidding games and random-turn games have been shown in

[8,9,10,11](see also [7]).

Parity continuous-bidding games were studied in [8]. The following key property was

identiﬁed in games played on strongly-connected graphs. With every positive initial budget, a

player can force visiting all vertices in the graph inﬁnitely often. Consider a strongly-connected

parity continuous-bidding game

. It follows that if the maximal parity index in

is odd, then

Player 1wins with any positive initial budget, i.e., the thresholds in

are all 0. Dually, if the

maximal parity index in

is even, then the thresholds are all 1. This property gives rise to a

simple reduction from parity bidding games to double-reachability bidding games: roughly, a

player’s goal is to reach a bottom strongly-connected component in which he can win with any

positive initial budget.

Discrete-bidding games. This paper studies discrete-bidding games, which are similar to

continuous-bidding games except that the granularity of the bids is restricted: the sum of the

budgets in the game is ﬁxed to

𝑘∈N

and bids are restricted to be integers. A key dierence

between continuous- and discrete-bidding games is bidding ties, which now need to be handled

explicitly. We focus on the tie-breaking mechanism that was deﬁned in [20]: one of the players

has the advantage and when a tie occurs, the player with the advantage chooses between (1) use

the advantage to win the bidding and pass it to the other player, or (2) keep the advantage and

let the other player win. Other tie-breaking mechanisms and the properties that they lead to

were studied in [1]. For example, the tie-breaking mechanism “alternate tie breaking” in which

the players alternate turns in winning ties, is not determined, i.e., there is a game with an initial

position such that neither player has a (pure) winning strategy. On the other hand, it was shown

that any tie-breaking mechanism that breaks ties without considering the history of ties, admits

determinacy.

The motivation to study discrete-bidding games is practical: in most applications, the

assumption that bids can have arbitrary granularity is unrealistic. We point out that the results

1 Stated as a decision problem: given a game and a vertex 𝑣, decide whether Th(𝑣) ≥ 0.5.

4/ 45 G. Avni, S. Sadhukhan

in continuous-bidding games, particularly those on inﬁnite-duration games, do in fact develop

strategies that bid arbitrarily small bids. It is highly questionable whether such strategies are

applicable in practical applications.

Bidding games model ongoing and stateful auctions. We list examples of domains in which

such auctions arise. An immediate example is auctions for online advertisements [27]. Bidding

games were applied in [12]as a scheduling mechanism in a “decoupled” synthesis procedure:

given an objective of the form

𝜓1∧𝜓2

, the idea is to ﬁnd, independently, two bidding strategies

𝑓1

for

𝜓1

and

𝑓2

for

𝜓2

and an initial budget allocation such that the strategies guarantee that

the outcome of playing

𝑓1

against

𝑓2

satisﬁes

𝜓1∧𝜓2

. For example, the strongest guarantees are

obtained when each strategy

𝑓𝑖

, for

𝑖=

2, is winning for

𝜓𝑖

, i.e., it guarantees

𝜓𝑖

even against

an adversary. Bidding as a mechanism for scheduling arises in blockchain technology, where

miners accept transaction fees, which can be thought of as bids, and prioritize transactions

based on them. Veriﬁcation against attacks is a well-studied problem [18,5]. Attacks based on

manipulations of these fees are hard to detect, can cause signiﬁcant loses, and thus call for

veriﬁcation of the protocols [18,5]. Another example is applying bidding games as a mechanism

for fair allocation of resources. Non-zero-sum Richman-bidding games were studied and applied

to resource allocation in [26]and poorman-bidding games (in which winning bids are paid to

the “bank”) were applied in [15]. Poorman discrete-bidding were studied in [13]. In addition,

researchers have studied training of agents that accept “advice” from a “teacher”, where the

advice is equipped with a “bid” that represents its importance [3]. Finally, recreation bidding

games have been studied, e.g., bidding chess [16], as well as combinatorial games that apply

bidding instead of alternating turns [30].

We reiterate that practical applications of bidding games require some granularity on

the bids. At the same time, we seek a high granularity to enable ﬂexibility. A high granularity

translates to choosing a large sum of budgets 𝑘.

Previous results. For reachability objectives, the theory of continuous bidding games was

largely adapted to discrete-bidding in [20]: threshold budgets were shown to exist and satisfy a

discrete version of the average property and winning strategies are derived from the thresh-

old budgets. However, the only known algorithm to compute thresholds is a value-iteration

algorithm whose worst-case running time is exponential when 𝑘is given in binary.

For parity discrete-bidding games there were large gaps in our understanding. In [1],

determinacy was shown, namely from each conﬁguration of the game, one of the players has

a (pure) winning strategy. Determinacy is achieved by showing that the game satisﬁes a local

property, which implies “global” determinacy. Using the observation that an additional budget

will not harm a player, we obtain existence of thresholds. Importantly, this technique does not

show that the thresholds satisfy the average property, and it was left open whether they indeed

satisfy the average property. In terms of complexity, the algorithm to decide the winner from a

5/ 45 Computing Threshold Budgets in Discrete-Bidding Games

conﬁguration is naive: construct and solve the explicit concurrent game that corresponds to

a bidding game. The running time of the algorithm is exponential when

𝑘

is given in binary.

Another disadvantage of the algorithm is that the strategies that it produces use exponential

memory and do not connect between bids and thresholds, as is done in reachability discrete-

bidding games. To make matters worse, it was observed that unlike the properties of thresholds

in reachability discrete-bidding games, which are conceptually similar to those in continuous-

bidding, threshold in parity discrete- and continuous-bidding games are inherently dierent: a

strongly-connected discrete-bidding game

was shown in which a player cannot force visiting

a vertex 𝑣inﬁnitely often even if he is initially allocated all of the budget. That is, when Gis a

Büchi game and

𝑣

is the only accepting vertex, then under continuous-bidding semantics, the

threshold are 0whereas under discrete-bidding, the thresholds are

𝑘+

1(meaning that even a

budget of 𝑘does not suce for winning).

Our results. We develop two complementary algorithms for computing threshold budgets in

parity discrete-bidding games. Our ﬁrst algorithm is a ﬁxed-point algorithm. It repeatedly solves

(i.e., ﬁnds threshold budgets) in frugal-reachability bidding games, which is an objective that

we introduce in which on top of a reachability objective, in order to win, a player must reach

its target with a sucient budget. Our algorithm is inspired by algorithms to solve turn-based

games such as Zielonka’s [31]and Kupferman and Vardi’s [23]algorithms, whereas continuous-

bidding games reduce to stochastic games. Recently, the ﬁxed-point algorithm was adapted to

bidding games with charging [6]. This algorithm shows, for the ﬁrst time, that threshold budgets

in parity discrete-bidding games satisfy the average property. Moreover, the strategies that it

produces are derived from the thresholds, as in reachability discrete-bidding games. On the

downside, the algorithm runs in exponential time when 𝑘is given in binary.

Second, we show that the problem of ﬁnding threshold budgets in parity discrete-bidding

games

is in NP and coNP. The bound applies also to reachability discrete-bidding games for

which only an exponential-time algorithm was known. We brieﬂy describe the idea of our

proof. A ﬁrst attempt to ﬁnd thresholds, is to guess thresholds (this is possible since the budgets

are discrete) and verify that the guess satisﬁes the average property (recall that in continuous-

bidding games, functions that satisfy the average property are unique). We show, however, that

functions that satisfy the discrete average property are not unique. That is, even if a function

satisﬁes the average property, it might not represent the thresholds in the game. We point out

that this observation holds already in reachability discrete-bidding games, and to the best of

our knowledge, was never made before. We overcome this challenge as follows. Our algorithm

ﬁrst guesses a function, checks whether it satisﬁes the average property, then veriﬁes that it

coincides with the thresholds. This last step is done via a reduction to turn-based parity games

and is based on the structure of the thresholds and strategies that our ﬁrst algorithm establishes.

2 Formally, given a discrete-bidding game G, a vertex 𝑣, and a threshold ℓ, decide whether Th(𝑣) ≥ ℓ.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1/452025:5ComputingThresholdBudgetsinDiscrete-BiddingGamesReceivedJan4,2024RevisedSep27,2024AcceptedNov23,2024PublishedJan22,2025KeywordsandphrasesDiscretebiddinggames,Richmangames,paritygames,reachabilitygamesGuyAvniaSumanSadhukhanaaUniversityofHaifa,IsraelABSTRACT.Inatwo-playerzero-sumgraphgame,...

展开>> 收起<<

Computing Threshold Budgets in Discrete-Bidding Games_2.pdf

共45页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Computing Threshold Budgets in Discrete-Bidding Games_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: