Externalities in Cake Cutting

1 Introduction

The area of Social Choice (and in particular the subarea of Computational Social Choice) is full of so-called negative results. On the one hand there are many axiomatic impossibility results, and on the other hand there are many computational intractability results. For instance, the famous impossibility result of Arrow [1950] states that there is no perfectly fair way (satisfying certain desirable axioms) of aggregating the preferences of a society of voters into a single preference ordering. As another example, Bartholdi et al. [1989] establish that it is computationally intractable (NP-hard) to determine whether some particular candidate wins an election under a voting scheme designed by Lewis Carroll. Most of these negative results hold for general preference profiles where any combination of preference orderings may occur.

One branch of Social Choice studies restricted domains of preference profiles, where only certain nicely structured combinations of preference orderings are admissible. The standard example for this approach are single-peaked preference profiles as introduced by Black [1948]: A preference profile is single-peaked if there exists a linear ordering of the alternatives such that any voter's preference along this ordering Gerhard J. Woeginger‡

∗Supported by the DFG project PAWS (NI 369/10).

†Supported by the Studienstiftung des Deutschen Volkes.

‡Supported by DIAMANT (a mathematics cluster of the Netherlands Organization for Scientific Research NWO), and by the Alexander von Humboldt Foundation.

TU Eindhoven, Netherlands gwoegi@win.tue.nl

is either always strictly increasing, always strictly decreasing, or first strictly increasing and then strictly decreasing. Single-peakedness implies a number of interesting properties, such as non-manipulability (Moulin [1980]) and transitivity of the majority rule (Inada [1969]). Under singlepeaked profiles, Arrow's impossibility result collapses. In a similar spirit (but in the algorithmic branch), Walsh [2007], Brandt et al. [2010], and Faliszewski et al. [2011b] show that many electoral bribery, control and manipulation problems that are NP-hard in the general case become tractable under single-peaked profiles. Besides the single-peaked domain, the literature contains many other restricted domains of nicely structured preference profiles (see Section 2 for precise mathematical definitions).

• Sen [1966] and Sen and Pattanaik [1970] introduced the domain of value-restricted preference profiles which satisfy the following: for any triple of alternatives, one alternative is not considered as the most preferred by any individual (best-restricted), or one is not considered as the least preferred by any individual (worst-restricted), or one is not considered as the intermediate alternative by any individual (medium-restricted).
• Inada [1964; 1969] considered the domain of groupseparable preference profiles which satisfy the following: the alternatives can be split into two groups such that every voter prefers every alternative in the first group to those in the second group, or prefers every alternative in the second group to those in the first group. Every group-separable profile is also medium-restricted.
• Single-caved [Inada, 1964] preference profiles result from a single-peaked profiles by reversing the preferences of every voter. Sometimes single-caved profiles are also called single-dipped [Klaus et al., 1997].
• Single-crossing preference profiles go back to a seminal paper of Roberts [1977] on income taxation. A preference profile is single-crossing if there exists a linear ordering of the voters such that for any pair of alternatives along this ordering, either all voters have the same opinion on the ordering of these two alternatives or there is a single spot where the voters switch from preferring one alternative to the other one.

Just like single-peakedness, each of these restrictions guarantees many nice properties, such as the transitivity of the simple majority rule. Unfortunately, real-world elections are almost never single-peaked, value-restricted, group-separable, single-caved or single-crossing. Often there are maverick voters whose vote is determined by race, religion or gender. Mavericks destroy nice combinatorial structures in the preference profiles. In a very recent line of research, Faliszewski et al. [2011a] searched a cure against such mavericks, and arrived at nearly single-peaked preference profiles: A profile is nearly single-peaked, if it is very close to a single-peaked profile. Of course, there are many mathematical ways of measuring the distance of profiles. Perhaps, the most natural way is (i) by deletion of voters or (ii) by deletion of alternatives. Faliszewski et al. analyze various control and bribery problems under such nearly single-peaked profiles, and derive a number of somewhat unexpected results.

In a closely related paper (with a disjoint set of results), Erd´elyi et al. [2013] study various notions of nearly singlepeaked profiles. Besides deletion of voters and deletion of alternatives, they also study distance measures that are based on swapping alternatives in the preferences of some voters, or on introducing additional political axes. However, their investigations are limited to single-peaked profiles.

Results of this paper. We investigate the problem of deciding the distance (by deletion of voters and by deletion of alternatives) of a given preference profile to a nicely structured one of a certain type (like being single-crossing, valuerestricted, or group-separable). We focus on some of the most fundamental definitions of distance measures and on the most popular restricted domains. Our results draw a clear line between computationally tractable (polynomial-time solvable) and computationally intractable (NP-hard) questions as they classify all considered problem variants with respect to their computational complexity. See Table 1 for an overview.

This paper is organized as follows. Section 2 summarizes all the basic definitions and notations. Section 3 surveys our main results. We conclude in Section 4. Due to lack of space, we defer some proofs to a full version of the paper.

2 Preliminaries and Basic Notations

Let a1, . . . , am be m alternatives and let v1, . . . , vn be n voters. A preference profile specifies the preference orderings of the voters, where voter vi ranks the alternatives according to a strict linear order ≻i. For alternatives a and b, a ≻i b means that voter vi strictly prefers a to b. We omit the subscript i if it is clear from the context whose preference ordering we are referring to.

Given two sets A and B of alternatives, we write A ≻i B to express that voter vi prefers set A to set B, that is, for each alternative a ∈ A and each alternative b ∈ B it holds that a ≻i b. In a similar way, we use A ≻i a to denote that voter vi prefers every alternative in A to alternative a and a ≻i A for the reverse situation. If we define the canonical ordering of the alternatives in A, then 〈A〉 denotes this canonical linear ordering. Further, 〈A1〉 ≻ 〈A2〉 denotes the preference ordering that is consistent with 〈A1〉 as well as 〈A2〉 and prefers all vertices in A1 to all vertices in A2.

Next, we review some concrete preference profiles of small size with special properties studied in the literature [Ballester and Haeringer, 2011; Bredereck et al., 2012]. We call such profiles configurations.

Value-restricted profiles. The first three configurations describe profiles with three alternatives where each alternative is at the best, medium, or worst position in some voter's preference ordering.

Definition 1 (Best-diverse configuration). A profile with three voters v1, v2, v3 and three distinct alternatives a, b, c is a best-diverse configuration if it satisfies the following:

Definition 2 (Medium-diverse configuration). A profile with three voters v1, v2, v3 and three distinct alternatives a, b, c is a medium-diverse configuration if it satisfies the following:

• v1: b ≻1 a ≻1 c or c ≻1 a ≻1 b;
• v2: a ≻2 b ≻2 c or c ≻2 b ≻2 a;
• v3: a ≻3 c ≻3 b or b ≻3 c ≻3 a.

Definition 3 (Worst-diverse configuration). A profile with three voters v1, v2, v3 and three distinct alternatives a, b, c is a worst-diverse configuration if it satisfies the following:

We use these three configurations to characterize several restricted domains: A profile is best-restricted (resp. mediumrestricted, worst-restricted) with respect to a triple T of alternatives if it contains no three voters that form a bestdiverse configuration (resp. a medium-diverse configuration, a worst-diverse configuration) with respect to T. A bestrestricted (resp. medium-restricted, worst-restricted) profile is best-restricted (resp. medium-restricted, worst-restricted) with respect to every possible triple of alternatives.

A profile is value-restricted [Sen, 1966] if for any triple T of alternatives, it is best-restricted, medium-restricted, or worst-restricted with respect to T .

Single-peaked profiles and single-caved profiles. The single-peaked property requires the existence of a "natural" linear ordering of the alternatives: A profile is singlepeaked [Black, 1948] if there is an ordering L of alternatives such that for each voter v, L can be split into two orderings L1 and L2, and v prefers each alternative a in L1 to any alternative to a's left while he prefers each alternative b in L2 to any alternative to b's right. Single-peaked preferences are necessarily worst-restricted. In addition, we need the following configuration to fully characterize the single-peaked domain:

Definition 4 (α-configuration). A profile with two voters v1 and v2, and four distinct alternatives a, b, c, d is an αconfiguration if it satisfies the following:

v1: a ≻1 b ≻1 c and d ≻1 b; v2: c ≻2 b ≻2 a and d ≻2 b.

The α-configuration represents a situation where two voters have opposite opinions on the ordering of three alternatives a, b and c but agree that a fourth alternative d is "better" than the one ranked in the middle. The profile is not singlepeaked, as alternatives b and d must be put between alternatives a and c, but then voter v1 prevents us from putting b next to a and voter v2 prevents us from putting d next to a.

Ballester and Haeringer [2011] show that a profile is single-peaked if and only if it is worst-restricted and contains no α-configurations. They also show that a profile is singlecaved if and only if it is best-restricted and contains no ¯αconfigurations, where an ¯α-configuration is a α-configuration with both preference orderings being reversed.

Group-separable profiles. The group-separable property requires that the set A of alternatives can be partitioned into two subsets A1 and A2 such that for each voter vi: A1 ≻i A2 or A2 ≻i A1. Group-separable profiles are necessarily medium-restricted. In addition, we need the following configuration to fully characterize this property:

Definition 5 (β-configuration). A profile with two voters v1 and v2 and four distinct alternatives a, b, c, d is a βconfiguration if it satisfies the following:

v1: a ≻1 b ≻1 c ≻1 d; v2: b ≻2 d ≻2 a ≻2 c.

The β-configuration represents a situation where the best and least preferred alternatives of the first voter are a and d which are different from the ones of the second voter: b and c. Both voters agree that b is better than c, but disagree whether d is better than a. This profile is not group-separable: We cannot partition the four alternatives into a one-alternative set and a three-alternatives set as each alternative is ranked in the middle once, and we cannot partition them into two subsets of size two each since voter v1 prevents us from putting alternatives a and c or alternatives a and d together and voter v2 prevents us from putting alternatives a and b together.

A profile is group-separable if and only if it contains neither medium-diverse configurations nor βconfigurations [Ballester and Haeringer, 2011].

Single-crossing profiles. The single-crossing property requires the existence of a "natural" linear ordering of the voters. A profile is single-crossing if there exists a linear ordering of the voters such that for any two alternatives along this ordering, there is a single spot where the voters switch from preferring one alternative to the other one. To characterize single-crossing preferences, we need the following two configurations.

Definition 6 (γ-configuration). A profile with three voters v1, v2, v3 and six (not necessarily distinct) alternatives a, b, c, d, e, f is a γ-configuration if it satisfies the following:

v1: b ≻1 a and c ≻1 d and e ≻1 f; v2: a ≻2 b and d ≻2 c and e ≻2 f;

v3: a ≻3 b and c ≻3 d and f ≻3 e.

The γ-configuration represents a situation where each voter disagrees with the other two voters on the ordering of exactly two distinct alternatives. The profile is not single-crossing, as none of the three voters can be put between the other two: The pair {a, b} prevents us from putting v1 into the middle, the pair {c, d} forbids voter v2 in the middle, and the pair {e, f} forbids v3 in the middle.

Definition 7 (δ-configuration). A profile with four voters v1, v2, v3, v4 and four (not necessarily distinct) alternatives a, b, c, d is a δ-configuration if it satisfies the following:

v1: a ≻1 b and c ≻1 d; v2: a ≻2 b and d ≻2 c; v3: b ≻3 a and c ≻3 d; v4: b ≻4 a and d ≻4 c.

The δ-configuration shows a different kind of voter behavior: Two voters disagree with the other two voters on the ordering of two alternatives, but also disagree between each other on the ordering of two further alternatives. As before, this profile is not single-crossing, as the pair {a, b} forces us to place v1 and v2 next to each other, and to put v3 and v4 next to each other; the pair {c, d} forces us to place v1 and v3 next to each other, and to put v2 and v4 next to each other. This means that no voter can be put into the first position.

A profile is single-crossing if and only if it contains neither γ-configurations nor δ-configurations [Bredereck et al., 2012].

Two central problems. As already discussed before, two natural ways of measuring the distance of profiles to some restricted domains is by deleting voters and by deleting alternatives. Hence, for Π∈{worst-restricted, medium-restricted, best-restricted, value-restricted, single-peaked, single-caved, single-crossing, group-separable}, we study the following two types of modification problems: Π MAVERICK DELETION and Π ALTERNATIVE DELETION.

Π MAVERICK DELETION

Input: A profile with n voters and an integer k ≤ n.

Question: Can we delete at most k voters such that the resulting profile has the Π-property?

Π ALTERNATIVE DELETION

Input: A profile with m alternatives and an integer k ≤ m. Question: Can we delete at most k alternatives such that the resulting profile has the Π-property?

3 Results

It is easy to see that both Π MAVERICK DELETION and Π ALTERNATIVE DELETION are in NP with Π being one of the eight properties we consider: Given a preference profile, one can check in polynomial time whether it is Π, since the Π-property is characterized by a fixed number of forbidden substructures. Thus, in order to show the NP-completeness of Π MAVERICK DELETION and Π ALTERNATIVE DELETION, we only have to show their NP-hardness.

We will use the NP-complete VERTEX COVER (VC) problem [Garey and Johnson, 1979] to show many of our NPhardness results: Given an undirected graph G = (U, E) and a non-negative integer k, VC asks whether there is a vertex cover U ′ ⊆ U of at most k vertices, that is, each edge is incident to at least one vertex in U ′ .

On deleting maverick voters. We start our findings on intractability results with the four domain-restrictions which are characterized by configurations with three alternatives.

Theorem 8. Π MAVERICK DELETION is NP-complete for every Π ∈ {best-restricted, medium-restricted, worstrestricted, value-restricted}.

Proof. We reduce from VC to show the NP-hardness result. Let (G, k) denote a VC-instance with vertex set U = {u1, . . . , ur} and edge set E = {e1, . . . , es}; without loss of generality r ≥ 4. The set of alternatives consists of three edge alternatives aj, bj, and cj for each edge ej ∈ E. The voter set one-to-one corresponds to vertex set U. In total, the number m of alternatives is 3s and the number n of voters is r. All voters prefer {aj, bj, cj} to {aj ′ , bj ′ , cj ′} whenever j < j ′ . Moreover, voter vi has aj ≻ bj ≻ cj if vi /∈ ej. Otherwise, let edge ej = {vi, vi′}. Voter vi ranks cj ≻ aj ≻ bj if i < i′ , and ranks bj ≻ cj ≻ aj, otherwise. In this way, the two vertex voters in ej and any other voter vz not in ej form a worst-diverse configuration, a medium-diverse configuration as well as a best-diverse configuration regarding the three edge alternatives ai,bi, and ci. The parameter k is the same. The whole construction runs in polynomial time. Due to lack of space, its correctness proof is deferred to a full version of the paper.

The profile constructed in the proof of Thm. 8 does not contain α-configurations, ¯α-configurations, or βconfigurations. Hence, NP-hardness transfers to singlecaved, group-separable, and single-peaked cases, respectively. Note that NP-hardness for SINGLE-PEAKED MAVERICK DELETION is already known by a different proof of Erd´elyi et al. [2013]. However, their proof does not work for Π MAVERICK DELETION with Π∈ {best-restricted, mediumrestricted, worst-restricted, group-separable}.

Corollary 9. Π MAVERICK DELETION is NP-complete for every Π∈{single-caved, group-separable, single-peaked}.

In contrast to all NP-complete Π MAVERICK DELETION problems above, SINGLE-CROSSING MAVERICK DELETION is tractable. The algorithm, which is similar to the single-crossing detection algorithm of Elkind et al. [2012], does not only solve the decision problem but the optimization problem asking for the smallest number k of voters to delete in order to make the profile single-crossing.

Theorem10. SINGLE-CROSSING MAVERICK DELETION is solvable in O(n3 · m2 ) time, where n denotes the number of voters and m denotes the number of alternatives.

Proof. In the following, we assume that the voters have pairwise distinct preference orderings. By using arc weights in the graphs to be constructed, the algorithm can be extended to also work for general preference profiles. Let vi, vi′ , and vi′′ be three distinct voters. We say that voter vi′ is ≻i-swaptransferable to voter vi′′ if one can transform the preference ordering of vi′ to the one of vi′′ by repetitive swapping of two alternatives aj and aj ′ with aj ≻i aj ′ and aj ≻i′ aj ′ .

Let L = 〈v1, . . . , vi′ , . . . , vi′′ , . . . 〉 be a linear ordering of voters with vi′ and vi′′ being two distinct voters. Then, by definition of single-crossing profiles, vi′ is ≻1-swaptransferable to vi′′ , but vi′′ is not ≻1-swap-transferable to vi′ .

The idea is to guess (by testing all) the first voter in a single-crossing ordering and to compute a maximum set of possible successive voters. This idea is realized as follows.

For each voter vi, build a directed graph Di with one vertex for each voter. Add an arc from vertex x to vertex y if x is ≻i-swap-transferable to y. By the definition of the swapoperation, the graph becomes acyclic. Now, a vertex ordering in a longest directed path among these graphs represents a single-crossing ordering of a subset of voters of maximum size. Thus, the minimum number k of voters to delete to make the profile single-crossing is n - ℓ with n being the number of voters and ℓ the length of a longest path.

Constructing Di takes O(n2 ·m2 ) time: Check for each ordered pair (x, y) of vertices whether the voter corresponding to x is ≻i-swap-transferable to y by checking any two alternatives. Computing the longest path in each Di takes O(n2 ) time. Thus, checking all n graphs takes O(n3 ·m2 ) time.

On deleting alternatives. Another way of obtaining nicely structured preference profiles is to delete alternatives. The corresponding problems are studied in the remainder of this section.

Theorem 11. Π ALTERNATIVE DELETION is NP-complete for every Π ∈ {best-restricted, medium-restricted, worstrestricted, value-restricted}.

Proof. We show a polynomial-time many-one reduction from VC to Π ALTERNATIVE DELETION with Π ∈ {mediumrestricted, value-restricted, worst-restricted}. For BESTRESTRICTED ALTERNATIVE DELETION one has to reverse all preference orderings in the forthcoming construction.

Let (G, k) denote a VC-instance with vertex set U = {u1, . . . , ur} and edge set E = {e1, . . . , es}. The set of alternatives consists of all vertices in U and of k + 1 new dummy alternatives. Let D denote the set of these new dummy alternatives. We arbitrarily fix a canonical ordering of D and set 〈U〉 = 〈u1, . . . , ur〉. The number m of constructed alternatives is r + k + 1. We introduce a voter v0 with the special preference ordering 〈D〉 ≻ 〈U〉. Furthermore, for each edge ei = {uj, uj ′} with j < j ′ , we introduce two edge voters v2i-1 and v2i with preference orderings uj ≻ uj ′ ≻ 〈D〉 ≻ 〈U \ ei〉 and uj ′ ≻ 〈D〉 ≻ 〈U \ {uj ′}〉, respectively. Together with voter v0, these two voters v2i-1 and v2i form a worst-diverse configuration and a mediumdiverse configuration with respect to the two vertex alternatives uj, uj ′ and any dummy alternative. In total, the number n of constructed voters is 2s+1. The parameter k remains the same. This completes the construction.

Our reduction runs in polynomial time. It remains to show its correctness. In particular, we show that (G, k) has a vertex cover of size at most k if and only if the constructed profile can be made worst-restricted (resp. medium-restricted), and hence, value-restricted by deleting at most k alternatives.

For the "only if" part, suppose that U ′ ⊆ U with |U ′ | ≤ k is a vertex cover. First, we show that after deleting the vertex alternatives corresponding to U ′ , the resulting profile is worst-restricted and, hence, value-restricted. Suppose for the sake of contradiction that the resulting profile still contains a worst-diverse configuration σ. Since all voters have the same ranking over D, σ contains at most one dummy alternative. But if σ contains one dummy alternative d ∈ D, then there is a voter with u ≻ u′ ≻ d, u, u′ ∈ U which means that edge {u, u′ } is not covered by U ′ . Hence, σ contains no dummy alternative. This means that σ contains three vertex alternatives uj , uj ′ , and uj ′′ with j < j ′ < j ′′ and by the definition of the worst-diverse configuration, σ concerns three voters with preferences {uj , uj ′ }≻uj ′′ , {uj , uj ′′ }≻uj ′ , and {uj ′ , uj ′′} ≻ uj, respectively. However, the last preference implies that {uj ′ , uj ′′} is an edge which is not covered by U ′-a contradiction.

Second, we show that after deleting the vertex alternatives corresponding to U ′ the resulting profile is mediumrestricted. Suppose for the sake of contradiction that the resulting profile still contains a medium-diverse configuration σ′ . Since all voters have the same ranking over D and no voter ranks d ≻ u ≻ d′ with d, d′ ∈ D and u ∈ U, σ′ can contain at most one dummy alternative. Now, if σ′ involves one dummy alternative d ∈ D and two vertex alternatives uj, uj ′ ∈ U with j < j ′ , then the voter ranking uj ′ between uj and d must have uj ≻ uj ′ ≻ d. But this means that {uj , uj ′ } is an uncovered edge-a contradiction. Hence, assume that σ′ contains no dummy alternative. This means that σ′ must involve three vertex alternatives uj , uj ′ , uj ′′ with j<j ′ <j ′′ . However, there is no voter with uj ≻uj ′′ ≻uj ′ or uj ′ ≻uj ′′ ≻uj in the resulting profile-a contradiction.

For the "if" part, suppose that the constructed profile is a yes-instance for the worst-restricted or the medium-restricted case. Let U ′ ⊆ U be the set of deleted vertex alternatives with |U ′ | ≤ k. Then U ′ is also a vertex cover of G. Assume towards a contradiction that ei = {uj , uj ′} (j < j ′ ) is an uncovered edge. Since |D|>k, at least one dummy alternative d is not deleted. Then, v0 and v2i, v2i-1 form a worst-diverse configuration as well as a medium-diverse configuration regarding uj , uj ′ , d-a contradiction.

The profile which results from deleting alternatives from the profile constructed in the proof of Thm. 11 is not only medium-restricted, but it even contains no β-configurations. By the definition of group-separability, this means that the NP-completeness result of MEDIUM-RESTRICTED ALTERNATIVE DELETION also holds for the group-separable case.

Corollary 12. GROUP-SEPARABLE ALTERNATIVE DELETION is NP-complete.

While making a profile single-crossing by deleting as few maverick voters as possible is in P, the decision variant of this problem becomes NP-hard if one instead deletes alternatives.

Theorem 13. SINGLE-CROSSING ALTERNATIVE DELETION is NP-complete.

Proof. For the NP-hardness result we reduce from the NP-complete satisfiability problem MAXIMUM 2SATISFIABILITY (MAX2SAT) [Garey and Johnson, 1979]. Given a set U of Boolean variables, a collection C of size-two clauses over U and a positive integer k′ , MAX2SAT asks whether there is a truth assignment for U such that at least k′ clauses in C are satisfied.

Let (U,C, k′ ) be a MAX2SAT-instance with variable set U ={x1, . . . , xr} and clause set C={c1, . . . , cs}. There are two sets O and O of 2(rs + r + s) + 1 dummy alternatives each. For each variable xi ∈ U, there are two sets Xi and Xi of s + 1 variable alternatives each. We say that Xi corresponds to xi and that Xi corresponds to xi. The canonical orderings 〈O〉, 〈O〉, 〈Xi〉 and 〈Xi〉, i ∈ {1, . . . , r}, are arbitrary but fixed. Let X be the union ⋃ri=1 Xi ∪Xi of all variable alternatives. The canonical ordering 〈X〉 is 〈X1〉≻〈X1〉≻. . .≻〈Xr〉≻〈Xr〉. For each clause cj ∈ C, there are two clause alternatives aj and bj. Let A denote the set of all clause alternatives. The canonical ordering 〈A〉 is a1 ≻ b1 ≻ . . . ≻ as ≻ bs. The total number m of alternatives is 6(rs + r + s) + 2.

The rough idea is that deleting all alternatives in Xi corresponds to setting xi to true, and deleting all alternatives in Xi corresponds to setting xi to false. Furthermore, deleting bj or aj corresponds to not-satisfied clause cj.

To this end, let the parameter k be r(s + 1) + (s - k′ ). There are two sets V and W of voters with |V | = 2r and |W| = 4s. Voter set V consists of two voters v2i-1 and v2i for each variable xi. Their preference orderings are

These two voters together with any other two voters vl and vl′ ∈ V \ {v2i-1, v2i} with odd l and even l′ form a δconfiguration regarding o ∈ O, o ∈ O, x ∈ Xi, x ∈ Xi:

Voter set W consists of four voters w4j-3, w4j-2, w4j-1, and w4j for each clause cj. These four voters have the same preference ordering 〈O〉 ≻ 〈O〉 ≻ 〈A1〉 ≻ 〈X〉 ≻ 〈A2〉 over set O ∪ O ∪ A1 ∪ A2 ∪X, where A1 = {aj ′ , bj ′ | j ′ < j} and A2 = {aj ′ , bj ′ | j ′ > j}. The positions of aj and bj are placed as follows: Let ̂Xj 1 denote the set of variable alternatives corresponding to the literal in cj with lower index and ̂Xj 2 denote the set of variable alternatives corresponding to the literal in cj with higher index. Voters w4j-3 and w4j-2 rank clause alternatives aj right below the last alternative in 〈 ̂Xj 1 〉 while voters w4j-1 and w4j rank it right above the first alternative in 〈 ̂Xj 1 〉. As for alternative bj, voters w4j-3 and w4j-1 rank bj right above the first variable alternative in 〈 ̂Xj 2 〉 while voters w4j-2 and w4j rank it right below the last variable alternative in 〈 ̂Xj 2 〉. Thus, these four voters form a δconfiguration regarding aj , bj , x ∈ ̂Xj 1 , and y ∈ ̂Xj 2 :

The reduction clearly runs in polynomial time. It remains to show that (U,C, k′ ) is a yes-instance for MAX2SAT if and only if the constructed profile together with k is a yesinstance for SINGLE-CROSSING ALTERNATIVE DELETION.

For the "only if" part, suppose that there is a truth assignment U→{true, false}r of the variables such that at least k′

clauses are satisfied. We delete all variable alternatives in Xi if xi is assigned to true, and delete all variable alternatives in Xi, otherwise. Furthermore, we delete the clause alternative bj if cj is not satisfied by the assignment. Let X′ be the set of remaining variable alternatives, and A′ the set of all remaining clause alternatives. Then the number of deleted alternatives is |X|+|A|-(|X′ |+|A′ |) ≤ r(s+1)+(s-k′ ) = k.

For each j ∈ {1, . . . , s}, we define zj by 〈zj〉 = 〈w4j-2,w4j,w4j-3,w4j-1〉 if the literal in clause cj with lower index is satisfied; otherwise, 〈zj〉 = 〈w4j-3,w4j-2,w4j-1,w4j〉. The resulting profile is single-crossing with respect to the voter ordering L := 〈v1, v3, . . . , v2r-1, v2, v4, . . . , v2r, z1, z2, . . . , zs〉. To show this, we define the concept of "separation": If 〈L〉 is a linear ordering of voters, then we say that a pair {a, b} of distinct alternatives separates ordering 〈L〉 (into two orderings 〈L1〉 and 〈L2〉) if 〈L〉 = 〈L1, L2〉 and no voter in 〈L1〉 agrees with any voter in 〈L2〉 on the ordering of a and b. Obviously, L is single-crossing if it can be separated by every possible pair of alternatives.

Suppose for the sake of contradiction that L is not a singlecrossing ordering which means that L cannot be separated by a pair {a, a′} ⊂ O ∪ O ∪ X′ ∪ A′ of alternatives. Note that all voters along L up to and including voter v2r-1 rank 〈O〉 ≻ 〈O〉 ≻ 〈X〉 while all voters from v2 onwards rank 〈O〉 ≻ 〈O〉 ≻ 〈X〉. Hence, a and a′ can neither both be in O ∪O, nor both be in X′ . Furthermore, a and a′ cannot both be in A′ , as all voters have the same ranking 〈A〉. Since all voters rank (O ∪ O) ≻ (X ∪ A), a and a′ are not in O ∪ O. This means, without loss of generality, a ∈ X′ and a′ ∈ A′ .

Assume that alternative a′ ∈ {aj, bj}. Then, alternative a cannot be in X′ \ ( ̂Xj 1 ∪ ̂Xj 2 ) since pair {a′ , a′′} with a′′ ∈ X′ \ ( ̂Xj 1 ∪ ̂Xj 2 ) separates ordering L into two orderings L1 and L2 where either L1 = 〈v1, v3, . . . , v2r-1, v2, v4, . . . , v2r, z1, z2, . . . , zj〉 and L2 = 〈zj+1, zj+2, . . . , zs〉, or L1 = 〈v1, v3, . . . , v2r-1, v2, v4, . . . , v2r, z1, z2, . . . , zj-1〉 and L2 = 〈zj, zj+1, . . . , zs〉. Thus, a ∈ ̂Xj 1 ∪ ̂Xj 2 . If the literal in cj with lower index is satisfied, then all variable alternatives in ̂Xj 1 are deleted and zj = 〈w4j-2,w4j,w4j-3,w4j-1〉. Hence, a ∈ ̂Xj 2 . All voters along L up to and including w4j prefer a to a′ , and all voters onwards w4j-3 prefer a′ to a. Hence, L is separated by {a, a′}. Otherwise, either bj or all alternatives in ̂Xj 2 are deleted, thus, zj = 〈w4j-3,w4j-2,w4j-1,w4j〉. If bj is deleted, then all voters along L up to and including w4j-2 prefer each a ∈ ̂Xj 1 ∪ ̂Xj 2 to a′ = aj, and all voters onwards w4j-3 prefer a′ = aj to each a ∈ ̂Xj 1 ∪ ̂Xj 2 . Otherwise, all alternatives in ̂Xj 2 are deleted. So, all voters along L up to and including w4j-2 prefer each a ∈ ̂Xj 1 to each a′ ∈ {aj, bj}, and all voters onwards w4j-3 prefer each a′ ∈ {aj, bj} to each a ∈ ̂Xj 1 ∪ ̂Xj 2 . Hence, L is separated by {a, a′ }. In summary, L can always be separated by {a, a′}-a contradiction to the assumption that L is not a single-crossing ordering.

For the "if" part, suppose that deleting a set K of at most k alternatives makes the remaining profile single-crossing. This means that by deleting K one eliminates all δ-configurations. Note that deleting K \ (O ∪ O) also results in a singlecrossing profile: Assume towards a contradiction that there is a δ-configuration involving a set D of alternatives with D∩(K\(O∪O)) = ∅. Clearly, D contains exactly two alternatives in O and in O each since otherwise σ does not form a δ-configuration or K is not a solution. Since |O| = |O| > k, there are two alternatives o∗ ∈ O and o∗ ∈ O which are not in K. If we replace the alternatives in D that are from O ∪O with o∗ and o∗ , then we get a δ-configuration for the profile which remains after deleting K-a contradiction. Hence, in the following we assume without loss of generality that none of the dummy alternatives is deleted.

For each xi ∈ U, all variable alternatives in either Xi or Xi must be deleted to destroy all δ-configurations involving alternatives in O ∪ O ∪ Xi ∪ Xi. Let X′ be the set of all deleted variable alternatives and let A′ be the set of all deleted clause alternatives. Then, |X′ | ≥ r(s + 1) and |A′ | ≤ k - r(s + 1) = s - k′ . We show that by setting variable xi ∈ U to true if Xi ⊆ X′ , and false otherwise, all clauses cj with {aj, bj} ∩ A′ = ∅ are satisfied. Suppose for the sake of contradiction that clause cj with {aj , bj}∩A′ = ∅ is not satisfied. This means both ̂Xj 1 as well as ̂Xj 2 are not completely in X′ . But then, voters w4i-3,w4i-2,w4i-1, and w4i form a δ-configuration regarding aj, bj, x, x′ with x ∈ ̂Xj 1 \X′ and x′ ∈ ̂Xj 2 \ X′ -a contradiction.

4 Conclusion

In terms of computational complexity theory, little is known about preference profiles which are "close" to being nicely structured. We showed that making a profile single-crossing by deleting as few voters as possible can be solved in polynomial time. In contrast, making a profile nicely structured by deleting at most k voters or at most k alternatives is NPhard for all other considered cases. However, we mention in passing that all these problems become tractable when k is small: All considered properties are characterized by a fixed number of forbidden substructures. Thus, by branching over all possible voters (resp. alternatives) of each forbidden substructure in the profile one obtains a fixed-parameter algorithm [Downey and Fellows, 1999; Flum and Grohe, 2006; Niedermeier, 2006] that is efficient for small distances. One line of future research is to investigate more sophisticated and more efficient (fixed-parameter) algorithms to compute the distance of a profile to a nicely-structured one.

A second line of research which has already been started by Erd´elyi et al. [2013] for single-peaked profiles is to study further distance measures.

A third line of research is to investigate whether and in which way properties of nicely structured preference profiles transfer to profiles that are only close to being nicely structured. This has been started by Faliszewski et al. [2011a] for some notion of nearly single-peakedness which is different from, but related to ours. They investigate cases where the computational tractability of attacks on single-peaked profiles transfers to nearly single-peaked preferences, and cases where the vulnerability disappears even if the preference profile is extremely close to being single-peaked.