8 papers
An Algorithm-to-Contract Framework without Demand Queries
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler +1
Consider costly and time-consuming tasks that add up to the success of a project, and must be fitted into a given time-frame. This is an instance of the classic budgeted maximizati…
Online Contract Design
Elad Lavi, Hadas Shachnai, Inbal Talgam-Cohen
We initiate the study of online contracts, which integrate the game-theoretic considerations of economic contract theory, with the algorithmic and informational challenges of onlin…
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
The -matroid intersection (-MI) problem asks if given matroids share a common basis. Already for , notable canonical NP-complete special cases are -…
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Ariel Kulik, Hadas Shachnai
In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best k…
Finding Possible Winners in Spatial Voting with Incomplete Information
Hadas Shachnai, Rotem Shavitt, Andreas Wiese
We consider a spatial voting model where both candidates and voters are positioned in the -dimensional Euclidean space, and each voter ranks candidates based on their proximity…
Spatial Voting with Incomplete Voter Information
Aviram Imber, Jonas Israel, Markus Brill +2
We consider spatial voting where candidates are located in the Euclidean -dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point…