8 citations · 18 across the 23 of their papers we have counts for
29 papers
Prophet Inequalities Beyond Utilitarian Social Welfare
Daniel Halpern, Abhiram Manohara, Alexandros Psomas
In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of agents who arrive sequentially, with values drawn independently from a known distributi…
Is Solving Better Than Evaluating GenAI Solutions?
Ethan Dickey, Marios Mertzanidis, Alexandros Psomas
As Generative AI (GenAI) tools become increasingly capable of generating solutions to computing assignments, the computing education community is exploring pedagogical approaches t…
Fair Division Under Inaccurate Preferences
Trung Dang, Daniel Halpern, Anuran Makur +3
The fair allocation of scarce resources is a central problem in mathematics, computer science, operations research, and economics. While much of the fair-division literature assume…
Truthful Fair Division under Stochastic Valuations
Daniel Halpern, Alexandros Psomas, Shirley Zhang
We study no-money mechanisms for allocating indivisible items to strategic agents with additive preferences under a stochastic model. In this model, items' values are drawn from an…
Sponsored Questions and How to Auction Them
Kshipra Bhawalkar, Alexandros Psomas, Di Wang
Online platforms connect users with relevant products and services using ads. A key challenge is that a user's search query often leaves their true intent ambiguous. Typically, pla…
On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences
Egor Gagushin, Marios Mertzanidis, Alexandros Psomas
We study the fundamental problem of fairly allocating a multiset of types of indivisible items among groups of agents, where all agents within a group have id…
On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
Arnav Mehra, Alexandros Psomas
We consider the classic cake-cutting problem of producing fair allocations for agents, in the Robertson-Webb query model. In this model, it is known that: (i) proportional allo…
Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game
Alexandros Psomas, Athina Terzoglou, Yu Wei +1
We consider the problem of a game theorist analyzing a game that uses cryptographic protocols. Ideally, a theorist abstracts protocols as ideal, implementation-independent primitiv…
Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations
Daniel Halpern, Alexandros Psomas, Paritosh Verma +1
We consider the fundamental problem of allocating indivisible items that arrive over time to agents with additive preferences, with the goal of minimizing envy. This proble…
Mechanism Design with Delegated Bidding
Gagan Aggarwal, Marios Mertzanidis, Alexandros Psomas +1
We consider the problem of a designer who wants to allocate resources to representatives, that then distribute the resources they receive among the individuals they represent. Moti…
V3rified: Revelation vs Non-Revelation Mechanisms for Decentralized Verifiable Computation
Tiantian Gong, Aniket Kate, Alexandros Psomas +1
In the era of Web3, decentralized technologies have emerged as the cornerstone of a new digital paradigm. Backed by a decentralized blockchain architecture, the Web3 space aims to…
Mechanism Design via the Interim Relaxation
Kshipra Bhawalkar, Marios Mertzanidis, Divyarthi Mohan +1
We study revenue maximization for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. In seminal work, Alaei~\cite{alaei201…
Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation
Marios Mertzanidis, Alexandros Psomas, Paritosh Verma
Food waste and food insecurity are two closely related pressing global issues. Food rescue organizations worldwide run programs aimed at addressing the two problems. In this paper,…
On the Fairness of Normalized p-Means for Allocating Goods and Chores
Owen Eckart, Alexandros Psomas, Paritosh Verma
Allocating items in a fair and economically efficient manner is a central problem in fair division. We study this problem for agents with additive preferences, when items are all g…
Refined Mechanism Design for Approximately Structured Priors via Active Regression
Christos Boutsikas, Petros Drineas, Marios Mertzanidis +2
We consider the problem of a revenue-maximizing seller with a large number of items for sale to strategic bidders, whose valuations are drawn independently from high-dimens…
On the Robustness of Mechanism Design under Total Variation Distance
Anuran Makur, Marios Mertzanidis, Alexandros Psomas +1
We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distrib…
Fairly Allocating Goods in Parallel
Rohan Garg, Alexandros Psomas
We initiate the study of parallel algorithms for fairly allocating indivisible goods among agents with additive preferences. We give fast parallel algorithms for various fundamenta…
On the Existence of Envy-Free Allocations Beyond Additive Valuations
Gerdus Benadè, Daniel Halpern, Alexandros Psomas +1
We study the problem of fairly allocating indivisible items among agents. Envy-free allocations, in which each agent prefers her bundle to the bundle of every other agent,…
Reward Selection with Noisy Observations
Kamyar Azizzadenesheli, Trung Dang, Aranyak Mehta +2
We study a fundamental problem in optimization under uncertainty. There are boxes; each box contains a hidden reward . Rewards are drawn i.i.d. from an unknown distrib…
Getting More by Knowing Less: Bayesian Incentive Compatible Mechanisms for Fair Division
Vasilis Gkatzelis, Alexandros Psomas, Xizhi Tan +1
We study fair resource allocation with strategic agents. It is well-known that, across multiple fundamental problems in this domain, truthfulness and fairness are incompatible. For…
Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions
Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta +2
Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amou…
Smoothed Analysis of Social Choice, Revisited
Bailey Flanigan, Daniel Halpern, Alexandros Psomas
A canonical problem in social choice is how to aggregate ranked votes: given voters' rankings over candidates, what voting rule should we use to aggregate these votes i…
Fair and Efficient Allocations Without Obvious Manipulations
Alexandros Psomas, Paritosh Verma
We consider the fundamental problem of allocating a set of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the absence of mone…
More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR
Tiantian Gong, Ryan Henry, Alexandros Psomas +1
A long line of research on secure computation has confirmed that anything that can be computed, can be computed securely using a set of non-colluding parties. Indeed, this non-coll…