Question 1. Fair Allocation with Subsidy
Assume that there is a set of ( M = {e_1, \dots, e_m} ) indivisible goods and ( N = {1, \dots, n} ) agents, where each agent is endowed with an additive valuation function ( v_i : 2^M \to \mathbb{R}{\geq 0} ). An allocation ( A = (A_1, \dots, A_n) ), where ( A_i ) is the bundle allocated to agent ( i ), is a partition of the set of ( m ) goods among ( n ) agents, i.e., ( \bigcup{i \in N} A_i = M ) and ( A_i \cap A_j = \emptyset ) for any two agents ( i \neq j ).
Two popular notions of fairness, envy-freeness (EF) and equitability (EQ), cannot be guaranteed all the time when items are indivisible. In the fair division literature, we can use some external money (subsidy) to circumvent it. Now, we would like to study whether an allocation can be EF and EQ simultaneously with the same amount of money. Here, let ( p = (p_1, \dots, p_n) ) denote the payment vector, where ( p_i \geq 0 ) for any ( i \in N ).
Definition 1 (EF)
An a