Samuel Hand

Alexander Koch

Pascal Lafourcade
email: pascal.lafourcade@uca.fr

Daiki Miyahara
email: miyahara@uec.ac.jp

Léo Robert

Check Alternating Patterns: A Physical Zero-Knowledge Proof for Moon-or-Sun

Keywords: Physical Zero-knowledge Proof, Pencil Puzzle, Card-based Cryptography, Moon-or-Sun, Nikoli Puzzle

A zero-knowledge proof (ZKP) allows a party to prove to another party that it knows some secret, such as the solution to a difficult puzzle, without revealing any information about it. We propose a physical zero-knowledge proof using only a deck of playing cards for solutions to a pencil puzzle called Moon-or-Sun. In this puzzle, one is given a grid of cells on which rooms, marked by thick black lines surrounding a connected set of cells, may contain a number of cells with a moon or a sun symbol. The goal is to find a loop passing through all rooms exactly once, and in each room either passes through all cells with a moon, or all cells with a sun symbol.

Finally, whenever the loop passes from one room to another, it must go through all cells with a moon if in the previous room it passed through all cells with a sun, and visa-versa. This last rule constitutes the main challenge for finding a physical zero-knowledge proof for this puzzle, as this must be verified without giving away through which borders the loop enters or leaves a given room. We design a card-based zero-knowledge proof of knowledge protocol for Moon-or-Sun solutions, together with an analysis of their properties. Our technique of verifying the alternation of a pattern along a non-disclosed path might be of independent interest for similar puzzles.

Introduction

A Zero-Knowledge Proof (ZKP) protocol is a cryptographic tool enabling a party to prove a statement without revealing information about it. Due to their versatility, numerous variants of these protocols exist with different possible applications. For instance, a ZKP could help to determine if a database contains information without revealing it. A ZKP protocol is also used for e-voting system to ensure that ballots are correctly shuffled. Lastly, ZKP protocols are also used for cryptocurrencies like Monero or ZCash to allow anonymous transactions.

We focus on a particular ZKP: interactive Zero-Knowledge Proof of Knowledge protocols. In this context, there are two parties involved: a prover P and a verifer V . The prover wishes to convince the verifier that it knows specific information without revealing it. These protocols have three properties:

-Completeness: if P knows a secret s then the protocol ends without failure (meaning that V is convinced P has s); -(Perfect) Soundness: if P does not have the solution s then the protocol will abort (with probability 1); -Zero-Knowledge: V learns nothing about s.

We design a ZKP protocol for the Moon-or-Sun puzzle. The goal of our protocol is that if a prover P has the solution for a given instance of the Moon-or-Sun puzzle, then it will be able to convince a verfier V of this fact, and the protocol will end (as stated by the completeness property). Further, any information revealed during the protocol should not leak any information about the solution (as stated by the zero-knowledge property). Finally, if P does not have the solution, then the protocol should abort (as stated by the soundness property).

In a nutshell, the protocol is done in two major steps: (1) the prover P commits its solution, and (2) the verifier V checks that the commited values are respecting the rules.

The Moon-or-Sun rules are given in Fig. 1. We also illustrate an example in Fig. 2 taken from Nikoli's webgpage 7 .

In [START_REF] Iwamoto | Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete[END_REF], the Moon-or-Sun puzzle is proven to be NP-complete which implies that a ZKP protocol exists, as proved in [START_REF] Ben-Or | Everything provable is provable in zero-knowledge[END_REF]. While the latter work is a constructive proof which implies the existence of a ZKP protocol, there is always the need to design a specific protocol for a given problem. Indeed, the generic construction is not efficient, nor interesting in itself.

1. Construct a loop. 2. The loop never crosses itself, branches off, or goes through the same cell twice. 3. The loop goes through each room (i.e., continuous cells delimited by thick edges) only once. 4. The loop goes through all moon or all sun for each room. This means that the loop cannot pass through moon and sun cells for a given room. 5. After the loop goes through the moons in one room it has to go through all the suns in the next room it enters and visa versa.

Related work.

The first physical ZKP protocol [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles[END_REF] for a Sudoku grid was constructed using a deck of cards. Since this novel protocol was devised, several papers have proposed physical ZKP protocols using a deck of cards for pencil puzzles, such as Sudoku [START_REF] Ruangwises | Two standard decks of playing cards are sufficient for a ZKP for Sudoku[END_REF][START_REF] Sasaki | Efficient card-based zero-knowledge proof for Sudoku[END_REF], Akari [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Takuzu [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Kakuro [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF][START_REF] Miyahara | Card-based physical zero-knowledge proof for Kakuro[END_REF], KenKen [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Makaro [START_REF] Bultel | Physical zero-knowledge proof for Makaro[END_REF], Norinori [START_REF] Dumas | Interactive physical zero-knowledge proof for Norinori[END_REF], Slitherlink [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF], Suguru [START_REF] Robert | Physical zeroknowledge proof and NP-completeness proof of Suguru puzzle[END_REF], Nurikabe [START_REF] Robert | Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake[END_REF], Ripple Effect [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF], Numberlink [START_REF] Ruangwises | Physical zero-knowledge proof for Numberlink puzzle and k vertex-disjoint paths problem[END_REF], Bridges [START_REF] Ruangwises | Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems[END_REF], Cryptarithmetic [START_REF] Isuzugawa | Zero-knowledge proof protocol for Cryptarithmetic using dihedral cards[END_REF], and Nonogram [START_REF] Chien | Cryptographic and physical zero-knowledge proof: From Sudoku to Nonogram[END_REF][START_REF] Ruangwises | An improved physical ZKP for Nonogram[END_REF]. More recent puzzles have been considered such as Shikaku [START_REF] Ruangwises | How to physically verify a rectangle in a grid: A physical ZKP for Shikaku[END_REF], Makaro (using a standard deck of cards) [START_REF] Ruangwises | Physical ZKP for Makaro using a standard deck of cards[END_REF], Nurimisaki [START_REF] Robert | Card-based ZKP protocol for Nurimisaki[END_REF], Topswops [START_REF] Komano | Physical zero-knowledge proof protocol for Topswops[END_REF], Pancake Sorting [START_REF] Komano | Card-based zero-knowledge proof protocol for Pancake Sorting[END_REF], and Usowan [START_REF] Robert | Hide a liar: Card-based ZKP protocol for Usowan[END_REF].

Contributions. We design a card-based, interactive ZKP protocol for the Moon-or-Sun puzzle. We rely on some existing techniques, such as constructing a non-branching loop or computing the sum of multiple commitments, but also propose original and simple sub-protocols, such as showing alternating pattern, to obtain a secure ZKP protocol. Our description is also accompanied of security proofs to show the completeness, perfect soundness and zero-knowledge of our protocol. An overview of our proposed protocol is depicted in Fig. 3.

We also demonstrate that our proposed ZKP protocol is related to a well-known NP-hard problem in graph theory. This may prove the significance of our protocol for a Moon-or-Sun puzzle.

Outline. We begin by introducing notations and existing protocols used in our ZKP protocol in Sect. 2. In Sect. 3, we present our ZKP protocol for a Moon-or-Sun puzzle. In Sect. 4, we prove that our ZKP protocol satisfies the ZKP properties. In Sect. 5, we discuss about our ZKP protocol. We conclude this study in Sect. 6.

Setup: P and V prepare the grid • The loop is constructed • A cell has a commitment equal to 1 if and only if the loop passes through it.

Verification: V verifies the remaining rules Fig. 3. Overview of our protocol. On the left with rounded corners are the main steps of our construction, and on the right are the main sub-protocols used.

Preliminaries

We present the general notions needed for our ZKP protocol, such as encoding and sub-protocols.

Cards and Encoding.

We use a deck of cards consisting of two suits: clubs ♣ and hearts ♡ . We then let an ordered pair of these cards represent a bit value according to the following encoding:

♣ ♡ → 0, ♡ ♣ → 1.
(1)

Each card in the deck has an identical back ? , and we refer to an ordered pair of face-down cards satisfying encoding (1) for a bit x ∈ {0, 1} as a commitment to x. Such a commitment to a bit x is then denoted by: ? ?

x .

We also define two converse encodings for integers modulo p [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF]:

-♣-scheme: to encode x ∈ Z/pZ use a row of p cards with one ♣ in position (x+1) from the left and the remaining p-1 positions occupied by ♡s. As an example, we would represent 2 with ♡ ♡ ♣ ♡ in Z/4Z. -♡-scheme: equivalently as above, but with ♡ and ♣ exchanged. Here 2 is instead represented by ♣ ♣ ♡ ♣ in Z/4Z.

Shuffle

We explain two types of shuffles that introduce randomness into the order of a sequence of cards. These shuffles are usually employed in card-based cryptography, particularly within ZKP protocols. Consider a pile consisting of ℓ cards, where ℓ > 0. Both shuffles are applied to multiple piles of cards, making the order of the piles unknown to everyone, while preserving the order of cards within each pile. Suppose that we have m piles denoted by (p 1 , p 2 , . . . , p m ), each containing ℓ cards.

Pile-scramble shuffle. This shuffling method, initially introduced in [START_REF] Mizuki | Voting with a logarithmic number of cards[END_REF], completely randomizes the order of piles. Applying a pile-scramble shuffle to (p 1 , p 2 , . . . , p m ) yields (p r -1 (1) , p r -1 (2) , . . . , p r -1 (m) ), where r is a random permutation uniformly distributed in a symmetric group of degree m, denoted by S m . This shuffling is denoted by

[•| . . . |•].
Pile-shifting shuffle. This shuffling method, initially introduced in [START_REF] Shinagawa | Card-based protocols using regular polygon cards[END_REF], randomly and cyclically shifts the order of piles. Applying a pile-shifting shuffle to (p 1 , p 2 , . . . , p m ) yields (p s+1 , p s+2 , . . . , p s+m ), where s is chosen randomly and uniformly from Z/mZ. This shuffling is denoted by ⟨

•| . . . |•⟩.
When m = 2, this shuffle is called a random bisection cut [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF], i.e., bisecting a sequence of cards and randomly swapping the two halves. When ℓ = 1, this shuffle is known as a random cut invented by Den Boer [START_REF] Den Boer | More efficient match-making and satisfiability: The Five Card Trick[END_REF].

XOR and Copy Protocols

Our protocol uses the existing card-based protocols for computing a logical function of two-input XOR and duplicating an input commitment [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF].

Here, we briefly introduce them, and their full descriptions are in Appendix A.

Given commitments to a, b ∈ {0, 1}, the Mizuki-Sone XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] outputs a commitment to a ⊕ b:

? ? a ? ? b → • • • → ? ? a⊕b .
Given a commitment to a ∈ {0, 1} along with two commitments to 0, the Mizuki-Sone copy protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] outputs two commitments to a:

? ? a ? ? 0 ? ? 0 → • • • → ? ? a ? ? a .

How to Form a Loop

To verify rule 2, i.e., the loop condition, we use the existing protocol from [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF]. Let us introduce an overview of the protocol [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF]. This protocol enables a prover P to create any single loop without revealing information about the loop shape, while simultaneously convincing a verifier V that the resulting loop is indeed a single loop. That is, this protocol creates a figure respecting rule 2 rather than verifying it.

Briefly, this protocol starts from the single loop going along the boundary of the board. P and V interactively create the solution P has from the single loop. During this process, V cannot obtain information other than that the process proceeds correctly, and hence, the resulting shape is indeed a single loop.

To represent a loop with a sequence of cards, we place a commitment between each cell. The value of such a commitment represents the existence of line, i.e., line passes through them if the value is 1, and no line passes if it is 0 as follows:

? ? 1 → Thus, the protocol [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF] begins by placing a commitment to 1 between each cell adjacent to the border of a given board and commitments to 0 on the remaining positions, representing the single loop. Refer to [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF] for specific methods on creating the solution P has.

Sum of Commitments

This protocol is defined in [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF]; we give a general description given as an example. Suppose that we have commitments to a, b ∈ {0, 1}, and we want to output a + b ∈ Z/3Z (in the ♡-scheme, see encoding Eq. ( 2 Notice that we described the sum protocol for an output of two bit commitments in Z/3Z. We can generalize by inductively applying the protocol for n bit commitments giving an output in Z/(n + 1)Z.

ZKP Protocol for Moon-or-Sun

We present a card-based ZKP protocol for a Moon-or-Sun puzzle. As shown in Fig. 3, our protocol has two phases: the setup and verification phases. The setup phase constructs a loop with the interaction between a prover P and a verifier V . The verification phase verifies all the rules other than rules 1 and 2.

Setup

As introduced in Sect. 2.3, a solution is represented with a commitment between each adjacent cells. Moreover, we place a commitment on each cell to represent the loop passing through a symbol (i.e., moon or sun symbol). The setup is done in two steps:

1. Constructing the loop using [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF]; 2. Placing the commitments inside the cells. Notice that we modify only cells with moon or sun symbol.

Forming the loop. We directly use the construction of [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF] described in Sect. 2.3. At this point, there are commitments between the cells but no commitment inside them.

Filling the grid. We want to put commitments inside the cells to model the line passing through it (or not). For each cell (corresponding to a moon or sun symbol), if the line passes through it, we observe that the sum of the values of the four neighbour commitments on its edge is always equal to two (otherwise, zero). Based on this observation, we place a commitment inside every cell as follows. We note that we execute the Mizuki-Sone copy protocol introduced in Sect. 2.2 whenever a commitment on the board is taken, so that the same commitment can be used for several times.

1. Apply the sum protocol (Sect. 2.4) to the four neighbours of the targeted cell c t . The result is in ♡-scheme:

? ?

? ?

? ? ? ? c t → ? ? ? ? ? .

Remember that if the sum is two, the third card from the left in the resulting sequence is a ♡ . 2. Make a commitment consisting of the third and first cards in the resulting sequence (in this order) by taking them and place it on c t .

V is convinced that each cell (containing a moon or a sun) is equal to 1 = ♡ ♣ if and only if the line passes through it, i.e., there are two neighbours equal to 1, exactly.

At this point, P has placed commitments according to its solution, and V wants to check that each rule is respected.

Verification Phases

The loop has been constructed in the previous step, so V wants to check if the other rules are respected.

Only moon or only sun (rule 4).

The loop must pass through only moon or only sun symbols in a given room but exactly one of them. The following verification is done for each room:

1. Consider all the commitments on sun cells, and place them in a sequence (in any order). Apply a random cut introduced in Sect. 2.1 and reveal it. If the result has alternating pattern, then continue; otherwise, abort.

We show an example when the room has three sun cells as follows:

? ? ? ? ? ? → ♣ ♡ ♣ ♡ ♣ ♡ or ♡ ♣ ♡ ♣ ♡ ♣ .

2. Repeat the previous step for moon cells.

3. Execute the Mizuki-Sone XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] with a commitment on any sun cell and a commitment on any moon cell. If the protocol outputs a commitment to 1, then V continues; otherwise, V aborts.

Note that no information is leaked if the rule 4 is respected. Indeed, if the commitments are equal (for a given symbol), the random cut hides the initial values of commitments (V does not know if they are 0s or 1s). However, if the rule is not respected, then V knows the number of commitments that are different (i.e., it can deduce the Hamming weight of the sequence).

One enter, one exit (rule 3). The loop must be passing through a room only once. This means that for each room, the loop crosses its edge exactly twice (one for entering and one for exiting the room). The idea is thus to shuffle the commitments located at the edge of a room and reveal them. Formally, we proceed as follows:

1. Consider a room and take all the commitments located at the edge. 2. Apply a pile-scramble shuffle to them. 3. Reveal all the commitments. If exactly two commitments to 1 appears, then continue; otherwise, abort. 4. Repeat the previous step until visiting all rooms.

Alternating pattern (rule 5). The loop must pass through a different symbol to the one in the previous room it enters. Let us first present the idea behind our verification for this rule.

Given a solution as in Fig. 2, consider verifying whether a room (referred to as the target) satisfies rule 5 or not. For this, we examine the two rooms connected to the target room (i.e., those through which line passes) and ensure that the loop passes through different symbols within the target room and the connected rooms. That is, we determine whether the two connected rooms are either both "sun rooms" or "moon rooms" and both of them differ to the target room. Our approach follows a similar logic: for every adjacent room, we collect a commitment on any sun cell 8 . Subsequently, from among the commitments, we somehow choose two commitments corresponding to the two connected rooms without leaking any information. The remaining steps are simple; we confirm that the values of the chosen commitments XORed with a commitment on any sun cell within the target room both yields ones. Now we are ready to describe the verification method. Suppose that we verify the rule 5 for a target room R 0 with k (≥ 2) adjacent rooms, R 1 , R 2 , . . . , R k . Let n i , 1 ≤ i ≤ k, denote the number of commitments on the border between R 0 and R i . The verification proceeds as follows.

1. For every adjacent room R i , let c j denote each of the n i commitments on the border between R 0 and R i , for 1 ≤ j ≤ n i (in any order). Collect one c j for every j and add "dummy" commitments to 0 so that the total number of collected commitments (i.e., n i ) becomes n max = max(n 1 , . . . , n k ) as follows: 4. Reveal all the commitments constituting s i for all i, 1 ≤ i ≤ k. Then exactly two commitments to 1 should be revealed, each appearing in different s i (rule 3) 9 . Denote these positions as a and b (a < b) as follows:

n
• • • c ′ r -1 (a) : ? ? s r -1 (a) : ♣ ♡ • • • ♡ ♣ • • • ♣ ♡ • • • • • • c ′ r -1 (b) : ? ? s r -1 (b) : ♣ ♡ • • • ♡ ♣ • • • ♣ ♡ • • • ,
where r ∈ S k is a random permutation generated through the application of a pile-scramble shuffle at step 3. ? ? ? ? ? ?

→ ♣ ♡ ♡ ♣ ♡ ♣ or ♡ ♣ ♣ ♡ ♣ ♡ → Continue.
We execute these steps for all the rooms. If V does not abort, then V is convinced that the commitments on the board respect rule 5. We discuss on reducing the number of executions of these steps in Sect. 5.

Efficiency

Let us evaluate the number of required shuffles for our proposed ZKP protocol for efficiency. Because the verification for rule 5 (alternating pattern) can also verify rule 3 (one enter, one exit) as mentioned, our protocol does not execute the verification for rule 3 in this evaluation. Also, let us omit the evaluation of the part of constructing the single loop [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF] because it cannot be included in this paper due to the page length limit.

Let n r denote the number of rooms in a given Moon-or-Sun puzzle and p × q denote the size of the puzzle. For verifying rule 4, our protocol uses two random cuts and one random bisection cut (for the XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF]) for each room, i.e., 3n r . For verifying rule 5 for each room, our protocol uses one pile-scramble shuffle, one random bisection cut, and a number of pile-scramble shuffles corresponding to the number of adjacent rooms. For duplicating commitments, our protocol applies the copy protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF], i.e., one random bisection cut, to each commitment between each pair of adjacent rooms and on moon and sun cells. For making a because rule 4 implies that the value of a commitment on any sun cell must differ to that on any moon cell within the same room, the XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] always outputs a commitment to 1 at step 3. One enter, one exit (rule 3): The number of commitments to 1 among all the commitments located at the edge must be two for every room. Therefore, two commitments to 1 always appear when revealing all of them at step 3. Alternating pattern (rule 5): At step 5, c ′ r -1 (a) and c ′ r -1 (b) come from commitments on any sun cell within different rooms such that lines exist between each of them and R 0 . This is because a commitment to 1 is revealed among each of s r -1 (a) and s r -1 (b) , and s i comes from commitments on the border between R 0 and R i . Rule 5 implies that the values of c ′ r -1 (a) and c ′ r -1 (b) must be both different to the value of c ′ 0 , i.e., the first configuration at step 5(a) is as follows:

c ′ 0 : ♡ ♣ c ′ r -1 (a) : ♣ ♡ c ′ r -1 (b) : ♣ ♡ or c ′ 0 : ♣ ♡ c ′ r -1 (a) : ♡ ♣ c ′ r -1 (b) : ♡ ♣ .
Thus, V never aborts when revealing all the cards at step 5(b). ⊓ ⊔ Theorem 2 (Soundness). If P does not know a solution of a Moonor-Sun grid, then V always rejects ( i.e., the protocol aborts).

Proof. Our protocol is a proof-of-knowledge because commitments placed on the grid after the setup phase represent a solution. Thus, in the remaining part of this proof, we prove that V always aborts if P does not provide a solution, i.e., at least one rule is not respected. Because rule 2 is always respected due to [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF], we consider the case that each of the remaining rules is not respected as follows.

Only moon or only sun (rule 4): For a given room, two cases are considered: (1) the loop does not pass through all suns (or moons) but only some of them, and (2) the loop passes through all moons and suns (or nothing). The first case can be detected at either step 1 or step 2 because a sequence of commitments on all sun (moon) cells does not have an alternating pattern, e.g., ♣ ♡ ♣ ♡ ♡ ♣ . The second case can be detected at step 3 because the value of commitment on any sun cell is the same as on any moon cell. One enter, one exit (rule 3): Because all commitments located at the edge of a given room and the target room are revealed at step 3, the number of times the loop enters the given room is revealed. Thus, V always detect the case in which rule 3 is violated. Alternating pattern (rule 5): If this rule is violated, it means that for a given room, there is at least one adjacent room such that line exists between them but the loop passes through the same symbol (assuming that rule 4 is respected). As stated in the above proof, because c ′ r -1 (a)

and c ′ r -1 (b) come from commitments on any sun cell within such rooms at step 5, V learns whether the values of them are equal to c ′ 0 using the XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF]. Thus, V always aborts.

In any case, the verifier always rejects.

⊓ ⊔ Theorem 3 (Zero-knowledge). V learns nothing about P 's solution of the given grid G.

Proof. We use the same proof technique as in [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles[END_REF], namely the description of an efficient simulator which simulates the interaction between an honest prover and a cheating verifier. As described in [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles[END_REF], this simulator does not have a correct solution, but has an ability that a sequence of cards can be swapped with the same number of cards during the application of shuffling; this ability is the replaced one with the rewind ability in cryptographic ZKP protocols. Informally, our protocol is zero-knowledge because it applies an appropriate shuffling to a sequence of cards before revealing them. The simulator can always swap the sequence such that the real and simulated protocols are indistinguishable.

Formally, in the setup phase, the simulator first constructs arbitrary loop executing [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF]. Subsequently, it applies the sum protocol [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF] introduced in Sect. 2.4. Note that this existing protocol [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF] is proved to be zero-knowledge. In the verification phase, for each of the remaining rules, it acts as follows.

Only moon or only sun (rule 4): At steps 1 and 2, during each application of a random cut, the simulator swaps the commitments with commitments to 1. Because a random cut cyclically and randomly shifts a sequence of cards, this swapping results in any of the alternating patterns with a probability of 1/2, which is indistinguishable from a real execution. At step 3, it executes the Mizuki-Sone XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] that is zero-knowledge. One enter, one exit (rule 3): At step 2, the simulator swaps the commitments with the ones where the number of commitments to 1 is exactly two. Because a pile-scramble shuffle randomly rearranges the order of piles consisting cards, the two commitments to 1 appear in random positions. Alternating pattern (rule 5): At step 1, the simulator swaps the n max commitments with the ones having exactly one commitment to 1 if i = 1, 2 and with n max commitments to 0 otherwise. At step 3, it acts nothing, but applying pile-scramble shuffles results in the case where the two commitments to 1 appears in different sequences of random positions. Finally, at step 5, it swaps c ′ 0 , c ′ r -1 (a) , and

c ′ r -1 (b)
with commitments to 1, 0, and 0, respectively. Because applying a random bisection cut to them results in either commitments to 1, 0, and 0 or commitments to 0, 1, and 1 with a probability of 1/2, V learns nothing other than that the value of c ′ 0 differs to those of c ′ r -1 (a) and c ′ r -1 (b) . ⊓ ⊔

Discussion

Here, we discuss whether we can reduce the number of executions of our method for rule 5 described in Sect. 3.2. Suppose that we execute the verification phase described in Sect. 3.2 for all rooms surrounding a given room. Then we prove that such a room does not need to be verified for rule 5 as in the following theorem. Proof. Suppose, for the sake of contradiction, that there exists a room R that does not satisfy rule 5, while all rooms surrounding R are verified to satisfy all the rules through the execution of our verification phase described in Sect. 3.2. Then, as R does not satisfy rule 5, there should exist a room R ′ such that the line passes between R and R ′ , passing through the same symbol in both. However, R ′ surrounds R, and this contradicts our assumption that all rooms surrounding R satisfy all the rules. Therefore, our initial assumption must be false, and hence, R satisfies rule 5.

⊓ ⊔

Theorem 4 implies that we do not need to verify all rooms for rule 5. We observe that optimally reducing the number of rooms for which rule 5 is verified in our protocol is related to one of the classical NP-hard problems, namely, the minimum vertex cover problem. This connection emerges if we consider a Moon-or-Sun puzzle as an undirected graph, wherein a vertex set comprises rooms, and an edge denotes the adjacency of rooms. A vertex cover of graph is a set of vertices where every edge of the graph has at least one vertex in the set. The minimum vertex cover problem asks the minimum size of such vertex covers if they exist.

Because a vertex cover represents rooms surrounding all the remaining rooms, it suffices to verify whether such rooms satisfy rule 5, as indicated in Theorem 4. However, if we wish to verify rule 5 for a minimum number of rooms we must initially find a minimum vertex cover. As mentioned, finding such a cover is an NP-hard problem, even on planar graphs, thus we are unable to perform this initial step efficently. Although techniques for evaluating the execution time of card-based protocols exist [START_REF] Miyahara | Evaluating card-based protocols in terms of execution time[END_REF], doing so in this case is non-trivial, due to this additional computationally intensive step. Additionally, constructing ZKP protocols for a Moon-or-Sun puzzle may prove more challenging than those in existing work because in essence, rule 5 involves not verifying a given room itself but comparing a given room with all of its adjacent rooms.

It is still possible to bound the number of rooms that we must verify rule 5 for, without requiring a computational step of infeasible running time. To begin, we note that any planar graph always has a vertex cover with at most 3n 4 vertices, and thus we have the following theorem: Theorem 5. It is possible to convince the verifier that all rooms satisfy rule 5 by checking this rule for at most 3 4 of the rooms. Proof. It follows from theorem 4 that it suffices to verify rule 5 only for rooms in a vertex cover. Furthermore every planar graph has a vertex cover containing at most 3 4 of the vertices. Thus it is only ever necessary to verify rule 5 for only 3 4 of the rooms. ⊓ ⊔ Furthermore, we know that we can find a cover of this size in polynomial time. To do so, we find a four coloring of the graph, and then take our cover to be the union of the three smallest color classes, yielding a cover that is of size most 3n 4 . It is possible to compute a four coloring for a planar graph in polynomial (quadratic) time [START_REF] Robertson | Efficiently four-coloring planar graphs[END_REF].

Conclusion

We proposed a ZKP protocol for Moon-or-Sun, which has an interesting rule: the loop must pass through different symbols within two consecutive rooms. Through the construction, we found this rule to be related to a well-known problem in graph theory, which leads some challenging problems.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Rules for Moon-or-Sun [1].

2 . 3 ... 4 .

 234 the two cards of the commitment to a and add a ♣ face-down to the right. Those three cards represent a in the ♡-scheme in Z/3Z: Add a ♡ on the right of the commitment to b. Those three cards represent b in the ♣-scheme in Z/3Z: ? ? Obtain three cards representing a + r and those representing b -r for a uniformly random value r ∈ Z/3Z as follows. (a) Place in reverse order the three cards obtained in Step 2 below the three cards obtained in Step 1: Apply a pile shifting shuffle as follows: For a uniformly random value r ∈ Z/3Z, we obtain three cards representing a + r and 2 -b + r. (c) Reverse the order of the three cards representing 2-b+r to obtain b -r: Reveal the three cards representing b -r, and shift to the right the three cards representing a + r to obtain those representing a + b in the ♡-scheme; apply the same routine for the remaining elements to compute the final sum.

5 .

 5 Let c ′ 0 denote a commitment on any sun cell in the target room R 0 . (If there is no sun, then denote a commitment on any moon cell by c ′ 0 and swap the two cards constituting c ′ 0 .) Execute an extended version of the Mizuki-Sone XOR protocol[START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] with c ′ 0 , c ′ r -1 (a) , and c ′ r -1 (b) as follows.(a) Place c ′ 0 , c ′ r -1 (a) , and c ′ r -1 (b) and apply a random bisection cut as follows: Reveal all the cards. If the values of the middle and bottommost commitments both differ from the value of the topmost commitment, then continue; otherwise, abort.

Theorem 4 .

 4 A room always satisfies rule 5 if all rooms surrounding the room satisfy all the rules.

Pattern: rule 5.

	Protocol: How to form a loop (Sect. 2.3)
	Protocol: Sum (Sect. 2.4)
	Protocol: XOR (Sect. 2.2)

• One enter, one exit: rule 3; • Only moon or only sun: rule 4; • Alternating

  Let s i denote the sequence of the n max commitments. Apply a pilescramble shuffle to s i as follows: ′ i denote a commitment on any sun cell within R i . Place one c ′ i above s i . (If R i has no sun, then let c ′ i denote a commitment on any moon cell and swap the two cards constituting c ′

	n i commitments		nmax -n i commitments
	? ? ? ? • • • ? ?	? ?	? ?	• • • ? ?
			0	0
	s i : s 1 : ? ? ? ? • • • ? ? ? ? ? ? • • • ? ? → s c ′ 1 : ? ? • • • s	c ′ k : ? ?

i commitments ? ? ? ? • • • ? ? → 0 . i : ? ? ? ? • • • ? ? . 2. For every adjacent room R i , 1 ≤ i ≤ k, let c i before placing it.) s i : ? ? ? ? • • • ? ? → c ′ i : ? ? s i : ? ? ? ? • • • ? ? . 3. Apply a pile-scramble shuffle to the n k piles consisting of s i and c ′ i , 1 ≤ i ≤ k, as follows: k : ? ? ? ? • • • ? ? .

Remember that the value of a commitment on a cell indicates the presence of line passing through the cell.

This means that rule 3 can be simultaneously verified for the target room.

Acknowledgements. We thank the anonymous referees, whose comments have helped us improve the presentation of the paper. The fourth author was supported in part by Kayamori Foundation of Informational Science Advancement and JSPS KAKENHI Grant Number JP23H00479. The third and fifth authors were partially supported by the French ANR project ANR-18-CE39-0019 (MobiS5). Other programs also fund to write this paper, namely the French government research program "Investissements d Ávenir" through the IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01). Finally, the French ANR project DECRYPT (ANR-18-CE39-0007) and SEVERITAS (ANR-20-CE39-0009) also subsidize this work.

commitment placed on each of moon and sun cells, our protocol applies the sum protocol [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF] to the four neighbour commitments, i.e., three pileshifting shuffles. In total, because the number of commitments between each pair of adjacent rooms (and on moon and sun cells) is less than p 2 × q 2 , our protocol uses O(p 2 q 2 ) shuffles.

Security Proofs

Our protocol needs to verify three security properties given as theorems.

Theorem 1 (Completeness). If P knows a solution of a Moon-or-Sun grid, then P can always convince V ( i.e., V does not abort).

Proof. In the setup phase described in Sect. 3.1, constructing the loop is directly taken from [START_REF] Lafourcade | How to construct physical zero-knowledge proofs for puzzles with a "single loop" condition[END_REF], so we refer readers to this paper for the proof.

For placing a commitment inside a cell, we use the sum protocol [START_REF] Ruangwises | Securely computing the n-variable equality function with 2n cards[END_REF] so that the value of the commitment represents the presence of line. Because the configuration of the four neighbors is either the following two (up to rotation), the resulting sequence at step 1 is always ♣ ♣ ♡ ♣ ♣ , representing two if line passes through the cell (the loop never branches off):

? ? If line does not pass, then the resulting sequence is ♡ ♣ ♣ ♣ ♣ because all the four neighbors are commitments to 0. Therefore, constructing a commitment with the first and third cards, from the previous sequence, correctly represents the presence of line for a cell.

For the verification phase, described in Sect. 3.2, we divide the proof into three parts, each corresponding to one rule.

Only moon or only sun (rule 4):

Because P knows a solution, the values of all the commitments on sun cells considered at step 1 are either 0s or 1s, i.e., ♣ ♡ ♣ ♡ • • • or ♡ ♣ ♡ ♣ • • • . Thus, applying a random cut to them always yields a sequence having an alternating pattern. This holds true for moon cells at step 2 as well. Finally,

A Full Description of XOR and Copy Protocols

XOR protocol. Given commitments to a, b ∈ {0, 1}, the Mizuki-Sone XOR protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF] outputs a commitment to a ⊕ b:

This protocol proceeds as follows.

1. Rearrange the sequence: Copy protocol. Given a commitment to a ∈ {0, 1} along with two commitments to 0, the Mizuki-Sone copy protocol [START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF]


Hidde Fokkema
email: h.j.fokkema@uva.nl

Korteweg-De Vries

Damien Garreau
email: damien.garreau@unice.fr

Tim Van Erven Korteweg-De Vries

The Risks of Recourse in Binary Classification

Algorithmic recourse provides explanations that help users overturn an unfavorable decision by a machine learning system. But so far very little attention has been paid to whether providing recourse is beneficial or not. We introduce an abstract learning-theoretic framework that compares the risks (i.e., expected losses) for classification with and without algorithmic recourse. This allows us to answer the question of when providing recourse is beneficial or harmful at the population level. Surprisingly, we find that there are many plausible scenarios in which providing recourse turns out to be harmful, because it pushes users to regions of higher class uncertainty and therefore leads to more mistakes. We further study whether the party deploying the classifier has an incentive to strategize in anticipation of having to provide recourse, and we find that sometimes they do, to the detriment of their users. Providing algorithmic recourse may therefore also be harmful at the systemic level. We confirm our theoretical findings in experiments on simulated and real-world data. All in all, we conclude that the current concept of algorithmic recourse is not reliably beneficial, and therefore requires rethinking.

Introduction

Machine learning (ML) models are increasingly being used to make consequential decisions in areas such as finance [START_REF] Mukerjee | Multi-objective evolutionary algorithms for the risk-return trade-off in bank loan management[END_REF], healthcare [START_REF] Begoli | The need for uncertainty quantification in machine-assisted medical decision making[END_REF][START_REF] Grote | On the ethics of algorithmic decision-making in healthcare[END_REF], and hiring [START_REF] Nabi | Fair inference on outcomes[END_REF][START_REF] Schumann | We need fairness and explainability in algorithmic hiring[END_REF]. When these decisions are unfavorable to the people they affect, algorithmic recourse provides explanations and recommendations to favorably change their situation (Karimi et al., 2022). For instance, when an individual is denied a bank loan, they might like to know the reasons and in particular what they can do to get a loan in the future.

A prominent approach to providing recourse is via counterfactual explanations, which suggest how the individual should change their features in order to flip the decision of the ML model [START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the GDPR[END_REF][START_REF] Ustun | Actionable recourse in linear classification[END_REF][START_REF] Joshi | Towards realistic individual recourse and actionable explanations in black-box decision making systems[END_REF]. Originally, counterfactuals were chosen to minimize the distance between the original and the new features [START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the GDPR[END_REF], but more recently attention has also been paid to generating realistic suggestions which are actionable and lie on the data manifold [START_REF] Ustun | Actionable recourse in linear classification[END_REF][START_REF] Joshi | Towards realistic individual recourse and actionable explanations in black-box decision making systems[END_REF]. In addition, various types of robustness have been studied, including to random perturbations [START_REF] Virgolin | On the robustness of sparse counterfactual explanations to adverse perturbations[END_REF][START_REF] Dominguez-Olmedo | On the adversarial robustness of causal algorithmic recourse[END_REF]Pawelczyk et al., 2022b), to data shifts [START_REF] Rawal | Algorithmic recourse in the wild: Understanding the impact of data and model shifts[END_REF][START_REF] Dutta | Robust counterfactual explanations for tree-based ensembles[END_REF], or to the case that the counterfactual might not be perfectly implementable [START_REF] Artelt | Evaluating robustness of counterfactual explanations[END_REF]. It has further been recognized that providing recourse has consequences at the population level, because it changes the distribution of the data. These consequences have been studied in the context of fairness for subgroups [START_REF] Gupta | Equalizing recourse across groups[END_REF] and with respect to social segregation [START_REF] Gao | On the impact of algorithmic recourse on social segregation[END_REF], but so far there has been no work that studies the consequences of providing recourse for classification accuracy.

To see why accuracy matters, consider again the loan example mentioned above. If a person is able to repay a loan they got through recourse, then recourse has been beneficial. But if they end up defaulting on their payment, then recourse has actually been harmful, both for the user and the lending institution. Providing recourse in a way that undermines the accuracy of the ML model in determining which users are likely to default, can therefore be dangerous. In fact, the bank loan example above, which is standard in the recourse literature, is also used as a motivating example in the context of strategic classification. There it is seen as a significant risk that loan applicants might try to game the system by changing their features to flip the class 1 arXiv:2306.00497v1 [cs.LG] 1 Jun 2023

R P (f ) = 0.2 x 0 x R Q f (f ) = 0.25
Figure 1: Left panel: Initial situation, the ML model classifies individual with starting features x 0 either negatively (in blue) or positively (in red). Its risk is denoted by R P (f ). Points classified negatively are given the opportunity to move to the decision boundary (yellow dotted arrows). Right panel: The points close enough to the boundary accept recourse and move towards the decision boundary. The risk with recourse, R Q f (f ), is then higher, because at the decision boundary the uncertainty about the true class is maximal, and the points that accepted recourse are now more likely to be misclassified. without actually improving their true creditworthiness [START_REF] Brown | Performative prediction in a stateful world[END_REF][START_REF] Perdomo | Performative prediction[END_REF][START_REF] Milli | The social cost of strategic classification[END_REF].

Main Contributions

In this work, we study the effects of recourse on classification accuracy at the population level. All our results are obtained in the context of a new learning-theoretic framework, which we introduce in Section 2. Accuracy is measured by the risk, which is the expected loss of a given classifier. When recourse is provided, it changes the distribution of the data, and hence the risk. We are primarily interested in whether recourse makes the risk go up or down. To answer this question it matters how the class probabilities of the users change upon receiving recourse. We distinguish between the compliant case, in which these class probabilities truly improve, and the defiant case, in which the class probabilities do not improve at all (for instance because the users are trying to game the system). In Section 3 we show that, if the classifier is optimal without recourse, then recourse will be harmful, because it increases the risk both for the compliant and for the defiant case. The reason is that recourse pushes users towards the decision boundary, where the class uncertainty is higher, which therefore leads to more mistakes. See Figure 1 for an illustration. Section 4 extends these results to probabilistic classifiers that are only near-optimal, which allows for estimation errors, and to surrogate losses like, e.g., the cross-entropy loss. In Section 5 we recognize that the party deploying the classifier may strategically choose their classifier in order to minimize the resulting risk after providing recourse. We obtain separate results for the defiant and compliant cases, which show that there is an incentive to preemptively undo the effect of recourse. For the defiant case, this makes the risks with and without recourse identical, so implementing recourse only places a burden on all parties, without any resulting advantage. For the compliant case, the risk with recourse does decrease, so this is the only case where we do observe an advantage to providing recourse. Finally, in Section 6 we corroborate our theoretical results by experiments, in which we observe the risk increase for a large majority of the experiments both on synthetic data and on real data.

Not Reliably Beneficial In summary, our findings show that there are many common cases in which recourse is harmful, because it leads to worse classification accuracy. This suggests that instead of debating how to provide recourse, we should rethink whether the current approach to recourse is desirable at all. Notably, there is no escape by pointing to exceptions in which recourse is beneficial, like e.g. our results on strategic classification for the compliant case, or by pointing to specific examples where it is beneficial in practice: if recourse is not reliably beneficial nearly all the time, then it is not suitable to be broadly adopted.

Further Related Work

Causality and Algorithmic Recourse The difference between the defiant and the compliant case has already been noted in the causal algorithmic recourse community. This has lead to counterfactual methods with guarantees for actual improvement of the class probabilities, which ensure that we are closer to the compliant case [START_REF] König | A causal perspective on meaningful and robust algorithmic recourse[END_REF][START_REF] König | Improvement-focused causal recourse (ICR)[END_REF]. However, our results show that, even in the fully compliant case, recourse may still be harmful. More generally, it has been pointed out that users can only act on counterfactual recommendations if these take the causal relation between the user's actions and their features into account [START_REF] Amir-Hossein | Algorithmic recourse: from counterfactual explanations to interventions[END_REF]. Our framework is general enough to express such causal interventions, because they only affect the risk via their effect on the distribution of the data.

Strategic Classification Strategic classification considers the effect of deploying a classifier in an environment with strategic players, who want to change their features in order to influence how they are classified [START_REF] Hardt | Strategic classification[END_REF][START_REF] Levanon | Strategic classification made practical[END_REF][START_REF] Miller | Strategic classification is causal modeling in disguise[END_REF][START_REF] Tsirtsis | Optimal decision making under strategic behavior[END_REF][START_REF] Wang | Linear classifiers that encourage constructive adaptation[END_REF]. This makes the distribution of the data dependent on f as well, because the behavior of the players depends on the classifier f . The more abstract setting in which there can be any dependence between f and the data distribution, has been studied under the heading of performative prediction [START_REF] Perdomo | Performative prediction[END_REF][START_REF] Mofakhami | Performative prediction with neural networks[END_REF]. Our results about strategizing in Section 5 are a special case of strategic classification, in which the behavior of the players is guided by the recourse mechanism. In contrast to previous results that mostly considered how to minimize the risk in f while taking the dependence of f on the distribution into account, our aim is to quantify the difference in the risk when we compare the settings with and without recourse.

Framework and Main Definitions

In this section we formalize the effect of recourse by comparing the risk in the situation without recourse to the risk with recourse applied.

General Framework

We consider binary classification, in which users with corresponding features x from a closed, convex domain X ⊆ R d will be classified into classes Y = {-1, +1}. We assume a model f : X → Y has already been trained. This may be a deterministic classifier, with Y = {-1, +1}, or a probabilistic classifier, with Y = [0, 1], for which f (x) represents the probability that x should be classified as +1. The error of a prediction ŷ ∈ Y with respect to the true label y ∈ Y is measured by a loss function ℓ : Y × Y → R. For instance, for deterministic predictions ŷ ∈ {-1, +1}, the 0/1 loss is ℓ(ŷ, y) = 1{ŷ ̸ = y}, and, for probabilistic predictions ŷ ∈ [0, 1], the log loss or cross-entropy loss is ℓ(ŷ, y)

= 1 2 (1 + y) ln 1 ŷ + 1 2 (1 -y) ln 1 1-ŷ .
In the absence of recourse, the data will consist of pairs (X 0 , Y ) from X × Y with distribution P , and the quality of f is evaluated by its risk

R P (f ) = E (X0,Y )∼P [ℓ(f (X 0 ), Y )].
(Risk without Recourse)

A classifier f * P ∈ arg min f R P (f ), which minimizes the risk, is called Bayes-optimal. For instance, for 0/1 loss, f * P (x 0 ) = sign(P (Y = 1|X 0 = x 0 ) -1 2 ) is Bayes-optimal. Throughout the paper, we take the sign function sign(z) to be +1 if z ≥ 0 and -1 for z < 0.

When we add recourse to the mix, a user first arrives with feature vector X 0 , which is drawn according to the marginal distribution of P on X . Then, depending on the original features X 0 , the specifics of the recourse protocol, and the model f , the user's features are transformed into new features X ∈ X . Here X may be a deterministic function of X 0 , but in general it can also depend on X 0 in a non-deterministic way if the recourse protocol is randomized or when the user's response to recourse is not fully predictable. Finally, a label Y is generated, and we let Q f denote the resulting distribution of (X 0 , X, Y ). The resulting risk is then measured under the marginal distribution of (X, Y ) under Q f :

R Q f (f ) = E (X,Y )∼Q f [ℓ(f (X), Y )].
(Risk with Recourse)

Thus the marginal distribution of X 0 under Q f is always the same as under P . Note further that f influences the risk with recourse in two ways: directly via its predictions f (X) and indirectly via its effect on the distribution Q f . Except for Section 5 we will think of f as fixed, and we will simplify notation by writing

Q instead of Q f .
As motivated in the introduction, we care about the accuracy of classifiers at the population level. This is measured by the risk, so we will say that recourse is beneficial if the risk under Q is smaller than the risk under P , and harmful otherwise.

Specializing the Framework

The framework above is so general that it can represent any mechanism for providing recourse. In order to say something concrete, we have to specialize it further.

Effect on the Label Distribution Naively, we might expect that changing the user's features from X 0 to X would also change their label distribution from P (Y |X 0 ) to P (Y |X), but what actually happens depends on the underlying causal effect of providing recourse [START_REF] Miller | Strategic classification is causal modeling in disguise[END_REF][START_REF] König | Improvement-focused causal recourse (ICR)[END_REF], and in general any effect on the label distribution is possible. We will focus on two extreme cases which differ in whether individuals fully comply with or fully defy this naive expectation:

(Compliant) Q(Y | X 0 , X) = P (Y | X).
The change in features causes a true change in label probability.

(Defiant) Q(Y | X 0 , X) = P (Y | X 0 ).
The user only changes their features, without altering their label probability.

The defiant case has also been referred to as "gaming"1 [START_REF] König | Improvement-focused causal recourse (ICR)[END_REF][START_REF] Perdomo | Performative prediction[END_REF]. It is illustrated well by the following example by [START_REF] König | Improvement-focused causal recourse (ICR)[END_REF]: consider a classifier which classifies whether a patient is infected with Covid based on their symptoms. Then taking cough drops to suppress coughing may change the classification without changing the true probability of being infected.

Recourse Mechanism We will think of class +1 as being favorable to the users, while class -1 is undesirable to them. For instance, +1 might represent a bank loan being granted, while -1 means that the loan application is rejected. Whenever a user with features X is classified as f (X) = -1 by a deterministic classifier, they may request recourse. Many prominent approaches [START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the GDPR[END_REF][START_REF] Ustun | Actionable recourse in linear classification[END_REF][START_REF] Amir-Hossein | Model-agnostic counterfactual explanations for consequential decisions[END_REF]Pawelczyk et al., 2022a) to algorithmic recourse provide the user with a counterfactual explanation X CF = φ(X 0 ) which is the solution to an optimization problem of the form

X CF ∈ arg min z∈X : f (z)=+1 c(X 0 , z), (1)
where c(x 0 , z) models the cost for the user of moving from x 0 to z. This can describe many different cost mechanisms, and can even be used to express constraints like monotonicity in an Age feature or consistency with a causal model, by assigning large cost to any z that violates the constraints. For the optimization problem in (1) to be well defined, we need to assume that the set

{x ∈ X | f (x) = +1} is closed. (2)
A consequence of this, is that a point on the decision boundary of a classifier will be classified as class +1. So, in order for f * P to satisfy this condition for 0/1 loss, it matters that we defined sign(0) = +1 above. For many of our results, we will further assume that the cost c(x 0 , z) increases monotonically with the distance ∥zx 0 ∥,

which means that larger changes require more effort from the user. Under this assumption, φ always maps users x 0 in the negative class to the decision boundary; for users in the positive class, recourse does not do anything and φ(x 0 ) = x 0 . (See Lemma 6 in Appendix A.) If the user implements the counterfactual explanation exactly, then X = X CF , but they might also deviate from it in a stochastic way, which would make X a noisy approximation of X CF (Pawelczyk et al., 2022b). For simplicity, we will focus on the noiseless case with X = X CF . We do explicitly take into account the fact that not all users might receive recourse and that each user has a choice in whether to implement it. Let B ∈ {0, 1} be an indicator variable for whether recourse is received and implemented, with conditional probability

Pr(B = 1 | X 0 ) = r(X 0 ). It then follows that X = (1 -B)X 0 + BX CF = (1 -B)X 0 + Bφ(X 0 ) . Note that, when f (X 0 ) = +1, we always have X = X 0 irrespective of B, because φ(X 0 ) = X 0 as mentioned above.
Some examples of possible r functions are:

• r(x 0 ) = 1. All users implement recourse;

• r(x 0 ) = 1{∥x 0φ(x 0 )∥ ≤ D} for some D > 0. Only those users within distance D of the decision boundary implement recourse;

• r(x 0 ) = e -∥x 0 -φ(x 0 )∥ 2 2σ 2
for some σ 2 > 0. All users implement recourse with some probability and that probability is exponentially decreasing in the squared distance they have to cover, with a bandwidth σ 2 .

Risk Increase for the Bayes-Optimal Classifier

In this section we present our first main result, which relates the risk with recourse under Q to the risk without recourse under P . The result implies that the risk with recourse is larger, because recourse will move data from a region where the prediction is relatively certain, for example P (Y = -1|X 0 ) = 0.9, to the decision boundary, where things are the least certain, because P (Y = +1|X) = 1/2. We also illustrate this in an example with Gaussian data. The proofs and additional details for the example in this section can be found in Appendix B.

Theorem 1 (Bayes-Optimal Classifier Risk Increase). Let ℓ be the 0/1 loss, and assume the setting of Section 2.2 (i.e., (1), ( 2), ( 3)). Suppose that P (Y = 1|X 0 = x) = 1 2 for all x on the decision boundary of f . Then (a) For the defiant case,

R Q (f * P ) = P (B = 1, Y = -1) -P (B = 1, f * P (X 0 ) ̸ = Y ) + R P (f * P ) ≥ R P (f * P ); (4) (b) For the compliant case, R Q (f * P ) = 1 2 P (B = 1, f * P (X 0 ) = -1) -P (B = 1, f * P (X 0 ) = -1, Y = 1) + R P (f * P ) ≥ R P (f * P ). (5)
Both inequalities are strict if P (B = 1, f * P (X 0 ) = -1) > 0, i.e. if the probability of recourse in the negative class is non-zero. Theorem 1 gives an explicit expression for the risk with recourse when f * P is the Bayes classifier for P . Under very general conditions, it shows that providing recourse always increases the risk, for any recourse probability function r and any monotonically increasing cost function c!

Gaussian Example

We proceed with a simple example that can be analyzed in closed form and plotted visually. We assume the data is generated as follows. Let P (X 0 | Y = y) be N (µ, Σ) for y = +1 and N (ν, Σ) for y = -1 for positive definite Σ, with equal prior class probabilities P (Y = -1) = P (Y = +1) = 1 2 . For simplicity we will assume that ∥µ∥ Σ -1 = ∥ν∥ Σ -1 and set θ := Σ -1 (µν). Then the optimal classifier is known to be f * P (x 0 ) = sign(x ⊤ 0 θ), and the Bayes risk can be expressed in terms of the distribution function Φ of a standard normal distribution: R P (f * P ) = Φ(-1 2 ∥µ -ν∥ Σ -1 ). For Euclidean cost c(x 0 , z) = ∥x 0 -z∥, providing recourse boils down to projecting onto the hyperplane {x ∈ X | x ⊤ θ = 0} and this projection can be expressed analytically by a linear transformation φ(x 0 ) = I -θθ ⊤ ∥θ∥ 2 x 0 . We see the effect of providing recourse on the data distribution and the risk for the compliant case in Figure 2. We have taken µ = (+1, +1) ⊤ , ν = (-1, -1) ⊤ and Σ = ( 1 0.5 0.5 1 ), and set r(x 0 ) = 1. In this case, R P (f * P ) = Φ(-1 2 ∥µ -ν∥ Σ -1 ) ≈ 0.1. The figure also shows empirically that the risk increases, which matches the prediction by Theorem 1 that

R Q (f * P ) = 1 4 + 1 2 Φ(-1 2 ∥µ -ν∥ Σ -1 ) ≈ 0.31. The defiant case is not shown, because it would result in a similar picture, but with R Q (f * P ) = 1 2 . +1 correct -1 correct +1 wrong -1 wrong R P (f * P ) = 0.11 R Q (f * P ) = 0.30

Risk Increase for Probabilistic Classifiers

In practice, we do not have direct access to the Bayes-optimal classifier and the classifier is learned from data. In this section, we therefore drop the requirement that the classifier is exactly Bayes-optimal. We will further consider probabilistic classifiers g : X → [0, 1]. Thresholding g then leads to a binary classifier f (x) = sign(g(x) -1 2 ). We will compare the risk with recourse to the risk without recourse, first for the 0/1 loss and then for a class of surrogate losses that includes the cross-entropy loss. The assumptions we make differ, but in both cases the conclusion is that the risk with recourse exceeds the risk without recourse when g is sufficiently accurate. The proofs for this section are presented in Appendix C.

4.1 Risk Increase for the 0/1 loss We again focus on the 0/1 loss first. We can handle the defiant case without further assumptions. But for the compliant case we require that g is highly accurate in the sense that its decision boundary is close to Bayes-optimal. A simple sufficient requirement would be that there exists ε ≥ 0 such that

1 2 -P (Y = 1 | X 0 = x) ≤ ε for all x such that g(x) = 1/2. (A)
This gives a uniform control over deviations anywhere along the decision boundary of g. At the cost of a slightly more complicated condition, this uniform bound can be relaxed to an average under the distribution over the points from the negative class that get mapped to the decision boundary of g:

{x0:g(x0)< 1 /2} | 1 2 -P (Y = 1 | X = φ(x 0 ))|P (dx 0 ) ≤ ε. (B)
Assuming g is continuous, it will equal g(x) = 1/2 for all points x on its decision boundary. When φ maps all points x 0 from the negative class to the decision boundary of g, it follows that (A) implies (B).

We are now ready to derive an analogous result to Theorem 1:

Theorem 2 (Probabilistic Classifier Risk Increase, 0/1 loss). Let ℓ be the 0/1 loss. Let g : X → [0, 1] be a continuous, probabilistic classifier, and define f (x) = sign(g(x) -1 2 ). Assume (1), ( 2), (3) from Section 2.2. Then, (a) For the defiant case,

R Q (f ) = P (B = 1, Y = -1) -P (B = 1, f (X 0 ) ̸ = Y ) + R P (f ). Moreover, R Q (f ) ≥ R P (f ) if and only if P (Y = -1 | B = 1, f (X 0 ) = -1) ≥ 1 2 . ( 6
)
If we additionally assume that g satisfies (B) with 0 ≤ ε ≤ 1 2 , then (b) For the compliant case, R Q (f ) is lower and upper bounded by

( 1 2 ± ε)P (B = 1, f (X 0 ) = -1) + P (f (X 0 ) = +1, Y = -1) + P (B = 0, f (X 0 ) = -1, Y = 1). Moreover, R Q (f ) ≥ R P (f ) if P (Y = -1 | B = 1, f (X 0 ) = -1) ≥ 1 2 + ε. (7)
Equations ( 6) and ( 7) express that the class -1 is actually more likely (with a margin of ε) conditional on the set of points in the negative class that accept recourse. This will be satisfied when f is a reasonably accurate classifier. The intuition is that in this case moving points to the decision boundary is harmful, because they are more likely to be misclassified there. We also note that, for ε = 0, f will be equal to the Bayes-optimal classifier, and the condition is always satisfied, so we recover the conclusion from Theorem 1 that the risk will always increase.

Risk Increase for Surrogate Losses

In this section, we investigate the scenario in which the loss is not the 0/1 loss, but rather a surrogate loss. We are primarily thinking of the cross-entropy loss, as defined in Section 2, but our result also applies to any other loss for probabilistic predictions ŷ ∈ [0, 1] which is such that ℓ(1/2, -1) = ℓ(1/2, +1) is constant.

Theorem 3 (Probabilistic Classifier Risk Increase, Surrogate Loss). Let ℓ : [0, 1] × {-1, +1} → R be any loss such that ℓ(1/2, -1) = ℓ(1/2, +1) = c for some constant c. Let g : X → [0, 1] be a continuous, probabilistic classifier, and define f (x) = sign(g(x) -1 2 ). Further assume (1), ( 2), (3) from Section 2.2. Then, both for the defiant and for the compliant case, we have R Q (g) ≥ R P (g) if and only if

E (X0,Y )∼P B∼Bernoulli(r(X0)) [ℓ(g(X 0 ), Y ) | f (X 0 ) = -1, B = 1] ≤ c. (8)
Condition 8 means that, on average over users from the negative class who receive recourse, the loss should be lower than the value of the loss at the decision boundary. This means that g should be a reasonably accurate classifier, which performs better on this group than simply predicting 1/2. But it is much weaker than requiring that g should be close to Bayes-optimal, as we did in Theorems 1 and 2. We can get away with this weaker requirement, because, at the decision boundary, g(x) = 1/2 and therefore the loss is c regardless of the underlying distribution of Y . This is also the reason that the defiant and the compliant case coincide.

Strategic Classification

So far we have assumed that the classifier f was fixed, but when the party deploying f knows in advance that they will need to provide recourse, they have an incentive to strategically choose f in order to minimize the resulting risk under Q. In this section, we study the result of strategizing for both the defiant and compliant scenario. Before presenting our results, we first introduce the part of the setup that is common to both. At the end of the section, we reflect on our findings in a short discussion.

Common Setup

Throughout this section we focus on binary classifiers f : X → {-1, +1} with the 0/1 loss. And, since f is now variable, we write Q f and φ f instead of Q and φ. We assume that anyone either accepts or rejects recourse deterministically, i.e. that r(x 0 ) ∈ {0, 1} for all x 0 . And we also assume that the classifier f is selected from a restricted class of functions F. Under the effect of recourse, F transforms into

F φ := {x 0 → f (φ f (x 0 )) | f ∈ F} .
We say that F is invariant under recourse if, for any f ∈ F, there exists a unique f ′ ∈ F such that f ′ with recourse is equivalent to f without recourse, i.e. f ′ (φ f ′ (x 0 )) = f (x 0 ) for all x 0 . This implies, in particular, that F φ = F. As a concrete example, one can think of linear classification, with recourse defined at bringing any point with distance less than D > 0 to the positive class. In this example, shifting the original classifier by D orthogonally to the decision boundary in the direction of the negative class gives another equivalent classifier: it is thus invariant under recourse. Details for this example and another one are provided in Appendix D.

Defiant Case

In the defiant case, the setting above implies that providing recourse does not change the risk:

Theorem 4 (Strategizing in the Defiant Case). Let ℓ be the 0/1 loss, assume (1), ( 2), (3) from Section 2.2 with r(x 0 ) ∈ {0, 1} for all x 0 ∈ X , and suppose F is invariant under recourse. Then, providing recourse in the defiant case does not change the risk when the party deploying the classifier strategizes to minimize their risk over F:

min f ∈F R Q f (f ) = min f ∈F R P (f ) .
Intuitively, the reason is that in the defiant case it is strategically optimal to maintain the original decision boundary, because users do not really change upon receiving recourse. This is possible when F is recourse invariant, because then there is always a function available that compensates for the effect of recourse.

Recourse therefore has no effect on the final decisions, but instead only places a burden on users who have to implement it and on the party deploying the classifier, which has to provide a recourse mechanism. In this case, recourse therefore has only negative effects, and may be considered harmful. We prove Theorem 4 in Appendix D.

Compliant Case

In the compliant case, the situation is different and strategizing can actually improve the risk. We require the following definition.

Table 1: Estimated risks on synthetic data sets. Lower risk is bold.

Moons data Circles data Gaussians data Definition 1. Suppose F is recourse invariant, and let f ∈ arg min f ∈F R P (f ) be a minimizer of the risk without recourse. Let f ′ ∈ F be the (unique) classifier such that f ′ (φ f ′ (x 0 )) = f (x 0 ) for all x 0 ∈ X and define γ to be,

R P R Q R P R Q R P R Q Logistic Regression (
γ := E (X0,Y )∼P [ℓ(f (X 0 ), Y )] - E (X0,Y )∼Q f ′ [ℓ(f (X 0 ), Y )] .
Here, the function f ′ compensates the effect of giving recourse for the original classifier f , and it exists by recourse invariance. The quantity γ measures the change in risk when we fix the classifier to be f , but the data are either generated by P (no recourse) or Q f ′ (recourse for the classifier f ′ ). Intuitively, γ measures the effect of recourse on the distribution of users when the strategy is to choose a function f ′ that compensates for the effect of recourse. We generally expect recourse to move users further into the positive class, and therefore to make it more certain that their class label will indeed be Y = +1, which means that γ would be positive. A detailed example is provided in Appendix D.

Theorem 5 (Strategizing in the Compliant Case). Let ℓ be the 0/1 loss, assume (1), ( 2), (3) from Section 2.2 and suppose F is invariant under recourse. Let γ be as in Definition 1. Then, the risk after providing recourse in the compliant case can be bounded in terms of the risk without recourse when the party deploying the classifier strategizes to minimize their risk over F,

min f ∈F R Q f (f ) ≤ R Q f ′ (f ′ ) = min f ∈F R P (f ) -γ,
where f ′ is as in Definition 1.

When γ is positive, this shows that providing recourse will be beneficial. In Appendix D, we prove Theorem 5 and expand the example of Section 3.1 by showing that γ > 0 in that case.

Discussion

We observe that both in the defiant and in the compliant case, an appealing strategy for the party deploying the classifier is to compensate for the effect of recourse by changing their classifier in a way that maintains the original decision boundary. This implies that all users get classified exactly the same way as without recourse, and the only effect of recourse is to change the conditional distribution of Y . For instance, in a bank loan setting, the same customers would get the loan, but some customers might be required to reduce their probability of defaulting before getting it.

R P (f ) = 0.09 R Q (f ) = 0.30 R P (f ) = 0.19 R Q (f ) = 0.26 R P (f ) = 0.13 R Q (f ) = 0.33
P R Q R P R Q R P R Q R P R Q R P R Q R P R Q R P R Q R P R Q R P R Q LR 0.

Experiments

In addition to our theoretical results, we perform several experiments that showcase the possible increase in risk by providing recourse. We conduct these on synthetic data and real data. In both cases we generate Y according to the compliant setting, and recourse is provided for all x 0 that are classified as class -1. Further details for all the experiments are available in Appendix E.

Synthetic Data

The synthetic data consist of the 3 datasets shown in Figure 3, all in 2 dimensions: a Moons dataset, which consists of two translated semi-circles with Gaussian noise; a Circles dataset, which consists of two nested circles with Gaussian noise; and a final dataset consisting of 2 Gaussians with different means and covariances. Counterfactuals for c(x 0 , z) = ∥zx 0 ∥ were computed by a brute force search to find the closest point z with f (z) = +1 from a dense grid over X .

A summary of the estimated risks for a variety of classifiers can be seen in Table 1. We observe that the risk increases in all cases with the exception of logistic regression on the Circles dataset. This happens because logistic regression has a linear decision boundary, which is severely inappropriate for this data. Without recourse, almost half of the class +1 is misclassified, because the linear boundary cuts both circles. If the points of the outer circle, which are of class -1, are projected onto this line, a large portion will land inside the inner circle, where the conditional probability of class +1 will be significantly larger than 1 2 .

Real Data

For the real datasets we use the Give me Credit, Census Income, and Home Equity Line of Credit (HELOC) datasets, from the CARLA Python package [START_REF] Pawelczyk | CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms[END_REF]. All features were normalized to [0, 1]. We compare various classifiers, and 3 counterfactual methods: Wachter's method [START_REF] Wachter | Counterfactual explanations without opening the black box: Automated decisions and the GDPR[END_REF], the Growing Spheres method [START_REF] Laugel | Inverse classification for comparison-based interpretability in machine learning[END_REF], and Counterfactual Genetic Search (CoGS) [START_REF] Virgolin | On the robustness of sparse counterfactual explanations to adverse perturbations[END_REF]. The main challenge on real data is that we do not have access to the true conditional distribution, P (Y | X 0 ). This distribution is needed to sample Y after obtaining X = φ(X 0 ) through recourse.

To circumvent this issue we reserve a large portion of the data to train a calibrated classifier for the conditional probabilities.

A summary of the estimated risks can be seen in Table 2. Again, we see that in most cases the risk increases. Most exceptions occur in the Credit dataset. A possible explanation here is that the classes are very unbalanced, with class -1 appearing only 6.8% of the time. This may lead to low precision P (Y = -1 | f (X 0 ) = -1), because there are many positive examples that can be misclassified as negative. Since the precision should be high in order to satisfy the condition in (7), as we have

P (Y = -1 | f (X 0 ) = -1, B = 1) = P (Y = -1 | f (X 0 ) = -1
) by giving recourse to every point, this opens up the possibility that recourse improves the risk.

Conclusion

We demonstrated, analytically and empirically, that in many cases the risk will increase when recourse is provided. This implies that recourse can be harmful at the population level, and therefore for a large group of users. In such cases, alternative types of explanations might be called for. One interesting alternative direction is the existing work on contestability, which addresses the question of whether an algorithmic decision is correct according to common sense, moral or legal standards [START_REF] Freiesleben | The intriguing relation between counterfactual explanations and adversarial examples[END_REF]. As a possibility for future work, our framework might be extended by also accounting for the cost incurred by the users when implementing recourse, e.g. by adding a scaled version of c(X 0 , X) to R Q (f ). Assuming positive costs, this would make recourse even less appealing, and lead to the conclusion that it is harmful in an even larger number of cases. Another extension, which would be more interesting to explore, would be to apply our framework in cases where the users and the party deploying the classifier have different loss functions. Then the relation between f and Bayes-optimal decisions for the user's loss would be broken, which might lead to different conclusions.

A Proofs of Section 2

Recall that, for any x 0 ∈ X , we choose

φ(x 0 ) ∈ arg min z∈X : f (z)=+1 c(x 0 , z) . Lemma 6. Assume that {z ∈ X | f (z) = +1} is a closed subset of R d ,
and that for any fixed x 0 , c(x 0 , z) is increasing with ∥x 0 -z∥. Then φ(x 0 ) belongs to the boundary of {z ∈

X | f (z) = +1} for all x 0 ∈ X such that f (x 0 ) = -1 and φ(x 0 ) = x 0 if x 0 belongs to {z ∈ X | f (z) = +1}.
Proof. First, we remark that c(x 0 , z) is minimized by z = x 0 , whenever

x 0 ∈ {z ∈ X | f (z) = +1}, which shows that φ(x 0 ) = x 0 for all x 0 in {z ∈ X | f (z) = +1}.
Moving towards the case of x 0 such that f

(x 0 ) = -1. Let us set x 1 = φ(x 0 ) and A = {z ∈ X | f (z) = +1}.
By contradiction, assume that x 1 does not belong to the boundary of A. Since by construction x 1 ∈ A, then we must have x 1 ∈ A o , the interior of A. Therefore, there exists ρ > 0 such that the open ball B(x 1 , ρ) is fully included in A. Let us construct x 2 , the intersection point between segment [x 0 , x] and the closed sphere centered at x of radius ρ/2. We know that x 2 ∈ A, and

∥x 0 -x 2 ∥ = ∥x 0 -x 1 ∥ -ρ/2 < ∥x 0 -x 1 ∥ .
Since c(x 0 , z) is increasing with ∥x 0 -z∥, c(x 0 , x 2 ) < c(x 0 , x 1 ). This contradicts the definition of x 1 and concludes the proof.

B Further Details for Section 3

Before we start the proof of the main result in Section 3, we will introduce notation and some additional results. The conditional distributions of Y given X 0 will be denoted by

p + (x) := P (Y = +1 | X 0 = x) = 1 -P (Y = -1 | X 0 = x) =: 1 -p -(x).
Now, we will prove a general result about expressing the risk under Q, of which Theorem 1 is a consequence.

Every expectation E will be with respect to P in this section.

Lemma 7. Let ℓ be a loss function with ℓ(y, y) = 0, and assume the setting of Section 2.2 (i.e., (1), ( 2), (3)). Suppose that P (Y = 1|X 0 = x) = 1 2 for all x on the decision boundary of f . Then (a) For the defiant case,

R Q (f ) = ℓ(1, -1)P (Y = -1)E [r(X 0 )|Y = -1] + E [(1 -r(X 0 ))ℓ(f (X 0 ), Y )] ; (9)
(b) For the compliant case,

R Q (f ) = ℓ(1, -1)E [r(X 0 )p -(φ(X 0 ))] + E [(1 -r(X 0 ))ℓ(f (X 0 ), Y )] . (10)
Proof. Before distinguishing between the 2 cases, we expand the expression for the risk under Q as

R Q (f ) = X 2 ×Y ℓ(f (x), y)Q(dy | x, x 0 )Q(dx|x 0 )P (dx 0 ) = X ×Y r(x 0 )ℓ(f (φ(x 0 )), y)Q(dy | φ(x 0 ), x 0 )P (dx 0 ) + X ×Y (1 -r(x 0 ))ℓ(f (x 0 ), y)P (dy | x 0 )P (dx 0 ) = ℓ(1, -1) X r(x 0 )Q(Y = -1 | φ(x 0 ), x 0 )P (dx 0 ) (since f (φ(x 0 )) = 1) + E [(1 -r(X 0 ))ℓ(f (X 0 ), Y )] .
We focus now on the integral in the first term.

From this we see that for θ = Σ -1 (µν) and θ 0 = -1 2 (∥µ∥ 2 Σ -1 -∥ν∥ 2 Σ -1 ) the Bayes classifier is given by f * P (x) = sign(x ⊤ θ + θ 0 ). We can now calculate the Bayes risk by first rewriting this risk as

R P (f * P ) = 1 2 P (f * P (X 0 ) = -1 | Y = 1) + 1 2 P (f * P (X 0 ) = 1 | Y = -1) = 1 2 P (X ⊤ 0 θ + θ 0 < 0 | Y = 1) + 1 2 P (X ⊤ 0 θ + θ 0 ≥ 0 | Y = -1). (16)
As X 0 is Gaussian, conditional on Y , we know that X ⊤ 0 θ + θ 0 is also Gaussian. For Y = 1, we get N (µ ⊤ θ + θ 0 , ∥θ∥ 2 Σ -1 ) and for Y = -1 we get N (ν ⊤ θ + θ 0 , ∥θ∥ 2 Σ -1 ). Translating and rescaling allows us to rewrite the probabilities in ( 16) in terms of the CDF Φ of the standard normal distribution,

P (X ⊤ 0 θ + θ 0 < 0 | Y = 1) = Φ -µ ⊤ θ -θ 0 ∥θ∥ Σ -1 = Φ -∥µ∥ 2 Σ -1 + µ ⊤ Σ -1 ν + 1 2 (∥µ∥ 2 Σ -1 -∥ν∥ 2 Σ -1 ) ∥µ -ν∥ Σ -1 = Φ -1 2 ∥µ -ν∥ 2 Σ -1 ∥µ -ν∥ Σ -1 = Φ(-1 2 ∥µ -ν∥ Σ -1 ).
Analogously, we would get

P (X ⊤ 0 θ + θ 0 ≥ 0 | Y = -1) = Φ(-1 2 ∥µ -ν∥ Σ -1
). Combining the two probabilities gives the desired result.

C Proofs of Section 4

In this section we present all the previous and additional results of Section 4.

C.1 Proof of Theorem 2

Theorem 2 (Probabilistic Classifier Risk Increase, 0/1 loss). Let ℓ be the 0/1 loss. Let g : X → [0, 1] be a continuous, probabilistic classifier, and define f (x) = sign(g(x) -1 2 ). Assume (1), ( 2), (3) from Section 2.2. Then, (a) For the defiant case,

R Q (f ) = P (B = 1, Y = -1) -P (B = 1, f (X 0 ) ̸ = Y ) + R P (f ). Moreover, R Q (f ) ≥ R P (f ) if and only if P (Y = -1 | B = 1, f (X 0 ) = -1) ≥ 1 2 . ( 6
)
If we additionally assume that g satisfies (B) with 0 ≤ ε ≤ 1 2 , then (b) For the compliant case, R Q (f ) is lower and upper bounded by

( 1 2 ± ε)P (B = 1, f (X 0 ) = -1) + P (f (X 0 ) = +1, Y = -1) + P (B = 0, f (X 0 ) = -1, Y = 1). Moreover, R Q (f ) ≥ R P (f ) if P (Y = -1 | B = 1, f (X 0 ) = -1) ≥ 1 2 + ε. (7)
Proof. Defiant Case: We again use Lemma 7 which gives us

R Q (f ) = P (Y = -1) E[r(X 0 ) | Y = -1] + E[(1 -r(X 0 )1(f (X 0 ) ̸ = Y )] = P (Y = -1, B = 1) + P (f (X 0 ) ̸ = Y ) -P (f (X 0 ) ̸ = Y, B = 1) = P (Y = -1, B = 1) -P (f (X 0 ) ̸ = Y, B = 1) + R P (f ).
To derive the second claim, we upper bound R P (f ) by R Q (f ). We see that the R P (f ) term drops on both sides and we are left with

P (f (X 0 ) ̸ = Y, B = 1) ≤ P (Y = -1, B = 1)
Proof. Let I = 1{f (X 0 ) = -1, B = 1} be the indicator for recourse in the negative class. Then, since φ(X 0 ) lies on the decision boundary (DB) when X 0 is in the negative class,

R Q (g) = E (X,Y )∼Q [ℓ(g(X), Y )] = E (X0,Y )∼Q [ℓ(g(φ(X 0 )), Y )I] + E (X,Y )∼Q [ℓ(g(X), Y )(1 -I)] = E (X0,Y )∼Q [ℓ(1/2, Y )I] + E (X0,Y )∼P [ℓ(g(X 0 ), Y )(1 -I)] (φ(X 0 ) on the DB) = cP (f (X 0 ) = -1, B = 1) + E (X0,Y )∼P [ℓ(g(X 0 ), Y )(1 -I)]
(by definition of c)

≥ E P [ℓ(g(X 0 ), Y )I] + E (X0,Y )∼P [ℓ(g(X 0 ), Y )(1 -I)] = R P (g),
where the inequality is equivalent to (8).

D Additional results and proofs for

f θ,θ ′ 0 (φ(f θ,θ ′ 0 , x 0 )) = f θ,θ0 (x 0 ) for all x 0 ∈ X when θ ′ 0 = θ 0 -D∥θ∥.
To see this, note that the (signed) distance from x 0 to the decision boundary for f

θ,θ ′ 0 is -x ⊤ 0 θ-θ ′ 0 ∥θ∥
. Hence the following are all equivalent:

f θ,θ ′ 0 (φ(f θ,θ ′ 0 , x 0 )) = +1 -x ⊤ 0 θ -θ ′ 0 ∥θ∥ ≤ D x ⊤ 0 θ + θ ′ 0 ≥ -D∥θ∥ x ⊤ 0 θ + θ 0 ≥ 0 f θ,θ0 (x 0 ) = +1.
One can extend this idea to other geometrical shapes:

′ = b + D: f θ,b ′ (φ(f θ,b ′ , x 0 )) = f θ,b (x 0 )
for all x 0 ∈ X .

D.2 Proof of Theorem 4

Theorem 4 (Strategizing in the Defiant Case). Let ℓ be the 0/1 loss, assume (1), ( 2), (3) from Section 2.2 with r(x 0 ) ∈ {0, 1} for all x 0 ∈ X , and suppose F is invariant under recourse. Then, providing recourse in the defiant case does not change the risk when the party deploying the classifier strategizes to minimize their risk over F:

min f ∈F R Q f (f ) = min f ∈F R P (f ) . Proof. Note that in the defiant case Q(Y | X 0 ) = P (Y | X 0 ). We write min f ∈F R Q f (f ) = min f ∈F E (X,Y )∼Q f [ℓ(f (X), Y )] = min f ∈F E (X0,Y )∼Q f [ℓ(f (φ f (X 0 )), Y )] = min f ∈F E (X0,Y )∼P [ℓ(f (φ f (X 0 )), Y )] (By defiant case) = min f ∈Fφ E (X0,Y )∼P [ℓ(f (X 0 ), Y )] (by definition of F φ ) = min f ∈F E (X0,Y )∼P [ℓ(f (X 0 ), Y )] (since F = F φ ) min f ∈F R Q f (f ) = min f ∈F R P (f ) .
(X 0 |Y = -1) = N (ν, Σ). Then f = f θ,θ0 for θ = Σ -1 (µ -ν) and θ 0 = -1 2 (µ + ν) ⊤ Σ -1 (µ -ν)
is the Bayes optimal classifier. See Section B.1 for a justification. The compensating classifier is given by f

′ = f θ,θ ′ 0 for θ ′ 0 = θ 0 -D∥θ∥.
Then recourse for f ′ affects users in a band of width D∥θ∥ which lies just in the positive class according to f :

A = {x : 0 ≤ x ⊤ θ + θ 0 < D∥θ∥}, and γ = A P (Y = -1 | X 0 = x 0 ) -P (Y = -1 | X 0 = φ f ′ (x 0 )) P (dx 0 ) = A P (Y = -1 | X 0 = x 0 ) -P Y = -1 | X 0 = x 0 - f ′ (x 0 ) ∥θ∥ 2 θ P (dx 0 ).
Again by Section B.1, we can write the posterior distribution as

P (Y = -1|X 0 = x) = 1 1 + e θ ⊤ x+θ0 , Now, we write θ ⊤ φ(f ′ , x 0 ) + θ 0 = θ ⊤ x 0 + θ 0 -(θ) ⊤ f ′ (x 0 ) ∥θ∥ 2 θ = θ ⊤ x 0 + θ 0 + 1 , since f ′ (x 0 ) = -1. Thus, θ ⊤ φ f ′ (x 0 ) + θ > θ ⊤ x 0 + θ 0 . Since the mapping t → 1/(1 + exp(t)
) is decreasing, we deduce that γ > 0 in this case.

D.4 Proof of Theorem 5

Theorem 5 (Strategizing in the Compliant Case). Let ℓ be the 0/1 loss, assume (1), ( 2), (3) from Section 2.2 and suppose F is invariant under recourse. Let γ be as in Definition 1. Then, the risk after providing recourse in the compliant case can be bounded in terms of the risk without recourse when the party deploying the classifier strategizes to minimize their risk over F,

min f ∈F R Q f (f ) ≤ R Q f ′ (f ′ ) = min f ∈F R P (f ) -γ,
where f ′ is as in Definition 1.

Proof. As in the defiant case, the proof considers the strategic choice f ′ , which compensates for the effect of recourse in order to maintain the same decision boundary as in the case without recourse. The effect of recourse is then only to change the distribution in a way that is captured by Definition 1. We first notice that

min f ∈F R Q f (f ) ≤ R Q f ′ (f ′ ) holds because f ′ ∈ F. Then we write R Q f ′ (f ′ ) = E (X,Y )∼Q f ′ [ℓ(f ′ (X), Y ))] = E (X0,Y )∼Q f ′ [ℓ(f ′ (φ f ′ (X 0 )), Y )] = E (X0,Y )∼Q f ′ [ℓ(f (X 0 ), Y )] = E (X0,Y )∼P [ℓ(f (X 0 ), Y )] -γ (definition of γ) R Q f ′ (f ′ ) = min f ∈F R P (f ) -γ .

E Details Experimental Setup

All the code to reproduce the experiments and figures in this paper is available in a GitHub repository2 . file provided with the supplementary material. All experiments were performed on a single 32-core CPU node (AMD Rome 7H12) with 64GB of RAM. For all experiments we used the following classifiers from the scikit-learn (version 1.0) library:

• LogisticRegression, with the default parameters, except for class_weigt='balanced'. • GradientBoostingClassifier, with the default parameters, except for n_estimators=10 . • DecisionTreeClassifier, with the default parameters, except for class_weigt='balanced' and max_depth=4. • GaussianNB, with the default parameters.

• RandomForestClassifier, with the default parameters except for class_weigt='balanced', max_depth=4 and n_estimators=10. • QuadraticDiscrimantAnalysis, with the default parameters.

• MLPClassifier, with the default parameters and hidden layers, hidden_layer_sizes=(4,). • MLPClassifier, with the default parameters and hidden layers, hidden_layer_sizes=(4, 4). • MLPClassifier, with the default parameters and hidden layers, hidden_layer_sizes=(8,). • MLPClassifier, with the default parameters and hidden layers, hidden_layer_sizes=(8, 16). • MLPClassifier, with the default parameters and hidden layers, hidden_layer_sizes=(8, 16, 8). The amount of time the experiments need to be run in fill was too long to run multiple iterations to generate error bounds on the estimated risks presented in Tables 1 and2. To circumvent this issue, we upper bound standard error by 1 2 √ Ntest , as the outcome of the risk is in the bounded interval [0, 1]. If the estimated risk before and after recourse is within this error, we highlighted both the risks.

Figure 2 :

 2 Figure 2: Left: Bayes classifier, original predictions; Right: predictions after providing recourse in the compliant case.

Figure 3 :

 3 Figure 3: From left to right: Moons, Circles and Gaussian datasets. The left image for each shows the classifications with gradient boosted trees; the right image shows the effect of giving recourse.

  Section 5 D.1 Examples of classifiers invariant under recourse Let us justify more rigorously the linear classifier example introduced in Section 5. Example 1. Consider the set of linear classifiers F = {f θ,θ0 (x) = sign(x ⊤ θ + θ 0 ) | θ ∈ R d , θ 0 ∈ R} with the convention that sign(z) = +1 for z ≥ 0 and sign(z) = -1 otherwise. If the recourse map is such that any point x 0 within distance D > 0 of the decision boundary of f θ,θ0 gets mapped to the positive class, then this class is invariant under recourse, because

Example 2 .

 2 Consider the spherical classifiers for which f θ,b (x) = +1 if and only if ∥x -θ∥ ≥ b. Then the set F = {f θ,b | θ ∈ R d , b ∈ R + } is invariant under recourse when the recourse map is again such that any point x 0 in the negative class that lies within distance D > 0 of the decision boundary of f θ,b gets mapped to the positive class. This follows because providing recourse has the effect of effectively shrinking b by D, so we can undo this effect by increasing b to b

D. 3

 3 Explicit γ bound Example 3. Let us further specialize the setting of Example 1 to the task of distinguishing between two Gaussians with different means µ, ν ∈ R d and common positive definite covariance matrix Σ. That is, let P (Y = -1) = P (Y = +1) = 1/2, and the data is distributed according to P (X 0 |Y = +1) = N (µ, Σ) and P

E. 1

 1 Synthetic DataFor each of the synthetic data experiments, we generated 5000 training samples and 1000 test samples with balanced classes, i.e. P (Y = +1) = P (Y = -1) = 1 2 . Examples of the results of these experiments can be found in Figures4, 5, and 6.

Figure 4 :Figure 5 :RFigure 6 :

 456 Figure 4: Examples of the effect of giving recourse with various classifiers on the Moons data set. From left to Right, Top to Bottom: LR, QDA, GBT, NB, DT, NN(8, 16).

Table 2 :

 2 Estimated risks on real data sets. Lower risk is bold.

	Wachter	Credit data GS	CoGS	Wachter	Census data GS	CoGS	Wachter	HELOC data GS	CoGS
	R

  17 0.05 0.17 0.05 0.17 0.04 0.21 0.29 0.21 0.33 0.21 0.32 0.29 0.41 0.29 0.41 0.29 0.

	44 0.06 0.06 0.06 0.07 0.06 0.07 0.15 0.04 0.15 0.23 0.15 0.33 0.20 0.21 0.20 0.25 0.20 0.37 0.29 0.12 0.29 0.05 0.29 0.05 0.23 0.21 0.23 0.43 0.23 0.45 0.19 0.25 0.19 0.21 0.19 0.31 0.11 0.06 0.11 0.06 0.11 0.07 0.19 0.78 0.19 0.76 0.19 0.81 0.29 0.44 0.29 0.43 0.29 0.48 0.12 0.06 0.12 0.06 0.12 0.07 0.20 0.78 0.20 0.75 0.20 0.82 0.32 0.46 0.32 0.47 0.32 0.52 0.06 0.06 0.06 0.07 0.06 0.06 0.16 0.26 0.16 0.25 0.16 0.26 0.29 0.47 0.29 0.46 0.29 0.50 0.06 0.06 0.06 0.07 0.06 0.07 0.15 0.30 0.15 0.27 0.15 0.30 0.29 0.47 0.29 0.47 0.29 0.51 0.06 0.06 0.06 0.06 0.06 0.07 0.16 0.34 0.16 0.33 0.16 0.33 0.28 0.44 0.28 0.46 0.28 0.51 0.06 0.06 0.06 0.07 0.06 0.07 0.15 0.36 0.15 0.34 0.15 0.36 0.27 0.42 0.27 0.45 0.27 0.46 NN(8, 16, 8) 0.06 0.06 0.06 0.07 0.06 0.07 0.15 0.36 0.15 0.34 0.15 0.36 0.27 0.42 0.27 0.45 0.27 0.46 GBT DT NB QDA NN(4) NN(4, 4) NN(8) NN(8, 16)

We avoid this terminology in the context of algorithmic recourse, because users may follow a recourse recommendation in good faith and still not change their label probability.

https://github.com/HiddeFok/consequences-of-recourse

Defiant Case: The first term in the expression in the above display becomes X r(x 0 )Q(Y = -1 | φ(x 0 ), x 0 )P (dx 0 ) = X r(x 0 )P (Y = -1 | x 0 )P (dx 0 ) = P (Y = -1) X r(x 0 )P (dx 0 | Y = -1)

Compliant Case: The first term now becomes X r(x 0 )Q(dy | φ(x 0 ), x 0 )P (dx 0 ) = X r(x 0 )P (dy | φ(x 0 ))P (dx 0 )

We are now ready to prove Theorem 1.

Theorem 1 (Bayes-Optimal Classifier Risk Increase). Let ℓ be the 0/1 loss, and assume the setting of Section 2.2 (i.e., (1), ( 2), (3)). Suppose that P (Y = 1|X 0 = x) = 1 2 for all x on the decision boundary of f . Then (a) For the defiant case, R Q (f * P ) = P (B = 1, Y = -1) -P (B = 1, f * P (X 0 ) ̸ = Y ) + R P (f * P ) ≥ R P (f * P );

(b) For the compliant case, R Q (f * P ) = 1 2 P (B = 1, f * P (X 0 ) = -1) -P (B = 1, f * P (X 0 ) = -1, Y = 1) + R P (f * P ) ≥ R P (f * P ).

(5)

Both inequalities are strict if P (B = 1, f * P (X 0 ) = -1) > 0, i.e. if the probability of recourse in the negative class is non-zero.

Proof. For both cases, we will first prove the equality and then show that the expectation is always non-negative for the inequality. From those proofs it can be seen how the strict inequality is derived. We apply Lemma 7 to both cases. Remark that ℓ(1, -1) = ℓ(-1, 1) = 1 and rewrite the common term as

Defiant Case: In this case, we rewrite the first term in (9) to get

) Combining expressions (11) and ( 12) gives the result,

It remains to show that the difference of the first two probabilities is positive. We return to the formulation in terms of expectations and indicator functions. We can rewrite the indicator functions in (13) as

The expectation in (4) now becomes X ×Y r(x 0 )(1(y = -1) -1(f * P (x 0 ) ̸ = y))P (dx 0 , dy)

Now, by f * P being the Bayes optimal classifier we know that p -(x 0 ) ≥ p + (x 0 ) for all x 0 on {f * P = -1}. So, we see that the integral in ( 14) is non-negative.

Compliant Case: We note that p + (φ(x 0 )) = p -(φ(x 0 )) = 1 2 for any x 0 with f * P (x 0 ) = -1, because those points are projected onto the decision boundary by assumption (3) and Lemma 6. The points on the decision boundary of the Bayes classifier are exactly where the probability of being either class is 1 2 , by assumption. The first expectation in (10) can now be written as

(15) We note that the second probability in (15) cancels the second probability (11) partly. First we write the latter probability as 15) and ( 11) into the expression for R

Subtracting both probabilities gives

To derive the necessary inequality, we focus again on the first two probabilities and write this explicitly as an integral. This integral is given by

≥ 0 Where we have used that the on the set

The strict inequality follows by remarking that the difference of the integrand in both integrals of the defiant and compliant case will be strictly positive on some positive probability set, if P (B = 1, f * P = -1) > 0.

B.1 Additional Details Gaussian Example in Section 3.1

In Section 3.1 it is claimed that the Bayes risk can be written as R P (f * P ) = Φ(-1 2 ∥µ -ν∥ Σ -1 ). Here, we show this and additionally derive the Bayes optimal classifier for general µ, ν ∈ R d .

The conditional distribution can be calculated explicitly

We expand the terms

Again, cancelling the common terms gives us

Compliant Case: We apply Lemma 7. Note, that Assumption B and Lemma 6 tell us that on the set

For the first expectation we get the upper bound

). Analogously, for the lower bound we get

). We write the second expectation as follows in this case,

Similarly, for the lower bound we get

Combining expressions ( 17) and ( 18) gives the desired lower and upper bound.

We move to the second claim. This time, we upper bound R P (f ) by the derived lower bound. This gives us

Theorem 3 (Probabilistic Classifier Risk Increase, Surrogate Loss). Let ℓ : [0, 1] × {-1, +1} → R be any loss such that ℓ(1/2, -1) = ℓ(1/2, +1) = c for some constant c. Let g : X → [0, 1] be a continuous, probabilistic classifier, and define f (x) = sign(g(x) -1 2 ). Further assume (1), ( 2), (3) from Section 2.2. Then, both for the defiant and for the compliant case, we have R Q (g) ≥ R P (g) if and only if

Moons dataset The Moons dataset is acquired through the make_moons function from scikit-learn.

A data point X 0 is sampled by first discretizing [0, π) uniformly and drawing one of these points U uniformly, without replacement. Then, sample ε ∼ N (0, σ 2 I 2 ) and construct X 0 by setting

For our examples we selected σ = 0.2.

To re-sample the label Y after providing recourse we calculate the conditional distribution of this model. Let, p be the density of ε. Then, the density of X 0 | Y = +1 and X 0 | Y = -1, denoted by g + and g -respectively, is given by

In our implementation this integral is approximated by a Riemann sum. The conditional distribution now follows,

.

Circles dataset

The Circles dataset is acquired through the make_circles function from scikit-learn. A data point X is sampled by first discretizing [0, 2π) uniformly and drawing one of these points U uniformly, without replacement. Then, sample ε ∼ N (0, σ 2 I 2 ), set λ ∈ (0, 1) and construct X by setting

For our examples we selected σ = 0.2 and λ = 0.6.

To re-sample the label Y after providing recourse we calculate the conditional distribution of this model. Let, p be the density of ε. Then, the density of X 0 | Y = 1 and X 0 | Y = -1, denoted by g + and g -respectively, is given by

In our implementation this integral is approximated by a Riemann sum. The conditional distribution now follows,

.

Gaussians dataset

The Gaussian data points are sampled from 2 Gaussians with different means µ, ν ∈ R 2 and different covariances

The densities of the 2 conditional distributions are given by The conditional distribution is given by the odds between the densities of the 2 gaussians

.

E.2 Real Data

Here, we describe how the experiments for the real data was performed.

Conditional distribution estimation

As mentioned before the main challenge with real data is that we do not have access to P (Y | X 0 ). To circumvent this, we estimate this function as well as possible, by reserving most of the data to train a calibrated classifier. N cond train are used to train this classifier and N cond calib are used to calibrate this classifier. The exact values of the data splits are given in Table 3. Furthermore, we perform a grid search over a large set of parameters using cross validation to find the best performing calibrated classifier. The parameters in the grid search are

• learning_rate: {0.05, 0.15},

• n_estimators: {10, 20, 60},

• subsample: {0.8, 0.9, 1},

• max_depth: {1, 2, 3}.

As a base classifier we use the GradientBoostedClassifier from scikit-learn and we use Platt scaling [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF] to calibrate the probabilities.

Classification and Recourse After a conditional distribution is estimated for each dataset, we train the same set of classifiers as for the synthetic data on N train different data points. Then, counterfactuals are generated using the different methods and using the trained conditional estimated distribution a new class label is sampled for the position at the counterfactual point. The estimated risk is then calculated for the dataset before and after recourse is provided.