4 papers
Position Auctions with a Capacity Constraint
Eleni Batziou, Georgios Birmpas, Georgios Chionas +1
Sponsored search auctions are commonly modeled as an assignment of a fixed set of slots (positions) to a set of advertisers, with welfare maximization being reducible to a standard…
The Complexity of Sparse Win-Lose Bimatrix Games
Eleni Batziou, John Fearnley, Abheek Ghosh +1
We prove that computing an -approximate Nash equilibrium of a win-lose bimatrix game with constant sparsity is PPAD-hard for inverse-polynomial . Our result holds for 3-spars…
Monotone Contractions
Eleni Batziou, John Fearnley, Spencer Gordon +2
We study functions that are both monotone and contracting, and we consider the problem of finding an -approximate fixed point of $f…
Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem
Eleni Batziou, Kristoffer Arnsfelt Hansen, Kasper Høgh
In the consensus halving problem we are given n agents with valuations over the interval . The goal is to divide the interval into at most pieces (by placing at most n…