5 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 positions to a set of advertisers, with welfare maximization reducible to a standard matching prob…
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…
Assignment Markets with Budget Constraints
Eleni Batziou, Martin Bichler, Maximilian Fichtl
This paper studies markets where a set of indivisible items is sold to bidders with quasilinear, unit-demand valuations, subject to a hard budget constraint. Without financial cons…
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…