44 citations · 80 across the 32 of their papers we have counts for
15 papers · 1 filter
Sequential Linear Contracts on Matroids
Kanstantsin Pashkovich, Jacob Skitsko, Yun Xing
In this work, we study sequential contracts under matroid constraints. In the sequential setting, an agent can take actions one by one. After each action, the agent observes the st…
Multidimensional Budget-Feasible Mechanism Design
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested players. We have a valuation function ,…
An -approximate budget feasible mechanism for subadditive valuations
Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy
In budget-feasible mechanism design, there is a set of items , each owned by a distinct seller. The seller of item incurs a private cost for supplying her i…
Linear Contracts for Supermodular Functions Based on Graphs
Kanstantsin Pashkovich, Jacob Skitsko
We study linear contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a linear contract with several agents, each of whom can decide to…
Matroid Bayesian Online Selection
Ian DeHaan, Kanstantsin Pashkovich
We study a class of Bayesian online selection problems with matroid constraints. Consider a vendor who has several items to sell, with the set of sold items being subject to some s…
Single Sample Prophet Inequality for Uniform Matroids of Rank 2
Kanstantsin Pashkovich, Alice Sayutina
We study the prophet inequality when the gambler has an access only to a single sample from each distribution. Rubinstein, Wang and Weinberg showed that an optimal guarantee of 1/2…
Non-Adaptive Prophet Inequalities for Minor-Closed Classes of Matroids
Kanstantsin Pashkovich, Alice Sayutina
We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight -competitive me…
A Two-Step Approach to Optimal Dynamic Pricing in Multi-Demand Combinatorial Markets
Kanstantsin Pashkovich, Xinyue Xie
Online markets are a part of everyday life, and their rules are governed by algorithms. Assuming participants are inherently self-interested, well designed rules can help to increa…
Approximating Stable Matchings with Ties of Bounded Size
Jochen Koenemann, Kanstantsin Pashkovich, Natig Tofigzade
Finding a stable matching is one of the central problems in algorithmic game theory. If participants are allowed to have ties and incomplete preferences, computing a stable matchin…
Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
Frits Hof, Walter Kern, Sascha Kurz +2
A simple game is given by a set of players and a partition of~ into a set~ of losing coalitions~ with value that is closed under takin…
Computing the Nucleolus of Weighted Voting Games in Pseudo-polynomial Time
Kanstantsin Pashkovich
We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007…
On the approximability of the stable matching problem with ties of size two
Robert Chiang, Kanstantsin Pashkovich
The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum…
Three-dimensional Stable Matching with Cyclic Preferences
Kanstantsin Pashkovich, Laurent Poirrier
We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. Despite extensive study of the problem by experts from di…
On Critical Threshold Value for Simple Games
Kanstantsin Pashkovich
In this note, we show that for every simple game with n players the critical threshold value is at most n/4. This verifies the conjecture of Freixas and Kurz.
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time
Jochen Koenemann, Kanstantsin Pashkovich, Justin Toth
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in [Faigle,…