Fair Allocation in Dynamic Mechanism Design
Authors: Alireza Fallah
Michael Jordan
Annie S Ulichney
Venue: NeurIPS 2024 poster (2024)
Keywords: Mechanism Design
Auctions
Fairness
Primary area: algorithmic_game_theory
TL;DR: We study a dynamic mechanism design problem subject to a fairness constraint that ensures a minimum average allocation for each group.

Abstract: We consider a dynamic mechanism design problem where an auctioneer sells an indivisible good to two groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group. We begin by studying the static case ($T=1$) and establish that the optimal mechanism involves two types of subsidization: one that increases the overall probability of allocation to all buyers, and another that favors the group which otherwise has a lower probability of winning the item. We then extend our results to the dynamic case by characterizing a set of recursive functions that determine the optimal allocation and payments in each round. Notably, our results establish that in the dynamic case, the seller, on one hand, commits to a participation reward to incentivize truth-telling, and, on the other hand, charges an entry fee for every round. Moreover, the optimal allocation once more involves subsidization in favor of one group, where the extent of subsidization depends on the difference in future utilities for both the seller and buyers when allocating the item to one group versus the other. Finally, we present an approximation scheme to solve the recursive equations and determine an approximately optimal and fair allocation efficiently.

Fair Allocation in Dynamic Mechanism Design
Alireza Fallah University of California, Berkeley af afallah@berkel edu
Michael I. Jordan
University of California, Berkeley and INRIA, Paris jordan@cs bewkseey..eeke.k..... edu
Annie Ulichney
University of California, Berkeley annie_ull we__ullchhne eelleeeeebeer..ee......... edu
Abstract
We consider dynamic mechanism design problem where an auctioneer sells an indivisible good two groups of buyers every round, for total of rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to fairness constraint that guarantees a minimum average allocation for each group. We begin by studying the static case (7 1) and establish that the optimal mechanism involves two types of subsidization: one that increases the overall probability of allocation to all buyers, and another that favors the group which otherwise has a lower probability of winning the item. We then extend our results to the dynamic case by characterizing a set of recursive functions that determine the optimal allocation and payments in each round. Notably, our results establish that in the dynamic case, the seller, on the one hand, commits to participation reward to incentivize truth-telling, and, on the other hand, charges an entry fee for every round. Moreover, the optimal allocation once more involves subsidization in favor of one group, where the extent of subsidization depends on the difference in future utilities for both the seller and buyers when allocating the item to group versus the other. Finally, we present an approximation scheme to solve the recursive equations and determine approximately optimal and fair allocation efficiently.
Introduction
Auctions play a pivotal role allocation decisions across various domains, serving as a structured methodology for determining the distribution of resources based on bids. Housing, government contracts, electromagnetic spectrum rights, and advertising slots are few of the many domains where allocations are determined by auctions. In many of the real-world applications of nuction-based allocations, the resource in question is both valuable and limited, which raises concerns about fairness.
For instance, housing auctions are often governed by policies addressing the needs of low- and moderate-income households, such Affordable Housing Quotas in the United Kingdom credits and vouchers in the United States 20 22). Government procurement contracts for goods and services in the United States are subject to the United States Small Business Act which outlines target contracting rates across categories (c.g., woman- -owee businesses, veteran-owne businesses, historically underutilized zones) [17]. The United States Federal Communications Commission drives initiatives ensuring. for instance, that small and regional companies maintain reasonable access to connectivity
35
The importance of incorporating a consideration of fairness in important real-world use cases motivates recent work that extends classical work on auction design emphasizing economic efficiency to ensure outcomes do not disproportionately favor some bidders over others. Integrating fairness
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

into auction designs is, however, a source of significant complexity, given that buyers often have different valuations, which can lead to strategic bidding behavior that may skew fairness.
In this paper, we focus on studying the question of fairness in a dynamic mechanism design setting, where a seller allocates indivisible item through an auction at every round and for T rounds to two groups of buyers, each group including n. buyers. At each round, the buyers' values are realized independently from an underlying distribution (which may differ between the two groups), and the buyers then submit their bids. The seller's goal is to decide on an allocation rule as a function of the submitted bids that maximizes their total discounted revenue with a discount factor 5, while ensuring that each group receives a minimum allocation, or more specifically, that group i's average discounted allocation is greater than or equal some Ct..
This fairness constraint enforces a proportional notion of fairesss regarding the number of items each group wins. There are several advantages to adopting such a faimesss notion. First, it is typically more straightforward from a policy perspective compared to, for instance, focusing on the total value won by each group. For example, most regulations concerning fair housing allocation emphasize the percentage of housing allocated to low-income groups as a measure of success (27]. Moreover, a buyer's value in private-value auctions not solely determined by the intrinsic value of the item but also depends on the financial constraints of the buyers or asymmetric information about the item's 's value. Therefore, proportional fairness constraint is suitable choice in cases where one group values are systematically lower than another's. 's. For example, in the context of housing allocation, low-income individuals may assign lower monetary value homes compared to wealthier individuals. as they are more concerned with basic shelter than with investment or resale value. In such scenarios, the allocation ratio a more effective approach to mitigate allocation inequality compared to using buyers' value.
We start by considering the static case with T 1. In the unconstrained case, it is well-known that the optimal allocation is the second-price auction with a reserve price, which allocates the item to the buyer with the highest bid, conditioned on the bid being above certain reserve price. Here, we establish that the optimal allocation under the fairness constraint has two main differences: first, the optimal fair mechanism subsidizes one group that would otherwise not meet the target fairness constraint. Second, the optimal allocation may increase the chance of allocating the item to both groups in general by reducing the reserve price (again disproportionately in favor of one group).
We next focus on the general dynamic case. Here, we characterize the optimal allocation through set of recursive functions. At any round f, we define the residual minimum allocation, which, roughly speaking, given the allocation so far, updates the fairness constraint as if we were to start at this round. We establish that, given the residual minimum allocation, we may have to allocate the item to one of the two groups to be on track to satisfy the fairness constraint overall, and that, in this case, we would simply allocate to the highest bidder in the group and charge them the second- hiihhst bid within their group. However, in cases where we have the option to allocate to both groups, the design of the optimal allocation is more complicated because buyers in each group may consider underreporting their value in the current round to keep their chances of winning the item in future rounds higher, especially if they expect their value in future rounds to be higher.
In this case, we establish that, as the above reasoning suggests, there is a utility associated with not winning the item. This utility is the difference between a buyer's is expected utility in future rounds if their group does not win the item this round, compared to the scenario where their group wins the item at the current round. We establish that, in the optimal allocation, and to incentivize buyers to report their values truthfully, the seller commits to paying them a participation reward if their group wins the item, and this reward is equal the aforementioned net utility of not winning the item. On the other hand, the seller charges them an entry fee, which is equal to the expected reward payment that they would miss they did not participate. Finally, we also prove that the optimal allocation rule is similar to the static case at high level: when allocating an item to group, it is assigned to the buyer with the highest bid. Second, the decision regarding which group receives the item takes the form of a subsidy. However, here, the amount of the subsidy depends on the above net utility of not winning the item and the seller's future utility from allocating the item to one group or the other.
As our results so far suggest, finding the optimal allocation requires solving a set of recursive functions, and as we see. the computational complexity could grow exponentially with the number of rounds. Our next contribution is to provide an efficient approximation scheme. In particular, we establish that, for any g > O, we can find an allocation that guarantees the same utility the seller
2

---

and fairness constraint of (1 =)) =) for group i. This requires only 0(E-1/0-8)) calls to an oracle that computes integrals. We further provide constant approximation scheme which requires Poly(1/(1 - 8)) calls to the oracle, which is more applicable to scenarios where 6 is close to one. We conclude our paper by providing a simple numerical experiment to illustrate the impact of the fairness constraint on the utility of both the seller and users.
Our work is related to the growing literature on questions related to fairness in mechanism design 15 36 24). Many works in fair mechanism design with an algorithmic focus draw from notions of fairness central computer science and machine learning [19]. For instance, a prominent related area of fair algorithmic mechanism design studies frameworks that ensure equity in the distribution of online advertisements across protected user attributes in the setting of online auctions, e.g. [14, [13], and [21].
Related work:
Our work is also related to a rich literature on fair division that studies fair allocation without
considering the strategic behavior of agents, e.g. (8) [6] [1], M. [1].
3 Our work joins the set
of works that consider both fairness and incentive compatibility allocation. Where (25). [9] [
consider truthful fair allocations with respect to variants of envy-freeness and (7]. [6] consider more broadly the feasibility of different notions of fairness in strategic setting, we join works that adopt a proportional notion of fairess,, e.g, M. 4l [1]] We further depart from these works in our
focus on revenue optimization (instead of, e.g., optimizing social welfare 36 and in our treatment of the dynamic strategic environment.
Another group of related works studies the impact of budgetary and liquidity constraints auction revenue, e.g. [26), and [18]. These works' motivation for considering budget constraints aligns with the setting where fair allocation guarantees are relevant. In particular, both settings drop the assumption that a bidder's 's valuation is accurately reflected by their willingness to pay. The setting of asymmetric budgetary constraints studied by (32] motivates the relevance of our work's introduction of guarantees for relative allocative fairness between groups We build upon this set of work by introducing a framework where the allocative limitations of both homogeneous and heterogeneous budget constraints can be simultaneously overcome as efficiently as possible. A separate set of related works empirically studies the impact on efficiency of subsidizing targeted groups of bidders in procurement auctions (23), [5]. These works complement ours by pointing to bid subsidies as the cost-optimal mechanism to enforce fairness.
The closest setting to ours is that of 31 which examines a similar notion of fairness in the single- round (static) case, but only for one group. We depart from their work as we consider the dynamic case and present an approximation scheme. Additionally, even in the static case, we consider a minimum allocation constraint for both groups, which introduces a second type of subsidization.
2 Model
We consider a monopolist seller that interacts with two groups of buyers over T rounds I with buyers in each group At each round t [T] the seller conducts auction to sell single indivisible item. The private value of buyer & E [m]] from group i E [2] (or simply, buyer (i, k)) for this item is denoted by vi,,. which is drawn from the publicly known and full support continuous
distribution with density ff [0f, of] + R. We also denote its cumulative distribution function by F...) We assume the buyers' values are independent.
Timeline of the auction: At each time t, buyers' private values are realized, and then each buyer (i, k) submits a bid b6 We denote the vector of bids at round by b'. The seller then conducts the auction and decides on the allocation x' (b', h') where h' denotes the public history of allocations up to (but not including) time t, i.c., which buyers received the items in the previous t rounds. In particular, af,e(b' h²) E (0, 1} denotes whether the kth buyer in group gets the item in round t. Notice that since we allocate single item each round, we should have En Ex_ 2/, h²) < for every t E [T]. Finally, buyer (i, k) makes the payment pi. (b',, h²)
'We demonstrate that the results extend to the case of multiple groups of buyers in an extended version available at httttss//axxivoorg http:/awwwi.../aa/////..... http//bb//24001....
"Here, for simplicity in notation, we assume that the two groups are of equal size n. However, our analysis and results apply to the general case, including unequal group sizes and scenarios with more than two groups For any integer N. [N] denotes the set NN.....N).
3

---

to the seller. The vector of payments at time t is denoted by p' h'). Notice that the mechanism is determined by the allocation and payment functions (x: (x'">" pp" 1:7).
1:
Utility functions: The utility function of buyer (i, k) at time t is given by (1i,s 6', ft') := of, (b,, h')e,, (B',
P (b', ,,)). Buyer (i, k) and seller's overall utilities are, respectively, given by:
T 8 8 L (vlass' h²) and ub h
T
U. " 6 hTT) E
Σ pi hh) (1) (1.A)
where d (0, 1] is the discount factor. Our goal is to identify mechanisms that maximize the seller's expected utility, subject to certain fairness constraints ensuring a minimum allocation is guaranteed to each group. We next formally define these fairness constraints.
The seller, acting as the auctioneer, aims to ensure that a minimum allocation is guaranteed to each group in this dynamic setting. More specifically, let a; represent the minimum (discounted) average allocation promised to group i, with the condition that on + Q2 S 1. Then, each round the seller ensures that the discounted average of the items allocated to group i thus far, combined with the expected allocation in the remaining rounds, is at least o;:
The fairness constraint:
T Σ
1 1
+
2 0i.
(2)
1 1 8T
R=
where the expectation is taken over the realization of the private values at time t and the future rounds. We call the auction infeasible at round t if it is not possible to satisfy the fairness constraint over the remaining rounds.
Notice that this condition is ex ante with respect to the allocation at time onwards as we find this condition more compatible compared to an ex post fairness in a setting with indivisible goods. Also, it is straightforward to verify that if the condition (2) holds for T, then it would hold for any I < T. However, as we will elaborate later, this condition determines the set of feasible allocations for any /. < T 1. For instance, suppose T = 4 and 01 = 022 1/3. Then, if we allocate the item to group 1 in the first three rounds, we cannot satisfy condition for group 2 in the last round.
Direct truthful mechanisms: The dynamic revelation principle states that, without loss of general- ity, we can focus on direct, truthful mechanisms where buyers bidding truthfully is a Nash equilibrium [29]. It is important to note that the dynamic revelation principle requires truthful reporting only on the equilibrium path; that is, assuming all buyers have been truthful in the past. However, in our setting, this would imply truthful reporting under any history, even if buyer has previously been dishonest (and we are off the equilibrium path). To see why this is the case, note that the utility of each buyer depends on their current (private) value and all past bids (but not on the past true values). Thus, when it is optimal for the buyer to bid truthfully when past reports have been truthful, it remains optimal for them to bid truthfully even if some buyers have lied in the past. This argument generally for a detailed discussion on this topic.)
holds true for Markovian environments (see [33 37]
In this paper, definition and its comparison with the weaker notion of Bayesian incentive compatibility in dynamic mechanism design). More specifically, for any mechanism (x ":"" "p':p""" p!:T)) ), the following Markovian
the periodic ex post incentive compatibillity (see [10] for discussion on this
decision problem finds the best bid for buyer from group i, assuming that all other buyers are reporting their values truthfully:
( h²) max {ut, ( (o) by of ((.)): h²) + E bi,
h
(3)
with the convention that U the optimal bid by maximizing the sum of their utility at the current moment and the maximum of what they could achieve in the future, while they assume that all other buyers are bidding truthfully. mechanism called ex post incentive compatible if the maximum is achieved through truthful bidding. The formal definition is provided below.
UT+ (.-)) O. This is recursive formula in which the buyer identifies
Definition 1. A mechanism 1x. .p" 1 is ex post incentive compatible (EPIC) if:
of arg max {uii Vileibin v' "'ma h²) + 8 E [ ( .1111) h Vi, ki t, o', n' (4)
4

---

Note that the EPIC mechanism can be identified through backward induction, starting at the last round and progressing back the first. By doing so, at time t, we would realize that maximum utility in future rounds achieved through truthful bidding. Consequently, the term U (v'+1, h h++1) could be replaced with the utility assuming that everyone reports truthfully. In other words, to identify the EPIC mechanism, it is sufficient to find mechanism that satisfies the following condition:
U³S42 arg max { Ui (1i,es of (..)): h') S 6
}
Σ LT=
UT hT) ht
(5)
Finally, we state the individual rationality assumption or the participation condition. This assumption ensures that, each round, each buyer (knowing only their value) would weakly prefer to participate in the auction. In other words, each buyer's expected utility is weakly higher if they participate rather than choosing their outside option, which is skipping that round.
Definition 2. A mechanism (x: .p p. ) is individually rational (IR) if for all i, i, t, o/ and h':
E ( ,,)] 2 S
U (v'+1 (h')41)(nn)
(6)
where (h') denotes the history under which buyer (i, has not participated at round t, and the expectations are taken over o² (i.k) and 1++1:
The left hand side of (6) demonstrates the expected utility of buyer ke) at time and thereafter, assuming their participation round t. However, the right hand side of (6) shows the expected utility of buyer (z, k)) when they skip the t-th round (and receive no utility in the t-th round).
Throughout our analysis, we adopt the following regularity assumption on the distribution of values that is common in mechanism design literature. This assumption applies to a variety of distributions, including uniform, exponential, and normal distributions
Assumption 1. For any i and I, the distribution F is regular, i.e, the virtual value function (1()) (v) is increasing in f(())
For the rest of the paper, our goal is to find EPIC and IR mechanism (x ,p' I:T) that maximizes the expected seller utility subject to the faimess constraint (2). We start our analysis by discussing the static case, i.e., T = 1, which will be used in our analysis for the dynamic setting.
3 The static case
To simplify the notation, we drop the dependence of the parameters on time in this section. Here, our fairness constraint (2) reduces to < Tt,a] 2 ay, where the expectation is taken over single realization of the private values.
It is well-known that in the absence of the faimess constraint, and under Assumption I the item is allocated to the buyer who has the highest virtual value, provided that at least one buyer's 's virtual value is non-negative. Conversely, the seller does not allocate the item if all virtual values are negative. This mechanism is known as the second-pen -picee auction (or Vickrey auction) with reserve pricing, as detailed in [30]. This allocation is depicted in Figure
We next present the main result of this section which establishes the optimal allocation under the fairness constraint.
Theorem 1. Suppose Assumption holds. For any i E [2]. let = max; U4 be the maximum value among buyers in group Then, the following results hold for the optimal allocation:
(i) If the item is allocated to group i, then it is allocated the buyer in group i with the highest value, i.e., if x4 = 1, then 04 Us.
'In the case of n = 1, buyer's non-participation could lead to the infeasibility of the auction as the item cannot be allocated to their group in that round. To avoid such special cases, in the case of n = 1, we assume that may still allocate the item to their group if they do not participate, but this potential allocation does not count towards their outside option utility.
*We demonstrate that the results in both the static and dynamic cases hold when this is assumption is weakened via ironing in extended version available at https///axi..oog/////244......
5

---

(s(ex)
ds(es) (v(
(a) Without fairness constraint
(b) With faimeess constraint
Figure 1: Optimal allocation in the static case.
(i) The allocation decision at the group level depends only on the maximum value of the two groups, vi and v2. For any i, let G, denote the pair (v), v2) for which the item allocated to group i. Then, there exists Th 122 2 O and y with 1/2 = 1n + y such that (up to measure-zero set)
G ((11, (1((1) 22(U2) y and Φ1 (V1) -m), G2 = ((v1, (22 2 (11) and (2( 2 -12
(7a) (7b)
The proof of this result (along with all other proofs) can be found in the appendix. An example of the optimal allocation rule with y > 0 depicted in Figure Tb where group one is allocated the item in the yellow and orange regions and group two is allocated the item in the blue and green regions.
The theorem follows from the fact that the loss in the seller's utility increases in Euclidean distance from the boundary of the unconstrained optimal allocation di (vi) (2(22). Therefore, virtual valuations of the under-allocated group that are closest to those of the over-allocated group, specif- ically within distance y, the set that minimize the cost of reallocating to the target group to achieve the desired balance between groups In the case of insufficient unconstrained allocation, the further modification of allocating in cases where the item remains unallocated in the unconstrained mechanism is necessary.
As Theorem shows, the optimal fair mechanism subsidizes one group that would otherwise not meet target allocation levels. To maximize revenue while satisfying a given fairness constraint, we deviate from the unconstrained allocation in the most cost efficient way, that is, we reassign the good to lower valuation bidder in cases that least impact expected seller revenue.
Also, notice that, when there is no fairness constraint, the seller does not allocate the item if the maximum bid is below their reserve price min (o (0), Φ5 (0)). Thus, is possible that, the unconstrained optimal mechanism, the total probability of allocation across both groups be less than the sum of the target allocation levels a, This is the intuition behind why 7/1 7/2 may both be greater than zero in some cases. In other words, we must simultaneously enforce that the item is allocated more often in general and that the relative rates of allocation between groups is sufficiently balanced.
We conclude this section with result which helps us to identify MT, and 7/2-
Proposition 1. Let y, nr and n2 correspond to the optimal allocation given by Theorem ! Then, if Y > 0, i.e., the seller strictly subsidizes in favor of the second group, we have P(G2) = 02 Moreover, if >> O, we have I(G on the other hand, if < 0, i.e the seller strictly subsidizes in favor of the first group, we have P(G1) = a1, Moreover, if 1/2 > we have P(G2) = Q2-
The probability PP(-) above is defined with respect to the distribution of the pair of maximum values U2) with CDF Fma (11, 02) Fi (v) (er)) F= The intuition behind this proposition is that the seller satisfies the fairness constraint while maximizing their utility by deviating from the optimal unconstrained only much is necessary satisfy the fairness constraint with equality.

---

4
The dynamic case
We next turn our attention the dynamic case. Here, our main approach involves using backward induction. The analysis from the previous section serves as the basis for the optimal allocation at the last round, i.e., T. In this section, we describe how we proceed backward find the optimal dynamic auction under the faimess constraint. We make the following assumption which simplifies the characterization of the optimal mechanism and allows us to focus on the insights. In the appendix, we discuss how our analysis extends to cases where this assumption does not hold.
Assumption 2. We assume the seller must allocate the item in any round, except possibly the last.
We start our analysis by making number of definitions and observations. Suppose we are at the beginning of round Given (2) following constraint:
our allocation at round t and the future rounds should satisfy the
Σ
Σ 1=1
Ll + 88
a Σ
R
1 8t-1
1- 8 8 04 Σ 88-1
12
(8)
We refer to the right-hand side as the residual minimum allocation for group i. It is noteworthy that equation (8) can be interpreted if the auction is starting time f, with the faimnes constraint given by (1 - -1) 105--- -9. We next make the following simple observation:
Fact 1. Given the allocation at time I, the residual minimum allocation at time + 1, i.e., R is equal to (R - 1) when the item is allocated to group i and equal to 1 R, otherwise.
5
We next introduce two interim functions. For the sake of these two definitions, assume the auction starts at time t, i.e. the utility at any time т, for T 2 t. is discounted by a factor of 8T-1, With this assumption, and for a given pair of residual minimum allocations (R2, (t,), we define μ² ('ti,, Rt) as the (discounted) sum of the expected utility of the seller at time and thereafter, under the optimal mechanism satisfying equation (8), prior the realization of values. Similarly, 1/ (R). R2)) represents the expected utility of a buyer in group i. It is worth noting that, given the distribution of values within each group is similar, v does not depend on l (the buyer's ''r's index within the group). We also set the these functions equal to oo if there is no feasible auction satisfying (8). The following result regarding vI (: and j (..-) a corollary of Theorem [ Notice that the last round can be seen static auction with faimess constraint for group given by Rİ
Corollary 1. At round T, and for given pair of residual minimum allocations (RT, R ), we have
v.7 (RT R²)) = 1 [ 1 1-F7(uV) (ETTi(U1s v2):
(9a)
n1 J.. (T())
n [RT Rbg = | of (La v2) ( o (v2)d (o., v2),
(9b)
where (1 = (v (12)" and G 's are defined in Theorem 7
This corollary is proved in the appendix. Now, suppose we are in the 1-th round, conducting the backward induction. Consequently, we have access to (..-) (for i E [2]) and (..)). Next, we will establish the optimal allocation for round t and describe how to compute (..-) and (+,-)) accordingly. We have three main regimes:
(I) When the auction is infeasible: Suppose that no matter whether the seller gives the item to the first or second group, they would not be able to satisfy the residual minimum allocation constraint in the remaining rounds. In this case, we declare the auction is infeasible at round t.
Fact 2. For given pair of residual minimum allocations (R², R2), suppose we have ( 1)/5, 8) and pt+1 (Rf/ 56 (R), 1)/8) -cc Then, there is no feasible auction satisfying the residual minimum allocation constraints, and hence, we set (R, Rt)) and v (R,, R2), for both
i [2), equal to -C.
To better highlight this proposition, us consider a simple example. Suppose = 2, 8 = 0.5, and 01 022 = 0.4. In this scenario, R2 = R2 0.6. Now, the residual minimum allocation for the second round for the group that doesn" 't receive the item in the first round would be 1 1. which not feasible. Hence, there is no feasible auction that satisfies the faimess constraint.
7

---

(II) When the item must be allocated to a certain group: Suppose, for instance, that if the seller allocated the item to the second group. they would not be able to satisfy the resulting residual minimum allocation constraints in the remaining rounds. However, allocating the item to the first group would result in a feasible auction. Therefore, in this case, the seller must allocate the item (if keeping it were feasible, then allocating it to the second group would also have been feasible), and moreover, the item must be allocated to the first group. The following result formalizes the optimal allocation for this scenario.
Proposition 2. Suppose Assumption 7 holds. For a given pair of residual minimum allocations (Ri4 R2)) and some E [2]. suppose we have ( (R,/5, (R' 1)/6) -co but uu+1((I,) 1)/0, R0) -c. Then, the seller allocates the item the buyer with the highest value in group i, with the payment being equal to the second-highest highest value within the same group.
Intuitively, if the item must be allocated to the first group, the question of who within that group receives the item essentially boils down to static Vickrey auction: the buyer offering the highest value acquires the item and pays the price equal to the second highest value in the group. It is important to note that, in this scenario, there is no reserve price (and we do not need to explicitly impose Assumption 2 because the seller is obliged to allocate the item to meet the fairness constraint. Lastly, the update of interim functions are provided in Appendix 1.4.1
(III) When allocation both groups is feasible: Suppose that whether the seller allocates the item to the first or second group. they still have the opportunity to meet the allocation constraint in future rounds. Now, what should be the seller's allocation strategy to maximize their utility?
Note that the expected utility of buyers in each group changes based on whether or not they receive the item in the current round. The difference between these two scenarios can be interpreted as the expected utility of not receiving the item. More formally, for a given pair of residual minimum allocations (R2 R&,) ). and when allocation to both groups is feasible, the net utility of not receiving the item for group is defined as
(R, =
(R -(;))
(10)
It is worth noting that, interestingly, the net utility of not receiving the item could be negative in some case (See Appendix A.5). Lastly, we define A (Ri. RR)) as the difference in seller's future utility by allocating the item the first group, compared to allocating to the second group, i.c.
(R,, R²)= = ((R) - 1)/8, R2/0) - ((R) 1)/5, R)/5,
(11)
Theorem 2. Suppose Assumptions | and Land@holk hold. For a given pair of residual minimum allocations (R), Rt)), suppose both (Rt /6, (1t: 1))5) and o ( 1)/6, R8)8) are finite. Then, the seller allocates the item to the buyer with the highest value in group i if (vi, v5) E G where u/ == max; 1/y,k is the maximum value among buyers in group and G is given by
G: = ((1
- -'',(0-)= nd ()) - (A,( + ( (R)) R
Moreover, let i" denote the index of the winner group. Then, the payment of buyer (i, k) is given by
- -fan 2l, vi (z 5A R))C -1(i- =))), (12)
wie 2 ( 8" (a.x))
where Ç denotes the probability of group i winning the item if the auction runs with n 1 buyers from their group instead of n buyers.
The explicit characterization of "t's along with the update of interim functions are provided in Appendix A.6 It worth emphasizing that while the term Ç depends on the allocation rule of an auction with 2n- 1 buyers, we can derive it in a non-recursive manner. The reason is that finding the allocation, similar to G. above, does not require running the smaller-size auction. Next, we would like to draw few insights from this result. First, notice that, similar to the static case, the boundary of allocation rule is a linear function of the maximum virtual values of both group.
Next, note that the payment function consists of three terms. The first term, tf ah,a (1f ((())))
"hi, (1, 0² -(.())))))))))))>) d2z represents what only the winner pays and is equal to the minimum bid
8

---

they could have made to still win the item. This is indeed similar to the second-pres auction in which the winner's payment is equal to the second highest bid. To better understand the other two terms, and for the sake of discussion, suppose (, Rb)'s are non-negative, indicating non-negative net future utility associated with not receiving the item at the current time (because means your chance of receiving it in the future increases). The second term of the payment function is - ((i = i), which is negative and thus represents a transfer from the seller to the buyers (we call this participation reward). Only the buyers from the group that wins the item receive this payment. To understand why such a reward is needed from the seller, notice that when a buyer's s group wins the item, they are in fact losing amount of 8 [Ri R)) in their future utility because their group has a lower chance of winning in the future. Hence, in some sense, this reduces the value of the item in the current round, and the buyers may find it profitable to underreport their value. That said, this payment serves to incentivize truthful reporting. Finally, the last term in the payment function is (
(R, R2, R:)G which is a payment that every buyer should make the seller. The rationale here is that if the buyer skips the current round, then if their group wins, which happens with probability ç. their group would receive payment equal to ( R5) from the seller, elaborated above. Hence, the seller charges the same amount as the entry fee.
Lastly, notice that in the allocation rule GV, there is threshold of no (A)(R), -B)) R2)) -
(-1)'A66( RR, R2)) which determines which group receives the item. Notice that this threshold increases as (R R3)) increases, meaning that the seller is less willing to give the item to group i. This is because a higher (R) R5) means that the seller has make higher payment group i's buyers if they win. Additionally, this threshold decreases for the first group when A (Rf Rb)) increases, indicating that the seller more willing allocate the item the first group when (R,, R2)) is higher. This is intuitive as this term represents the seller's future net utility by allocating the item the first group compared to allocating it the second group.
Our results so far offer an exact characterization of the optimal dynamic allocation. However, due to the recursive nature of the analysis, the computational complexity of this allocation increases exponentially with the number of rounds, T. We conclude this section by discussing efficient methods to find an approximately optimal allocation. Since focus is not on approximating the integrals here, we assume we have access to an oracle which can compute integrals and solve integral equations.
An approximation scheme:
Assumption 3. We have access to oracle that, for any i E [n] and t E (T), can com- (x.) pute the integrals Sa (u"),, d'Ftt (U1, v22) and So A(e.) d'F (V1,02) 02) with Fi U2) = Ft (u,)" F and over any affine subspace G. Furthermore, the oracle can find the optimal allocation in the static case by solving the integral equations in Proposition
We start by making the following observation regarding the case 6 1.
Fact 3. Suppose 6 1 and Assumptions 1 3 hold. Then, can find the exact optimal allocation by calling the oracle (T times.
To see why this holds, notice that, for the case of 5 = 1. the pair (R₁, R2)) at most takes T different values for any t, and so computing all {n'(R', R3), VR(R RR),RR)),, R²), r2( RB), would overall require O(T2) round of computation using the recursive derivations we stated earlier. However, for the case 5 < 1, this is not the case anymore, as the pair (R), RX)) could take as much as 2n different values. In this case, can technically choose some To T and aim to achieve the fairness constraint approximately in the first To rounds, and then run the regular second-price auction in the remaining rounds. The following result formalizes this.
Proposition 3. Suppose Assumptions exists an allocation x' with the following properties: (1) x' guarantees that the fairness constraint for group i is satisfied at a level of at least (1 - =)((a; - e), (2) x' guarantees that the sellers total utility is at least that of the optimal allocation, and (3) xx can be computed by calling the oracle O (e-1/logg 1/g///81/8 times.
3 hold and that 8 < 1. Then, for any E [0, min; oz), there
Intuitively, the approximation guarantees that the faimess constraint is satisfied within of the target level by conducting the fair allocation scheme at level a; 8 up to a sufficiently large time step such that approximate fairness is met no matter the allocations of the remaining rounds. In the remaining rounds, a standard sroond-price auction is carried out, thereby ensuring that total seller utility is at least that of the case where the fair allocation scheme is carried out to the last round.

---

0.4
5.06
0.40
-0.
0.04
0.3
-02
0.02
0.30
0.3
0.7
0.20
0,02
0.39
04
-0.04
0.19
0.1
699
000
2:10
6:00
0.91
6:0
-05
0.6
0.20
0.40
030
-0.00
0.00
0.2
010
0.2
0.00
0.46
0.52
0.5
(a) Seller utility
(b) Group One utility
(c) Group Two utility
Figure 2: Difference in utility relative to unconstrained optimal allocation for T = 2
0
0.40
0.09
0.2
-01
08
0.10
0.1
-022
0.00
0.0
-088
0.92
(a) Seller utility
(b) Group One utility
(c) Group Two utility
Figure Difference utility relative to unconstrained optimal allocation for T=
Notice that the complexity of the approximation given by proposition grows large for 5 close 1. Next, we present a second approximation scheme for the case where ò is close to one.
1. Then, for a fixed constant e < 82. there exists allocation x" with the following properties: (1) x" satisfies the fairness constraint for group at a level of at least c ac (2) x" guarantees that the sellers total utility is at least times that of that of the optimal allocation, and (3) x" can be computed by calling the oracle Poly (1=8) times where the polynomial's 's degree and coefficients depend on c.
Proposition Suppose Assumptions 3 hold and that
This x" modifies the approximation x' presented in Proposition 3 by introducing a discontinuous discounting technique. In x", we partition the first To rounds into buckets that use common approximate discount factor such that the computational complexity of each bucket may be controlled in the same manner Fact A complete proof as well complete proof statement that relates the early stopping approximation with the discounting approximation that can be tuned to achieve an overall approximation level can be found in Appendix A.8
Experiments
Here, present the results of numerical experiment assessing the impact utilities of varying the fairness constraints of each group. In particular, we implement the case where 5 = 0.99, n = of Uniform(O.55 1.5), and uy Uniform(0.) 1) for t E [2] for T 4.
For each value of T, we consider combinations of fairness constraints on a discretized grid where oij and 02 range over (0, 0.5) with increments of 0.1. For each pair a',, Q2, we calculate the mean difference in utility between the optimal fair allocation at level d11, Q2 and the unconstrained optimal 10,000 iterations
allocation satisfying Assumption 2 (i.e.. 01, 02 0), for the seller and buyers of the mechanism. Note that, for these distributions, when T = 2 the average unconstrained allocation probabilities are 0.69 and 0.31 for groups one and two, respectively, The results are reported in Figures] 3
We see that the seller utility is decreasing in 01, 02 but only after the point at which the constraints bind. For group one, we see that, for a fixed a,, utility decreasing in a2, since, to satisfy the fairness constraint, we re-allocate higher value regions group two and allocate lower-value regions that would otherwise go unallocated to group one. contrast, for group two, we see that, for fixed 022 utility is relatively constant in (₃ since the optimal allocation tends to reallocate to group one from the vower-value no-allocation region.
10

---

6 Acknowledgements
The authors thank Scott Kominers, Rakesh Vohra, and anonymous reviewers for insightful discussion and comments. Alireza Fallah acknowledges support from the European Research Council Synergy Program, the National Science Foundation under grant number DMMS-1289300, and the Alfred P. Sloan Foundation under grant G-2021-16778. The latter two grants correspond to his residency at the Simons Laufer Mathematical Sciences Institute (formerly known MSRI) in Berkeley, California, during the Fall 2023 semester. Michael Jordan acknowledges support from the Vannevar Bush Faculty Fellowship program under grant number N00014-21-1-294 and the European Research Council 20--2-2------AANN NONN-00116600)) Annie Ulichney's 's work is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE 2146752. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or the European Research Council.
References
[1] G. Amanatidis, G. Birmpas, and E. Markakis. On truthful mechanisms for maximin share allocations. arXiv preprint arXiv:1605.0000 04006, 2016.
[2] G. Amanatidis, G. Birmpas, G. Christodoulou, and E. Markakis. Truthful allocation mechanisms without payments: Characterization and implications on fairness. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 545-562, 2017.
[3] G. Amanatidis, G. Birmpas, and E. Markakis. Comparing approximate relaxations of envy- freeness. arXiv preprint arXiv: 1806.0006.11111 14, 2018.
[4] G. Amanatidis, G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser. Allocating indivisible goods to strategic agents: Pure Nash equilibria and fairness. Mathematics of Operations Research, 2023.
[5] S. Athey, D. Coey, and J. Levin. Set-asides and subsidies in auctions. American Economic Journal: Microeconomics, 5(1):1-27, February 2013. doi: 10.1257/mic.5.111 URL https
//www. aeaweb. org/ http//rrccessssd1111 htt.cc/ess7..111..12mm........
[6] M. Babaioff and U. Feige. Fair shares: Feasibility, domination and incentives. arXiv preprint
arXiv:2205.07519 2022.
[7] M. Babaioff and U. Feige. Share-based fairness for arbitrary entitlements. arXiv preprint 2XXv:2445514575: 2024.
[8] M. Babaioff, T. Ezra, and U. Feige. On borth fair-share allocations. In Interna- tional Conference on Web and Internet Economics, pages 237-255. Springer, 2022.
[9] Y. Babichenko, M. Feldman, R. Holzman, and V. V. Narayan. Fair division via quantile shares. arXiv preprint arXiv:2312.011
2023.
[10] D. Bergemann and J. Välimäki. Dynamic mechanism design: An introduction. Journal of Economic Literature, 57(2):235-274, 2019.
[11] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 1061-1130,1 2011.
[12] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos. and M. Kyropoulou. On low-envy truthful allocations. In Algorithmic Decision Theory: First International Conference, ADT 2009, Venice, Italy, October 20-23, 2009. Proceedings 1, pages 111-119. Springer, 2009.
[13] E. Celis, A. Mehrotra, and N. Vishnoi. Toward controlling discrimination in online ad auctions. In International Conference on Machine Learning, pages 4456-4465. PMLR, 2019.
[14) S. Chawla and M. Jagadeesan. Individual fairness in advertising auctions through inverse proportionality. arXiv preprint arXiv:2003. 13966, 2020.
[15] R. Cole, V. Gkatzelis, and G. Goel. Mechanism design for fair division: allocating divisible items without payments. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pages 251-268, 2013.
[16] V. Conitzer, R. Freeman, and N. Shah. Fair public decision making. Proceedings of the 2017 ACM Conference on Economics and Computation, pages 629-646666666 2017.

---

[17] C. Cravero. Socially responsible public procurement and set-asides. Arctic Review on Law and Polities, 8:174-192, 2017.
[18] S. Dobzinski, R. Lavi, and N. Nisan. Multi-unit auctions with budget limits. Games and Economic Behavior, 74(2)488-5503, 2012.
[19] J. Finocchiaro, R. Maio, F. Monachou, G. K. Patro, M. Raghavan, A.-A. Stoica, and S. Tsirtsis. Bridging machine learning and mechanism design towards algorithmic faimesss In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 489-503, 2021.
[20] N. Gallent. Planning and affordable housing: from old values to new labour. Town Planning Review, 71(2))123, 2000.
[21] C. Ilvento, M. Jagadeesan, and S. Chawla. Multi-category fairness in sponsored search auctions. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 348-358, 2020.
[22] M. P. Keightley and J. M. Stupak. An introduction the low-income housing tax credit. Library of Congress, Congressional Research Service Washington, DC, 2014.
[23] E. Krasnokutskaya and Seim. Bid preference programs and participation in highway procurement auctions. American Economic Review, 101(6)2653-2666, 2011.
[24] K. Kuo, A. Ostuni, E. Horishny, M. J. Curry, S. Dooley, P.-y. Chiang, T. Goldstein, and J. P. Dickerson. Proportionnet: Balancing fairness and revenue for auction design with deep learning. arXiv preprint arXiv:2010.06339, 2020.
[25] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004.
[26] A. Malakhov and R. V. Vohra. Optimal auctions for asymmetrically budget constrained bidders. Review of Economic Design, 12:245-257, 2008.
[27] M. McCarty, L. Perl, and K. Jones. Overview of federal housing assistance programs and policy, Congressional Research Service, Library of Congress, 2014.
[28) R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58-73,
1981.
[29] R. B. Myerson. Multistage games with communication. Econometrica: Journal of the Econo- metric Society, pages 323-358, 1986.
[30] N. Nisan, Т. Roughgarden. E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, USA, 2007. ISBN 0521872820.
[31] M. M. Pai and R. Vohra. Auction design with fairness concerns: Subsidies set-asides. Technical report, Discussion Paper, 2012.
[32] M. M. Pai and R. Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383-425 2014.
[33] A. Pavan, I. Segal, and J. Toikka. Dynamic mechanism design: A Myersonian approach. Econometrica, 82(2):601-655 2014.
[34] A. D. Procaccia and J. Wang. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, pages 675-692, 2014.
[35] C. L. Rachfal and A. A. Gilroy. Broadband internet access and the digital divide: Federal assistance programs. Congressional Research Service, 2019.
[36] A. Sinha and Anastasopoulos. Mechanism design for fair allocation. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 467-473. IEEE, 2015.
[37] T. Sugaya and A. Wolitzky. The revelation principle in multistage games. The Review of Economic Studies, 1003)1500-11540, 2021.
12

---

A
Appendix
In this appendix, we present proofs and details that are omitted from the body of the paper.
A.1 Proof of Theorem
We first revisit the following well-known result for EPIC and IR mechanisms in the static scenario (see Chapters and 13 of [30] for the proof):
Proposition 5 ((28). L. A mechanism (æ, p) is EPIC if and only if. for every and k, the allocation
function iiA (v, v ---0000000.. (i,k) is weakly increasing in v, and the payment function is given by
v- (,, = 2i, -J zu,(2, (-(x))) + ((V-(i,))
(13)
with c(U-(1.)) 0 for IR mechanisms. Moreover, the seller's expected utility for any EPIC and IR mechanism is given by
Ep
Σ
(14)
[EE2)
Next, let S be the set of (o: (vi,))) for which the seller allocates the item to one of the groups in the optimal allocation i.c.
(dL E6, (.)( =1]
(15)
Recall that 0; = max; Ui We first establish that, given S, the boundary of the optimal allocation in the form of Φ1 (vi) (2(22) + y for some Note that the set S is measurable as the allocation function is measurable.
Notice that the probability of S is at least a1 + Q2. Since fi(-) and fa(-) are continuous, we can find an allocation rule that is confined to S, satisfies the fairness constraint, and its boundary takes the form é1 (1,) (2 + for some 7 (we call such allocations as affine allocations). That is, group one (2(2)))
receives the object if and only if di (v) 2 (2(22) + and (v1),, 02 (v2)) E S; similarly, group two receives the object if and only if @1 (11) < Φh (12) + y and (ø1 (v1), (12)) E S. We further assume this allocation allocates the item the buyer with highest value within each group. Denote this allocation by x². If there are multiple allocation rules of this form, we select the one whose corresponding 7 has smallest absolute value. On can verify by inspection that such allocation monotone, and hence, satisfies the EPIC condition with its corresponding payment identity. Without loss of generality, we may assume 7 > 0, as the case for y < can be argued similarly.
If we had to allocate every pair in S but there were no fairness constraints, the optimal allocation would have been by checking to the buyer with the highest value. which from groups' pointw of view would mean the boundary Φi (vi) $ (222))). Let A be the region that x² allocates differently from this unconstrained allocation over S, i.e..
A A-= = E E 2 22(22) (01)
(16)
We define À similarly for the allocation 5 as the set values for which we allocate the item suboptimally. Also, for any j E [2]. let Qj C S be the region that is allocated to group j in the optimal unconstrained allocation, i.c.,
Q; = (dr(t)))) E S 2 (-)(v-))}
(17)
In particular, note that A C Q1. We next make the following claim.
Claim 1. The probability of Ån Q1 is lower bounded by the probability of A", i.e.
(An 2 (A
(18)
Moreover. equality only occur if Ā Q
13

---

Proof. To see why this is the case, notice that since T satisfies the fairness constraint, we should have
( P. 2 P.(AnQ1) + + 02
(19)
Now, if (8) does not hold, then we would have
Pa(A") + (Q2))) 02:
(20)
but then this would mean that we can lower the 7 in allocation x² which contradicts its definition.
Notice that the loss of allocation x² compared to the optimal unconstrained allocation is given by
Lossg" := 1/, ( (61 - de (2,x (d.))())
(21)
Let also Loss; denote the loss of allocation ă compared to the optimal unconstrained allocation. This loss is lower bounded by
J Jane: (6I(mx))) 22 (max (2axx2
Loss;
(22)
Notice that, since is the optimal allocation, the right hand side of 22 should be lower than 21
J
( v1 - &2 (max U2 x2,x)) & / (Ø) (mmam)),1,))) 2 (max U2,1 (dF((). (23)
Anqu
&
We next claim that this implies that A AnQ
Claim 2. We have A = Án Q1 (up to a measure-zero set).
Proof. To simplify the notation, let L(v1, 22) = (01) 22(2)) Suppose these two sets not equal. This implies that there some region B outside region A that in region Å Qi and some region B" that is outside region Á n Q1 but inside region A". By Claim 1 we have:
J dF(() 2 { dF(o).
(24)
Next, by 23 have
[ L(v L111, (2) & / L(vi, 02 dF))
(25)
Notice that T(v1, 02) is nonnegative over B and B" Also, the fact that B n A is empty (along with B C Q1) means that sup L(vi, 12) S < inf g L(v1, 02). Next, notice that
/ B-
/ dF(v)
((11,22)F((0 < sup L(v1, 12)
B
B.
and
J
/ dF(().
inf L( L()) U2)
B
B
Combined with (44) these inequalities yield that
J/L L(vi, (2)1,)))F(())
L(u,,e))FF(0
where the equality holds only if and B" are measure zero, which should be the case given 25 This shows that ă and xx the same, up measure zero set.
This claim along with the equality condition of Claim shows that A and À are equal up measure-zero set. Hence, for a given S, the optimal allocation is an affine allocation.
Now, this result was for given S. Using similar argument, we can establish that the optimal set S should be in the form of
{(02(12)) d2 (22
(222))))) (v1)) 2 - or Φ2((2) 2 -122
(26)
14

---

(122)
22(12) = x1(11)
11 (11) )2((2) +
2 (1(1))
722 (m1 + 7)
Figure The case where 1/2 < 1h + 7-
for some 7, 722 2 O. We finally establish that 7/2 + 7. Suppose that 1/2 < ? + y in the optimal fair allocation. Then, there exists the following region of allocations to group one: = (()((e)) (2(2)) (2(22) E (-72, -M -7), (v1) E (-71, -m -2+72), @2(22) 2 d1 (+))+)). Notice that G constitutes a triangle as depicted in the red region in Figure 4 Consider modifying the allocation rule follows. For some g G. do not allocate g. Instead, allocate region of equal measure to group beginning at (-7n, - -7)) This switch changes the loss by the amount 7/1 7/2- Then, return to the original and total levels of allocation by reallocating another equal- measure region on the border Φi (v) = 22( (22) 7 to group 2. The second switch changes the loss by the amount y. Therefore, the total change the loss is !/1 7/2 + < 0 by initial assumption. Thus, this modification results decreased loss to the seller, and it cannot be optimal. Now, suppose that 1/2 ?/. y in the optimal fair allocation. Then, there exists region that is not allocated under the optimal mechanism defined by H = (()((1)) (2(2)) (12) E (-11 ?, -m), Φi (v1) E
-17 7, 7,-7) (v2) (1(v1) + 7}. As before, is a triangle depicted in gray in Figure 5 However, notice that the unallocated values in H are closer to the unconstrained allocation
(11) <= 171 62(22) e (-m1 - 7 - (2(U2) 2 Φ2 (21) - ). Therefore, such an allocation cannot be the optimal fair allocation due to the result shown in the proof of Theorem T that loss is increasing in Euclidean distance from the unconstrained allocation boundary la Observing that these two cases together
boundary than the allocated set of virtual values {(0) (v1), (2(2)))
imply equality concludes the proof.
A.2 Proof of proposition
Let Loss, and Lossg denote the loss of allocations and è compared the original unconstrained allocation, respectively. Notice that the change loss under the modified allocation can be expressed
Loss, LLoss f (0r (max Je,
(2,
(27)
Since b1(max, v1,x) 22 (Inxx v2 E (0.7) for every pair (max U1,k, max; v2 G₂ and G is a set with nonzero measure, we may conclude that Loss, Loss; > 0 In other words, the seller's utility increases under the allocation T as compared to that of allocation z. Therefore, for an optimal fair allocation where 7 > 0, it must be that P(22) 02-
15

---

(122
22(12) = 01(11)
11 (11) )2((2) +
(1(v))
(m 7)
7/2
Figure The case where 1/2 > th + 7-
The proof is similar to show that, if m > 0, i.e, there is insufficient total allocation in the optimal unconstrained allocation, we have PPG1)) Q1 As before, clearly P(G,) a1, otherwise the faimess constraint is not satisfied. Suppose, for sake of contradiction, that P(G1) 2 a. Then there some subset
G ((11, 02)1 m (1 s 0, S (1(11)
(28)
with nonzero measure such that PGG Gb) 2 a1- Notice that G some subset of the orange region in Figure 1b Once again, let be the original allocation and &. be the modified allocation where we do allocate region Gzz. The change in loss under the modified allocation given by
Losss = - (0r (max v1,e) Φ2(max v2
Loss
(29)
Since G has nonzero measure and (2(22) for all (maxı, U1 max; U2 E G follows that Loss: Loss, > 0. Once again, this contradicts the optimality of allocation 2, and it must be that P(G1) a1.
Observing that the second claim follows from exchanging the roles of groups and in the preceding work concludes the proof.
A.3 Proof of corollary
Both results follow from an application of the following claim.
Claim 3. Let (( ) be some function of o Then
E [ (b h² (f(ef()) T f/_ ((..,)dF (11, U2)
(30)
First, by the law of total probability and observing that 2T, 0 if ofTx max of
E [ nh [V)(() E o (b h²) (((()))))) of = max
uf PP (
max of
(31)
16

---

Next, since of t.d. FT, P( maxA vi,k) #.- Also observe that 2f' 0 for (Ul, v2) & G..
Thus,
E E h (((TT) - E MOTWA - max u (2), E Gi)
&
(32)
((u]))dm ma U2)
Jg.
Now, we use the preceding claim to evaluate the expected utility of a buyer in group denoted of RR] R²)). Note that
o (RR ( [ D", h²)l = [ N (b" h²)]
(33)
The expected payment of buyer in group can equivalently be expressed as
T. (b", h²) E (b", )ok (vfA))
(34)
as shown in 30 Lemma 13.11]. Substitution of this result into yields
vf R2) = E T.. (b7. h²) (vTA - of (vTN))
(35)
From here, applying the claim 3 to the function ofe (b" hT) yields the desired result.
Next, we show the second part of the claim. By definition 14 we may express the expected utility of the seller in group denoted μ² (RT R2 as
E |oh (UL, ( + 22 (11
(36)
By linearity of expectation and an application of claim 3 to functions Φn (v1,k) and (12 yields the desired result.
A.4 Proof of proposition
First, notice that the seller must allocate the item member of the group, otherwise the auction becomes infeasible. Therefore, this case reduces static Vickrey auction with no reserve price where the revenue-mase maximizing allocation and payments characterized by (28) as follows. To optimize seller revenue, the seller allocates to the highest bidder who pays an amount equal to the second highest bid.
By definition, we may express the expected utility as
T
T
( Rby =
UT,,
= E
[
+
SE
Σ
8
87-(4+
(37)
Since the seller allocates the item to a buyer in group with probability to maintain feasibility and by Fact I
8E
8 (1-
5z - 1)/5,
(38)
L==+1
From 35 the definition of virtual values, and the observation that this setting reduces to Vickrey auction,
1- (-(N)) fl(
{ 0/.x max of }
E (b', h²) (Vi, (((,,))
(39)
Since v/AA is distributed according to F!( for all E [m], (nL. = max, og =FF (F) Therefore,
E [ nt) ( - (((,,,))
(40)
and the result follows.
17

---

Next, we evaluate the expected utility of buyer -i that does not receive the item. Since buyer -i does not receive the item with probability I, their expected utility reduces to the discounted expected utility over future rounds, i.e.,
(R) R3) =8E
Σ
8 ST-
(41)
The result follows by applying Fact 1 to see that
8 uf
Sv ((Ri - 1)/6, R5/6).
(42)
T=++1
Last, we evaluate the seller's ' expected utility. By Definition 14 and since the good is allocated to the maximum valuation buyer in group with probability
T
= of max vi )] 54 5 1)/6,
( Rb)
Σ
R2,/0).
(43)
Recalling that maxe of (v)", we can express the first term as
)= ((())))
of max of
(44)
&
and the result follows.
A.4.1 Update of interim functions
Under the premise of Proposition 2 the interim functions are updates in the following manner:
(Ri R$) = / F(O))((())) du 5v ((R) - 1)/5, RL,/8),
(45a)
(R,, 12)) = n (R, Rb) = (((()) + + ((R) R(.))).
(45b)
(45c)
A.5 Example with negative net utility of not receiving an item
One might expect the net utility of not receiving the item be nonnegative for each group, given that not receiving the item at the current time implies higher chance of receiving it in future rounds. However, interestingly, this argument is not necessarily true; the expected utility of a buyer may decrease even as the fairness constraint on their group increases. Let us elaborate this matter by simple example. Consider a scenario with T = values are identical across both groups, i.e., F = F for ł E [2]. while the values from the first round are significantly lower than those from the second round, i.c., E. < e². Initially, let aj = Q2 = 0.2. In this scenario, each group has some positive probability of receiving the item in the second round. Now, let us increase an to 0.5. is straightforward to verify that the only feasible allocation is to give the item to the first group in the first round and to the second group in the second round. Given that the values in the first round are considerably lower, this allocation actually decreases the expected utility for the first group.
1, and 8 0.8. Suppose the distributions of
A.6 Proof of theorem
Notice that the variable
n
Σ
(0")
(46)
18

---

determines whether group i receives the item or not. Now, suppose buyer (i, k) submits bid b. Given Assumption 2
we can write the utility of buyer (i,k) k) as:
(b, u --(ua)) (b, 0² (1,1))
x Lb oi (R 1)/00).
(47)
Notice that the last term ōv ++ (R//6, (R=; 1) is constant, independent of the values and the bid. Hence, we can drop this constant from the buyer's s decision making, Now, assuming v' (i.k) is
fixed, we can write the adjusted utility
db, v' (aa(a)))ff Pi o' ((,,)))
(48)
where
(b, 0- ((x))) = (b, 2- -(ax) + 60
E x Lee (ax))
(49)
Using this representation, we can interpret round t-th auction as one round auction. Hence, given proposition 5 for an allocation to be EPIC, æf,4 (b, v' ('.()))) should be (weakly) monotone in b and we also should have
Pl of ((.)) ((..)) b xb, ((n)) [ 2i (ux)) ci
(i (1,6))
(50)
for some function (.)(.) which is independent v. As a result, for any E [2] and E [n]. the payment is given by
pl o' c'x)))) =
(51)
x ( o' (1x))) - ["" s,, v' (1,))) - 80
2 a sl, (1n))) Rb)) + ((((=(())))) t=1
The seller wants to choose C as large as possible, but the IR constraint puts an upper bound on Substituting the payment (11 into (47. the buyer utility is given by
(2, o' (1,) + oottI(R//00 (RL, (1)6)) c,,
(52)
Now, to check the constraint, suppose buyer (i, k)) skips round and denote the optimal allocation in that case by H². Hence, the expected utility of buyer (i, k) from time + onwards is given by
"R, (RL, 1)/6) 8
(i (1.00) (1.))) ) R2))
(53)
Esf
The IR constraint implies that the expectation of (2) minus (53) for any of Thus, we should have
over of (i.k) should be nonnegative
Σ 3 (0 (m))) EgEk
Eyg (1,0) (( (R) RS} Eyg Eus
(54)
and so, the seller sets the function c;,(() to achieve the equality case. Note that the right hand side is only function of We denote it by cq. We next make the following claim regarding the expected payment of buyer (i, k) to the seller in this case.
Claim 4. The expected payment of buyer (i, k) to the seller at round is given by
E
D ( () R2)) c.
(55)
19

---

The proof of this claim follows from the classical derivation of payment in static mechanism design (see [Lemma 13.11] for instance) along with the characterization of payment in (5T). As consequence, the seller's utility at round is given by
2
Engs ΣΣ k=1
Σ
nó
RS) Σ Eoielott
+ +ne + nez.
(56)
i=1
t=1
Therefore, the seller's expected utility for time L onwards is given by
(l(l)))) + Σ 8 (1 (
((R) 1)/6, RL. mAN Ra)) Σ (alc(o))
+not trae.
(57)
Notice that the seller wants to maximize (7 First, notice that, since of(+) is increasing by Assumption [ if we allocate the item to group we would allocate it to the buyer with the highest value which we denote its value by of = max; of
Now, need determine whether the item is allocated the buyer with the highest value in group one or to the buyer with the highest value in the second group. Given (57). is straightforward to see that the item is allocated to group one if
si (vf) nó (A)
o5 (v5)
(58)
(E)) + å
( ()66,
and otherwise it is allocated to the second group. Notice that this allocation is indeed monotone, and hence, along with the above payment, is an EPIC and IR allocation. This gives the set G in the theorem's is statement. Finally, to derive the update of interim functions, notice that the expected utility of seller follows from (57). The expected utility of buyers can also derived from Claim similar to the proof of Corollary
A.6.1 Characterization of Ç
Recall that of is given by
c = --) R33
(59)
where
Ezhelo' (1.)))
Ç7 - Bo= (1.0)
(60)
is the probability of group i winning the object when they participate with one fewer buyer. Notice that, an argument similar to the one made above implies that in the case where have n-1 buyers from group and buyers from the other group, group wins the item if (maxeş< of,e, maxe u(. E G with
a = (c1, 02) of((s)) (²_(v==) (n- 1)84 RS) nóA (R,, R3 (-1)'84 RR, Rb)
As result, we have
Ç = /
(v=:))))
(61)
0
A.6.2 Update of interim functions
The expected utility of seller follows from (7 The expected utility of buyers can also be derived from Claim 4 similar the proof of Corollary Hence, we have
(1:) dFt max (11, U2) + 50 ++1
(R) R2) Ja
- R3yt
fl(e))
(62a)
('(R, R³)=
(62b)
Σ
2
02) (1 (l) dF (1), + (P(())))* 11/6 /8) + (n, - IP(G)))
1=1
where the probability measure PP.)) taken with respect to the distribution pt (w), v2) =
F) F((z)"
20

---

A.6.3 Relaxing Assumption 2
Revisiting our proof shows that we can relax Assumption 2 and repeat the proof steps. In particular, when not allocating to either of the two groups is feasible, the utility of buyer (i. k)) in (47) will change to
(b, v- (1.b) 10, - Pi v- (1,s)) - 5 ++1 (R 15, (6)
e0, 0² (1.)))) (1) 122) - 8(
2) (b, v-
12),
(63)
1=1
with
|,,00 -1
(64)
(R, [,)===== (RL2
(65)
We can follow similar steps to derive the payment and allocations. We do not repeat the proof steps here as they follow similar argument.
A.7 Proof of proposition
We first define x' as follows: We assume that the auction designed to run for To rounds (for a chosen value of To determined later) and use the recursive functions developed earlier to determine the exact fair allocation under the fairness constraint at level a; E for group i (computed over the first To rounds). For the remaining T To rounds, conduct the standard second-prii -ernnde--iceeeee auction.
First, we characterize the approximation x' relation to the exact fair allocation. Let x" denote the allocation to group i at time É under the optimal allocation that satisfies the fairness constraint (2) at level a; for i (1, Next, we consider the fairness guarantees of x == {xx ||== with early stopping.
Claim 5. the allocation x" is stopped time To = < T, then fx {att)7 To constraint (2) at a level (a; E).
iltml satisfies the fairness
Proof. Observe that xx satisfies
To
T
T-1
Σ
8
x
st
8'
(66)
t=1
t=Tb+1
1=0
Now, since x² E {0, 1} for all t, we can see that
T
T- To
T To
8 88-11
5 8oo
8
=
8
t=0
where the second equality follows from the fact that 8To by construction. From here, that
Ee, 8"-
IT-10 8t
E1
T-1-T 8t
レ= 8'
El-11 8z
Eee
Eie 8z
(a; 8
E
To
8'
04
where the last two inequalities follow from the fact that 8t > 0 for all and that To < T. It follows that
To
To 8'
x 2 (a:
=)
(67)
1=0
Now, we use this claim to evaluate the faireess guarantee of x'. We claim that, over T rounds, x' satisfics the fairness condition at a level (1 - e)(a; - =) for E {1,2), i.c.
T
8l- x 2 (1 - (1- Σ 8¹.
21

---

Since x²; xx; for E [Tol. by Claim it suffices to show
T
T-1
Σ
8
8
(a:
Σ
8
c(a; -5
Σ
8
(68)
t=
t=To
t=0
Now, since d E (0, 1) and 2 To. we can observe that
8T
8T
87h
1 8
1 1
Substituting og and recognizing these expressions as geometric series yields
T-1
T-1
8
t=To
Now, noticing that a; - 2 and rearranging, we see that
T-1
T-1
N (a: - E)
Σ 8c E(a; - E)
Σ
8:. (=0
To
We reach the desired result of Equation (68) by noting that _- that, over T rounds, x' achieves a fairness level of at least - (1- E).
for all and we have shown
Next, we consider the computational guarantee of x'. Since the fair allocation algorithm is recursive, its computational complexity increases exponentially in the number of rounds. the approximation, we conduct exactly To rounds of the fair allocation, therefore, the computational complexity can be bounded as follows:
(2 S0 (c = (221110())) =0
logt1783
Finally, we consider seller utility guarantees of x'. First, we note that, by Claim 5 the seller utility up to time To under x' is at least that of x² up To because the set of allocations over which x is optimal over the first To rounds terms of seller utility is a subset of those allocations over which xx is optimal. Second, since, under x' we perform remaining T To rounds, it follows that x', must also guarantee seller utility that is at least that of the optimal fair allocation xx over the second interval. Therefore, x guarantees seller utility that is at least that of x" over all T rounds.
unconstrained second-price auction in the
A.8 Proof of proposition
4
First, give the full proposition statement:
Proposition 6. Suppose Assumptions 7 hold and that 5 < 1. Then, for any E (0, min, mi,))()))))) 1 6, there exists an approximation to the optimal allocation x" with the following properties:
1. x" satisfies the fairness constraint over all rounds at a level of at least ( (1-=)(1-3)((a--))
2. x" guarantees that the sellers total utility is at least (1 - B) of that of the optimal allocation.
[ log 1=5(1
3. x" can be computed by calling the oracle o
times.
Note that 3 can be chosen to achieve given S 82 such that the proof statement in the body holds.
Now, we proceed with the proof by first defining x" as follows: As in the approximation x' presented proposition 3 we assume under x" that the fair auction runs over To rounds (the same value To which we detail later) where we partition these To rounds into To/8 buckets of rounds (we later also define in detail) and approximate the discount factor as being constant within each bucket. Then, within each bucket, recursively calculate the fair allocation at level (1 B1 a.) with
22

---

respect to the approximated discontinuous discounting scheme. For the remaining T To rounds, we conduct standard second price auction.
In partieular, as before, we take To logie) and we choose such that 8 B. Without loss of log(o)
generality, we assume To/e, e, are integers. In the kth bucket, we approximate the discount factor of each round in the bucket with 8 for &o E [To/[]-
Now, we characterize the allocation under æ" in relation to the exact fair allocation x" defined in the proof of proposition 3 to show its fairness guarantee. First, observe the following relationship between the true discount factors and those of the discontinuous discounting scheme in x":
Tofi
8
B)
Σ l (((k-1),
(69)
Therefore, by Claim 5 and our construction of the discontinuous discounting scheme, x" satisfies the fairness constraint at the level (1 B) - E) with respect to the discontinuous discounting scheme over the first To rounds, i.e.,
To/e-1
To
Toft Σ l (((k-1)
8th
8
2x
(1 B)(a; -E)
1=k(+1
From here, we characterize x" the allocation such that, in the first rounds, we perform the fair allocation procedure that satisfies fairness constraint at level (1 (a; =) with respect to the discontinuous discounting scheme and standard second- priceppice auction in the remaining T To rounds. It follows that xx satisfies
To
Tott-1
kt
To Σ
8' 2 (1- 3)
Σ
8
Σ t=k++1
x; (1-))
-
8
In other words, over the first To rounds, x" satisfies the fairness constraint at a level of at least - (a, =) with respect the original discounting scheme. By the same manner the proof of proposition 3 it follows that, over 7 rounds, x" guarantees fairness at the level at least
(1-=) (a; -e). E). Finally, by (69 and the same logic as the proof proposition we conclude
that the seller's 's utility is at least (1 5) that of x" under x" over T rounds.
A.9 Experiment Details
Here, we provide the full results of the experimentation summarized in the body of the paper For each combination of 01,, 02 and each value of T 2, 4, we compute 10,000 iterations of the seller-optimal allocation satisfying the fairness constraint at level a; for group E [2] over 2 rounds with discount factor 8 0.99. Also note that buyer values are distributed as follows: of ~ Unniform(O.5. 1.5). and uy ~ Uniform (0, 1) for E T 2,3, 4. useful to note that, in the seller-optimal unconstrained mechanism, groups and 2 are allocated the item with probabilities 0.69 and 0.31, respectively. Our implementation maintains all key assumptions outlined in the presentation of the mechanism. We report the difference in mean utility of the seller, group 1, and group that satisfies the fairness constraint specified by particular (n,, O22 relative to the utility of the optimal unconstrained mechanism satisfying assumption 2 (i.e. the optimal fair mechanism level 01, (2 = 0). Standard errors are reported for each value in Tables 1 and reflect the standard error of the mean which assumes sample independence.
'Note that additional experimental results are available in an extended version available at httpss//aaiivorrr/////4660....00
23

---

Table Difference in seller utility relative unconstrained optimal allocation with standard errors
for T
a2
Q1
0.0
0.1
0.2
0.3
0.4
0.5
0.0
-0.0019
-0.0015
-0.004
-0.0134
-0.0624
0.0
(0.0031)
(0,0032)
(0.0032)
(0.0032)
(0.003)
(0.0029)
-0.2033
-0.1957
-0.2033
-0,2016
-0.2224
-0.2679
0.1
(0.0037)
(0.0037)
(0.0037)
(0.0037)
(0.0036)
(0.0034)
-0.2688
-0.267
-0.2759
-0.2715
-0.2777
-0.3291
0.2
(0.0038)
(0.0038)
(0.0038)
(0.0038)
(0.0037)
(0.0036)
-0.3495
-0.344
-0.3445
-034166
-0.3531
-0.4061
0.3
(0.0039)
(0.0039)
(0.004)
(0.0039)
(0.0038)
(0.0036)
-0.4341
-0.4285
-0.4245
-0,4227
-0,4383
-0.4828
0.4
(0.0038)
(0.0039)
(0.0039)
(0.0039)
(0.0038)
(0.0036)
-0.5297
-0.5351
-0.5337
-0.5325
-0.5394
-0.587
0.5
(0.0036)
(0.0036)
(0.0036)
(0.0036)
(0.0035)
(0.0033)
Table 2:
Difference in group 1 utility relative to unconstrained optimal allocation with standard errors
for T
a2
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.0065
0.0007
0.0019
0.023
0.0622
0.0
(0.0036)
(0.0037)
(0.0037)
(0.0037)
(0.0037)
(0.0038)
-0,0155
-0.0058
-0,0123
-0.0081
0.0035
0.0587
0.1
(0.0035)
(0.0036)
(0.0036)
(0.0035)
(0.0036)
(0.0037)
-0,0232
-0.0169
-0.0166
-0.0184
-0.0018
0.0409
0.2
(0.0034)
(0.0034)
(0.0034)
(0.0034)
(0.0035)
(0.0035)
-0.0305
-0.0317
-0.0247
-0.0267
-0.0119
0.037
0.3
(0.0033)
(0.0033)
(0.0033)
(0.0033)
(0.0034)
(0.0034)
-0.0451
-0.0413
-0.0455
-000377
-0.0277
0.013
0.4
(0.0032)
(0.0032)
(0.0032)
(0.0032)
(0.0032)
(0.0033)
-0.0639
-0,0609
-0,0618
-0.0598
-0.0549
0.0002
0.5
(0.0031)
(0.0031)
(0.0031)
(0.0031)
(0.0031)
(0.0032)
Table 3: Difference in group 2 utility relative to unconstrained optimal allocation with standard errors
for T
02
di1
0.0
0.1
0.2
0.3
0.4
0.5
0.0
-0,0021
-0.0009
-0.0037
0.0032
0.0226
0.0
(0.0025)
(0.0026)
(0.0026)
(0.0025)
(0.0026)
(0.0027)
0.1773
0.1729
0.1789
0.1749
0.1807
0.1873
0.1
(0.0033)
(0.0033)
(0.0033)
(0.0032)
(0.0033)
(0.0034)
0.2214
0.2187
0.2215
0.2194
0.2212
0.2337
0.2
(0.0033)
(0.0034)
(0.0034)
(0.0033)
(0.0034)
(0.0035)
0.2634
0.2705
0.2626
0.2629
0.2742
0.2849
0.3
(0.0034)
(0.0034)
(0.0034)
(0.0034)
(0.0034)
(0.0035)
0.3245
0.3228
0.3253
0.3205
0.3284
0,3424
0.4
(0.0034)
(0.0035)
(0.0034)
(0.0035)
(0.0035)
(0.0036)
0.3923
0.3896
0.3933
0.3861
0.397
0.4075
0.5
(0.0034)
(0.0035)
(0.0034)
(0.0034)
(0.0034)
(0.0035)
24

---

Table Difference in seller utility relative unconstrained optimal allocation with standard errors
for T
a2
Q1
0.0
0.1
0.2
0.3
0.4
0.5
0.0
-0.0006
-0.0209
-0.06
-0.0642
-0.1069
0.0
(0.0035)
(0.0034)
(0.0035)
(0.0035)
(0.0035)
(0.0038)
-0.2693
-0.2578
-0,2767
-0.3308
-0.324
-0.3715
0.1
(0.0038)
(0,0038)
(0.0038)
(0.0038)
(0.0038)
(0.0039)
-0.4226
-0.4145
-0.4279
-0,4767
-0,4801
-0.5395
0.2
(0.0038)
(0.0037)
(0.0038)
(0.0038)
(0.0038)
(0.0038)
-0.623
-0,6251
-0.6363
-0.6913
-0.6895
-0.7614
0.3
(0,0038)
(0.0037)
(0.0038)
(0.0038)
(0.0037)
(0.0037)
-0.6836
-0.6792
-0.6955
-0.7329
-0.741
-0.8184
0.4
(0.0038)
(0.0038)
(0.0038)
(0.0038)
(0.0038)
(0.0036)
-0.4898
-0.4868
-0.4955
-0.5465
-0.5498
-0.6848
0.5
(0.0036)
(0.0036)
(0.0036)
(0.0036)
(0.0035)
(0.0037)
Table 5: Difference in group utility relative to unconstrained optimal allocation with standard errors
for T
Q2
0.0
0.1
0,2
0.3
0.4
0.5
0.0
0.0055
0.0117
0.0673
0.0652
0.1944
0.0
(0.0054)
(0.0055)
(0.0055)
(0.0055)
(0.0054)
(0.0055)
-0.0467
-0.0412
-0.035
0.0103
0.0164
0.1613
0.1
(0.0053)
(0.0052)
(0.0053)
(0.0052)
(0.0053)
(0.0054)
-0.0824
-0.0812
-0.0765
-0.0269
-0.0245
0.1163
0.2
(0.0051)
(0.0051)
(0.0051)
(0.0051)
(0.0051)
(0.0052)
-0.1372
-0.1325
-0.1204
-0.0862
-0.0712
0.0673
0.3
(0.0049)
(0.0049)
(0.0049)
(0.005)
(0.0049)
(0.005)
-0.1641
-0.1592
-0.1881
-0.0988
-0.0956
0.0514
0.4
(0.0048)
(0.0048)
(0.0048)
(0.0048)
(0.0048)
(0.0049)
-0.2634
-0.2681
-0246
-0.2055
-0.1944
+0.0228
0.5
(0.0042)
(0.0042)
(0.0042)
(0.0042)
(0.0042)
(0.0043)
Table 6: Difference in group 2 utility relative to unconstrained optimal allocation with standard errors for T
02
0.0
0.1
0,2
0.3
0.4
0.5
0.0
-0.0058
-0.0081
-0.011
-0.0087
-0.0666
0.0
(0.0043)
(0.0043)
(0.0043)
(0.0043)
(0.0043)
(0.0042)
0.2473
0.2397
0.2362
0.2397
0.2408
0.1908
0.1
(0.0046)
(0.0046)
(0.0045)
(0.0045)
(0.0046)
(0.0045)
0.3692
0.3712
0.3722
0.3757
0.3814
0.3376
0.2
(0.0046)
(0.0046)
(0.0046)
(0.0046)
(0.0046)
(0.0046)
0.5476
0,5475
0.5437
0,5486
0,5436
0,5274
0.3
(0.0049)
(0.0048)
(0.0049)
(0.0049)
(0.0049)
(0.005)
0.5734
0.5748
0.5663
0.5591
0.5699
0,345
0.4
(0.0049)
(0.005)
(0.005)
(0.005)
(0.0051)
(0.005)
0.2677
0.2783
0,2751
0.2692
0.2739
0,2945
0.5
(0.0048)
(0.0048)
(0.0048)
(0.0048)
(0.0048)
(0.0048)
All experiments were performed using hardware with the following specifications: Intel Xeon CPU 2.20GHz, CPU core. The total experiment runtime was 23 minutes and 10 seconds and used 1.5
GB system RAM.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The introduction and abstract accurately describe that the paper presents the optimal static mechanism for allocating an indivisible good among two groups that guarantees each group minimum specified allocation probability, extends this result to the dynamic setting, and presents approximations for and experimentation of these optimal mechanisms. The introduction and abstract also identify the setup and key assumptions of these results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Throughout the paper, modeling assumptions are stated clearly which make clear the limitations of our results. For instance, our results assume regularity of the value distributions (i.c., virtual value is increasing) as well as the independence of realized values where lifting these assumptions the topic of future work. The computational complexity of the optimal mechanism that we present as well as the approximations that follow are presented clearly.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
26

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper clearly states or references the full set of assumptions of each result. A complete proof of each result is included in either the body of the paper the appendix and a proof sketch is provided in the body of the paper when the full proof is included the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides the full details of the experimental procedure as well as the code to recreate the results of the experiment including all figures and tables.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
27

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the complete code and procedure reproduce our results including all figures and tables. Since our results include simulated data, we also include the full procedure and code to reproduce synthetic data generation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
mublic//uuiee//CdeSttiiii son.eedessammssssoooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
ptsiiss.cc/publicguuudee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper fully specifies the process of data generation, the allocation algo- rithm, and the procedure of experimentation. The body of the paper presents a thorough summary of the experimentation process, and full details are specified in the appendix. The full self-contained code reproduce our results also included.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
28

---

7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate
information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report standard errors of our experiments the appendix along with relevant details and assumptions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide hardware specifications, runtime, and memory for all experimenta- tion in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /etne///npssisee wweeurpss.ccpubliiee. cc.ppublic/tthiccccud........
Answer: [Yes]
Justification:
This work conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We identify the broader societal impacts of our work in the introduction where we outline relevant applications and motivation for considering for fairness in resource allocation.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We release no such data models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com com/datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The optimal allocation mechanism that we introduce is specified full detail, the approximations to this mechanism.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does involve crowsourcing not research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
31

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowsourcing not research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "9mLMKbrNjA", "reviewer": "Reviewer_5sNL", "summary": "The authors study the problem of dynamic mechanism design when in which for $T$ rounds an auctioneer sells an indivisible good to two groups of people. The goal is to design a mechanism which incentivizes the agents first to participate in the auction and second to bid truthfully and moreover maximizes the discounted revenue of the seller while guaranteeing a minimum expected allocation for each group. The proposed mechanism utilizes two types of subsidization. One is to reduce the reserved bid to increase the probability of allocation for all buyers and another is to favor the group which otherwise is less probable to win the good. These hold even when $T=1$. For $T>1$, the seller rewards the winner to incentivize truth-telling since otherwise, the agents might benefit from underbidding to increase the probability of winning in later rounds (which they might expect to value more). Moreover, the seller also charges the participants with an entry fee which is the expected reward payment they lose by not participating. \n\nThe proposed mechanism finds the optimal allocation in exponential time in terms of $T$. However, the authors propose an efficient approximation scheme and a poly-time constant approximation scheme. They also implement their mechanism and compare the utility to the case with no fairness constraints.", "questions": "Could you please clarify the points mentioned in the last section. Namely,\n1. please motivate the studied setting by real-world instances.\n2. please justify the proposed fairness notion.", "limitations": "The limitations are addressed in a sense that the assumptions on the studied setting are mentioned.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The studied problem of achieving fairness in mechanism design where agents are strategic is important and interesting. While the paper is quite notation-heavy, intuitions are provided to better understand what is going on.", "weaknesses": "The paper is not clear in some parts. The parameter $\\delta$ is never clearly defined and it was very confusing to see it in line 112 without any proper previous description. Furthermore, the setting is not motivated. 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. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and comments. Please find our answers below. \n\n> The parameter $\\delta$ is never clearly defined and it was very confusing to see it in line 112 without any proper previous description.\n\nWe 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.\n\n> 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.\n\nWe 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. \n\nWe 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.\n\nWe 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. \n\n> 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.\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sXSR237Yxr", "reviewer": "Reviewer_WPVa", "summary": "This paper studies a fair allocation problem where an auctioneer sells an indivisible good to two groups of buyers every round for T rounds. The auctioneer’s objective is to maximize their discounted revenue with fairness constraints. The authors show that for the static case with T=1, the optimal mechanism subsidizes one group to meet the fairness constraints, and may increase the probability of allocating the item to both groups by reducing the reserve price (compared to Myerson’s auction). For the dynamic case with multiple rounds, they characterize the optimal allocation by a set of recursive functions. They establish that in the optimal allocation, to incentivize truthful value reporting, the seller pays a participation reward for the winning group, but also charges the buyers an entry fee. Similar to the static case, the optimal allocation involves subsidizing in favor of one group. Finally, they present an approximation algorithm to solve the recursive equations.", "questions": "* Would you add some motivation for the discount factor?\n* Would you add some discussions of the limitations of this work and future directions in the main paper?", "limitations": "The authors discussed limitations in the paper checklist form, but those are not explicitly mentioned in the main paper, potentially because of page limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of allocating an indivisible good with some fairness constraints is well motivated. This paper extends previous work with a similar fairness definition in the single group and single round setting to two groups and multiple rounds, and characterizes different types of subsidization for this setting. This paper is mostly well written and related work is adequately cited.", "weaknesses": "* Minor comments\n  * The discount factor $\\delta$ is mentioned in the introduction, better to make sure it’s also defined in the Model section for notation reference.\n  * Page 1, line 11: “on one hand” -> “on the one hand”\n  * Page 6, line 231: “methods is provided” -> “methods are provided”\n  * Page 6, line 253: “Aggregated-SP seem to be” -> “Aggregated-SP seems to be”\n  * Page 8, line 315: “provide upper bound” -> “provide an upper bound”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and comments. Please find our answers below.\n\n> The discount factor  is mentioned in the introduction, better to make sure it’s also defined in the Model section for notation reference.\n\nWe 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.\n\n> Minor Comments and Typos\n\nWe thank the reviewer for pointing out all the typos, and we would fix them in the final version.\n\n> Would you add some motivation for the discount factor?\n\nThe 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.\n\nThat 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.\n\n> Would you add some discussions of the limitations of this work and future directions in the main paper?\n\nWe 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.\n\nRegarding 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yRFjGAu983", "reviewer": "Reviewer_ssTM", "summary": "This paper studies the incorporation of fairness constraints into revenue-optimal single-item auctions. Specifically, it focuses on a scenario with two groups bidders. Within each group, bidders' private valuations are sampled i.i.d. from a distribution, with the two groups having different valuation distributions. The fairness constraint is defined by two numbers, $\\alpha_1$ and $\\alpha_2$, requiring the mechanism to ensure that the expected allocation to group $i$ is at least $\\alpha_i$. The objective is to identify the revenue-optimal EPIC and IR mechanism that meets this fairness criterion.\n\n\nThe submission first investigates the static case where only one round of the auction is conducted and characterizes the optimal mechanism. The authors demonstrate that, compared to the optimal auction without fairness constraints, the optimal mechanism with fairness constraints subsidizes all bidders in the virtual value space to enhance their chances of allocation. Additionally, the paper observes that the optimal mechanism provides subsidies to the disadvantaged group. From a technical perspective, the argument extends Myerson’s original proof of optimal auctions without fairness considerations in a relatively straightforward manner.\n\nNext, the authors extend their analysis to a dynamic auction setting where the auction is conducted over $T$ rounds, with an item being auctioned in each round. Valuations can vary across rounds. In this dynamic setting, the fairness constraint imposes a lower bound on the expected number of allocated items in future rounds based on the allocation history of previous rounds. Bidder incentives become more complex, as they might underbid in the current round to gain an advantage in future rounds with higher-valued items due to the fairness constraints. The authors characterize the optimal mechanism using backward induction, noting that the optimal mechanism starting from round $t$ depends only on the remaining fairness quota for each group. With this insight, the optimal mechanism starting from round $t$ can be determined by implementing Myerson’s auction after adjusting the bidder's value by the externality (the decrease in future revenue from awarding the item to the bidder in the current round). With a discounting factor, finding the exact optimal mechanism requires exponential time. The authors propose methods to efficiently approximate it through early stopping and discretization.\n\nThe paper concludes with a numerical experiment illustrating how different fairness constraints impact revenue and bidders’ utilities in each group.\n\nMinor comments: \n- There is an extra symbol in equation (6).\n- It would be much clearer to add a description of the allocation for each region in Figure 1.", "questions": "- Do the results still hold when bidders in one group have different valuation distributions?\n- The paper assumes that all distributions are regular. Do main results extend to arbitrary distribution by ironing?", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem is well-motivated. I believe studying fairness notions in dynamic auction settings has its potential. In addition, the specific model considered in the paper feels reasonable.\n- The paper fully characterizes the optimal mechanism and provides some high-level interpretations.\n- The paper is well-written. Technical parts are easy to follow.", "weaknesses": "- Experiments seem too simple, it would be better if the authors conducted a more extensive experiment.\n- Though the authors claim that results should extend to more than 2 groups, it would better to include some formal statements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and comments. Please find our answers below. \n\n> Minor Comments\n\nWe 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.\n\n> Experiments seem too simple, it would be better if the authors conducted a more extensive experiment.\n\nWe 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.\n\n> Though the authors claim that results should extend to more than 2 groups, it would be better to include some formal statements.\n\nWe thank the reviewer for their suggestion. Please see General Comment 2 in our global response. \n\n> Do the results still hold when bidders in one group have different valuation distributions?\n\nWe 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.\n\nThat 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.\n\nNotice 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.\n\n> The paper assumes that all distributions are regular. Do main results extend to arbitrary distribution by ironing? \n\nWe 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$.\n\nLet $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$. \n\nNow, as Myerson [1981] establishes, the seller's revenue can be cast as \n$$\\mathbb{E}\\_{\\pmb{v}} \\left [ \\sum_{i \\in [2],k \\in [n]} \\phi_{i}(v_{i,k}) x_{i,k}(\\pmb{v}) \\right] = \n\\mathcal{R} - \\mathcal{E}\n$$\nwith \n$$\n\\mathcal{R} := \\mathbb{E}\\_{\\pmb{v}} \\left [ \\sum_{i \\in [2],k \\in [n]} \\tilde{\\phi}\\_{i}(v_{i,k}) x_{i,k}(\\pmb{v}) \\right]$$\nand \n$$\n\\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 ]. \n$$\n\nNow, notice that since $\\tilde{\\phi}\\_i$ is monotone, our current result gives us the allocation that maximizes $\\mathcal{R}$ subject to the fairness constraint, which, as Theorems 1 and 2 suggest, is in the form of $\\max_{k} \\tilde{\\phi}\\_1(v_{1,k}) - \\max_{k} \\tilde{\\phi}\\_2(v_{2,k}) \\lesseqgtr \\gamma$ for some $\\gamma$.\n\nTherefore, it suffices to show that for allocations in this form, $\\mathcal{E}$ is zero. Notice that $\\mathcal{E}$ can only be positive when $H_i(F_i(v)) > G_i(F_i(v))$ and $dx\\_{i,k}(v, \\pmb{v}\\_{-(i,k)}) > 0$. However, by the definition of the convex hull, when $H_i(F_i(v)) > G_i(F_i(v))$, then $G_i$ is linear in a neighborhood of $v$, which means $g'_i(v) = 0$, implying that $\\tilde{\\phi}\\_i(v)$ is constant in a neighborhood of $v$. Now, as the value of others is fixed and the virtual value of buyer $(i,k)$ is also constant in a neighborhood of $v$, given the above form of the allocation, $x\\_{i,k}(v, \\pmb{v}\\_{-(i,k)})$ also remains constant in that neighborhood, which implies $dx\\_{i,k}(v, \\pmb{v}\\_{-(i,k)}) = 0$. This completes the proof that $\\mathcal{E} = 0$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AjwpYrjkOW", "reviewer": "Reviewer_ZeA8", "summary": "The paper explores an auction mechanism where an auctioneer aims to maximize discounted overall revenue while adhering to fairness constraints that ensure a minimum average allocation to two distinct groups. The study begins with a simple T = 1 scenario to establish the foundational optimal mechanism constraints, which include:\n\n- Overall probability distribution to all buyers\n- Preferential treatment for the group with an otherwise lower probability of winning\n\nIn a dynamic setting, the paper extends to explore recursive solutions that utilize price history to optimize revenue while maintaining fairness. This approach extends with incentives beyond the traditional second price auction optimality, adjusting for group-based discrimination in each round.", "questions": "- 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?\n- How standard is Assumption 1 used within the model, and how does it compare to assumptions typically made in similar studies?\n- 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.", "limitations": "Addressed in the prior comments. Further experimentation on real world datasets could be useful but not a major limitation as this is largely a theoretical paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The manuscript is exceptionally well-written, with all assumptions clearly justified and results thoroughly explained prior to their introduction. The logical flow and clarity of exposition make the results easily interpretable.\n- Although brief, experiments using randomly generated datasets illustrate the practical application of the theoretical results, especially emphasizing the dynamic setting's theoretical contributions.\n- The discussion on optimal allocation rules is insightful and presents a novel extension beyond existing literature, addressing new contexts of fairness in auction settings.", "weaknesses": "- The paper would benefit from a more comprehensive discussion of related works to better situate its contributions within the existing body of knowledge.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and comments. Please find our answers below. \n\n> The paper would benefit from a more comprehensive discussion of related works to better situate its contributions within the existing body of knowledge.\n\nWe 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.\n\nIn 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.\n\nAlso, 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.  \n\n> 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.\n\nWe 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.\n\n>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?\n\nYes, please see General Comment 2 in our global response. \n\n> How standard is Assumption 1 used within the model, and how does it compare to assumptions typically made in similar studies?\n\nAssumption 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.\n\n> 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.\n\nThe 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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Global Responses:**

We thank the review team for their thoughtful and detailed comments. Here, we provide our general answers before addressing each reviewer's questions separately.

**General comment 1: Motivating examples based on real-world applications**

Auctions are used in various real-world applications, and in many of them, fairness considerations play an important role. In what follows, we provide a number of examples of such applications:

First, auctions are commonly used for allocating houses, either by private entities or government agencies. At the same time, several policies in different countries address the housing needs of low- and moderate-income households, from Affordable Housing Quotas in the United Kingdom to tax credits and vouchers in the United States. Our framework can be seen as an approach to combine such fairness considerations with auctions frequently used for allocating new houses.

Second, the federal government in the United States uses auctions to choose contractors for certain types of procurements. The United States Small Business Act sets targets for contracting with specific categories of businesses (e.g., woman-owned businesses, veteran-owned businesses, historically underutilized zones). These are yearly targets, and our approach would allow for these targets to be met as efficiently as possible.

Third, governments use auctions to decide on telecommunications licenses, i.e., which band of the electromagnetic spectrum should be used by each company to transmit signals. Ensuring smaller or regional companies have a chance to compete with larger national companies is one of the considerations in such allocations, which aligns with our framework. In fact, the Communications Act of 1934’s “equal opportunity” section requires that radio and television broadcasters provide “reasonable access” to all major political candidates. There has also been a recent push for the same requirement for digital/social media ads, which are sold algorithmically via auction.

Last but not least, auctions are used in environmental settings, including fishing rights, and there has been discussion about using auctions for the allocation of water rights given the growing conflicts among states and countries regarding access to water resources. It is evident that having a framework that motivates the fair allocation of resources among different agents while running auctions over time can be very applicable in these settings as well.


**General comment 2: Extension to more than two groups**


Regarding the question raised by two of the reviewers, we would like to briefly discuss how our results and insights extend to the case where we have more than two groups. Due to the character limit, we include the static case here.

In particular, let us see how Theorem 1 changes when we have $L$ groups. Part (i) remains unchanged, meaning that if the item is allocated to group $i$, it is allocated to the buyer with the highest value (and let’s denote this highest value by $v_i$). Then, we have the following:

*There exist nonnegative numbers $\eta_1, \cdots, \eta_L$ that characterize the optimal allocation in the following way: the item is allocated to group $i$ if and only if $\phi_i(v_i) + \eta_i \geq 0$ and $\phi_i(v_i) + \eta_i \geq \phi_j(v_j) + \eta_j$ for any $j \neq i$.*

Notice that the insight behind this result is very similar to the current Theorem 1 for two groups. $\eta_i$ is the subsidy to group $i$ and $\min_i \eta_i$ can be seen as the overall subsidy to the society (similar to $\gamma$ in our current draft).

The proof involves several steps, but the idea is similar to the case with two groups: we show that the best way to help groups that do not get the item with sufficient probability in the unconstrained case is to shift the allocation boundary of the unconstrained case towards them. More formally, here are the steps of the proof:

First, let $x^*$ denote the optimal allocation. If $x^*$ is not in the above form, we will show that through a series of steps, it can be transformed into an allocation of that form. Furthermore, we will establish that in this process, the seller's revenue can only increase, and the fairness constraints are not violated. While the intermediate allocations are not necessarily monotone, the final result will be a monotone (and hence a legitimate) allocation. In this process, we make use of the following lemma:

*Lemma 1: For any $i$ and $j$, there exists $\eta_{i,j}$ such that, if the item is allocated to one of the groups $i$ or $j$, then it is allocated to group $i$ if and only if $\phi_i(v_i) - \phi_j(v_j) \geq \eta_{i,j}$.*

If there are multiple choices for $\eta_{i,j}$, we pick the one with the smallest absolute value. Now, it remains to show that the $\eta_{i,j}$'s are indeed connected to each other. To do so, we show the following lemma:

*Lemma 2: Suppose $\eta_{i,j} \geq 0$ and $\eta_{j,k} \geq 0$. Then, we have $\eta_{i,k} = \eta_{i,j} + \eta_{j,k}$.*

The proof of this lemma is very similar to the way we prove $\eta_2 = \eta_1 + \gamma$ in Appendix A.1 of the submission draft (starting from line 491).

We hope this result establishes how our insight carries over to multi-group fairness. We will include a detailed result for both the static and dynamic cases as a new appendix in the final version of our paper.


**General comment 3: Additional experiments**


In response to reviewers' comments, we have conducted a number of additional numerical experiments (please see the attached file). In particular, we have included experiments that extend our initial utility comparison for a larger number of rounds, $T$. We have also included experiments comparing our fair mechanism to one that achieves fairness via set-asides, complementing the existing literature on their comparative merits (e.g., Athey et al. [2013], Pai and Vohra [2012]).

Meta-review: Reviewers found the problem well-motivated, the characterizations and the algorithm interesting, and the paper well-written. Review also appreciated the clear logic flow and high-level proof ideas and the experiments. No significant concerns remain after the rebuttal. All reviews agreed that this is a nice piece of work for NeurIPS. We hope the authors find the reviews helpful. Thanks for submitting to NeurIPS!
Decision: Accept (poster)