Publications (56)
Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas +1
In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies pr…
Approximate-EFX Allocations with Ordinal and Limited Cardinal Information
Aris Filos-Ratsikas, Georgios Kalantzis, Alexandros A. Voudouris
We study a discrete fair division problem where agents have additive valuation functions over a set of goods. We focus on the well-known -EFX fairness criterion, accord…
The Adjusted Winner Procedure: Characterizations and Equilibria
Haris Aziz, Simina Brânzei, Aris Filos-Ratsikas +1
The Adjusted Winner procedure is an important fair division mechanism proposed by Brams and Taylor for allocating goods between two parties. It has been used in practice for divorc…
Utilitarian Distortion with Predictions
Aris Filos-Ratsikas, Georgios Kalantzis, Alexandros A. Voudouris
We study the utilitarian distortion of social choice mechanisms under the recently proposed learning-augmented framework where some (possibly unreliable) predicted information abou…
Equilibrium Computation in First-Price Auctions with Correlated Priors
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
We consider the computational complexity of computing Bayes-Nash equilibria in first-price auctions, where the bidders' values for the item are drawn from a general (possibly corre…
Rewarding High-Quality Data via Influence Functions
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 mod…
A Theoretical Approach to Stablecoin Design via Price Windows
Katherine Molinet, Aris Filos-Ratsikas
In this paper, we explore the short- and long-term stability of backed stablecoins offering constant mint and redeem prices to all agents. We refer to such designs as price window-…
Truthful ownership transfer with expert advice: Blending mechanism design with and without money
Ioannis Caragiannis, Aris Filos-Ratsikas, Swaprava Nath +1
When a company undergoes a merger or transfers its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur…
Approximate mechanism design for distributed facility location
Aris Filos-Ratsikas, Alexandros A. Voudouris
We consider a single-facility location problem, where agents are positioned on the real line and are partitioned into multiple disjoint districts. The goal is to choose a location…
Heterogeneous Facility Location with Limited Resources
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris
We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the lin…
Reinforcement Mechanism Design for e-commerce
Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang +1
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…
Consensus Halving is PPA-Complete
Aris Filos-Ratsikas, Paul W. Goldberg
We show that the computational problem CONSENSUS-HALVING is PPA-complete, the first PPA-completeness result for a problem whose definition does not involve an explicit circuit. We…
Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas +1
Aggregating the preferences of individuals into a collective decision is the core subject of study of social choice theory. In 2006, Procaccia and Rosenschein considered a utilitar…
Pushing the Frontier on Approximate EFX Allocations
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 (…
The Distortion of Stable Matching
Aris Filos-Ratsikas, Georgios Kalantzis
We initiate the study of distortion in stable matching. Concretely, we aim to design algorithms that have limited access to the agents' cardinal preferences and compute stable matc…
Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship
Ioannis Caragiannis, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen +2
We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric spac…
Facility location with double-peaked preference
Aris Filos-Ratsikas, Minming Li, Jie Zhang +1
We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being o…
On the Computational Complexity of Blind Detection of Binary Linear Codes
Alexios Balatsoukas-Stimming, Aris Filos-Ratsikas
In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish t…
Egalitarianism of Random Assignment Mechanisms
Haris Aziz, Jiashu Chen, Aris Filos-Ratsikas +2
We consider the egalitarian welfare aspects of random assignment mechanisms when agents have unrestricted cardinal utilities over the objects. We give bounds on how well different…
Social welfare in one-sided matchings: Random priority and beyond
Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang
We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set…
The Pareto Frontier of Inefficiency in Mechanism Design
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos
We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give…
Efficient Equilibrium Computation in Symmetric First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
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…
Settling the Distortion of Distributed Facility Location
Aris Filos-Ratsikas, Panagiotis Kanellopoulos, Alexandros A. Voudouris +1
We study the distributed facility location problem, where a set of agents with positions on the line of real numbers are partitioned into disjoint districts, and the goal is to cho…
Consensus-Halving: Does It Ever Get Easier?
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki +1
In the -Consensus-Halving problem, a fundamental problem in fair division, there are agents with valuations over the interval , and the goal is to divide th…
A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas +1
We consider the one-sided matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is…
Putting Ridesharing to the Test: Efficient and Scalable Solutions and the Power of Dynamic Vehicle Relocation
Panayiotis Danassis, Marija Sakota, Aris Filos-Ratsikas +1
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…
On the Complexity of Equilibrium Computation in First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +2
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 b…
Fair Division of Indivisible Goods: Recent Progress and Open Questions
Georgios Amanatidis, Haris Aziz, Georgios Birmpas +5
Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources…
Fair Division of Indivisible Goods: A Survey
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas +1
Allocating resources to individuals in a fair manner has been a topic of interest since the ancient times, with most of the early rigorous mathematical work on the problem focusing…
Infochain: A Decentralized, Trustless and Transparent Oracle on Blockchain
Naman Goel, Cyril van Schreven, Aris Filos-Ratsikas +1
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)…
Approximate Envy-Free Allocations up to any Goods
Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang
We study the problem of finding approximate envy-free allocations up to any goods (-EFkX), when agents have additive values over goods in a bundle. As our main result, we s…
Distortion in Social Choice Problems: The First 15 Years and Beyond
Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah +1
The notion of distortion in social choice problems has been defined to measure the loss in efficiency -- typically measured by the utilitarian social welfare, the sum of utilities…
Hardness Results for Consensus-Halving
Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg +1
We study the consensus-halving problem of dividing an object into two portions, such that each of agents has equal valuation for the two portions. The -approximate consensu…
Revisiting the Distortion of Distributed Voting
Aris Filos-Ratsikas, Alexandros A. Voudouris
We consider a setting with agents that have preferences over alternatives and are partitioned into disjoint districts. The goal is to choose one alternative as the winner using a m…
Walrasian Pricing in Multi-unit Auctions
Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen +1
Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equili…
Social Welfare in One-Sided Matching Mechanisms
George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen +3
We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both or…
Maximum Nash Welfare and Other Stories About EFX
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas +2
We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness noti…
Proportionality Degree in Participatory Budgeting
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 Seq…
On the Computation of Equilibria in Discrete First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
We study the computational complexity of computing Bayes-Nash equilibria in first-price auctions with discrete value distributions and discrete bidding space, under general subject…
FIXP-membership via Convex Optimization: Games, Cakes, and Markets
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a new technique for proving membership of problems in FIXP - the class capturing the complexity of computing a fixed-point of an algebraic circuit. Our technique const…
The Distortion of Distributed Metric Social Choice
Elliot Anshelevich, Aris Filos-Ratsikas, Alexandros A. Voudouris
We consider a social choice setting with agents that are partitioned into disjoint groups, and have metric preferences over a set of alternatives. Our goal is to choose a single al…
On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes
Georgios Amanatidis, Aris Filos-Ratsikas, Philip Lazos +2
We study elections where voters are faced with the challenge of expressing preferences over an extreme number of issues under consideration. This is largely motivated by emerging b…
A Topological Characterization of Modulo- Arguments and Implications for Necklace Splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki +1
The classes PPA- have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with thieves, for prime . Howeve…
Stable Fractional Matchings
Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos +1
We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). A…
Walrasian Dynamics in Multi-unit Markets
Simina Brânzei, Aris Filos-Ratsikas
In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not alw…
AI-driven Prices for Externalities and Sustainability in Production Markets
Panayiotis Danassis, Aris Filos-Ratsikas, Haipeng Chen +2
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-p…
Mechanism Design for Facility Location Problems: A Survey
Hau Chan, Aris Filos-Ratsikas, Bo Li +2
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the las…
Improved Metric Distortion via Threshold Approvals
Elliot Anshelevich, Aris Filos-Ratsikas, Christopher Jerrett +1
We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance betwee…
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros Hollender
We consider the -Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions…
PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problem…
Truthful approximations to range voting
Aris Filos-Ratsikas, Peter Bro Miltersen
We consider the fundamental mechanism design problem of approximate social welfare maximization under general cardinal preferences on a finite number of alternatives and without mo…
Truthful Interval Covering
Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris
We initiate the study of a novel problem in mechanism design without money, which we term Truthful Interval Covering (TIC). An instance of TIC consists of a set of agents each asso…
The distortion of distributed voting
Aris Filos-Ratsikas, Evi Micha, Alexandros A. Voudouris
Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying t…
Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior
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 requi…
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
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 resu…
Optimal Metric Distortion for Matching on the Line
Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian +2
We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, agents need to be matched to items, and each agent's cost in a matc…