research
∙
05/17/2023
Improved Bounds for Single-Nomination Impartial Selection
We give new bounds for the single-nomination model of impartial selectio...
share
research
∙
05/02/2023
Incremental Maximization via Continuization
We consider the problem of finding an incremental solution to a cardinal...
research
∙
01/27/2023
Complexity of equilibria in binary public goods games on undirected graphs
We study the complexity of computing equilibria in binary public goods g...
research
∙
01/11/2023
Optimal Impartial Correspondences
We study mechanisms that select a subset of the vertex set of a directed...
research
∙
01/09/2023
Improved Approximation Algorithms for the Expanding Search Problem
A searcher faces a graph with edge lengths and vertex weights, initially...
research
∙
11/03/2022
The Polyhedral Geometry of Truthful Auctions
The difference set of an outcome in an auction is the set of types that ...
research
∙
09/20/2022
Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
This paper studies the problem of maximizing a monotone submodular funct...
research
∙
05/19/2022
Public Signals in Network Congestion Games
We consider a largely untapped potential for the improvement of traffic ...
research
∙
05/18/2022
Impartial Selection with Additive Guarantees via Iterated Deletion
Impartial selection is the selection of an individual from a group based...
research
∙
03/24/2022
Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs
This paper studies a variant of the minimum-cost flow problem in a graph...
research
∙
12/14/2021
Multi-Leader Congestion Games with an Adversary
We study a multi-leader single-follower congestion game where multiple u...
research
∙
08/02/2021
Generalized permutahedra and optimal auctions
We study a family of convex polytopes, called SIM-bodies, which were int...
research
∙
06/28/2021
Fractionally Subadditive Maximization under an Incremental Knapsack Constraint
We consider the problem of maximizing a fractionally subadditive functio...
research
∙
07/17/2020
Pure Nash Equilibria in Resource Graph Games
This paper studies the existence of pure Nash equilibria in resource gra...
research
∙
02/19/2019
Travelling on Graphs with Small Highway Dimension
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (...
research
∙
11/20/2018
Parametrized Nash Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians
We consider atomic splittable congestion games with affine cost function...
research
∙
05/31/2018
Computing all Wardrop Equilibria parametrized by the Flow Demand
We develop an algorithm that computes for a given undirected or directed...
research
∙
05/09/2018
Tight bounds for undirected graph exploration with pebbles and multiple agents
We study the problem of deterministically exploring an undirected and in...
research
∙
05/07/2018
Online Best Reply Algorithms for Resource Allocation Problems
We study online resource allocation problems with a diseconomy of scale....
research
∙
08/09/2017