text: ∈ × The weak formulation of (??) is as follows. A pair (u , u ) H1(Ω) H1(Ω) 1 2 0 0 of functions is called a weak solution of (??) if ∃ ∈ h , h L2(Ω) s.t. 1 2 ∇ ∇ ∀ ∈ ( u , w) = (h , w) w H1(Ω) ∇ 1 ∇ L2 1 L2 ∀ ∈ 0 (21) ( u , w) = (h , w) w H1(Ω) 2 L2 ∈ 2 L2 0 ∈ (h (x), h (x)) f(x, u (x), u (x)) for a.e. x Ω 1 2 1 2 × To simplify the notation, we denote V := H1(Ω) H1(Ω) and H := × ∗ − × − 0 0 L2(Ω) L2(Ω) with V = H 1(Ω) H 1(Ω). The spaces V and H are equipped with the scalar products (u, v) := (u , v ) + (u , v ) , (h, g) := (h , g ) + (h , g ) V 1 1 H1 2 2 H1 H 1 1 L2 2 2 L2 0 0 ∗ and the corresponding norms. The duality pairing between V and V is given by (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) ϕ, u := ϕ , u + ϕ , u . 1 1 2 2 ⊂ ⊂ ∗ Note that V H V is a Gelfand triple. It can be shown that the set-valued Nemytskii operator given by { ∈ ∈ } N (u) := h H : h(x) f(x, u(x)) a.e. f → CBC is a continuous mapping N : H (H), which is also l -ROSL. If, f (cid:55)→ f in addition, the mapping (s , s ) f(x, s , s ) is L -Lipschitz w.r.t. the ∈ 1 2 1 2 f Euclidean norm for all x Ω, then N is L -Lipschitz as well. f f We can rewrite (??) as an operator inclusion ∈ 0 (∆u , ∆u ) + N (u , u ). (22) 1 2 f 1 2 To comply with the notation in Section ??, we denote F := (∆, ∆) : → ∗ → CBC V V V and F := N : H (H) with one-sided Lipschitz constants − H f ⊂ l = 1 and l = l . As the embedding V H is compact, the continuity V H f of N is, according to Remark ??(i), suﬃcient for the application of Theorem f ??, provided that l < 1/c2 . We stress that, by deﬁnition of the embedding f V H constant c , the quantity 1/c2 is simply the ﬁrst Dirichlet eigenvalue of − V H V H ∆ on Ω. We have seen in the proof of Theorem ?? that the norm (cid:107) (cid:107) (cid:107) (cid:107) − (cid:107) (cid:107) ∈ u 2 = u 2 l u 2 for u V W V f H 21

text: The

text: weak

text: formulation

text: of

text: is

text: as

text: follows.

text: A

text: pair

text: (u

text: u

text: of

text: functions

text: is

text: called

text: a

text: weak

text: solution

text: of

text: if

text: h

text: h

text: s.t.

text: u

text: w)

text: (h

text: w)

text: w

text: u

text: w)

text: (h

text: w)

text: w

text: (h

text: (x),

text: h

text: (x))

text: f(x,

text: u

text: (x),

text: u

text: (x))

text: for

text: a.e.

text: x

text: Ω

text: To

text: simplify

text: the

text: notation,

text: we

text: denote

text: V

text: and

text: H

text: with

text: V

text: H

text: H

text: The

text: spaces

text: V

text: and

text: H

text: are

text: equipped

text: with

text: the

text: scalar

text: products

text: (u,

text: v)

text: (u

text: v

text: (u

text: v

text: (h,

text: g)

text: (h

text: g

text: (h

text: g

text: V

text: H

text: and

text: the

text: corresponding

text: norms.

text: The

text: duality

text: pairing

text: between

text: V

text: and

text: V

text: is

text: given

text: by

text: ϕ,

text: u

text: ϕ

text: u

text: ϕ

text: u

text: Note

text: that

text: V

text: H

text: V

text: is

text: a

text: Gelfand

text: triple.

text: It

text: can

text: be

text: shown

text: that

text: the

text: set-valued

text: Nemytskii

text: operator

text: given

text: by

text: N

text: (u)

text: h

text: H

text: h(x)

text: f(x,

text: u(x))

text: a.e.

text: f

text: CBC

text: is

text: a

text: continuous

text: mapping

text: N

text: H

text: (H),

text: which

text: is

text: also

text: l

text: -ROSL.

text: If,

text: f

text: f

text: in

text: addition,

text: the

text: mapping

text: (s

text: s

text: f(x,

text: s

text: s

text: is

text: L

text: -Lipschitz

text: w.r.t.

text: the

text: f

text: Euclidean

text: norm

text: for

text: all

text: x

text: Ω,

text: then

text: N

text: is

text: L

text: -Lipschitz

text: as

text: well.

text: f

text: f

text: We

text: can

text: rewrite

text: as

text: an

text: operator

text: inclusion

text: (∆u

text: ∆u

text: N

text: (u

text: u

text: f

text: To

text: comply

text: with

text: the

text: notation

text: in

text: Section

text: we

text: denote

text: F

text: CBC

text: V

text: V

text: V

text: and

text: F

text: N

text: H

text: (H)

text: with

text: one-sided

text: Lipschitz

text: constants

text: H

text: f

text: l

text: and

text: l

text: l

text: As

text: the

text: embedding

text: V

text: H

text: is

text: compact,

text: the

text: continuity

text: V

text: H

text: f

text: of

text: N

text: is,

text: according

text: to

text: Remark

text: ??(i),

text: suﬃcient

text: for

text: the

text: application

text: of

text: Theorem

text: f

text: provided

text: that

text: l

text: We

text: stress

text: that,

text: by

text: deﬁnition

text: of

text: the

text: embedding

text: f

text: V

text: H

text: constant

text: c

text: the

text: quantity

text: is

text: simply

text: the

text: ﬁrst

text: Dirichlet

text: eigenvalue

text: of

text: V

text: H

text: V

text: H

text: on

text: Ω.

text: We

text: have

text: seen

text: in

text: the

text: proof

text: of

text: Theorem

text: that

text: the

text: norm

text: u

text: u

text: l

text: u

text: for

text: u

text: V

text: W

text: V

text: f

text: H


text: ∗ (cid:107) · (cid:107) → (cid:107) · (cid:107) because J : (V , ∗) (V, ) is an isometrical isomorphism. W W W From a computational perspective, it may be advantageous to recast the optimization problem (cid:107) (cid:107) ∈ J F (u ) + J h = min! subject to h N (u ) W V n W W f n with pointwise inequality constraints into an unconstrained dual problem. · · Lemma 17. Let X be a Hilbert space with inner product ( , ) and norm (cid:107) · (cid:107) ∈ CBC X , and let A (X). Then the optimization problems X (cid:107) (cid:107) ∈ 1 x 2 = min! subject to x A (24) 2 X and (cid:107) (cid:107) − 1 x 2 + σ ( x, A) = min! (25) 2 X X on the entire space X possess the same unique solution. Proof. It is well-known (see, e.g., [?, Proposition 7.4]) that (??) possesses a ∗ ∈ unique solution x A, which is also the unique solution of the variational inequality − ≥ ∀ ∈ (x, a x) 0 a A (26) X (cid:55)→ (cid:107) (cid:107) − in A. As the function x 1 x 2 + σ ( x, A) is convex, lower semi- 2 X X continuous and coercive, problem (??) possesses at least one solution. Any ∈ solution x∗ X of (??) satisﬁes the necessary optimality condition ∈ − − 0 x∗ ∂σ ( x∗, A), X · · where ∂σ ( , ) denotes the subdiﬀerential w.r.t. the ﬁrst variable. This im- X plies ∈ − − ⊂ x∗ ∂σ ( x∗, A) = argmax ∈ ( x∗, a) A, (27) X a A X 23 ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: because

text: J

text: (V

text: (V,

text: is

text: an

text: isometrical

text: isomorphism.

text: W

text: W

text: W

text: From

text: a

text: computational

text: perspective,

text: it

text: may

text: be

text: advantageous

text: to

text: recast

text: the

text: optimization

text: problem

text: J

text: F

text: (u

text: J

text: h

text: min!

text: subject

text: to

text: h

text: N

text: (u

text: W

text: V

text: n

text: W

text: W

text: f

text: n

text: with

text: pointwise

text: inequality

text: constraints

text: into

text: an

text: unconstrained

text: dual

text: problem.

text: Lemma

text: Let

text: X

text: be

text: a

text: Hilbert

text: space

text: with

text: inner

text: product

text: and

text: norm

text: CBC

text: X

text: and

text: let

text: A

text: (X).

text: Then

text: the

text: optimization

text: problems

text: X

text: x

text: min!

text: subject

text: to

text: x

text: A

text: X

text: and

text: x

text: σ

text: x,

text: A)

text: min!

text: X

text: X

text: on

text: the

text: entire

text: space

text: X

text: possess

text: the

text: same

text: unique

text: solution.

text: Proof.

text: It

text: is

text: well-known

text: (see,

text: e.g.,

text: Proposition

text: that

text: possesses

text: a

text: unique

text: solution

text: x

text: A,

text: which

text: is

text: also

text: the

text: unique

text: solution

text: of

text: the

text: variational

text: inequality

text: (x,

text: a

text: x)

text: a

text: A

text: X

text: in

text: A.

text: As

text: the

text: function

text: x

text: x

text: σ

text: x,

text: A)

text: is

text: convex,

text: lower

text: semi-

text: X

text: X

text: continuous

text: and

text: coercive,

text: problem

text: possesses

text: at

text: least

text: one

text: solution.

text: Any

text: solution

text: x∗

text: X

text: of

text: satisﬁes

text: the

text: necessary

text: optimality

text: condition

text: x∗

text: ∂σ

text: x∗,

text: A),

text: X

text: where

text: ∂σ

text: denotes

text: the

text: subdiﬀerential

text: w.r.t.

text: the

text: ﬁrst

text: variable.

text: This

text: im-

text: X

text: plies

text: x∗

text: ∂σ

text: x∗,

text: A)

text: argmax

text: x∗,

text: a)

text: A,

text: X

text: a

text: A

text: X

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ≥ Remark 5. The deﬁnition of an ROSL mapping with constant l 0 is for- mally similar to that of a monotone mapping. Nevertheless, ROSL and mono- tone mappings have fundamentally diﬀerent properties. Monotone mappings on Hilbert spaces are single-valued outside a set of ﬁrst Baire category (see [?]), and the operator I +αT is onto and possesses a single-valued inverse for any monotone T and any α > 0, which is the theoretical basis for the proximal → CC point algorithm (see [?]). In contrast, the 1-ROSL mapping F : R (R) − given by F (x) = x + [ 1, +1] is set-valued on the whole space, and for all − − α > 0 the inverse of I +αF , given by (I +αF )(x) = (1 α)x+[ α, α], is set ≤ valued as well. Similarly, ROSL mappings with constants l 0, which are mainly considered in the present paper, look formally similar to mappings T − with T monotone but have fundamentally diﬀerent properties. We also recall the following facts which are well known and easy to see. ∈ Lemma 6. Let X be a Hilbert space, and let x X. ⊂ a) If M X is closed and convex, then Proj(x, M) is a single point. ⊂ b) If M X is weakly sequentially closed, then Proj(x, M) is nonempty. ⊂ ⊂ ∈ (cid:107) − (cid:107) → c) If M X is closed, and if (x ) X and x¯ X satisfy x x¯ 0 → →n n∞ ∈ n X and dist (x , M) 0 as n , then x¯ M. X n The following standard observations will also be used later on. Lemma 7. Let Y be a reﬂexive Banach space, Z a normed vector space ∈ L ∈ CBC ⊂ CBC and T (Y, Z). Then for every A (Y ) we have T (A) (Z). → CBC Consequently, every map F : M (Y ) deﬁned on an arbitrary set M ◦ → CBC gives rise to a map T F : M (Z) ∈ CBC Proof. Let A (Y ). Since T is linear and continuous, T (A) is convex and bounded. To see that T (A) is closed, we consider a sequence (z ) in → ∈ → ∞ ∈ k k T (A) such that z z Z as k . Choosing y A such that T (y ) = z ∈ k k k k for k N, we obtain a bounded sequence (y ) in A. Since Y is reﬂexive, k k ∈ (cid:48) (cid:51) → ∞ we may pass to a subsequence such that y (cid:42) y Y as N k , and ∈ k y A by Mazur’s Theorem. Moreover, T (y) = w-lim →∞ T y = w-lim →∞ z = z k k k k ∈ and thus z T (A). Hence T (A) is closed. 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Remark

text: The

text: deﬁnition

text: of

text: an

text: ROSL

text: mapping

text: with

text: constant

text: l

text: is

text: for-

text: mally

text: similar

text: to

text: that

text: of

text: a

text: monotone

text: mapping.

text: Nevertheless,

text: ROSL

text: and

text: mono-

text: tone

text: mappings

text: have

text: fundamentally

text: diﬀerent

text: properties.

text: Monotone

text: mappings

text: on

text: Hilbert

text: spaces

text: are

text: single-valued

text: outside

text: a

text: set

text: of

text: ﬁrst

text: Baire

text: category

text: (see

text: and

text: the

text: operator

text: I

text: +αT

text: is

text: onto

text: and

text: possesses

text: a

text: single-valued

text: inverse

text: for

text: any

text: monotone

text: T

text: and

text: any

text: α

text: which

text: is

text: the

text: theoretical

text: basis

text: for

text: the

text: proximal

text: CC

text: point

text: algorithm

text: (see

text: In

text: contrast,

text: the

text: mapping

text: F

text: R

font: unknown

text: (R)

text: given

text: by

text: F

text: (x)

text: x

text: is

text: set-valued

text: on

text: the

text: whole

text: space,

text: and

text: for

text: all

text: α

text: the

text: inverse

text: of

text: I

text: +αF

text: given

text: by

text: (I

text: +αF

text: )(x)

text: α)x+[

text: α,

text: α],

text: is

text: set

text: valued

text: as

text: well.

text: Similarly,

text: ROSL

text: mappings

text: with

text: constants

text: l

text: which

text: are

text: mainly

text: considered

text: in

text: the

text: present

text: paper,

text: look

text: formally

text: similar

text: to

text: mappings

text: T

text: with

text: T

text: monotone

text: but

text: have

text: fundamentally

text: diﬀerent

text: properties.

text: We

text: also

text: recall

text: the

text: following

text: facts

text: which

text: are

text: well

text: known

text: and

text: easy

text: to

text: see.

text: Lemma

text: Let

text: X

text: be

text: a

text: Hilbert

text: space,

text: and

text: let

text: x

text: X.

text: a)

text: If

text: M

text: X

text: is

text: closed

text: and

text: convex,

text: then

text: Proj(x,

text: M)

text: is

text: a

text: single

text: point.

text: b)

text: If

text: M

text: X

text: is

text: weakly

text: sequentially

text: closed,

text: then

text: Proj(x,

text: M)

text: is

text: nonempty.

text: c)

text: If

text: M

text: X

text: is

text: closed,

text: and

text: if

text: (x

text: X

text: and

text: x¯

text: X

text: satisfy

text: x

text: x¯

text: →n

text: n∞

text: n

text: X

text: and

text: dist

text: (x

text: M)

text: as

text: n

text: then

text: x¯

text: M.

text: X

text: n

text: The

text: following

text: standard

text: observations

text: will

text: also

text: be

text: used

text: later

text: on.

text: Lemma

text: Let

text: Y

text: be

text: a

text: reﬂexive

text: Banach

text: space,

text: Z

text: a

text: normed

text: vector

text: space

text: L

text: CBC

text: CBC

text: and

text: T

text: (Y,

text: Z).

text: Then

text: for

text: every

text: A

text: (Y

text: we

text: have

text: T

text: (A)

text: (Z).

text: CBC

text: Consequently,

text: every

text: map

text: F

text: M

text: (Y

text: deﬁned

text: on

text: an

text: arbitrary

text: set

text: M

text: CBC

text: gives

text: rise

text: to

text: a

text: map

text: T

text: F

text: M

text: (Z)

text: CBC

text: Proof.

text: Let

text: A

text: (Y

text: Since

text: T

text: is

text: linear

text: and

text: continuous,

text: T

text: (A)

text: is

text: convex

text: and

text: bounded.

text: To

text: see

text: that

text: T

text: (A)

text: is

text: closed,

text: we

text: consider

text: a

text: sequence

text: (z

text: in

text: k

text: k

text: T

text: (A)

text: such

text: that

text: z

text: z

text: Z

text: as

text: k

text: Choosing

text: y

text: A

text: such

text: that

text: T

text: (y

text: z

text: k

text: k

text: k

text: k

text: for

text: k

text: N,

text: we

text: obtain

text: a

text: bounded

text: sequence

text: (y

text: in

text: A.

text: Since

text: Y

text: is

text: reﬂexive,

text: k

text: k

text: we

text: may

text: pass

text: to

text: a

text: subsequence

text: such

text: that

text: y

text: y

text: Y

text: as

text: N

text: k

text: and

text: k

text: y

text: A

text: by

text: Mazur’s

text: Theorem.

text: Moreover,

text: T

text: (y)

text: w-lim

text: T

text: y

text: w-lim

text: z

text: z

text: k

text: k

text: k

text: k

text: and

text: thus

text: z

text: T

text: (A).

text: Hence

text: T

text: (A)

text: is

text: closed.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 20 Computability on the countable ordinals Proof. (Sketch): In this situation, the set inclusions in the proof of Theorem 64 are tight. (cid:80) (cid:0) (cid:1) The computable Hausdorﬀ-Kuratowski theorem has at its heart a dependent sum type; C namely the construction ∈ N (X, L Y) for some represented spaces X, Y. (αi)i∈N COrd (αi)i∈N A point in this space is a pair, consisting of a sequence of countable ordinals and a function → f : X Y, the latter given only in a L -continuou(cid:80)s way. (cid:0) (cid:1) (αi)i∈N Theorem 66 (Computable Hausdorﬀ-Kuratowski theorem). Let X, Y be represented spaces, C ∇ ⇒ C and X be complete. Then the map HK : (X, Y ) ∈ N (X, L Y) where ∈ (αi)i∈N COrd (αi)i∈N ((α ) ∈N, g) HK(f) iﬀ f = g, is computable. i i NN Proof. The general case reduces to the situation where X = Y = : As a complete represented NN → space, X has a total representation δ : X. We can then operate on a realizer of the X original f, as all involved endofunctors are derived from jump operators. ∈ C NN NN ∇ That we have f ( , ( ) ) means we may evaluate f with ﬁnitely many mindchanges. Any such mindchange occurs after a ﬁnite preﬁx of the input has been read. Thus, we may ∈ N identify countably many mindchange occurrences. Using 0 to denote no mindchange at (cid:22) all, we can proceed to obtain a relation and a numbering of the mindchange occurrences, ≺ such that if mindchange n occurs after mindchange m, then n m. If we are not aware of any not-yet-numbered mindchange occurrences, we just allocate the next natural number to the none-mindchange at 0 again. We adjust the realizer for f in a way such that any regular output n is replaced by 2n, and a mindchange symbol corresponding to the m-th mindchange is replaced by 2m + 1. N ≺ As f is total, we ﬁnd that any decreasing chain through ( , ) corresponds to the mind- ≺ changes made for some input to f. Thus, the relation is well-founded, and the other properties of a nice relation (cf. Deﬁnition 60) follow from the construction. Using the operation Lower, ∈ N we can identify for each n the corresponding ordinal of its height in the relation, yielding the sequence (α ) ∈N. i i → Corollary 67. Let f : X Y be computable with ﬁnitely many mindchanges, and X be complete. Then Lev(f) exists and is a computable ordinal. Proof. Combine Theorem 66 with Theorem 64. The result of the preceding corollary was also announced by Selivanov at CCA 2014. 6 Iteration over some ordinal Having a suitable notion of computability of the countable ordinals available allows us to deﬁne an important notion in the study of Weihrauch reducibility: What it means to iterate some (potentially non-computable) principle over some given countable ordinal. There are some similarities to how ATR is used in reverse mathematics – this principle is often informally 0 characterized as being able to iterate the Turing jump over some countable ordinal, cf. [16]. A notable diﬀerence is that in reverse mathematics, one has to prove that the ordinal one wants to iterate over is indeed an ordinal within the conﬁnes of the given system, whereas in the Weihrauch lattice, we only need to construct the ordinal eﬀectively, but can use classical logic to prove well-foundedness. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Computability

text: on

text: the

text: countable

text: ordinals

text: Proof.

text: (Sketch):

text: In

text: this

text: situation,

text: the

text: set

text: inclusions

text: in

text: the

text: proof

text: of

text: Theorem

text: are

text: tight.

text: The

text: computable

text: Hausdorﬀ-Kuratowski

text: theorem

text: has

text: at

text: its

text: heart

text: a

text: dependent

text: sum

text: type;

text: C

text: namely

text: the

text: construction

text: N

text: (X,

text: L

text: Y)

text: for

text: some

text: represented

text: spaces

text: X,

text: Y.

text: (αi)i∈N

text: COrd

text: (αi)i∈N

text: A

text: point

text: in

text: this

text: space

text: is

text: a

text: pair,

text: consisting

text: of

text: a

text: sequence

text: of

text: countable

text: ordinals

text: and

text: a

text: function

text: f

text: X

text: Y,

text: the

text: latter

text: given

text: only

text: in

text: a

text: L

text: way.

text: (αi)i∈N

text: Theorem

text: (Computable

text: Hausdorﬀ-Kuratowski

text: theorem).

text: Let

text: X,

text: Y

text: be

text: represented

text: spaces,

text: C

text: C

text: and

text: X

text: be

text: complete.

text: Then

text: the

text: map

text: HK

text: (X,

text: Y

text: N

text: (X,

text: L

text: Y)

text: where

text: (αi)i∈N

text: COrd

text: (αi)i∈N

text: ((α

text: ∈N,

text: g)

text: HK(f)

text: iﬀ

text: f

text: g,

text: is

text: computable.

text: i

text: i

text: NN

text: Proof.

text: The

text: general

text: case

text: reduces

text: to

text: the

text: situation

text: where

text: X

text: Y

text: As

text: a

text: complete

text: represented

text: NN

text: space,

text: X

text: has

text: a

text: total

text: representation

text: δ

text: X.

text: We

text: can

text: then

text: operate

text: on

text: a

text: realizer

text: of

text: the

text: X

text: original

text: f,

text: as

text: all

text: involved

text: endofunctors

text: are

text: derived

text: from

text: jump

text: operators.

text: C

text: NN

text: NN

text: That

text: we

text: have

text: f

text: means

text: we

text: may

text: evaluate

text: f

text: with

text: ﬁnitely

text: many

text: mindchanges.

text: Any

text: such

text: mindchange

text: occurs

text: after

text: a

text: ﬁnite

text: preﬁx

text: of

text: the

text: input

text: has

text: been

text: read.

text: Thus,

text: we

text: may

text: N

text: identify

text: countably

text: many

text: mindchange

text: occurrences.

text: Using

text: to

text: denote

text: no

text: mindchange

text: at

text: all,

text: we

text: can

text: proceed

text: to

text: obtain

text: a

text: relation

text: and

text: a

text: numbering

text: of

text: the

text: mindchange

text: occurrences,

text: such

text: that

text: if

text: mindchange

text: n

text: occurs

text: after

text: mindchange

text: m,

text: then

text: n

text: m.

text: If

text: we

text: are

text: not

text: aware

text: of

text: any

text: not-yet-numbered

text: mindchange

text: occurrences,

text: we

text: just

text: allocate

text: the

text: next

text: natural

text: number

text: to

text: the

text: none-mindchange

text: at

text: again.

text: We

text: adjust

text: the

text: realizer

text: for

text: f

text: in

text: a

text: way

text: such

text: that

text: any

text: regular

text: output

text: n

text: is

text: replaced

text: by

text: and

text: a

text: mindchange

text: symbol

text: corresponding

text: to

text: the

text: m-th

text: mindchange

text: is

text: replaced

text: by

text: N

text: As

text: f

text: is

text: total,

text: we

text: ﬁnd

text: that

text: any

text: decreasing

text: chain

text: through

text: corresponds

text: to

text: the

text: mind-

text: changes

text: made

text: for

text: some

text: input

text: to

text: f.

text: Thus,

text: the

text: relation

text: is

text: well-founded,

text: and

text: the

text: other

text: properties

text: of

text: a

text: nice

text: relation

text: (cf.

text: Deﬁnition

text: follow

text: from

text: the

text: construction.

text: Using

text: the

text: operation

text: Lower,

text: N

text: we

text: can

text: identify

text: for

text: each

text: n

text: the

text: corresponding

text: ordinal

text: of

text: its

text: height

text: in

text: the

text: relation,

text: yielding

text: the

text: sequence

text: (α

text: ∈N.

text: i

text: i

text: Corollary

text: Let

text: f

text: X

text: Y

text: be

text: computable

text: with

text: ﬁnitely

text: many

text: mindchanges,

text: and

text: X

text: be

text: complete.

text: Then

text: Lev(f)

text: exists

text: and

text: is

text: a

text: computable

text: ordinal.

text: Proof.

text: Combine

text: Theorem

text: with

text: Theorem

text: The

text: result

text: of

text: the

text: preceding

text: corollary

text: was

text: also

text: announced

text: by

text: Selivanov

text: at

text: CCA

text: Iteration

text: over

text: some

text: ordinal

text: Having

text: a

text: suitable

text: notion

text: of

text: computability

text: of

text: the

text: countable

text: ordinals

text: available

text: allows

text: us

text: to

text: deﬁne

text: an

text: important

text: notion

text: in

text: the

text: study

text: of

text: Weihrauch

text: reducibility:

text: What

text: it

text: means

text: to

text: iterate

text: some

text: (potentially

text: non-computable)

text: principle

text: over

text: some

text: given

text: countable

text: ordinal.

text: There

text: are

text: some

text: similarities

text: to

text: how

text: ATR

text: is

text: used

text: in

text: reverse

text: mathematics

text: this

text: principle

text: is

text: often

text: informally

text: characterized

text: as

text: being

text: able

text: to

text: iterate

text: the

text: Turing

text: jump

text: over

text: some

text: countable

text: ordinal,

text: cf.

text: A

text: notable

text: diﬀerence

text: is

text: that

text: in

text: reverse

text: mathematics,

text: one

text: has

text: to

text: prove

text: that

text: the

text: ordinal

text: one

text: wants

text: to

text: iterate

text: over

text: is

text: indeed

text: an

text: ordinal

text: within

text: the

text: conﬁnes

text: of

text: the

text: given

text: system,

text: whereas

text: in

text: the

text: Weihrauch

text: lattice,

text: we

text: only

text: need

text: to

text: construct

text: the

text: ordinal

text: eﬀectively,

text: but

text: can

text: use

text: classical

text: logic

text: to

text: prove

text: well-foundedness.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 24 Computability on the countable ordinals [19] Peter Hertling (1996): Unstetigkeitsgrade von Funktionen in der eﬀektiven Analysis. Ph.D. thesis, Fernuniversit¨at, Gesamthochschule in Hagen. [20] Peter Hertling (2002): Topological Complexity of Zero Finding with Algebraic Operations. Journal of Complexity 18, pp. 912–942. [21] Peter Hertling & Klaus Weihrauch (1994): Levels of degeneracy and exact lower complexity bounds. In: 6th Canadian Conference on Computational Geometry, pp. 237–242. [22] Kojiro Higuchi & Arno Pauly (2013): The degree-structure of Weihrauch-reducibility. Logical Meth- ods in Computer Science 9(2), doi:10.2168/LMCS-9(2:2)2013. [23] Jeﬀry L. Hirst (1994): Reverse mathematics and ordinal exponentiation. Annals of Pure and Applied Logic 66(1), pp. 1 – 18, doi:10.1016/0168-0072(94)90076-0. [24] Jeﬀry L. Hirst (1998): Reverse Mathematics and Ordinal Multiplication. Mathematical Logic Quar- terly 44, pp. 459–464, doi:10.1002/malq.19980440404. [25] Jeﬀry L. Hirst (1999): Reverse mathematics of prime factorization of ordinals. Archive of Mathe- matical Logic 38(3), pp. 195–201, doi:10.1007/s001530050123. [26] J.E. Jayne & C.A. Rogers (1982): First level Borel functions and isomorphisms. Journal de Math´ematiques Pures et Appliqu´ees 61, pp. 177–205. [27] Takayuki Kihara & Arno Pauly (2014): Point degree spectra of represented spaces. arXiv:1405.6866. [28] S. C. Kleene (1938): On notation for ordinal numbers. Journal of Symbolic Logic 3, pp. 150–155, doi:10.2307/2267778. [29] G. Kreisel (1959): Analysis of Cantor-Bendixson theorem by means of the analytic hierarchy. Bulletin de l’Acad´emie Polonaise des Sciences 7, pp. 621–626. [30] St´ephane Le Roux & Arno Pauly (2014): Inﬁnite sequential games with real-valued payoﬀs. arXiv:1401.3325. Available at http://arxiv.org/abs/1401.3325. [31] St´ephane Le Roux & Arno Pauly (2014): Weihrauch degrees of ﬁnding equilibria in sequential games. arXiv:1407.5587. Available at http://arxiv.org/abs/1407.5587. [32] Zhenhao Li & Joel D. Hamkins: On eﬀectiveness of operations on countable ordinals. unpublished notes. [33] Nicolas Lusin (1927): Sur les ensembles analytiques. Fundamenta Mathematicae 10, pp. 1–95. [34] Yiannis N. Moschovakis (1980): Descriptive Set Theory. Studies in Logic and the Foundations of Mathematics 100, North-Holland. [35] Yiannis N. Moschovakis (2010): Classical descriptive set theory as a reﬁnement of eﬀective descrip- tive set theory. Annals of Pure and Applied Logic 162, pp. 243–255. [36] Luca Motto Ros & Brian Semmes (2009): A New Proof of a Theorem of Jayne and Rogers. Real Analysis Exchange 35(1), pp. 195–204. [37] Eike Neumann & Arno Pauly (2016): A topological view on algebraic computations models. arXiv:1602.08004. [38] Dag Normann (2016): On the Cantor–Bendixson rank of a set that is searchable in Go¨dels T. Computability 5(1), pp. 61–73, doi:10.3233/COM-150043. [39] Arno Pauly (2007): Methoden zum Vergleich der Unstetigkeit von Funktionen. Masters thesis, FernUniversit¨at Hagen. [40] Arno Pauly (2010): How Incomputable is Finding Nash Equilibria? Journal of Universal Computer Science 16(18), pp. 2686–2710, doi:10.3217/jucs-016-18-2686. [41] Arno Pauly (2010): On the (semi)lattices induced by continuous reducibilities. Mathematical Logic Quarterly 56(5), pp. 488–502, doi:10.1002/malq.200910104. [42] Arno Pauly (2014): The descriptive theory of represented spaces. arXiv:1408.5329.

text: Computability

text: on

text: the

text: countable

text: ordinals

label: reference

text: Peter

text: Hertling

text: Unstetigkeitsgrade

text: von

text: Funktionen

text: in

text: der

text: eﬀektiven

text: Analysis.

text: Ph.D.

text: thesis,

text: Fernuniversit¨at,

text: Gesamthochschule

text: in

text: Hagen.

text: Peter

text: Hertling

text: Topological

text: Complexity

text: of

text: Zero

text: Finding

text: with

text: Algebraic

text: Operations.

text: Journal

text: of

text: Complexity

text: pp.

text: Peter

text: Hertling

text: Klaus

text: Weihrauch

text: Levels

text: of

text: degeneracy

text: and

text: exact

text: lower

text: complexity

text: bounds.

text: In:

text: Canadian

text: Conference

text: on

text: Computational

text: Geometry,

text: pp.

text: Kojiro

text: Higuchi

text: Arno

text: Pauly

text: The

text: degree-structure

text: of

text: Weihrauch-reducibility.

text: Logical

text: Meth-

text: ods

text: in

text: Computer

text: Science

text: Jeﬀry

text: L.

text: Hirst

text: Reverse

text: mathematics

text: and

text: ordinal

text: exponentiation.

text: Annals

text: of

text: Pure

text: and

text: Applied

text: Logic

text: pp.

text: Jeﬀry

text: L.

text: Hirst

text: Reverse

text: Mathematics

text: and

text: Ordinal

text: Multiplication.

text: Mathematical

text: Logic

text: Quar-

text: terly

text: pp.

text: Jeﬀry

text: L.

text: Hirst

text: Reverse

text: mathematics

text: of

text: prime

text: factorization

text: of

text: ordinals.

text: Archive

text: of

text: Mathe-

text: matical

text: Logic

text: pp.

text: J.E.

text: Jayne

text: C.A.

text: Rogers

text: First

text: level

text: Borel

text: functions

text: and

text: isomorphisms.

text: Journal

text: de

text: Math´ematiques

text: Pures

text: et

text: Appliqu´ees

text: pp.

text: Takayuki

text: Kihara

text: Arno

text: Pauly

text: Point

text: degree

text: spectra

text: of

text: represented

text: spaces.

text: S.

text: C.

text: Kleene

text: On

text: notation

text: for

text: ordinal

text: numbers.

text: Journal

text: of

text: Symbolic

text: Logic

text: pp.

text: G.

text: Kreisel

text: Analysis

text: of

text: Cantor-Bendixson

text: theorem

text: by

text: means

text: of

text: the

text: analytic

text: hierarchy.

text: Bulletin

text: de

text: l’Acad´emie

text: Polonaise

text: des

text: Sciences

text: pp.

text: St´ephane

text: Le

text: Roux

text: Arno

text: Pauly

text: Inﬁnite

text: sequential

text: games

text: with

text: real-valued

text: payoﬀs.

text: Available

text: at

text: St´ephane

text: Le

text: Roux

text: Arno

text: Pauly

text: Weihrauch

text: degrees

text: of

text: ﬁnding

text: equilibria

text: in

text: sequential

text: games.

text: Available

text: at

text: Zhenhao

text: Li

text: Joel

text: D.

text: Hamkins:

text: On

text: eﬀectiveness

text: of

text: operations

text: on

text: countable

text: ordinals.

text: unpublished

text: notes.

text: Nicolas

text: Lusin

text: Sur

text: les

text: ensembles

text: analytiques.

text: Fundamenta

text: Mathematicae

text: pp.

text: Yiannis

text: N.

text: Moschovakis

text: Descriptive

text: Set

text: Theory.

text: Studies

text: in

text: Logic

text: and

text: the

text: Foundations

text: of

text: Mathematics

text: North-Holland.

text: Yiannis

text: N.

text: Moschovakis

text: Classical

text: descriptive

text: set

text: theory

text: as

text: a

text: reﬁnement

text: of

text: eﬀective

text: descrip-

text: tive

text: set

text: theory.

text: Annals

text: of

text: Pure

text: and

text: Applied

text: Logic

text: pp.

text: Luca

text: Motto

text: Ros

text: Brian

text: Semmes

text: A

text: New

text: Proof

text: of

text: a

text: Theorem

text: of

text: Jayne

text: and

text: Rogers.

text: Real

text: Analysis

text: Exchange

text: pp.

text: Eike

text: Neumann

text: Arno

text: Pauly

text: A

text: topological

text: view

text: on

text: algebraic

text: computations

text: models.

text: Dag

text: Normann

text: On

text: the

text: Cantor–Bendixson

text: rank

text: of

text: a

text: set

text: that

text: is

text: searchable

text: in

text: Go¨dels

text: T.

text: Computability

text: pp.

text: Arno

text: Pauly

text: Methoden

text: zum

text: Vergleich

text: der

text: Unstetigkeit

text: von

text: Funktionen.

text: Masters

text: thesis,

text: FernUniversit¨at

text: Hagen.

text: Arno

text: Pauly

text: How

text: Incomputable

text: is

text: Finding

text: Nash

text: Equilibria?

text: Journal

text: of

text: Universal

text: Computer

text: Science

text: pp.

text: Arno

text: Pauly

text: On

text: the

text: (semi)lattices

text: induced

text: by

text: continuous

text: reducibilities.

text: Mathematical

text: Logic

text: Quarterly

text: pp.

text: Arno

text: Pauly

text: The

text: descriptive

text: theory

text: of

text: represented

text: spaces.


text: A. Pauly 25 [43] Arno Pauly (2015): Computability on the Countable Ordinals and the Hausdorﬀ-Kuratowski Theorem (Extended Abstract). In Giuseppe F Italiano, Giovanni Pighizzini & Donald T. Sannella, editors: Mathematical Foundations of Computer Science 2015, Lecture Notes in Computer Science 9234, Springer, pp. 407–418, doi:10.1007/978-3-662-48057-1 32. Available at http://dx.doi.org/10. 1007/978-3-662-48057-1_32. [44] Arno Pauly (2016): On the topological aspects of the theory of represented spaces. Computability 5(2), pp. 159–180, doi:10.3233/COM-150049. Available at http://arxiv.org/abs/1204.3763. [45] Arno Pauly & Matthew de Brecht (2013): Towards Synthetic Descriptive Set Theory: An instanti- ation with represented spaces. http://arxiv.org/abs/1307.1850. [46] Arno Pauly & Matthew de Brecht (2014): Non-deterministic Computation and the Jayne Rogers Theorem. Electronic Proceedings in Theoretical Computer Science 143, doi:10.4204/EPTCS.143.8. DCM 2012. [47] Arno Pauly & Matthew de Brecht (2015): Descriptive Set Theory in the Category of Represented Spaces. In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 438–449, doi:10.1109/LICS.2015.48. [48] Yann Pequignot (2015): A Wadge hierarchy for second countable spaces. Archive for Mathemat- ical Logic, pp. 1–25, doi:10.1007/s00153-015-0434-y. Available at http://dx.doi.org/10.1007/ s00153-015-0434-y. [49] Matthias Schr¨oder (2002): Admissible Representations for Continuous Computations. Ph.D. thesis, FernUniversit¨at Hagen. [50] Matthias Schr¨oder (2002): A Natural Weak Limit Space with Admissible Representation which is not a Limit Space. ENTCS 66(1), pp. 165–175. [51] Victor L. Selivanov (2013): Total representations. Logical Methods in Computer Science 9(2). [52] Cliﬀord Spector (1955): Recursive well-orderings. Journal of Symbolic Logic 20(2), pp. 151–163, doi:10.2307/2266902. [53] Alan Turing (1936): On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the LMS 2(42), pp. 230–265. [54] Alan Turing (1937): On computable numbers, with an application to the Entscheidungsproblem: Corrections. Proceedings of the LMS 2(43), pp. 544–546. [55] Klaus Weihrauch (1987): Computability. Monographs on Theoretical Computer Science, Springer- Verlag. [56] Klaus Weihrauch (1992): The TTE-interpretation of three hierarchies of omniscience principles. Informatik Berichte 130, FernUniversit¨at Hagen, Hagen. [57] Klaus Weihrauch (2000): Computable Analysis. Springer-Verlag. [58] Martin Ziegler (2007): Real Hypercomputation and Continuity. Theory of Computing Systems 41, pp. 177 – 206, doi:10.1007/s00224-006-1343-6. [59] Martin Ziegler (2007): Revising Type-2 Computation and Degrees of Discontinuity. Electronic Notes in Theoretical Computer Science 167, pp. 255–274, doi:10.1016/j.entcs.2006.08.015. Acknowledgements I am grateful to Victor Selivanov for sparking my interest in a computable version of the Hausdorﬀ Kuratowski theorem and to Vasco Brattka and Matthew de Brecht for various discus- sions on this question. The comparison of the various representations of the countable ordinals started with a discussion with Vassilios Gregoriades. A remark by Takayuki Kihara was crucial for the formulation of Theorem 72. ##LTLine##

text: A.

text: Pauly

text: Arno

text: Pauly

text: Computability

text: on

text: the

text: Countable

text: Ordinals

text: and

text: the

text: Hausdorﬀ-Kuratowski

text: Theorem

text: (Extended

text: Abstract).

text: In

text: Giuseppe

text: F

text: Italiano,

text: Giovanni

text: Pighizzini

text: Donald

text: T.

text: Sannella,

text: editors:

text: Mathematical

text: Foundations

text: of

text: Computer

text: Science

text: Lecture

text: Notes

text: in

text: Computer

text: Science

text: Springer,

text: pp.

text: Available

text: at

text: Arno

text: Pauly

text: On

text: the

text: topological

text: aspects

text: of

text: the

text: theory

text: of

text: represented

text: spaces.

text: Computability

text: pp.

text: Available

text: at

text: Arno

text: Pauly

text: Matthew

text: de

text: Brecht

text: Towards

text: Synthetic

text: Descriptive

text: Set

text: Theory:

text: An

text: instanti-

text: ation

text: with

text: represented

text: spaces.

text: Arno

text: Pauly

text: Matthew

text: de

text: Brecht

text: Non-deterministic

text: Computation

text: and

text: the

text: Jayne

text: Rogers

text: Theorem.

text: Electronic

text: Proceedings

text: in

text: Theoretical

text: Computer

text: Science

text: DCM

text: Arno

text: Pauly

text: Matthew

text: de

text: Brecht

text: Descriptive

text: Set

text: Theory

text: in

text: the

text: Category

text: of

text: Represented

text: Spaces.

text: In:

text: Annual

text: ACM/IEEE

text: Symposium

text: on

text: Logic

text: in

text: Computer

text: Science

text: (LICS),

text: pp.

text: Yann

text: Pequignot

text: A

text: Wadge

text: hierarchy

text: for

text: second

text: countable

text: spaces.

text: Archive

text: for

text: Mathemat-

text: ical

text: Logic,

text: pp.

text: Available

text: at

text: Matthias

text: Schr¨oder

text: Admissible

text: Representations

text: for

text: Continuous

text: Computations.

text: Ph.D.

text: thesis,

text: FernUniversit¨at

text: Hagen.

text: Matthias

text: Schr¨oder

text: A

text: Natural

text: Weak

text: Limit

text: Space

text: with

text: Admissible

text: Representation

text: which

text: is

text: not

text: a

text: Limit

text: Space.

text: ENTCS

text: pp.

text: Victor

text: L.

text: Selivanov

text: Total

text: representations.

text: Logical

text: Methods

text: in

text: Computer

text: Science

text: Cliﬀord

text: Spector

text: Recursive

text: well-orderings.

text: Journal

text: of

text: Symbolic

text: Logic

text: pp.

text: Alan

text: Turing

text: On

text: computable

text: numbers,

text: with

text: an

text: application

text: to

text: the

text: Entscheidungsproblem.

text: Proceedings

text: of

text: the

text: LMS

text: pp.

text: Alan

text: Turing

text: On

text: computable

text: numbers,

text: with

text: an

text: application

text: to

text: the

text: Entscheidungsproblem:

text: Corrections.

text: Proceedings

text: of

text: the

text: LMS

text: pp.

text: Klaus

text: Weihrauch

text: Computability.

text: Monographs

text: on

text: Theoretical

text: Computer

text: Science,

text: Springer-

text: Verlag.

text: Klaus

text: Weihrauch

text: The

text: TTE-interpretation

text: of

text: three

text: hierarchies

text: of

text: omniscience

text: principles.

text: Informatik

text: Berichte

text: FernUniversit¨at

text: Hagen,

text: Hagen.

text: Klaus

text: Weihrauch

text: Computable

text: Analysis.

text: Springer-Verlag.

text: Martin

text: Ziegler

text: Real

text: Hypercomputation

text: and

text: Continuity.

text: Theory

text: of

text: Computing

text: Systems

text: pp.

text: Martin

text: Ziegler

text: Revising

text: Computation

text: and

text: Degrees

text: of

text: Discontinuity.

text: Electronic

text: Notes

text: in

text: Theoretical

text: Computer

text: Science

text: pp.

text: Acknowledgements

text: I

text: am

text: grateful

text: to

text: Victor

text: Selivanov

text: for

text: sparking

text: my

text: interest

text: in

text: a

text: computable

text: version

text: of

text: the

text: Hausdorﬀ

text: Kuratowski

text: theorem

text: and

text: to

text: Vasco

text: Brattka

text: and

text: Matthew

text: de

text: Brecht

text: for

text: various

text: discus-

text: sions

text: on

text: this

text: question.

text: The

text: comparison

text: of

text: the

text: various

text: representations

text: of

text: the

text: countable

text: ordinals

text: started

text: with

text: a

text: discussion

text: with

text: Vassilios

text: Gregoriades.

text: A

text: remark

text: by

text: Takayuki

text: Kihara

text: was

text: crucial

text: for

text: the

text: formulation

text: of

text: Theorem

text: ##LTLine##


text: A. Pauly 7 ⊆ NN → Deﬁnition 16. We deﬁne a representation δnf : COrd inductively via: nK 1. δnf (0p) = 0 nK 2. δnf (1p) = δnf (p) + 1 nK nK (cid:104) (cid:105) ∀ ∈ N ∈ { } 3. δnf (2 p , p , p , . . . ) = sup ∈N δnf (p ), provided that i p (0) 0, 1 . nK 0 1 2 ∼ i nK i i Observation 17. COrd = (COrd, δnf ). nK → NN Proof. The identity id : (COrd, δnf ) COrd is realised by the identity on . For the other nK direction we simply use tupling functions to ﬂatten out immediate nestings of sup. (cid:101) NN Observation 18. dom(δnf ) is a closed subset of dom(δ ), and not even a Σ1 subset of . nK nK 1 ∈ \ Proof. If p dom(δ ) dom(δnf ), then there is some immediate nesting of sup in p, which we nK nK can detect. For the second claim, note that a Wadge-reduction from the set of well-founded trees can be obtained in a straight-forward manner, and this is the standard example of a Π1-complete 1 set, see e.g. [34]. ∈ ∈ NN ∈ NN ≤ Deﬁnition 19. Given some q dom(δ ) and some p , we call r a -certiﬁcate for nK (p, q) iﬀ the following conditions are satisﬁed: 1. If q(0) = 0, then p(0) = 0. ≤ (cid:104) (cid:105) 2. If q = 1q , then either p = 1p and r is a -certiﬁcate for (p , q ), or p = 2 n p , n p , . . . ∈0 { } (cid:104) 0 (cid:105) ∈ N 0 0 ≤ 0 0 1 1 with n 0, 1 and r = r , . . . , and for each i with n = 0, r is a -certiﬁcate for i 0 i i (p , q ). i 0 (cid:104) (cid:105) 3. If q = 2 q , q , . . . , then either 0 1 (a) p(0) = 0. ≤ (b) p = 1p , r = nr and r is a -certiﬁcate for (p, q ). 0 0 0 n (cid:104) (cid:105) (cid:104) (cid:104) (cid:105)(cid:105) ∈ N ≤ (c) or p = 2 p , p , . . . , r = h, r , r , . . . , and for each i , r is a -certiﬁcate for 0 1 0 1 i (p , q ). i h(i) ∈ ≤ ∈ Observation 20. Let q dom(δ ). If (p, q) has a -certiﬁcate, then p dom(δ ) and ≤ ∈ nK ≤ ≤ nK δ (p) δ (q). If p dom(δnf ) and δnf (p) δ (q), then (p, q) admits a -certiﬁcate. The nK ≤ nK nK nK nK set of -certiﬁcates for (p, q) is a closed set computable from p and q. Proof. By induction over the structure of q. C NN → Theorem 21. sup : ( , COrd) COrd is well-deﬁned and computable. Proof. First, we shall show that this map is well-deﬁned, i.e. that any continuous function deﬁned on the entirety of Baire space into the countable ordinals is bounded by some countable NN → NN ordinal. For that, assume the contrary, and that F : is a continuous realizer of a ∈ NN ∈ NN counterexample f. Consider the set O of all q such that there exists p, r such that r ≤ (cid:101) is a -certiﬁcate for (q, F (p)). By deﬁnition, O is a Σ1-set. By the unboundedness assumption ⊆ 1⊆ on f and Observation 20, we ﬁnd that dom(δnf ) O dom(δ ). Now Observation 18 both (cid:101) nK nK implies from there that dom(δnf ) is a Σ1-set, and shows that this is not the case1. nK 1 1The result itself is folklore, and the proof here is closely following an argument from [17]. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A.

text: Pauly

text: NN

text: Deﬁnition

text: We

text: deﬁne

text: a

text: representation

text: δnf

text: COrd

text: inductively

text: via:

text: nK

label: list

text: δnf

text: nK

text: δnf

text: δnf

text: (p)

text: nK

text: nK

text: N

text: δnf

text: p

text: p

text: p

text: sup

text: ∈N

text: δnf

text: (p

text: provided

text: that

text: i

text: p

text: nK

text: i

text: nK

text: i

text: i

text: Observation

text: COrd

text: (COrd,

text: δnf

text: nK

text: NN

text: Proof.

text: The

text: identity

text: id

text: (COrd,

text: δnf

text: COrd

text: is

text: realised

text: by

text: the

text: identity

text: on

text: For

text: the

text: other

text: nK

text: direction

text: we

text: simply

text: use

text: tupling

text: functions

text: to

text: ﬂatten

text: out

text: immediate

text: nestings

text: of

text: sup.

text: NN

text: Observation

text: dom(δnf

text: is

text: a

text: closed

text: subset

text: of

text: dom(δ

text: and

text: not

text: even

text: a

text: Σ1

text: subset

text: of

text: nK

text: nK

text: Proof.

text: If

text: p

text: dom(δ

text: dom(δnf

text: then

text: there

text: is

text: some

text: immediate

text: nesting

text: of

text: sup

text: in

text: p,

text: which

text: we

text: nK

text: nK

text: can

text: detect.

text: For

text: the

text: second

text: claim,

text: note

text: that

text: a

text: Wadge-reduction

text: from

text: the

text: set

text: of

text: well-founded

text: trees

text: can

text: be

text: obtained

text: in

text: a

text: straight-forward

text: manner,

text: and

text: this

text: is

text: the

text: standard

text: example

text: of

text: a

text: set,

text: see

text: e.g.

text: NN

text: NN

text: Deﬁnition

text: Given

text: some

text: q

text: dom(δ

text: and

text: some

text: p

text: we

text: call

text: r

text: a

text: -certiﬁcate

text: for

text: nK

text: (p,

text: q)

text: iﬀ

text: the

text: following

text: conditions

text: are

text: satisﬁed:

text: If

text: then

text: If

text: q

text: then

text: either

text: p

text: and

text: r

text: is

text: a

text: -certiﬁcate

text: for

text: (p

text: q

text: or

text: p

text: n

text: p

text: n

text: p

text: ∈0

text: N

text: with

text: n

text: and

text: r

text: r

text: and

text: for

text: each

text: i

text: with

text: n

text: r

text: is

text: a

text: -certiﬁcate

text: for

text: i

text: i

text: i

text: (p

text: q

text: i

text: If

text: q

text: q

text: q

text: then

text: either

text: (a)

text: (b)

text: p

text: r

text: nr

text: and

text: r

text: is

text: a

text: -certiﬁcate

text: for

text: (p,

text: q

text: n

text: N

text: (c)

text: or

text: p

text: p

text: p

text: r

text: h,

text: r

text: r

text: and

text: for

text: each

text: i

text: r

text: is

text: a

text: -certiﬁcate

text: for

text: i

text: (p

text: q

text: i

text: h(i)

text: Observation

text: Let

text: q

text: dom(δ

text: If

text: (p,

text: q)

text: has

text: a

text: -certiﬁcate,

text: then

text: p

text: dom(δ

text: and

text: nK

text: nK

text: δ

text: (p)

text: δ

text: (q).

text: If

text: p

text: dom(δnf

text: and

text: δnf

text: (p)

text: δ

text: (q),

text: then

text: (p,

text: q)

text: admits

text: a

text: -certiﬁcate.

text: The

text: nK

text: nK

text: nK

text: nK

text: nK

text: set

text: of

text: -certiﬁcates

text: for

text: (p,

text: q)

text: is

text: a

text: closed

text: set

text: computable

text: from

text: p

text: and

text: q.

text: Proof.

text: By

text: induction

text: over

text: the

text: structure

text: of

text: q.

text: C

text: NN

text: Theorem

text: sup

text: COrd)

text: COrd

text: is

text: well-deﬁned

text: and

text: computable.

text: Proof.

text: First,

text: we

text: shall

text: show

text: that

text: this

text: map

text: is

text: well-deﬁned,

text: i.e.

text: that

text: any

text: continuous

text: function

text: deﬁned

text: on

text: the

text: entirety

text: of

text: Baire

text: space

text: into

text: the

text: countable

text: ordinals

text: is

text: bounded

text: by

text: some

text: countable

text: NN

text: NN

text: ordinal.

text: For

text: that,

text: assume

text: the

text: contrary,

text: and

text: that

text: F

text: is

text: a

text: continuous

text: realizer

text: of

text: a

text: NN

text: NN

text: counterexample

text: f.

text: Consider

text: the

text: set

text: O

text: of

text: all

text: q

text: such

text: that

text: there

text: exists

text: p,

text: r

text: such

text: that

text: r

text: is

text: a

text: -certiﬁcate

text: for

text: (q,

text: F

text: (p)).

text: By

text: deﬁnition,

text: O

text: is

text: a

text: By

text: the

text: unboundedness

text: assumption

text: 1⊆

text: on

text: f

text: and

text: Observation

text: we

text: ﬁnd

text: that

text: dom(δnf

text: O

text: dom(δ

text: Now

text: Observation

text: both

text: nK

text: nK

text: implies

text: from

text: there

text: that

text: dom(δnf

text: is

text: a

text: and

text: shows

text: that

text: this

text: is

text: not

text: the

text: nK

text: result

text: itself

text: is

text: folklore,

text: and

text: the

text: proof

text: here

text: is

text: closely

text: following

text: an

text: argument

text: from

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: we bribe more than k voters in X to approve p. Then b gets at least n + 2 points in some round of the resulting election; let j be the ﬁrst such round. As all voters prefer b to p, it cannot be the case that p gets n + 2 points in round j, so this bribery is not successful. Hence, applying t must increase p’s approval count by exactly k, via bribing a subset of ⊆ { } voters S X of size k. Note that this implies α(I) = k as well. Let S = s , . . . , s . V 1 k Now, looking at the scores of the candidates in , one can see that a support bribery ∈ V that bribes voters in S to increase p’s score is successful if and only if each v receives − i at most k 1 additional points from the voters in S. This holds if and only if each vertex is V \ V \ missing from at least one of the sets N[s ], . . . , N[s ]. This is equivalent to s , . . . , s 1 k 1 k being a dominating set. Thus, the proof is complete. Since the hardness result of Theorem 9 for Fallback-support bribery holds even if all ∞ bribery costs are either 0 or + , it follows that this problem does not admit an approxi- mation algorithm with a bounded approximation ratio. Theorem 9 shows that Fallback-support bribery is W[2]-hard with respect to the ≥ parameter α. Given that we have β(I) α(I) for each instance I, it is natural to ask whether Fallback-support bribery remains hard if even β is small, i.e., every minimal optimal bribery only makes small changes to the approval counts. In Section , we will see that even a very restricted version of this problem remains hard. More precisely, in Theorem 11 we will prove that support bribery for each of SP-AV, simpliﬁed Fallback voting, and Fallback voting remains NP-hard and also W[1]-hard with respect to parameter | | β, even for single-peaked electorates and unit costs, i.e., when σi(k) = k for each k and each i = 1, . . . , n. However, the hardness proof in Theorem 11 (see Section ) heavily relies on the fact that unit cost functions allow us to increase approval counts in some of the votes while decreasing them in some other votes. In contrast, we will now prove that if all cost functions are positive or all cost functions are negative, (simpliﬁed) Fallback-support bribery is ﬁxed-parameter (cid:48) tractable with respect to β (and hence also with respect to β). Theorem 10. support bribery for SP-AV, simpliﬁed Fallback voting, and Fallback voting (cid:48) is FPT with respect to parameter β (the minimum total change in approval counts over all optimal briberies), as long as either all bribery cost functions are positive or all bribery cost functions are negative. | | Proof. Suppose we are given an instance I = (C, V, Σ, p) of support bribery with V = n. (cid:48) (cid:48) It will be convenient to assume that we also given β = β (I); if this is not the case, we (cid:48) can try each possible value of β in an increasing fashion. We will present an algorithm that works for both the simpliﬁed and the classic variant of Fallback voting; the algorithm can easily be modiﬁed (indeed, simpliﬁed) for SP-AV. Under the Fallback rule, a candidate can win by either (a) having the highest number of approvals in the Bucklin winning round or (b) having the highest number of approvals when there is no Bucklin winning round; for simpliﬁed Fallback rule, condition (a) changes (cid:48) to (a ) obtaining a majority of approvals in the Bucklin winning round. To take into account briberies that ensure p’s victory via case (b), we view this case as an “extra round” in which 17 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: we

text: bribe

text: more

text: than

text: k

text: voters

text: in

text: X

text: to

text: approve

text: p.

text: Then

text: b

text: gets

text: at

text: least

text: n

text: points

text: in

text: some

text: round

text: of

text: the

text: resulting

text: election;

text: let

text: j

text: be

text: the

text: ﬁrst

text: such

text: round.

text: As

text: all

text: voters

text: prefer

text: b

text: to

text: p,

text: it

text: cannot

text: be

text: the

text: case

text: that

text: p

text: gets

text: n

text: points

text: in

text: round

text: j,

text: so

text: this

text: bribery

text: is

text: not

text: successful.

text: Hence,

text: applying

text: t

text: must

text: increase

text: p’s

text: approval

text: count

text: by

text: exactly

text: k,

text: via

text: bribing

text: a

text: subset

text: of

text: voters

text: S

text: X

text: of

text: size

text: k.

text: Note

text: that

text: this

text: implies

text: α(I)

text: k

text: as

text: well.

text: Let

text: S

text: s

text: s

text: V

text: k

text: Now,

text: looking

text: at

text: the

text: scores

text: of

text: the

text: candidates

text: in

text: one

text: can

text: see

text: that

text: a

text: support

text: bribery

text: V

text: that

text: bribes

text: voters

text: in

text: S

text: to

text: increase

text: p’s

text: score

text: is

text: successful

text: if

text: and

text: only

text: if

text: each

text: v

text: receives

text: i

text: at

text: most

text: k

text: additional

text: points

text: from

text: the

text: voters

text: in

text: S.

text: This

text: holds

text: if

text: and

text: only

text: if

text: each

text: vertex

text: is

text: V

text: V

text: missing

text: from

text: at

text: least

text: one

text: of

text: the

text: sets

text: N[s

text: N[s

text: This

text: is

text: equivalent

text: to

text: s

text: s

text: k

text: k

text: being

text: a

text: dominating

text: set.

text: Thus,

text: the

text: proof

text: is

text: complete.

text: Since

text: the

text: hardness

text: result

text: of

text: Theorem

text: for

text: Fallback-support

text: bribery

text: holds

text: even

text: if

text: all

text: bribery

text: costs

text: are

text: either

text: or

text: it

text: follows

text: that

text: this

text: problem

text: does

text: not

text: admit

text: an

text: approxi-

text: mation

text: algorithm

text: with

text: a

text: bounded

text: approximation

text: ratio.

text: Theorem

text: shows

text: that

text: Fallback-support

text: bribery

text: is

text: with

text: respect

text: to

text: the

text: parameter

text: α.

text: Given

text: that

text: we

text: have

text: β(I)

text: α(I)

text: for

text: each

text: instance

text: I,

text: it

text: is

text: natural

text: to

text: ask

text: whether

text: Fallback-support

text: bribery

text: remains

text: hard

text: if

text: even

text: β

text: is

text: small,

text: i.e.,

text: every

text: minimal

text: optimal

text: bribery

text: only

text: makes

text: small

text: changes

text: to

text: the

text: approval

text: counts.

text: In

text: Section

text: we

text: will

text: see

text: that

text: even

text: a

text: very

text: restricted

text: version

text: of

text: this

text: problem

text: remains

text: hard.

text: More

text: precisely,

text: in

text: Theorem

text: we

text: will

text: prove

text: that

text: support

text: bribery

text: for

text: each

text: of

text: SP-AV,

text: simpliﬁed

text: Fallback

text: voting,

text: and

text: Fallback

text: voting

text: remains

text: NP-hard

text: and

text: also

text: with

text: respect

text: to

text: parameter

text: β,

text: even

text: for

text: single-peaked

text: electorates

text: and

text: unit

text: costs,

text: i.e.,

text: when

text: σi(k)

text: k

text: for

text: each

text: k

text: and

text: each

text: i

text: n.

text: However,

text: the

text: hardness

text: proof

text: in

text: Theorem

text: (see

text: Section

text: heavily

text: relies

text: on

text: the

text: fact

text: that

text: unit

text: cost

text: functions

text: allow

text: us

text: to

text: increase

text: approval

text: counts

text: in

text: some

text: of

text: the

text: votes

text: while

text: decreasing

text: them

text: in

text: some

text: other

text: votes.

text: In

text: contrast,

text: we

text: will

text: now

text: prove

text: that

text: if

text: all

text: cost

text: functions

text: are

text: positive

text: or

text: all

text: cost

text: functions

text: are

text: negative,

text: (simpliﬁed)

text: Fallback-support

text: bribery

text: is

text: ﬁxed-parameter

text: tractable

text: with

text: respect

text: to

text: β

text: (and

text: hence

text: also

text: with

text: respect

text: to

text: β).

text: Theorem

text: support

text: bribery

text: for

text: SP-AV,

text: simpliﬁed

text: Fallback

text: voting,

text: and

text: Fallback

text: voting

text: is

text: FPT

text: with

text: respect

text: to

text: parameter

text: β

text: (the

text: minimum

text: total

text: change

text: in

text: approval

text: counts

text: over

text: all

text: optimal

text: briberies),

text: as

text: long

text: as

text: either

text: all

text: bribery

text: cost

text: functions

text: are

text: positive

text: or

text: all

text: bribery

text: cost

text: functions

text: are

text: negative.

text: Proof.

text: Suppose

text: we

text: are

text: given

text: an

text: instance

text: I

text: (C,

text: V,

text: Σ,

text: p)

text: of

text: support

text: bribery

text: with

text: V

text: n.

text: It

text: will

text: be

text: convenient

text: to

text: assume

text: that

text: we

text: also

text: given

text: β

text: β

text: (I);

text: if

text: this

text: is

text: not

text: the

text: case,

text: we

text: can

text: try

text: each

text: possible

text: value

text: of

text: β

text: in

text: an

text: increasing

text: fashion.

text: We

text: will

text: present

text: an

text: algorithm

text: that

text: works

text: for

text: both

text: the

text: simpliﬁed

text: and

text: the

text: classic

text: variant

text: of

text: Fallback

text: voting;

text: the

text: algorithm

text: can

text: easily

text: be

text: modiﬁed

text: (indeed,

text: simpliﬁed)

text: for

text: SP-AV.

text: Under

text: the

text: Fallback

text: rule,

text: a

text: candidate

text: can

text: win

text: by

text: either

text: (a)

text: having

text: the

text: highest

text: number

text: of

text: approvals

text: in

text: the

text: Bucklin

text: winning

text: round

text: or

text: (b)

text: having

text: the

text: highest

text: number

text: of

text: approvals

text: when

text: there

text: is

text: no

text: Bucklin

text: winning

text: round;

text: for

text: simpliﬁed

text: Fallback

text: rule,

text: condition

text: (a)

text: changes

text: to

text: (a

text: obtaining

text: a

text: majority

text: of

text: approvals

text: in

text: the

text: Bucklin

text: winning

text: round.

text: To

text: take

text: into

text: account

text: briberies

text: that

text: ensure

text: p’s

text: victory

text: via

text: case

text: (b),

text: we

text: view

text: this

text: case

text: as

text: an

text: “extra

text: round”

text: in

text: which

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We now describe our algorithm. First, the algorithm guesses the round (cid:96) in which p wins in psh(C, V, t) and the number δ(p) of approvals that p loses until this round; in other words, we guess ((cid:96), δ(p)) for which t is an ((cid:96), δ(p))-bribery. By our previous observations, (cid:48) (cid:48) there are β + 1 choices of (cid:96) and β + 1 choices of δ(p). The algorithm then computes the set of candidates that have to lose at least one point as a result of t (this computation depends on whether we consider classic or simpliﬁed Fallback voting). Let R be the set that consists of these candidates as well as candidate p; we say that the candidates in R are relevant. By Observation (1), if I is solvable and we (cid:48) guessed (cid:96) and δ(p) correctly, the set R contains at most β + 1 candidates. The algorithm ∈ \ { } also computes integers δ − (c) and δ (c) for each c R p such that: (cid:96) 1 (cid:96) ∈ \ { } (3) an ((cid:96), δ(p))-bribery makes p a winner if and only if each candidate c R p loses − at least δ − (c) points until round (cid:96) 1, and at least δ (c) points until round (cid:96). (cid:96) 1 (cid:96) The procedure for computing these integers depends on whether we consider classic or ≤ simpliﬁed Fallback voting. In particular, we always have δ − (c) δ (c) and under simpliﬁed (cid:96) 1 (cid:96) Fallback voting we have δ − (c) = δ (c). We set δ − (c) = 0 if (cid:96) = 1. (cid:96) 1 (cid:96) { (cid:96) |1 ∈ ≤ ≤ (cid:48)} Next, the algorithm partitions the set (v, t) v V, 1 t β into equivalence classes. By applying a pair (vi, t) we mean bribing voter vi to decrease her approval count − (cid:48) (cid:48) ∈ from (cid:96)i to (cid:96)i t. We say that (v, t) and (v , t ) are equivalent if for each c R it holds (cid:48) (cid:48) r that applying (v, t) has the same eﬀect on c as applying (v , t ). More formally, (v, t) and (cid:48) (cid:48) ∈ r (cid:48) (cid:48) (v , t ) are equivalent if for each c R it holds that (i) (v, t) and (v , t ) decrease the r − (cid:48) (cid:48) number of approvals c gets until round (cid:96) 1 by the same amount and (ii) (v, t) and (v , t ) r decrease the number of approvals c gets until round (cid:96) by the same amount. A pair (v, t) r can behave in three possible ways with respect to c : it can leave its approval count until r − round (cid:96) (and hence also its approval count until round (cid:96) 1) unchanged, it can decrease by one its approval count in round (cid:96) (but not in earlier rounds), or it can decrease by one its − approval count until round (cid:96) 1, thereby also decreasing its approval count until round (cid:96). | | ≤ (cid:48) Therefore, there are at most 3 R 3β +1 equivalence classes. Note that applying some pair (v, t) instead of another pair that is equivalent to it does not change whether a given push action is successful or not. Finally, the algorithm proceeds as follows: it guesses an equivalence class, picks a cheap- est pair (vi, t) from this class that has not been applied so far, and applies it. Clearly, in | | some of the at most 3 R branches the algorithm will choose a pair that can be extended to (cid:48) an optimal bribery, if there exists one. It repeats this step until it reaches the bound β on (cid:48) the total approval count modiﬁcation; this means at most β branchings. By the arguments above, a minimum-cost solution for I can be obtained by taking a minimum-cost bribery among all the successful briberies (that is, ones that ensure p’s victory) considered. Positive cost functions. Let us now focus on the case of positive cost functions, where each bribery can only increase a candidate’s number of approvals. For each possible (cid:96) and δ(p), the algorithm tries to ﬁnd a minimal ((cid:96), δ(p))-bribery t of | | minimum cost that makes p a winner. This means considering at most C + 1 possibilities (cid:48) for (cid:96), and, by (2), at most β +1 possibilities for δ(p). Note that under positive cost functions 19

text: We

text: now

text: describe

text: our

text: algorithm.

text: First,

text: the

text: algorithm

text: guesses

text: the

text: round

text: in

text: which

text: p

text: wins

text: in

text: psh(C,

text: V,

text: t)

text: and

text: the

text: number

text: δ(p)

text: of

text: approvals

text: that

text: p

text: loses

text: until

text: this

text: round;

text: in

text: other

text: words,

text: we

text: guess

text: δ(p))

text: for

text: which

text: t

text: is

text: an

text: δ(p))-bribery.

text: By

text: our

text: previous

text: observations,

text: there

text: are

text: β

text: choices

text: of

text: and

text: β

text: choices

text: of

text: δ(p).

text: The

text: algorithm

text: then

text: computes

text: the

text: set

text: of

text: candidates

text: that

text: have

text: to

text: lose

text: at

text: least

text: one

text: point

text: as

text: a

text: result

text: of

text: t

text: (this

text: computation

text: depends

text: on

text: whether

text: we

text: consider

text: classic

text: or

text: simpliﬁed

text: Fallback

text: voting).

text: Let

text: R

text: be

text: the

text: set

text: that

text: consists

text: of

text: these

text: candidates

text: as

text: well

text: as

text: candidate

text: p;

text: we

text: say

text: that

text: the

text: candidates

text: in

text: R

text: are

text: relevant.

text: By

text: Observation

text: if

text: I

text: is

text: solvable

text: and

text: we

text: guessed

text: and

text: δ(p)

text: correctly,

text: the

text: set

text: R

text: contains

text: at

text: most

text: β

text: candidates.

text: The

text: algorithm

text: also

text: computes

text: integers

text: δ

text: (c)

text: and

text: δ

text: (c)

text: for

text: each

text: c

text: R

text: p

text: such

text: that:

text: an

text: δ(p))-bribery

text: makes

text: p

text: a

text: winner

text: if

text: and

text: only

text: if

text: each

text: candidate

text: c

text: R

text: p

text: loses

text: at

text: least

text: δ

text: (c)

text: points

text: until

text: round

text: and

text: at

text: least

text: δ

text: (c)

text: points

text: until

text: round

text: The

text: procedure

text: for

text: computing

text: these

text: integers

text: depends

text: on

text: whether

text: we

text: consider

text: classic

text: or

text: simpliﬁed

text: Fallback

text: voting.

text: In

text: particular,

text: we

text: always

text: have

text: δ

text: (c)

text: δ

text: (c)

text: and

text: under

text: simpliﬁed

text: Fallback

text: voting

text: we

text: have

text: δ

text: (c)

text: δ

text: (c).

text: We

text: set

text: δ

text: (c)

text: if

text: Next,

text: the

text: algorithm

text: partitions

text: the

text: set

text: (v,

text: t)

text: v

text: V,

text: t

text: β

text: into

text: equivalence

text: classes.

text: By

text: applying

text: a

text: pair

text: (vi,

text: t)

text: we

text: mean

text: bribing

text: voter

text: vi

text: to

text: decrease

text: her

text: approval

text: count

text: from

text: to

text: t.

text: We

text: say

text: that

text: (v,

text: t)

text: and

text: (v

text: t

text: are

text: equivalent

text: if

text: for

text: each

text: c

text: R

text: it

text: holds

text: r

text: that

text: applying

text: (v,

text: t)

text: has

text: the

text: same

text: eﬀect

text: on

text: c

text: as

text: applying

text: (v

text: t

text: More

text: formally,

text: (v,

text: t)

text: and

text: r

text: (v

text: t

text: are

text: equivalent

text: if

text: for

text: each

text: c

text: R

text: it

text: holds

text: that

text: (i)

text: (v,

text: t)

text: and

text: (v

text: t

text: decrease

text: the

text: r

text: number

text: of

text: approvals

text: c

text: gets

text: until

text: round

text: by

text: the

text: same

text: amount

text: and

text: (ii)

text: (v,

text: t)

text: and

text: (v

text: t

text: r

text: decrease

text: the

text: number

text: of

text: approvals

text: c

text: gets

text: until

text: round

text: by

text: the

text: same

text: amount.

text: A

text: pair

text: (v,

text: t)

text: r

text: can

text: behave

text: in

text: three

text: possible

text: ways

text: with

text: respect

text: to

text: c

text: it

text: can

text: leave

text: its

text: approval

text: count

text: until

text: r

text: round

text: (and

text: hence

text: also

text: its

text: approval

text: count

text: until

text: round

text: unchanged,

text: it

text: can

text: decrease

text: by

text: one

text: its

text: approval

text: count

text: in

text: round

text: (but

text: not

text: in

text: earlier

text: rounds),

text: or

text: it

text: can

text: decrease

text: by

text: one

text: its

text: approval

text: count

text: until

text: round

text: thereby

text: also

text: decreasing

text: its

text: approval

text: count

text: until

text: round

text: Therefore,

text: there

text: are

text: at

text: most

text: R

text: 3β

text: equivalence

text: classes.

text: Note

text: that

text: applying

text: some

text: pair

text: (v,

text: t)

text: instead

text: of

text: another

text: pair

text: that

text: is

text: equivalent

text: to

text: it

text: does

text: not

text: change

text: whether

text: a

text: given

text: push

text: action

text: is

text: successful

text: or

text: not.

text: Finally,

text: the

text: algorithm

text: proceeds

text: as

text: follows:

text: it

text: guesses

text: an

text: equivalence

text: class,

text: picks

text: a

text: cheap-

text: est

text: pair

text: (vi,

text: t)

text: from

text: this

text: class

text: that

text: has

text: not

text: been

text: applied

text: so

text: far,

text: and

text: applies

text: it.

text: Clearly,

text: in

text: some

text: of

text: the

text: at

text: most

text: R

text: branches

text: the

text: algorithm

text: will

text: choose

text: a

text: pair

text: that

text: can

text: be

text: extended

text: to

text: an

text: optimal

text: bribery,

text: if

text: there

text: exists

text: one.

text: It

text: repeats

text: this

text: step

text: until

text: it

text: reaches

text: the

text: bound

text: β

text: on

text: the

text: total

text: approval

text: count

text: modiﬁcation;

text: this

text: means

text: at

text: most

text: β

text: branchings.

text: By

text: the

text: arguments

text: above,

text: a

text: minimum-cost

text: solution

text: for

text: I

text: can

text: be

text: obtained

text: by

text: taking

text: a

text: minimum-cost

text: bribery

text: among

text: all

text: the

text: successful

text: briberies

text: (that

text: is,

text: ones

text: that

text: ensure

text: p’s

text: victory)

text: considered.

text: Positive

text: cost

text: functions.

text: Let

text: us

text: now

text: focus

text: on

text: the

text: case

text: of

text: positive

text: cost

text: functions,

text: where

text: each

text: bribery

text: can

text: only

text: increase

text: a

text: candidate’s

text: number

text: of

text: approvals.

text: For

text: each

text: possible

text: and

text: δ(p),

text: the

text: algorithm

text: tries

text: to

text: ﬁnd

text: a

text: minimal

text: δ(p))-bribery

text: t

text: of

text: minimum

text: cost

text: that

text: makes

text: p

text: a

text: winner.

text: This

text: means

text: considering

text: at

text: most

text: C

text: possibilities

text: for

text: and,

text: by

text: at

text: most

text: β

text: possibilities

text: for

text: δ(p).

text: Note

text: that

text: under

text: positive

text: cost

text: functions


text: a minimal successful bribery always bribes voters so that in each modiﬁed vote the approval count is equal to the rank of p. Consequently, the number of bribed voters in a minimal successful ((cid:96), δ(p))-bribery is δ(p), and no other candidate receives additional approvals in round (cid:96). Having picked (cid:96) and δ(p), the algorithm tries all possible ways of choosing a (multi)set { } · · · (cid:48) of positive integers t[1], . . . , t[δ(p)] with t[1] + + t[δ(p)] = β , corresponding to the increase of the approval counts of the bribed voters. In other words, it guesses the non-zero (cid:48) ≤ (cid:48) (cid:48) elements of t (but not their positions in t). There are at most β δ(p) β β possibilities. ∈ \ { } Then, the algorithm computes integers δ(c), c C p , such that ∈ \{ } (3’) an ((cid:96), δ(p))-bribery makes p a winner if and only if each candidate c C p gains at − most δ(c) points until round (cid:96) 1 (and hence until round (cid:96) as well), assuming that p − does not get a majority of votes in round (cid:96) 1 or earlier and gains exactly δ(p) points until round (cid:96). The procedure for computing δ(c) depends on whether we consider simpliﬁed or classic Fallback voting, and is polynomial-time implementable in either case. The next step of the algorithm uses the color-coding technique of Alon, Yuster, and Zwick [1]. This results in a randomized algorithm with one-sided error, which produces a − (cid:48) correct output with probability at least 2 δ(p)β ; this algorithm can then be derandomized using standard methods. We associate a color with each bribed voter. Colors are denoted by integers between 1 ≤ (cid:48) and δ(p); recall that t bribes exactly δ(p) voters, and we have δ(p) β . We construct a → { } ∈ coloring A : C 2 1,...,δ(p) by assigning each candidate c C a random subset A(c) of ∈ \ { } colors chosen uniformly and independently. Intuitively, for a candidate c C p that obtains additional approvals as a result of the bribery t, the set A(c) corresponds to the set of bribed voters in psh(C, V, t) who grant an additional approval to c. For candidate p, the set A(p) corresponds to the set of bribed voters that grant an additional approval to p until − ∈ \ { } | | ≤ round (cid:96) 1. We say that A is valid for a candidate c C p if A(c) δ(c); it is valid for | | ≤ (cid:98) (cid:99) − (cid:48) (cid:48) p if A(p) n/2 s − (p), where s − (p) denotes the number of approval points p gets (cid:96) 1 −(cid:96) 1 in the original election until round (cid:96) 1. A coloring is valid if it is valid for all candidates in C. The concept of validity reﬂects the fact that we have to fulﬁll condition (3’). Given a valid coloring of the candidates A, the algorithm computes the set of admissible ∈ ∈ { } colors for each voter vi V . A color x 1, . . . , δ(p) is admissible for vi if the following holds: ≤ − (a) rank(p, vi) = (cid:96)i + t[x] and t[x] (cid:96) (cid:96)i, i.e., in order to give an extra approval to p in vi (in round (cid:96) or earlier), the approval count has to be increased by exactly t[x]; ∈ (b) if rank(p, vi) < (cid:96), then x A(p); ∈ (c) for each candidate c with (cid:96)i < rank(c, vi) < rank(p, vi), we have x A(c). ≤ ≤ We say that a collection vi1, . . . , viδ(p) of voters is proper if for each x, 1 x δ(p), the color x is admissible for voter vix. 20

text: a

text: minimal

text: successful

text: bribery

text: always

text: bribes

text: voters

text: so

text: that

text: in

text: each

text: modiﬁed

text: vote

text: the

text: approval

text: count

text: is

text: equal

text: to

text: the

text: rank

text: of

text: p.

text: Consequently,

text: the

text: number

text: of

text: bribed

text: voters

text: in

text: a

text: minimal

text: successful

text: δ(p))-bribery

text: is

text: δ(p),

text: and

text: no

text: other

text: candidate

text: receives

text: additional

text: approvals

text: in

text: round

text: Having

text: picked

text: and

text: δ(p),

text: the

text: algorithm

text: tries

text: all

text: possible

text: ways

text: of

text: choosing

text: a

text: (multi)set

text: of

text: positive

text: integers

text: t[δ(p)]

text: with

text: t[δ(p)]

text: β

text: corresponding

text: to

text: the

text: increase

text: of

text: the

text: approval

text: counts

text: of

text: the

text: bribed

text: voters.

text: In

text: other

text: words,

text: it

text: guesses

text: the

text: non-zero

text: elements

text: of

text: t

text: (but

text: not

text: their

text: positions

text: in

text: t).

text: There

text: are

text: at

text: most

text: β

text: δ(p)

text: β

text: β

text: possibilities.

text: Then,

text: the

text: algorithm

text: computes

text: integers

text: δ(c),

text: c

text: C

text: p

text: such

text: that

text: an

text: δ(p))-bribery

text: makes

text: p

text: a

text: winner

text: if

text: and

text: only

text: if

text: each

text: candidate

text: c

text: C

text: p

text: gains

text: at

text: most

text: δ(c)

text: points

text: until

text: round

text: (and

text: hence

text: until

text: round

text: as

text: well),

text: assuming

text: that

text: p

text: does

text: not

text: get

text: a

text: majority

text: of

text: votes

text: in

text: round

text: or

text: earlier

text: and

text: gains

text: exactly

text: δ(p)

text: points

text: until

text: round

text: The

text: procedure

text: for

text: computing

text: δ(c)

text: depends

text: on

text: whether

text: we

text: consider

text: simpliﬁed

text: or

text: classic

text: Fallback

text: voting,

text: and

text: is

text: polynomial-time

text: implementable

text: in

text: either

text: case.

text: The

text: next

text: step

text: of

text: the

text: algorithm

text: uses

text: the

text: color-coding

text: technique

text: of

text: Alon,

text: Yuster,

text: and

text: Zwick

text: This

text: results

text: in

text: a

text: randomized

text: algorithm

text: with

text: one-sided

text: error,

text: which

text: produces

text: a

text: correct

text: output

text: with

text: probability

text: at

text: least

text: δ(p)β

text: this

text: algorithm

text: can

text: then

text: be

text: derandomized

text: using

text: standard

text: methods.

text: We

text: associate

text: a

text: color

text: with

text: each

text: bribed

text: voter.

text: Colors

text: are

text: denoted

text: by

text: integers

text: between

text: and

text: δ(p);

text: recall

text: that

text: t

text: bribes

text: exactly

text: δ(p)

text: voters,

text: and

text: we

text: have

text: δ(p)

text: β

text: We

text: construct

text: a

text: coloring

text: A

text: C

text: by

text: assigning

text: each

text: candidate

text: c

text: C

text: a

text: random

text: subset

text: A(c)

text: of

text: colors

text: chosen

text: uniformly

text: and

text: independently.

text: Intuitively,

text: for

text: a

text: candidate

text: c

text: C

text: p

text: that

text: obtains

text: additional

text: approvals

text: as

text: a

text: result

text: of

text: the

text: bribery

text: t,

text: the

text: set

text: A(c)

text: corresponds

text: to

text: the

text: set

text: of

text: bribed

text: voters

text: in

text: psh(C,

text: V,

text: t)

text: who

text: grant

text: an

text: additional

text: approval

text: to

text: c.

text: For

text: candidate

text: p,

text: the

text: set

text: A(p)

text: corresponds

text: to

text: the

text: set

text: of

text: bribed

text: voters

text: that

text: grant

text: an

text: additional

text: approval

text: to

text: p

text: until

text: round

text: We

text: say

text: that

text: A

text: is

text: valid

text: for

text: a

text: candidate

text: c

text: C

text: p

text: if

text: A(c)

text: δ(c);

text: it

text: is

text: valid

text: for

text: p

text: if

text: A(p)

text: s

text: (p),

text: where

text: s

text: (p)

text: denotes

text: the

text: number

text: of

text: approval

text: points

text: p

text: gets

text: in

text: the

text: original

text: election

text: until

text: round

text: A

text: coloring

text: is

text: valid

text: if

text: it

text: is

text: valid

text: for

text: all

text: candidates

text: in

text: C.

text: The

text: concept

text: of

text: validity

text: reﬂects

text: the

text: fact

text: that

text: we

text: have

text: to

text: fulﬁll

text: condition

text: Given

text: a

text: valid

text: coloring

text: of

text: the

text: candidates

text: A,

text: the

text: algorithm

text: computes

text: the

text: set

text: of

text: admissible

text: colors

text: for

text: each

text: voter

text: vi

text: V

text: A

text: color

text: x

text: δ(p)

text: is

text: admissible

text: for

text: vi

text: if

text: the

text: following

text: holds:

text: (a)

text: rank(p,

text: vi)

text: t[x]

text: and

text: t[x]

text: i.e.,

text: in

text: order

text: to

text: give

text: an

text: extra

text: approval

text: to

text: p

text: in

text: vi

text: (in

text: round

text: or

text: earlier),

text: the

text: approval

text: count

text: has

text: to

text: be

text: increased

text: by

text: exactly

text: t[x];

text: (b)

text: if

text: rank(p,

text: vi)

text: then

text: x

text: A(p);

text: (c)

text: for

text: each

text: candidate

text: c

text: with

text: rank(c,

text: vi)

text: rank(p,

text: vi),

text: we

text: have

text: x

text: A(c).

text: We

text: say

text: that

text: a

text: collection

text: viδ(p)

text: of

text: voters

text: is

text: proper

text: if

text: for

text: each

text: x,

text: x

text: δ(p),

text: the

text: color

text: x

text: is

text: admissible

text: for

text: voter

text: vix.


text: 5 Support Bribery for Single-Peaked Electorates One possible way to circumvent the hardness results of Section is to study the complexity of support bribery under restricted preferences. Recent work [5, 8, 11, 27] shows that many hard problems in computational social choice become easy if the voters’ preferences can be assumed to be single-peaked. In the next theorem we show that this is not the case for support bribery, as this problem remains NP-hard (and also W[1]-hard with parameter β) even for single-peaked electorates, for each of the voting rules considered in this paper. Theorem 11. support bribery under single-peaked preferences is NP-hard and W[1]- hard with respect to parameter β for each of SP-AV, Fallback and simpliﬁed Fallback, even | | if σi(k) = k for each k and each i = 1, . . . , n. Proof. We present a parameterized reduction from the W[1]-hard multicolored clique problem [29]; the same reduction works for SP-AV, Fallback, and simpliﬁed Fallback. Con- V E sider an instance of multicolored clique given by an integer k and a graph G = ( , ) V { } V V with the vertex set = ν , . . . , ν partitioned into k independent sets 1, . . . , k. With- 1 N ∈ V ∈ V out loss of generality we assume that ν 1 and ν k. 1 N We will construct an instance I of support bribery with unit costs for a single-peaked − election. We will set the budget B = 2k3 k and ensure that an optimal bribery has cost B if and only if G contains a k-clique, and that there always is a successful bribery of cost ≤ ≤ (cid:48) ≤ at most B + 1. Since I has unit costs, this would imply B β(I) β (I) B + 1. (cid:83) We form an election (C, V ) contained in I as follows. For each i = 1, . . . , k and each ∈ V { | ≤ ≤ (cid:54) } vertex ν i, we introduce a candidate set C(ν ) = cj 1 j k, j = i , and we set a ∪ { } ∪ a a CV = ∈V C(ν). We then set C = CV p, q D, where p is our preferred candidate and ν D is a set of dummies (see the next paragraph). (cid:67) We deﬁne a linear order on the set of candidates as follows. The ﬁrst candidate in this order is q, the last one is p, and candidate ci precedes cj if either a < b, or a = b but i < j. a b The dummy candidates are placed between candidates that are adjacent in the sequence − − q, c2, c3, . . . , ck 2, ck 1, p. Speciﬁcally, we place 2B dummies between q and c2, as well as 1 1 − N N 1 between ck 1 and p, and we place two dummies between every pair of adjacent candidates N (cid:67) (cid:5) in CV. The linear order is illustrated below ( signs stand for the dummies). (cid:122) (cid:125)(cid:124) (cid:123) (cid:122) (cid:125)(cid:124) (cid:123) (cid:122) (cid:125)(cid:124) (cid:123) (cid:122) (cid:125)(cid:124) (cid:123) − − C(ν1) plus 2(k 2) dummies C(νN) plus 2(k 2) dummies 2B dummies 2B dummies (cid:5) · · · · · · (cid:5) (cid:5) (cid:5) (cid:5) (cid:5) · · · (cid:5) (cid:5) − (cid:5) (cid:5) · · · · · · (cid:5) (cid:5) (cid:5) (cid:5) · · · (cid:5) (cid:5) − (cid:5) (cid:5) − (cid:5) · · · · · · (cid:5) q c2 c3 ck 1 ck c1 c2 ck 2 ck 1 p 1 1 1 1 N N N N ∈ V { } ∈ E For each vertex ν , we introduce a voter w , and for each edge ν , ν , we a { | ∈ Va} { | a{ b } ∈ E} introduce a voter w{ }. We let WV = w ν and WE = w{ } ν , ν . a,b a a a,b a b To deﬁne the preferences of these voters, we need additional notation. For each candidate (cid:67) c and each integer i, we denote by preci(c) the i-th candidate before c in , and we denote (cid:67) by succi(c) the i-th candidate after c in . We sometimes write succ(c) instead of succ1(c) (cid:48) (cid:67) · · · (cid:48) and prec(c) instead of prec1(c). If c precedes c in , we denote by c c the sequence (cid:48) (cid:67) of candidates from c to c (inclusively) with respect to ; the same sequence in reverse is 22

label: section

text: Support

text: Bribery

text: for

text: Single-Peaked

text: Electorates

text: One

text: possible

text: way

text: to

text: circumvent

text: the

text: hardness

text: results

text: of

text: Section

text: is

text: to

text: study

text: the

text: complexity

text: of

text: support

text: bribery

text: under

text: restricted

text: preferences.

text: Recent

text: work

text: shows

text: that

text: many

text: hard

text: problems

text: in

text: computational

text: social

text: choice

text: become

text: easy

text: if

text: the

text: voters’

text: preferences

text: can

text: be

text: assumed

text: to

text: be

text: single-peaked.

text: In

text: the

text: next

text: theorem

text: we

text: show

text: that

text: this

text: is

text: not

text: the

text: case

text: for

text: support

text: bribery,

text: as

text: this

text: problem

text: remains

text: NP-hard

text: (and

text: also

text: with

text: parameter

text: β)

text: even

text: for

text: single-peaked

text: electorates,

text: for

text: each

text: of

text: the

text: voting

text: rules

text: considered

text: in

text: this

text: paper.

text: Theorem

text: support

text: bribery

text: under

text: single-peaked

text: preferences

text: is

text: NP-hard

text: and

text: hard

text: with

text: respect

text: to

text: parameter

text: β

text: for

text: each

text: of

text: SP-AV,

text: Fallback

text: and

text: simpliﬁed

text: Fallback,

text: even

text: if

text: σi(k)

text: k

text: for

text: each

text: k

text: and

text: each

text: i

text: n.

text: Proof.

text: We

text: present

text: a

text: parameterized

text: reduction

text: from

text: the

text: multicolored

text: clique

text: problem

text: the

text: same

text: reduction

text: works

text: for

text: SP-AV,

text: Fallback,

text: and

text: simpliﬁed

text: Fallback.

text: Con-

text: V

text: E

text: sider

text: an

text: instance

text: of

text: multicolored

text: clique

text: given

text: by

text: an

text: integer

text: k

text: and

text: a

text: graph

text: G

text: V

text: V

text: V

text: with

text: the

text: vertex

text: set

text: ν

text: ν

text: partitioned

text: into

text: k

text: independent

text: sets

text: k.

text: With-

text: N

text: V

text: V

text: out

text: loss

text: of

text: generality

text: we

text: assume

text: that

text: ν

text: and

text: ν

text: k.

text: N

text: We

text: will

text: construct

text: an

text: instance

text: I

text: of

text: support

text: bribery

text: with

text: unit

text: costs

text: for

text: a

text: single-peaked

text: election.

text: We

text: will

text: set

text: the

text: budget

text: B

text: k

text: and

text: ensure

text: that

text: an

text: optimal

text: bribery

text: has

text: cost

text: B

text: if

text: and

text: only

text: if

text: G

text: contains

text: a

text: k-clique,

text: and

text: that

text: there

text: always

text: is

text: a

text: successful

text: bribery

text: of

text: cost

text: at

text: most

text: B

text: Since

text: I

text: has

text: unit

text: costs,

text: this

text: would

text: imply

text: B

text: β(I)

text: β

text: (I)

text: B

text: We

text: form

text: an

text: election

text: (C,

text: V

text: contained

text: in

text: I

text: as

text: follows.

text: For

text: each

text: i

text: k

text: and

text: each

text: V

text: vertex

text: ν

text: i,

text: we

text: introduce

text: a

text: candidate

text: set

text: C(ν

text: cj

text: j

text: k,

text: j

text: i

text: and

text: we

text: set

text: a

text: a

text: a

text: CV

text: ∈V

text: C(ν).

text: We

text: then

text: set

text: C

text: CV

text: p,

text: q

text: D,

text: where

text: p

text: is

text: our

text: preferred

text: candidate

text: and

text: ν

text: D

text: is

text: a

text: set

text: of

text: dummies

text: (see

text: the

text: next

text: paragraph).

text: We

text: deﬁne

text: a

text: linear

text: order

text: on

text: the

text: set

text: of

text: candidates

text: as

text: follows.

text: The

text: ﬁrst

text: candidate

text: in

text: this

text: order

text: is

text: q,

text: the

text: last

text: one

text: is

text: p,

text: and

text: candidate

text: ci

text: precedes

text: cj

text: if

text: either

text: a

text: b,

text: or

text: a

text: b

text: but

text: i

text: j.

text: a

text: b

text: The

text: dummy

text: candidates

text: are

text: placed

text: between

text: candidates

text: that

text: are

text: adjacent

text: in

text: the

text: sequence

text: q,

text: ck

text: ck

text: p.

text: Speciﬁcally,

text: we

text: place

text: dummies

text: between

text: q

text: and

text: as

text: well

text: as

text: N

text: N

text: between

text: ck

text: and

text: p,

text: and

text: we

text: place

text: two

text: dummies

text: between

text: every

text: pair

text: of

text: adjacent

text: candidates

text: N

text: in

text: CV.

text: The

text: linear

text: order

text: is

text: illustrated

text: below

text: signs

text: stand

text: for

text: the

text: dummies).

text: plus

text: dummies

text: C(νN)

text: plus

text: dummies

text: dummies

text: dummies

text: q

text: ck

text: ck

text: ck

text: ck

text: p

text: N

text: N

text: N

text: N

text: V

text: E

text: For

text: each

text: vertex

text: ν

text: we

text: introduce

text: a

text: voter

text: w

text: and

text: for

text: each

text: edge

text: ν

text: ν

text: we

text: a

text: Va}

text: a{

text: b

text: E}

text: introduce

text: a

text: voter

text: w{

text: We

text: let

text: WV

text: w

text: ν

text: and

text: WE

text: w{

text: ν

text: ν

text: a,b

text: a

text: a

text: a,b

text: a

text: b

text: To

text: deﬁne

text: the

text: preferences

text: of

text: these

text: voters,

text: we

text: need

text: additional

text: notation.

text: For

text: each

text: candidate

text: c

text: and

text: each

text: integer

text: i,

text: we

text: denote

text: by

text: preci(c)

text: the

text: i-th

text: candidate

text: before

text: c

text: in

text: and

text: we

text: denote

text: by

text: succi(c)

text: the

text: i-th

text: candidate

text: after

text: c

text: in

text: We

text: sometimes

text: write

text: succ(c)

text: instead

text: of

text: and

text: prec(c)

text: instead

text: of

text: If

text: c

text: precedes

text: c

text: in

text: we

text: denote

text: by

text: c

text: c

text: the

text: sequence

text: of

text: candidates

text: from

text: c

text: to

text: c

text: (inclusively)

text: with

text: respect

text: to

text: the

text: same

text: sequence

text: in

text: reverse

text: is