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-spa…
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…
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…