## Background

## Voting

## Illustrative Example: Multi-Issue Elections and Lobbying

Voters →Electorateand Alternatives →IssuesPreferences →Approval Ballots(accept/reject) an issue Lobbying → Change a few votes to get all issues accepted...

and .

Can we change at most k rows of A such that each column has more 1's than 0's?

## Parameter: number of voters

[Christian/Fellows/Rosamond/Slinko, Review of Economic Design 2007]

An easy solution: brute-force

Also ETH-hardness (no algorithm) via a reduction from Vertex Cover

## Reduction overview

Based on the incidence matrix of the graph and some dummy entities

## Description

Start from an instance of Vertex Cover given by

Begin by setting to the incidence matrix ( columns, rows)

Add dummy rows + columns [total number of rows = ]

Add 1's in the dummy region so that each dummy column has exactly one 1 and each dummy row has exactly one 1.

Set

## Schematic - 1

## Schematic - 2

Dummy columns need at least rows to be coverted

## Example

## Parameter: size of solution

[Christian/Fellows/Rosamond/Slinko, Review of Economic Design 2007]

An easy solution: brute-force

Also W[2]-hard via a reduction from Dominating Set

Based on the incidence matrix of the graph and some dummy entities

## Description

Start from an instance of Dominating Set given by

Start with rows and columns

Add dummy rows (total number of rows = )

A column indexed by a vertex , in the top row positions, has 0’s in those rows that are indexed by vertices .

Set the dummy rows so that the total number of 0’s is one more than the total number of 1’s.

Use the extra column to "force" the solution to avoid dummy rows.

The parameter stays the same

## Schematic

The only zeroes in the column corresponding to are in the rows corresponding to .

## Parameter: number of candidates

[Bredereck/Chen/Hartung/Kratsch/Niedermeier/Suchy/Woeginger, JAIR 2014]

ILP-based FPT result for number of candidates

Desirable: variables

No polynomial kernel with respect to m + k

## ILP-based solution

Let be the number of rows of type that are affected. Note that number of types .

Let be the number of rows that ARE type .

Let be the target number of ones needed in column .

Let if and only if row i has a zero in column j

## Objective function

## Row constraints

## Column constraints

## Conclusion

FPT follows by Lenstra

[Lenstra, Mathematics of Operations Research, 1983]

Running time:

[Frank and Tardos, Combinatorica, 1987]
[Kannan, Mathematics of Operations Research, 1987]

Combinatorial methods? Better running time?