Philip Lazos

Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in the presence of strategic agents. Ideally, one would want to design truthful mechanisms that produce allocations with fairness guarantees. However, in the standard setting without monetary transfers, it is generally impossible to have truthful mechanisms that provide nontrivial fairness guarantees. Recently, Amanatidis et al. [Amanatidis G, Birmpas G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2023) Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. Math. Oper. Res., ePub ahead of print November 30, https://doi.org/10.1287/moor.2022.0058 ] suggested the study of mechanisms that produce fair allocations in their equilibria. Specifically, when the agents have additive valuation functions, the simple Round-Robin algorithm always has pure Nash equilibria, and the corresponding allocations are envy-free up to one good (EF1) with respect to the agents’ true valuation functions. Following this agenda, we show that this outstanding property of the Round-Robin mechanism extends much beyond the above default assumption of additivity. In particular, we prove that for agents with cancelable valuation functions (a natural class that contains, e.g., additive and budget-additive functions), this simple mechanism always has equilibria, and even its approximate equilibria correspond to approximately EF1 allocations with respect to the agents’ true valuation functions. Furthermore, we show that the approximate EF1 fairness of approximate equilibria surprisingly holds for the important class of submodular valuation functions as well, even though exact equilibria fail to exist. Funding: This work was supported by the Horizon 2020 European Research Council Advanced Grant “AMDROMA: Algorithmic and Mechanism Design Research in Online Markets” [Grant 788893], the Ministero dell’Università e della Ricerca Research project of national interest (PRIN) “ALGADIMAR: Algorithms, Games, and Digital Markets,” the Nederlandse Organisatie voor Wetenschappelijk Onderzoek Veni Project “Algorithmic Fair Division in Dynamic, Socially Constrained Environments” [Grant VI.Veni.192.153], and the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program [Grant MIS 5154714].

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported—rather than the true—values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely, envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX), and we positively answer the preceding question. In particular, we study two algorithms that are known to produce such allocations in the nonstrategic setting: round-robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden (EFX allocations for two agents). For round-robin, we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, whereas for the algorithm of Plaut and Roughgarden, we show that the corresponding allocations not only are EFX, but also satisfy maximin share fairness, something that is not true for this algorithm in the nonstrategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria, which all induce EFX allocations. Funding: This work was supported by the Horizon 2020 European Research Council Advanced “Algorithmic and Mechanism Design Research in Online Markets” [Grant 788893], the Ministero dell’Università e della Ricerca Research project of national interest (PRIN) “Algorithms, Games, and Digital Markets,” the Future Artificial Intelligence Research project funded by the NextGenerationEU program within the National Recovery and Resilience Plan (PNRR-PE-AI) scheme [M4C2, investment 1.3, line on Artificial Intelligence], the National Recovery and Resilience Plan-Ministero dell’Università e della Ricerca (PNRR-MUR) project IR0000013-SoBigData.it, the Nederlandse Organisatie voor Wetenschappelijk Onderzoek Veni Project [Grant VI.Veni.192.153], and the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program [Grant MIS 5154714].

We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy, reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.

Fair allocation of indivisible goods has attracted extensive attention over the last two decades, yielding numerous elegant algorithmic results and producing challenging open questions. The problem becomes much harder in the presence of strategic agents. Ideally, one would want to design truthful mechanisms that produce allocations with fairness guarantees. However, in the standard setting without monetary transfers, it is generally impossible to have truthful mechanisms that provide non-trivial fairness guarantees. Recently, Amanatidis et al. [2021] suggested the study of mechanisms that produce fair allocations in their equilibria. Specifically, when the agents have additive valuation functions, the simple Round-Robin algorithm always has pure Nash equilibria and the corresponding allocations are envy-free up to one good (EF1) with respect to the agents' true valuation functions. Following this agenda, we show that this outstanding property of the Round-Robin mechanism extends much beyond the above default assumption of additivity. In particular, we prove that for agents with cancelable valuation functions (a natural class that contains, e.g., additive and budget-additive functions), this simple mechanism always has equilibria and even its approximate equilibria correspond to approximately EF1 allocations with respect to the agents' true valuation functions. Further, we show that the approximate EF1 fairness of approximate equilibria surprisingly holds for the important class of submodular valuation functions as well, even though exact equilibria fail to exist!

Cryptocurrencies come with a variety of tokenomic policies as well as aspirations of desirable monetary characteristics that have been described by proponents as 'sound money' or even 'ultra sound money.' These propositions are typically devoid of economic analysis so it is a pertinent question how such aspirations fit in the wider context of monetary economic theory. In this work, we develop a framework that determines the optimal token supply policy of a cryptocurrency, as well as investigate how such policy may be algorithmically implemented. Our findings suggest that the optimal policy complies with the Friedman rule and it is dependent on the risk free rate, as well as the growth of the cryptocurrency platform. Furthermore, we demonstrate a wide set of conditions under which such policy can be implemented via contractions and expansions of token supply that can be realized algorithmically with block rewards, taxation of consumption and burning the proceeds, and blockchain oracles.

This work sets out a testing and containment framework developed for reopening universities in Mexico following the lockdown due to COVID-19. We treat diagnostic testing as a resource allocation problem and develop a testing allocation mechanism and practical web application to assist educational institutions in making the most of limited testing resources. In addition to the technical results and tools, we also provide a reflection on our current experience of running a pilot of our framework within the Instituto Tecnológico y de Estudios Superiores de Monterrey (ITESM), a leading private university in Mexico, as well as on our broader experience bridging research with academic policy in the Mexican context.

Blockchain systems come with the promise of being inclusive for a variety of decentralized applications (DApps) that can serve different purposes and have different urgency requirements. Despite this, the transaction fee mechanisms currently deployed in popular platforms as well as previous modeling attempts for the associated mechanism design problem focus on an approach that favors increasing prices in favor of those clients who value immediate service during periods of congestion. To address this issue, we introduce a model that captures the traffic diversity of blockchain systems and a tiered pricing mechanism that is capable of implementing more inclusive transaction policies. In this model, we demonstrate formally that EIP-1559, the transaction fee mechanism currently used in Ethereum, is not inclusive and demonstrate experimentally that its prices surge horizontally during periods of congestion. On the other hand, we prove formally that our mechanism achieves stable prices in expectation and we provide experimental results that establish that prices for transactions can be kept low for low urgency transactions, resulting in a diverse set of transaction types entering the blockchain. At the same time, perhaps surprisingly, our mechanism does not necessarily sacrifice revenue since the lowering of the prices for low urgency transactions can be covered from high urgency ones due to the price discrimination ability of the mechanism.

We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an $\varepsilon$-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete. We also provide an efficient algorithm for solving a special case of the problem, for a fixed number of bidders and available bids.

We consider the problem of computing a (pure) Bayes–Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an [Formula: see text]-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete. We also provide an efficient algorithm for solving a special case of the problem for a fixed number of bidders and available bids.