Piotr Krysta

I&C Journal 2026 Journal Article

Matroid and Knapsack House Allocation

• Jinshan Zhang
• Piotr Krysta

We explore two extensions of house allocation (HA) by enabling the allocation of each object (with limited or unlimited copies) to multiple agents. One extension is associated with matroid constraints, called the Matroid House Allocation Problem (MHA), while the other is associated with knapsack constraints, and is called the Knapsack House Allocation Problem (KHA). We investigate the highly general setting for both problems, where agents possess weights or priorities and can express indifference towards objects. Our focus is on designing (universally) truthful and Pareto optimal mechanisms to compute a maximum weighted matching. We propose a tight 2-approximate deterministic mechanism that is both truthful and Pareto optimal for the Matroid House Allocation Problem (MHA). Additionally, we develop a randomized mechanism that is universally truthful and Pareto optimal, with an approximation ratio of e e − 1 for the same problem. This ratio of e e − 1 is the best achievable among universally truthful and Pareto optimal mechanisms, assuming the mechanism is also non-bossy. These results represent significant advancements over previous findings and are achieved through different techniques. Furthermore, we apply our MHA mechanisms to the Online Bipartite Matching Problem and Job Recruitment Problems by incorporating matroid constraints, resulting in optimal algorithms for both problems. For the Knapsack House Allocation Problem (KHA), we design a (4, 2)-approximate mechanism that is universally truthful and Pareto optimal for cases with equal capacities. Additionally, we provide a universally truthful mechanism with a constant approximation for KHA. Moreover, we develop a 4-approximate mechanism for equal capacity KHA with strict preferences.

IJCAI Conference 2024 Conference Paper

Online Sampling and Decision Making with Low Entropy

• Mohammad Taghi Hajiaghayi
• Dariusz R. Kowalski
• Piotr Krysta
• Jan Olkowski

Suppose we are given an integer k and n boxes, labeled 1, 2, …, n by an adversary, each containing a single number chosen from an unknown distribution; the n distributions not necessarily identical. We have to choose an order to sequentially open the boxes, and each time we open the next box in this order, we learn the number inside. If we reject a number in a box, the box cannot be recalled. Our goal is to accept k of these numbers, without necessarily opening all boxes, such that the accepted numbers are the k largest numbers in the boxes (thus their sum is maximized). This problem, sometimes called a free order multiple-choice secretary problem, is one of the classic examples of online decision making problems. A natural approach to solve such problems is to sample elements in random order; however, as indicated in several sources, e. g. , Turan et al. NIST 2015 [35], Bierhorst et al. Nature 2018 [10], pure randomness is hard to get in reality. Thus, pseudorandomness has to be used, with a small entropy. We show that with a very small O(log log n) entropy an almost-optimal approximation of the value of k largest numbers can be selected, with only a polynomially small additive error, for k 1.

SODA Conference 2024 Conference Paper

Power of Posted-price Mechanisms for Prophet Inequalities

• Kiarash Banihashem
• MohammadTaghi Hajiaghayi
• Dariusz R. Kowalski
• Piotr Krysta
• Jan Olkowski

We study the power of posted pricing mechanisms for Bayesian online optimization problems subject to combinatorial feasibility constraints. When the objective is to maximize social welfare, the problem is widely studied in the literature on prophet inequalities. While most (though not all) existing algorithms for prophet inequalities are implemented using a pricing mechanism, whether or not this can be done in general is unknown, and was formally left as an open question by Dutting, Feldman, Kesselheim, and Lucier (FOCS 2017, SICOMP 2020). Understanding the power and limitations of posted prices is important from a mechanism design perspective because any posted price mechanism is truthful, and is also interesting in its own right as it can guide future research on prophet inequalities. We show that any prophet inequality has an implementation using a posted price mechanism, thereby resolving the open question of Dutting et al. Given an algorithm for Bayesian online optimization, we show that it can be transformed, in a black-box manner, to a posted price algorithm that has the same or higher expected social welfare and preserves the distribution over the assigned outcomes. We further show how to implement our reduction efficiently under standard assumptions using access to a sampling oracle. As an immediate consequence, we obtain improved pricing-based prophet inequalities for maximum weight matching, resolving an open problem of Ezra, Feldman, Gravin and Tang (EC 2020, MOR 2022). Correa and Cristi (STOC 2023) proved recently an existence of prophet inequality with constant approximation ratio for online social welfare maximizing combinatorial auctions with subadditive valuations. They left as an open problem to provide a posted pricing based implementation of their algorithm. Our technique resolves this question in affirmative as well.

AAMAS Conference 2024 Conference Paper

Who gets the Maximal Extractable Value? A Dynamic Sharing Blockchain Mechanism

• Pedro Braga
• Georgios Chionas
• Piotr Krysta
• Stefanos Leonardos
• Georgios Piliouras
• Carmine Ventre

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. MEV refers to any excess value that a block producer can realize by manipulating the ordering of transactions. In this paper, we propose to make the MEV extraction rate part of the protocol design space. Our aim is to leverage this parameter to maintain a healthy balance between block producers (who need to be compensated for the service they provide) and users (who need to feel encouraged to transact). We design a dynamic mechanism which updates the MEV extraction rate with the goal of stabilizing it at a target value. We analyse the evolution of this dynamic mechanism under various market conditions and provide formal guarantees about its long-term performance. The main takeaway from our work is that the proposed system exhibits desirable behavior (near-optimal performance) even when it operates in out of equilibrium conditions that are often met in practice. Our work establishes, the first to our knowledge, dynamic framework for the integral problem of MEV sharing between extractors and users.

IJCAI Conference 2023 Conference Paper

Adversarial Contention Resolution Games

• Giorgos Chionas
• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Piotr Krysta

We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as the only one at a round. Each player aims to minimize its packet latency. We introduce the notion of adversarial equilibrium (AE), which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also AE. We characterize the price of anarchy in the CR games with respect to AE.

NeurIPS Conference 2023 Conference Paper

Combinatorial Group Testing with Selfish Agents

• Georgios Chionas
• Dariusz Kowalski
• Piotr Krysta

We study the Combinatorial Group Testing (CGT) problem in a novel game-theoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have $n$ selfish agents corresponding to the elements of the universe $[n] =\{0, 1, \ldots, n-1\}$ and a hidden set $K \subseteq [n]$ of active agents of size $|K| = k \ll n$. In each round of the game, each active agent decides if it is present in a query $Q \subseteq [n]$, and all agents receive feedback on $Q \cap K$. The goal of each active agent is to assure that its id could be learned from the feedback as early as possible. We present a comprehensive set of results in this new game, where we design and analyze adaptive algorithmic strategies of agents which are AE's. In particular, if $k$ is known to the agents, then we design adaptive AE strategies with provably near optimal learning time of $O(k \log(n/k))$. In the case of unknown $k$, we design an adaptive AE strategies with learning time of order $n^k$, and we prove a lower bound of $\Omega(n)$ on the learning time of any such algorithmic strategies. This shows a strong separations between the two models of known and unknown $k$, as well as between the classic CGT, i. e. , without selfish agents, and our game theoretic CGT model.

AAAI Conference 2021 Conference Paper

Efficient Truthful Scheduling and Resource Allocation through Monitoring

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

We study the power and limitations of the Vickrey-Clarke- Groves mechanism with monitoring (VCGmon ) for cost minimization problems with objective functions that are more general than the social cost. We identify a simple and natural sufficient condition for VCGmon to be truthful for general objectives. As a consequence, we obtain that for any cost minimization problem with non-decreasing objective µ, VCGmon is truthful, if the allocation is Maximal-in-Range and µ is 1-Lipschitz (e. g. , µ can be the Lp-norm of the agents’ costs, for any p ≥ 1 or p = ∞). We apply VCGmon to scheduling on restricted-related machines and obtain a polynomial-time truthful-in-expectation 2-approximate (resp. O(1)-approximate) mechanism for makespan (resp. Lp-norm) minimization. Moreover, applying VCGmon, we obtain polynomial-time truthful O(1)-approximate mechanisms for some fundamental bottleneck network optimization problems with single-parameter agents. On the negative side, we provide strong evidence that VCGmon could not lead to computationally efficient truthful mechanisms with reasonable approximation ratios for binary covering social cost minimization problems. However, we show that VCGmon results in computationally efficient approximately truthful mechanisms for binary covering problems.

SODA Conference 2020 Conference Paper

Ultimate greedy approximation of independent sets in subcubic graphs

• Piotr Krysta
• Mathieu Mari
• Nan Zhi

JAIR Journal 2018 Journal Article

The Power of Verification for Greedy Mechanism Design

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.

AAMAS Conference 2017 Conference Paper

Mechanism Design for Ontology Alignment

• Piotr Krysta
• Minming Li
• TERRY R. PAYNE
• Nan Zhi

The aim of the ontology alignment problem is to find meaningful correspondences between two ontologies represented as collections of entities. This problem can be modelled as a novel mechanism design problem on an edge-weighted bipartite graph, where each side of the graph holds each agent’s private entities, and the objective is to maximise the agents’ social welfare. Having studied implementation in dominant strategies with and without payments, we report on findings that for truthful mechanisms, these problems need to be solved optimally. We also study greedy allocation rules with a first-price payment rule, and implementation in pure, mixed & Bayesian Nash equilibria, and have found tight bounds on the price of anarchy and stability.

AAMAS Conference 2016 Conference Paper

Network Pollution Games

• Eleftherios Anastasiadis
• Xiaotie Deng
• Piotr Krysta
• Minming Li
• Han Qiao
• Jinshan Zhang

We introduce a new network model of the pollution control problem and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, that could be thought of as sources of pollution, and edges between agents represent the effect of spread of pollution. The government as the regulator is responsible to maximize the social welfare while setting bounds on the levels of emitted pollution both locally and globally. Our model is inspired by the existing literature in environmental economics that applies game theoretical methodology to control pollution. We study the social welfare maximization problem in our model. Our main results include hardness results for the problem, and in complement, a constant approximation algorithm on planar graphs. Our approximation algorithm leads to a truthful in expectation mechanism, and it is obtained by a novel decomposition technique of planar graphs to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest.

TCS Journal 2015 Journal Article

Combinatorial auctions with verification are tractable

• Piotr Krysta
• Carmine Ventre

We study mechanism design for social welfare maximization in combinatorial auctions with general bidders given by demand oracles. It is a major open problem in this setting to design a deterministic truthful auction which would provide the best possible approximation guarantee in polynomial time, even if bidders are double-minded (i. e. , they assign positive value to only two sets in their demand collection). On the other hand, there are known such randomized truthful auctions in this setting. In the general model of verification (i. e. , some kind of overbidding can be detected) we provide the first deterministic truthful auctions which indeed provide essentially the best possible approximation guarantees achievable by any polynomial-time algorithm even if the complete input data is known. This shows that deterministic truthful auctions have the same power as randomized ones if the bidders withdraw from unrealistic lies. Our truthful auctions are based on greedy algorithms and our approximation guarantee analyses employ linear programming duality based techniques. Finally, our truthfulness analyses are based on applications of the cycle-monotonicity technique which we show to surprisingly couple with the greedy approach.

JAIR Journal 2015 Journal Article

Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods

• Piotr Krysta
• Orestis Telelis
• Carmine Ventre

We design and analyze deterministic truthful approximation mechanisms for multi-unit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Our main results are for multi-minded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful FPTAS that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1+e), for any fixed e>0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a PTAS that approximates the optimum Social Welfare within factor (1+e), for any fixed e>0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments.

IJCAI Conference 2015 Conference Paper

Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

• Piotr Krysta
• Orestis Telelis
• Carmine Ventre

We design and analyze deterministic truthful approximation mechanisms for multi-unit combinatorial auctions involving a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i. e. , for more than one unit per distinct good, that are expressed through their private valuation functions. Our objective is to determine allocations of multisets that maximize the Social Welfare approximately. Despite the recent theoretical advances on the design of truthful combinatorial auctions (for multiple distinct goods in unit supply) and multi-unit auctions (for multiple units of a single good), results for the combined setting are much scarcer. We elaborate on the main developments of [Krysta et al. , 2013], concerning bidders with multi-minded and submodular valuation functions, with an emphasis on the presentation of the relevant algorithmic techniques.

TCS Journal 2013 Journal Article

Ranking games that have competitiveness-based strategies

• Leslie Ann Goldberg
• Paul W. Goldberg
• Piotr Krysta
• Carmine Ventre

An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player’s score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players’ scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players.

AAMAS Conference 2010 Conference Paper

Combinatorial Auctions with Externalities

• Piotr Krysta
• Tomasz Michalak
• Tuomas Sandholm
• Michael Wooldridge

Although combinatorial auctions have received a great deal of attention from the computer science community over the past decade, research in this domain has focussed on settings in which a bidderonly has preferences over the bundles of goods they themselvesreceive, and is indifferent about how other goods are allocated toother bidders. In general, however, bidders in combinatorial auctions will be subject to externalities: they care about how the goodsthey are not themselves allocated are allocated to others. Our aimin the present work is to study such combinatorial auctions withexternalities from a computational perspective. We first presentour formal model, and then develop a classification scheme for thetypes of externalities that may be exhibited in a bidder's valuationfunction. We develop a bidding language for combinatorial auctions with externalities, which uses weighted logical formulae torepresent bidder valuation functions. We then investigate the properties of this representation: we study the complexity of the winnerdetermination problem, and characterise the complexity of classifying the properties of valuation functions. Finally, we considerapproximation methods for winner determination.

SODA Conference 2010 Conference Paper

Utilitarian Mechanism Design for Multi-Objective Optimization

• Fabrizio Grandoni 0001
• Piotr Krysta
• Stefano Leonardi 0001
• Carmine Ventre

SODA Conference 2007 Conference Paper

Buying cheap is expensive: hardness of non-parametric multi-product pricing

• Patrick Briest
• Piotr Krysta

TCS Journal 2006 Journal Article

Efficient approximation algorithms for the achromatic number

• Piotr Krysta
• Krzysztof Loryś

The achromatic number problem is, given a graph G = ( V, E ), to find the greatest number of colors, Ψ ( G ), in a coloring of the vertices of G such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. This problem is NP -complete even for trees. We obtain the following new results using combinatorial approaches to the problem. (1) A polynomial time O ( | V | 3 / 8 ) -approximation algorithm for the problem on graphs with girth at least six. (2) A polynomial time 2-approximation algorithm for the problem on trees. This is an improvement over the best previous 7-approximation algorithm. (3) A linear time asymptotic 1. 414 -approximation algorithm for the problem when graph G is a tree with maximum degree d ( | V | ), where d: N ⟶ N, such that d ( | V | ) = O ( Ψ ( G ) ). For example, d ( | V | ) = Θ ( 1 ) or d ( | V | ) = Θ ( log | V | ). (4) A linear time asymptotic 1. 118 -approximation algorithm for binary trees. We also improve the lower bound on the achromatic number of binary trees.

SODA Conference 2006 Conference Paper

Single-minded unlimited supply pricing on sparse instances

• Patrick Briest
• Piotr Krysta

STOC Conference 2005 Conference Paper

Approximation techniques for utilitarian mechanism design

• Patrick Briest
• Piotr Krysta
• Berthold Vöcking

This paper deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques.Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone FPTAS. This can be applied to various problems like, e.g., knapsack , constrained shortest path , or job scheduling with deadlines . For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multi-unit auctions . The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any bounded number of parameters per agent.The most efficient way to solve packing integer programs (PIPs) is LP-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs) , unsplittable flow routing and multicast routing . Our approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.

MFCS Conference 2005 Conference Paper

Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing

• Piotr Krysta

Abstract We study simple greedy approximation algorithms for general class of integer packing problems. We provide a novel analysis based on the duality theory of linear programming. This enables to significantly improve on the approximation ratios of these greedy methods, and gives a unified analysis of greedy for many packing problems. We show matching lower bounds on the ratios of such greedy methods. Applications to some specific problems, including mechanism design for combinatorial auctions, are also shown.

SODA Conference 2004 Conference Paper

Computing equilibria for congestion games with (im)perfect information

• René Beier
• Artur Czumaj
• Piotr Krysta
• Berthold Vöcking

SODA Conference 2003 Conference Paper

Optimizing misdirection

• Piotr Berman
• Piotr Krysta

MFCS Conference 2003 Conference Paper

Scheduling and Traffic Allocation for Tasks with Bounded Splittability

• Piotr Krysta
• Peter Sanders 0001
• Berthold Vöcking

Abstract We investigate variants of the problem of scheduling tasks on uniformly related machines to minimize the makespan. In the k -splittable scheduling problem each task can be broken into at most k ≥ 2 pieces to be assigned to different machines. In a more general SAC problem each task j has its own splittability parameter k j ≥ 2. These problems are NP -hard and previous research focuses mainly on approximation algorithms. Our motivation to study these scheduling problems is traffic allocation for server farms based on a variant of the Internet Domain Name Service (DNS) that uses a stochastic splitting of request streams. We show that the traffic allocation problem with standard latency functions from Queueing Theory cannot be approximated in polynomial time within any finite factor because of the extreme behavior of these functions. Our main result is a polynomial time, exact algorithm for the k -splittable scheduling problem as well as the SAC problem with a fixed number of machines. The running time of our algorithm is exponential in the number of machines but is only linear in the number of tasks. This result is the first proof that bounded splittability reduces the complexity of scheduling as the unsplittable scheduling is known to be NP -hard already for two machines. Furthermore, since our algorithm solves the scheduling problem exactly, it also solves the traffic allocation problem.

SODA Conference 2002 Conference Paper

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems

• Béla Csaba
• Marek Karpinski
• Piotr Krysta

STOC Conference 2002 Conference Paper

Selfish traffic allocation for server farms

• Artur Czumaj
• Piotr Krysta
• Berthold Vöcking

We investigate the price of selfish routing in non-cooperative networks in terms of the coordination and bicriteria ratios in the recently introduced game theoretic network model of Koutsoupias and Papadimitriou. We present the first thorough study of this model for general, monotone families of cost functions and for cost functionsm from Queueing Theory. Our main results can be summarized as follows. We give a precise characterization of cost functions having a bounded/unbounded coordination ratio. For example, cost functions that describe the expected delay in queueing systems have an unbounded coordination ratio.