Fair Allocation in Dynamic Mechanism Design

We thank the reviewer for their valuable feedback and comments. Please find our answers below.

The paper would benefit from a more comprehensive discussion of related works to better situate its contributions within the existing body of knowledge.

We acknowledge that the related work section should be expanded to include more papers. Due to space limitations, we were unable to include all the related papers in the submission version. We plan to provide a more comprehensive discussion of the related work in the main body or the appendix in the final version. To demonstrate that we already have the expanded related work available, we provide a brief summary of it here. We would also be happy to include any additional references that the reviewers suggest or find relevant.

In particular, we plan to draw connections between our work and the literature that studies fair allocation without considering strategic agents, such as Procaccia and Wang [2014] , [Babaioff et al., 2022], [Budish, 2011], [Caragiannis et al., 2023], [Conitzer et al., 2017], and [Amanatidis et al., 2018]. These works fundamentally differ from our paper as there is no incentive involved, but we would ensure to include them in the updated related work version.

Also, we would do a more broad discussion on papers that study fairness in the presence of strategic agents, including Lipton et al. [2004], Babichenko et al. [2023], Caragiannis et al. [2009], Sinha and Anastasopoulos [2015], Amanatidis et al. [2016], Amanatidis et al. [2017], Amanatidis et al. [2023b], Cole et al. [2013], and Babaioff and Feige [2022, 2024]. Note that these works differ from our work as they consider the static case and different notions of fairness, and some even consider social welfare rather than revenue. However, we plan to include all for the sake of completeness.

Concluding remarks discussing potential future directions and the real-world applicability of the theory are missing. While the limited space of conference submissions is acknowledged, such discussion could significantly enhance the paper's impact.

We thank the reviewer for pointing out these shortcomings. Please see General Comment 1 on a number of real-world applications of our results. Also, we have discussed potential future directions in our response to reviewer WPVa. We will incorporate both in the final version of the paper using the additional one-page space.

Could the model be extended to more than two groups, and if so, would this add significant complexity or insight compared to the current settings?

Yes, please see General Comment 2 in our global response.

How standard is Assumption 1 used within the model, and how does it compare to assumptions typically made in similar studies?

Assumption 1, i.e., the regularity assumption, is quite common in the mechanism design literature, dating back to the seminal work of Myerson [1981], and has been used in many other mechanism design papers over decades. That said, the original Myerson [1981] paper introduces the ironing technique, which can be used to relax this assumption in their model. As we discuss in our response to Reviewer ssTM, this technique can be applied in our setting as well to extend our results to cases where Assumption 1 does not hold. We have provided the proof in our response to Reviewer ssTM and will include it in the final version of the paper.

The term "dynamic" used to describe settings with $T > 1$ might need clarification or justification. Is there a more precise terminology that could better describe these recursive, history-dependent solutions? Dynamic usually refers to some flexibility in the allocation of items.

The choice of the term “dynamic” primarily follows the mechanism design literature, as “dynamic mechanism design” is the customary terminology used to refer to scenarios in which items are allocated over time through incentive-aware mechanisms (see reference [2] in our submission for a detailed reference).

We thank the reviewer for their valuable feedback and comments. Please find our answers below.

Minor Comments

We thank the reviewer for pointing out the typo. We also agree with the suggested improvements to our figures and would incorporate them in the final version.

Experiments seem too simple, it would be better if the authors conducted a more extensive experiment.

We acknowledge the simplicity of our initially included experimentation; we agree that extensions that consider complexities including those resulting from increasing the number of rounds and buyers or considering other value distributions, for instance, will be valuable to illustrate characteristics of the optimal fair mechanism under a variety of conditions. We intend to include a broader set of experimental findings from our ongoing extensions. That said, we have already run a number of additional experiments, as illustrated in the General Comment 3 in our global response.

Though the authors claim that results should extend to more than 2 groups, it would be better to include some formal statements.

We thank the reviewer for their suggestion. Please see General Comment 2 in our global response.

Do the results still hold when bidders in one group have different valuation distributions?

We thank the reviewer for this intriguing question. Yes, our analysis extends to that case as well. We made this assumption primarily based on our motivating examples (see General Comment 1, for instance). Specifically, we are looking for group-fairness guarantees, where we have homogeneous buyers within each group, but the distribution of values differs across groups. For instance, this could be because buyers in one group have lower incomes and, hence, lower willingness to pay.

That said, as we stated above, our analysis extends to the case where we have heterogeneous buyers within each group. The main difference in this case is that, within each group, the buyer with the highest virtual value has the chance of winning the item, rather than the buyer with the highest value (which is the current result). Furthermore, we should compare the highest virtual values of the two groups to decide on allocation. Let us formalize this for the static case; the dynamic case follows similarly.

Notice that in this case, the virtual value of buyer $(i,k)$ is denoted by $\phi_{i,k}(v_{i,k})$. Now, part (i) of Theorem 1 would change to: "If the item is allocated to group $i$, then it is allocated to the buyer in group $i$ with the highest virtual value." Regarding part (ii), equations (7a) and (7b) would hold, with the difference that we have to define $\phi_i(v_i) := \max_{i,k} \phi_{i,k}(v_{i,k})$. The proof of this updated result would follow identically to the proof of the current result.

The paper assumes that all distributions are regular. Do main results extend to arbitrary distribution by ironing?

We thank the reviewer for pointing out this relevant extension. Yes, the ironing technique can be used to extend our result to arbitrary distributions. We provide a brief summary of the result here, and we will include a detailed result in the appendix in the final version, along with a discussion in the main body. To simplify the notation here, we suppress the dependence on time $t$.

Let $h_i(.)$ be the virtual value function in the quantile space, i.e., $h_i(q) = \phi_i(F_i^{-1}(q))$ for any $q \in [0,1]$. Also, let $H_i$ be its cumulative virtual value function, i.e, $H_i(q) = \int_0^q h_i(q') dq'$. Now, let us recall the ironing technique from Myerson [1981]. We define $G_i: [0,1] \to \mathbb{R}$ as the convex hull of $H_i$, i.e., the largest convex function underestimator of $H_i$, and denote its derivative by $g'_i(\cdot)$. Now, the ironed virtual value function $\tilde{\phi}_i(\cdot)$ is simply defined as $\tilde{\phi}_i(v) = g_i(F_i(v))$. Notice that, given that we have dropped Assumption 1, $\phi_i(\cdot)$ is not necessarily monotone. However, given the ironing procedure, $\tilde{\phi}_i(\cdot)$ is monotone. In fact, when Assumption 1 holds, i.e., for regular distributions, $H(\cdot)$ is convex itself, and hence $g_i = h_i$ which implies $\tilde{\phi}_i = \phi_i$.

Now, as Myerson [1981] establishes, the seller's revenue can be cast as

with

\mathcal{E} := \sum_{i \in [2],k \in [n]} \mathbb{E}_{\pmb{v}_{-(i,k)}} \left [ \int_{\underline{v}_i}^{\bar{v}_i} (H_i(F_i(v)) - G_i(F_i(v))) ~ dx_{i,k}(v, \pmb{v}_{-(i,k)}) \right ].

We thank the reviewer for their valuable feedback and comments. Please find our answers below.

The parameter $\delta$ is never clearly defined and it was very confusing to see it in line 112 without any proper previous description.

We defined the discount factor $\delta$ earlier in the introduction (see line 34). However, we acknowledge that it should also be defined in the modeling section and we apologize for the lack of clarity there. We will address this in the final version.

It would be useful to mention some real-world scenarios in which these groups are formed and the goal is to be fair towards the groups as a whole while allocating the goods to individuals. Also, the fairness is defined as giving each group a certain amount of goods in expectation. It is not intuitive at all why this is a good fairness measure while the value of the agents for the goods are totally ignored in this notion.

We thank the reviewer for motivating us to further elaborate on the application of our results. Please see General Comment 1 regarding a number of examples in this regard.

We would like to use the first example on housing allocations to address the second part of your question. It is important to note that a buyer’s value is not always based solely on the intrinsic value of the item; it often reflects the buyer’s willingness to pay. In the housing example, a house in a good location might have a high value for both low-income and high-income groups, but their willingness to pay is limited by their ability to afford it. In such scenarios, the allocation ratio is a more effective approach to mitigate allocation inequality compared to using buyers’ value. This is why most regulations regarding fair housing allocation focus on the percentage of housing allocated to low-income groups as a measure of success.

We hope these examples help to clarify and further motivate the formulation and model we study in this paper. We would also include this discussion in the final version of the paper.

Also, it would be very useful to have a theorem in the paper which is stand-alone and concisely mentions the main contribution of the paper.

We see our paper as providing a framework for studying the fair allocation of goods through dynamic mechanism design. Our paper has three main contributions, which build on each other to complete the story. The first result, Theorem 1, illustrates the optimal allocation in the static case where we run the auction for one round. This result not only provides intuition on how fairness requirements change the optimal allocation but also serves as a basis for the dynamic case. The second main result, Theorem 2, demonstrates how we can find the optimal allocation recursively in the dynamic case. This can be seen as the main contribution of the paper. Finally, Propositions 3 and 4 aim to provide a computationally tractable framework for finding an approximation of the optimal allocation outlined by the previous theorem, making the result more accessible for applications. We hope this brief roadmap clarifies the main contributions of our paper.

I sincerely thank the authors for their thorough response. With the provided examples and explanation, I understand the significance of the work and the motivation behind the proposed fairness criteria better. I increased my score.

We thank the reviewer for their valuable feedback and comments. Please find our answers below.

The discount factor is mentioned in the introduction, better to make sure it’s also defined in the Model section for notation reference.

We thank the reviewer for this suggestion and acknowledge that the discount factor should also be defined with the model. We will address this in the final version.

Minor Comments and Typos

We thank the reviewer for pointing out all the typos, and we would fix them in the final version.

Would you add some motivation for the discount factor?

The discount factor is commonly used in settings where we allocate items over time to account for the time value of money, i.e., one dollar today is worth more than one dollar in a year. In the context of studying fairness, it is also important as it ensures that items are not disproportionately allocated to one group initially, but are distributed reasonably over time.

That said, it is worth noting that all our results extend to the case where we use a discount factor $\delta = 1$, i.e., the overall utility of each buyer is the average of utilities over $T$ rounds. The results for the dynamic setting would hold in this case, and Fact 3 elaborates that we can compute the optimal allocation efficiently under these conditions.

Would you add some discussions of the limitations of this work and future directions in the main paper?

We thank the reviewer for motivating us to further discuss the limitations of our work and potential future directions. We will add these discussions using the additional one page allowed for the main body in the final version.

Regarding limitations, our paper makes a number of theoretical assumptions, including the independence of buyers' values and the regularity of the distribution values. As we discuss in our response to Reviewer ssTM, the regularity assumption can be relaxed using the ironing technique, but studying the case with interdependent values requires more work and could be the topic of future research. Additionally, our paper assumes that the utility of each user is bilinear in the allocation and their value. Extending our results to a more general class of utility functions could be another potential direction for future work.