Aris Filos-Ratsikas

Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender et al.

We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values.

Aris Filos-Ratsikas, Sreedurga Gogulapati, Georgios Kalantzis

We initiate the study of the proportionality degree for participatory budgeting, with a particular focus on two popular methods: the Method of Equal Shares (MES) and Phragmen's Sequential Rule. Among other results, we derive tight bounds (up to small constant factors) on the proportionality degree of these two rules, which showcase that, despite MES satisfying stronger axiomatic guarantees, the two rules have the same proportionality degree from a quantitative perspective. We complement our theoretical findings with an extensive experimental evaluation on real-world participatory budgeting datasets, the results of which closely mirror those of our developed theory. Our experiments also provide more insights into the comparisons between the rules.

Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang

We study the problem of finding approximate envy-free allocations up to any $k$ goods ($α$-EFkX), when agents have additive values over goods in a bundle. As our main result, we show that for any $k>2$, $\frac{k+1}{k+2}$-EFkX allocations exist for any number of agents, and can be computed in polynomial time, via an appropriate generalization of the 3PA algorithm of [Amanatidis et al., 2024]. An immediate corollary of this result is that $3/4$-EF2X allocations exist for any number of agents; in contrast, $2/3$-EFX allocations are only known to exist for up to 7 agents. We improve this latter result by devising an algorithm that achieves $2/3$-EFX for 8 agents. We also consider EFkX graph orientations; we prove that such orientations do not always exist, and that deciding their existence is NP-complete, thereby generalizing the corresponding result of [Christodoulou et., 2023] for $k=1$.

Georgios Amanatidis, Aris Filos-Ratsikas, Alkmini Sgouritsa

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($α$-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For $α$-EFX, it is known that a $0.618$-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that $2/3$-EFX allocations exist when (a) there are at most \emph{seven agents}, (b) the agents' valuation functions can take at most \emph{three values}, or (c) the agents' valuation functions can be represented via a \emph{multigraph}. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to $2/3$-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of $0.618$ and achieve an approximation guarantee of $2/3$. Therefore, our results push the \emph{frontier} of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.

Panayiotis Danassis, Aris Filos-Ratsikas, Haipeng Chen et al.

Traditional competitive markets do not account for negative externalities; indirect costs that some participants impose on others, such as the cost of over-appropriating a common-pool resource (which diminishes future stock, and thus harvest, for everyone). Quantifying appropriate interventions to market prices has proven to be quite challenging. We propose a practical approach to computing market prices and allocations via a deep reinforcement learning policymaker agent, operating in an environment of other learning agents. Our policymaker allows us to tune the prices with regard to diverse objectives such as sustainability and resource wastefulness, fairness, buyers' and sellers' welfare, etc. As a highlight of our findings, our policymaker is significantly more successful in maintaining resource sustainability, compared to the market equilibrium outcome, in scarce resource environments.

Panayiotis Danassis, Marija Sakota, Aris Filos-Ratsikas et al.

We study the optimization of large-scale, real-time ridesharing systems and propose a modular design methodology, Component Algorithms for Ridesharing (CAR). We evaluate a diverse set of CARs (14 in total), focusing on the key algorithmic components of ridesharing. We take a multi-objective approach, evaluating 12 metrics related to global efficiency, complexity, passenger, driver, and platform incentives, in settings designed to closely resemble reality in every aspect, focusing on vehicles of capacity two. To the best of our knowledge, this is the largest and most comprehensive evaluation to date. We (i) identify CARs that perform well on global, passenger, driver or platform metrics, (ii) demonstrate that lightweight relocation schemes can significantly improve the Quality of Service by up to $50\%$, and (iii) highlight a practical, scalable, on-device CAR that works well across all metrics.

Adam Richardson, Aris Filos-Ratsikas, Boi Faltings

We consider a crowdsourcing data acquisition scenario, such as federated learning, where a Center collects data points from a set of rational Agents, with the aim of training a model. For linear regression models, we show how a payment structure can be designed to incentivize the agents to provide high-quality data as early as possible, based on a characterization of the influence that data points have on the loss function of the model. Our contributions can be summarized as follows: (a) we prove theoretically that this scheme ensures truthful data reporting as a game-theoretic equilibrium and further demonstrate its robustness against mixtures of truthful and heuristic data reports, (b) we design a procedure according to which the influence computation can be efficiently approximated and processed sequentially in batches over time, (c) we develop a theory that allows correcting the difference between the influence and the overall change in loss and (d) we evaluate our approach on real datasets, confirming our theoretical findings.

Naman Goel, Cyril van Schreven, Aris Filos-Ratsikas et al.

Blockchain based systems allow various kinds of financial transactions to be executed in a decentralized manner. However, these systems often rely on a trusted third party (oracle) to get correct information about the real-world events, which trigger the financial transactions. In this paper, we identify two biggest challenges in building decentralized, trustless and transparent oracles. The first challenge is acquiring correct information about the real-world events without relying on a trusted information provider. We show how a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong information. The second is a system design and implementation challenge. For the first time, we show how to implement a trustless and transparent oracle in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis.

Panayiotis Danassis, Aris Filos-Ratsikas, Boi Faltings

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments.

Aris Filos-Ratsikas, Paul W. Goldberg

We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit.

Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang et al.

We study the problem of allocating impressions to sellers in e-commerce websites, such as Amazon, eBay or Taobao, aiming to maximize the total revenue generated by the platform. We employ a general framework of reinforcement mechanism design, which uses deep reinforcement learning to design efficient algorithms, taking the strategic behaviour of the sellers into account. Specifically, we model the impression allocation problem as a Markov decision process, where the states encode the history of impressions, prices, transactions and generated revenue and the actions are the possible impression allocations in each round. To tackle the problem of continuity and high-dimensionality of states and actions, we adopt the ideas of the DDPG algorithm to design an actor-critic policy gradient algorithm which takes advantage of the problem domain in order to achieve convergence and stability. We evaluate our proposed algorithm, coined IA(GRU), by comparing it against DDPG, as well as several natural heuristics, under different rationality models for the sellers - we assume that sellers follow well-known no-regret type strategies which may vary in their degree of sophistication. We find that IA(GRU) outperforms all algorithms in terms of the total revenue.