Hadi Yami

AAAI Conference 2024 Conference Paper

Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements

• Max Springer
• MohammadTaghi Hajiaghayi
• Hadi Yami

We here address the problem of fairly allocating indivisible goods or chores to n agents with weights that define their entitlement to the set of indivisible resources. Stemming from well-studied fairness concepts such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) for agents with equal entitlements, we present, in this study, the first set of impossibility results alongside algorithmic guarantees for fairness among agents with unequal entitlements. Within this paper, we expand the concept of envy-freeness up to any good or chore to the weighted context (WEFX and XWEF respectively), demonstrating that these allocations are not guaranteed to exist for two or three agents. Despite these negative results, we develop a WEFX procedure for two agents with integer weights, and furthermore, we devise an approximate WEFX procedure for two agents with normalized weights. We further present a polynomial-time algorithm that guarantees a weighted envy-free allocation up to one chore (1WEF) for any number of agents with additive cost functions. Our work underscores the heightened complexity of the weighted fair division problem when compared to its unweighted counterpart.

AIJ Journal 2022 Journal Article

Fair allocation of indivisible goods: Beyond additive valuations

• Mohammad Ghodsi
• MohammadTaghi Hajiaghayi
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.

AAAI Conference 2021 Conference Paper

Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings

• Alireza Farhadi
• MohammadTaghi Hajiaghayi
• Mohamad Latifian
• Masoud Seddighin
• Hadi Yami

Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envyfreeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations (Lipton et al. 2004). In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is (φ − 1) ≃ 0. 61 by Amanatidis et al. (Amanatidis, Markakis, and Ntokos 2020). In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envyfreeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time 0. 73-approximation allocation algorithm. For our algorithm we use Nash Social Welfare Matching which makes a new connection between Nash Social Welfare and envy freeness.

JAIR Journal 2019 Journal Article

Fair Allocation of Indivisible Goods to Asymmetric Agents

• Alireza Farhadi
• Mohammad Ghodsi
• Mohammad Taghi Hajiaghayi
• Sébastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

IJCAI Conference 2019 Conference Paper

On the Efficiency and Equilibria of Rich Ads

• MohammadAmin Ghiasi
• MohammadTaghi Hajiaghayi
• Sébastien Lahaie
• Hadi Yami

Search ads have evolved in recent years from simple text formats to rich ads that allow deep site links, rating, images and videos. In this paper, we consider a model where several slots are available on the search results page, as in the classic generalized second-price auction (GSP), but now a bidder can be allocated several consecutive slots, which are interpreted as a rich ad. As in the GSP, each bidder submits a bid-per-click, but the click-through rate (CTR) function is generalized from a simple CTR for each slot to a general CTR function over sets of consecutive slots. We study allocation and pricing in this model under subadditive and fractionally subadditive CTRs. We design and analyze a constant-factor approximation algorithm for the efficient allocation problem under fractionally subadditive CTRs, and a log-approximation algorithm for the subadditive case. Building on these results, we show that approximate competitive equilibrium prices exist and can be computed for subadditive and fractionally subadditive CTRs, with the same guarantees as for allocation.

SODA Conference 2018 Conference Paper

Envy-free Chore Division for An Arbitrary Number of Agents

• Sina Dehghani
• Alireza Farhadi 0001
• MohammadTaghi Hajiaghayi
• Hadi Yami

AAMAS Conference 2017 Conference Paper

Fair Allocation of Indivisible Goods with Different Entitlements

• Alireza Farhadi
• MohammadTaghi Hajiaghayi
• Mohammad Ghodsi
• Sebastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang [14] wherein the agents are assumed to be symmetric. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Next, we assume that the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. We show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items. (The full version of the paper is available in https: //arxiv. org/abs/1703. 01649.) CCS Concepts •Computing methodologies → Multi-agent systems;

AAAI Conference 2017 Conference Paper

Market Pricing for Data Streams

• Melika Abolhassani
• Hossein Esfandiari
• MohammadTaghi Hajiaghayi
• Brendan Lucier
• Hadi Yami

Internet-enabled marketplaces such as Amazon deal with huge datasets registering transaction of merchandises between lots of buyers and sellers. It is important that algorithms become more time and space efficient as the size of datasets increase. An algorithm that runs in polynomial time may not have a reasonable running time for such large datasets. Here, we study the development of pricing algorithms that are appropriate for use with massive datasets. We especially focus on the streaming setting, the common model for big data analysis. We present an envy-free mechanism for social welfare maximization problem in the streaming setting using O(k2 l) space, where k is the number of different goods and l is the number of available items of each good. We also provide an αapproximation mechanism for revenue maximization in this setting given an α-approximation mechanism for the corresponding offline problem exists. Moreover, we provide mechanisms to approximate the optimum social welfare (or revenue) within 1 − factor, in space independent of l which would be favorable in case l is large compared to k. Finally, we present hardness results showing approximation of optimal prices that maximize social welfare (or revenue) in the streaming setting needs Ω(l) space. We achieve our results by developing a powerful sampling technique for bipartite networks. The simplicity of our sampling technique empowers us to maintain the sample over the input sequence. Indeed, one can construct this sample in the distributed setting (a. k. a, MapReduce) and get the same results in two rounds of computations, or one may simply apply this sampling technique to provide faster offline algorithms.