Budget-feasible Mechanisms for Representing Groups of Agents Proportionally

1 Introduction

Selecting a proper number of agents from each group to fairly represent the population of each group has received increased attention in recent years. For instance, selecting a committee consisting of members from different groups or hiring a set of workers of diverse attributes require making selection decisions on a given set of population (e.g., see [Bredereck et al., 2018; Cahuc and Postel-Vinay, 2002; Lang and Manove, 2011]). Fair representations also can be applied to the context of political poll or survey sampling in which the organizer wishes to obtain a diverse set of responses from various groups of populations [Bradburn et al., 2004; Jackson et al., 2020]. In fact, the consequences of inadequate group representation can result in inaccurate accounts/analysis (e.g., inaccurate poll predictions due to lacks of representative samples [Jackson et al., 2020]) and discrimination (e.g., group discrimination when hiring workers [Lang and Manove, 2011] ) in various domains.

In addition to the challenge of achieving fair representation, in many settings, there is an inherited private agent cost associated with selecting each agent (e.g., salary in job hiror not visible to the social planner. Ideally, the planner elicits cost information from the agents, determines the agents to select, and derives appropriate compensation or payment to the selected agents. However, the agents can be strategic and do not necessarily report their true cost. As a result, the social planner must take into account whom to select to represent groups when taking costs into consideration to ensure that the total payment to all agents does not exceed the available budget (e.g., the budget for hiring or conducting studies).

∗Corresponding author

The problem in hand can be cast naturally into a budgetfeasible mechanism design setting [Singer, 2010] where the social planner seeks to design a computationally efficient mechanism that elicits truthful cost information from the agents, selects representative agents to represent each group fairly, and ensures the total payment to the agents is no more than the budget. More specifically, can we design a budgetfeasible mechanism which fairly selects agents from different groups and guarantees desirable economic properties, while guaranteeing a bounded total payment from the planner?

Our Contribution. We consider the problem of designing budget-feasible mechanisms for representing groups of agents proportionally satisfying standard properties (i.e., individual rationality, budget feasibility, and truthfulness). We first adopt and formulate our objective to select agents that maximizes the minimum proportion ratio of the selected agents from each group, based on a well-studied notion of proportional representation (e.g., in electoral systems).

We consider two general models depending on whether each agent belongs to (1) one group or (2) multiple groups (in which the agents can be (2a) counted exactly once or (2b) multi-counted) and design proportional representation budget-feasible mechanisms for the models under our objective. The proposed mechanisms guarantee desirable theoretical properties including budget feasibility, individual rationality, truthfulness, and approximation guarantee.

In particular, for (1), we construct a novel greedy mechanism that considers all possible proportion ratios and appropriate payment schemes that select agents from each group satisfying the ratios and ensuring budget feasibility. The proposed mechanism achieves approximation performance that depends on the size of the largest and smallest groups. Moreover, we show the asymptotic matching lower bound that no budget-feasible proportion-representative mechanisms can achieve better performance asymptotically.

For the multiple group setting (2a) or (2b), we construct a novel mechanism that leverages the Max-Flow algorithm to test the proportional representation in the maximummatching under a given agent set, in which we can find the candidate agent set with the greatest proportional representation within the budget constraint. We then apply the minimum weight matching to identify the final selected agents from candidate agents, whereby the tested maximum proportional representation can be obtained and the corresponding payment determined. The designed mechanisms in this setting can also achieve approximation performance that depends on the size of groups.

Related Work. Since the seminal work of [Singer, 2010], many research efforts have been invested to design budgetfeasible mechanisms for various planner's valuation functions. [Chen et al., 2011] further develop improved mechanisms with better approximation ratio for the submodular value function, while [Amanatidis et al., 2017] consider symmetric submodular valuations, a prominent class of nonmonotone submodular functions. [Anari et al., 2014] design a constant-approximation budget-feasible mechanism for large markets where sellers' costs are far less than the buyer's budget and show that it is impossible to achieve bounded approximation ratio without large market assumption when sellers' items are divisible. [Singer and Mittal, 2013] focus on designing pricing mechanisms with the objective to maximize the number of tasks while guaranteeing budget feasibility. These mechanisms in existing literature do not perform well for our settings directly as they do not consider groups and ensure proportional representation. Several works take the group attributes into account and consider the diversity fairness when designing auction mechanisms [Ilvento et al., 2020; Kuo et al., 2020; Chawla and Jagadeesan, 2020]. However, they all ignore the planner's budget constraint and cannot guarantee the budget-feasibility. In this work, we want to design proportion-representative mechanisms while ensuring the budget constraint.

Rather than the incentive mechanism design setting addressed in this paper, we note that proportional representation has been studied from the optimization or algorithmic perspective in various areas such as voting and electoral systems. For example, [Procaccia et al., 2008] focus on analyzing the complexity of achieving proportional representation. [Buisseret and Prato, 2020] consider the voter preferences in proportional representation systems to understand the candidate selection and behavior. In addition, there are works considering diversity fairness in matching/allocation problems [Benabbou et al., 2020; Ahmadi et al., 2019].

2 Preliminaries

In this section, we define the proportion-representative selection settings and the desirable properties of the mechanisms.

2.1 The Model

We consider a scenario with a planner a and a set of n agents S = {s1, s2, ..., sn}. The agents have group attributes, specifying one or more groups the agent belongs to based on, e.g., genders, ages, ethnicities, regions and educational levels. The agents are divided into m groups G = {G1,G2, ...,Gm}. Each group Gj is a subset of S, i.e., ∅ ̸= Gj ⊆ S, and G1 ∪G2 ∪ · · · ∪Gm = S. Let G(si) denote the set of groups that agent si belongs to. The agents are to be selected by the planner for proportional representation.

The planner has a budget B ∈ R+ and each agent si has a private cost ci ∈ R+ (e.g., her required cost for time, privacy or fees) when selected to represent her group. We use C = {c1, c2, ..., cn} to denote agents' costs. Let C-i denote all costs except si's cost ci. Let nj be the total number of agents in group Gj, i.e., |Gj| = nj. Denote by nmin and nmax the minimum and maximum total number of agents among all the groups respectively, i.e., nmin = min1≤j≤mnj, nmax = max1≤j≤mnj. The agents may act strategically to maximize their own utilities by misreporting their costs. Each agent bids a cost bi that may be different from her real cost ci in order to maximize her utility (defined below). Let b = {b1, b2, ..., bn} denote agents' bid profile and b-i denote all bids except si's bid bi. We sometime use (bi, b-i) to represent b as to highlight si's bid.

2.2 The Mechanism

A mechanism M = (X , P) consists of an allocation rule X deciding the selected agents (who are chosen by the planner) and a payment scheme P deciding the payment to each agent. Denote by Sw the selected agent set. The allocation function X maps a set of bids b to the selected agent set Sw = X(b1, ..., bn) ⊆ S. We use xi ∈ {0, 1} to indicate whether agent si is chosen by the planner and pi to denote the payment to agent si. Let X = {x1, x2, ..., xn} and P = {p1, p2, ..., pn} denote the allocation and payment profile, respectively. Given a mechanism M, the utility of agent si is defined as the difference between the payment she receives and her true cost, i.e.,

We consider both the single group setting problem (SGP) where each agent only belongs to one group, and the multiple group setting problem (MGP) where agents may belong to multiple groups. Let Qj denote the number of selected agents in group Gj . Next, we define two main group setting models.

Single Group Setting Problem (SGP): Since each agent belongs to only one group, we have |G(si)| = 1. Then, the number of selected agents in group Gj is Qj = ∑si∈Gj xi.

Multiple Group Setting Problem (MGP): In this setting, an individual agent may belong to multiple groups, i.e., 1 ≤ |G(si)| ≤ m. Depending on whether each selected agent can be counted into all groups, we further consider two cases: Single Counting (MGP-SC) case where a selected agent is counted just once in one of the groups she belongs to and Multiple Counting (MGP-MC) case where a selected agent is counted in all groups she belongs to. For example, when forming a committee, the agent selected can only represent one of groups to which she belongs, or when she is selected, all the groups to which the agent belongs are happy.

(1) MGP-SC: Each selected agent is only included in the selected agents of the group she is matched to. Let xij = 1 indicate that agent si is matched to group Gj ∈ G(si), otherwise, xij = 0. We also have xi = ∑j:Gj∈G(si) xij ≤

1 where xij ∈ {0, 1}, ∀i ≤ n. Thus, we have Qj = ∑si∈Gj xij. (2) MGP-MC: Each selected agent is counted in all groups she belongs to. Thus, we have Qj = ∑si∈Gj xi.

To obtain a proportion-representative selection of agents, we define the selection ratio of group Gj as Qj nj , representing the ratio between the number of selected agents and the total number of agents in group Gj. As such, the mechanisms we design aim to consider the objective of maximizing the minimum selection ratio of groups, i.e., maxmin1≤j≤m Qj nj .

We consider budget-feasible proportion-representative mechanismM that has the following properties:

• Budget feasibility. The total payment of the planner does not exceed her budget B, i.e., ∑1≤i≤n pi ≤ B.
• Individual rationality. The utility of each agent si is non-negative, i.e., ui(ci, b-i,M) ≥ 0.
• Truthfulness. Each agent achieves the maximum utility by bidding her real cost, i.e., ui(ci, b-i,M) ≥ ui(bi, b-i, M).
• Computational efficiency. The output of the mechanism can be computed in polynomial time.
• Approximation. Let ALG(I) be the minimum selection ratio among groups of the proposed mechanismM on input instance I. We compare the output of the mechanism with the optimal achievable selection ratio when agents' costs are known in advance. We say that a mechanism is α-approximate if ALG(I) ≥ 1α OPT(I) for any instance I.

3 Mechanism for Single Group Settings

We introduce a Budget-feasible Proportion-representative mechanism for the Single Group setting (BPSG) below.

The main idea of Mechanism BPSG is as follows. We first generate a virtual ratio set which contains all possible selection ratios for each group when selecting different number of agents from this group. In order to maximize the minimum selection ratio among all groups within the budget constraint, we find all feasible virtual ratios which ensure that the selection ratio for each group does not fall below that ratio and the current total payment does not exceed the budget. Specifically, the payments for the selected agents depend on the the bids of agents after the last selected agent in each group. Among all these feasible virtual ratios, we find the maximum one as the final selection ratio for all groups.

The detail of Mechanism BPSG is shown in Algorithm 1. In order to distinguish the agents belonging to different groups, we use bji to denote the i-th agent's (agent sji ) bid in group Gj (We sort all agents in the same group Gj:1≤j≤m in the non-decreasing order of their bids, i.e., bj1 ≤ bj2 ≤ · · · ≤ bjnj ). Denote by pji the payment for agent sji . We then generate a virtual ratio set R which consists of possible selection ratios among all groups, i.e.,

We remove duplicate elements from R and sort all ratios in the non-decreasing order of their values where γl is the l-th element in R, i.e., γ1 < γ2 < · · · < γl < · · · < γ|R|. Denote by rf the final base selection ratio as the minimum selection ratio among groups in the final solution.

To find the final base selection ratio, we iteratively consider ratios in R starting with the first ratio γ1 1 . Suppose that we are now considering ratio γl. Let Ij(γl) denote the minimum number of agents which ensures that the selection ratio in group Gj is at least γl, and we thus have Ij(γl) = ⌈γl · nj⌉. Specifically, Mechanism BPSG will select up to nj - 1 agents from each group Gj (as to ensure truthfulness). Thus, when trying ratio γl, BPSG will terminate and output γl-1 as the final base selection ratio if there exists group Gj with Ij(γl) = nj (line 6). If we have Ij(γl) < nj, ∀j ≤ m, we compute the current payment for each of the first Ij(γl) agents in group Gj as the bid of agent sjIj(γl)+1 , i.e., pji = bjIj(γl)+1 , ∀i ≤ Ij(γl). Thus, when all groups have a selection ratio of at least γl, the total payment, denoted by Pγl , is

It is easy to see that Pγl is increasing with γl. If Pγl ≤ B, we continue to try the next ratio γl+1. Otherwise, the final base selection ratio is rf = γl-1.

Once deciding the final base selection ratio, we determine the final selected agents and corresponding payments. Let kj denote the number of selected agents in group Gj, i.e., kj = Ij(rf) = Qj. In each group Gj, the first kj agents are selected, i.e., sji ∈ Sw, ∀i ≤ kj, and we have kj < nj. Then we have

Running example: We now show a running example of Mechanism BPSG. Suppose there are nine agents who can be divided into two groups G1 and G2. Group G1 has four agents G1 = {s11 , s12 , s13 , s14 } with costs {1, 1.5, 3, 4} and group G2 has five agents G2 = {s21 , s22 , s23 , s24 , s25 } with costs {0.5, 1.5, 2, 3, 5}. Thus, we have n1 = 4 and n2 = 5. The virtual ratio set is R = {0, 0.2, 0.25, 0.4, 0.5, 0.6, 0.75, 0.8, 1}. The planner has budget B = 10. We now try virtual ratios by starting from the first non-zero ratio 0.2:

1. Try ratio 0.2: We have I1(0.2) = 1 and I2(0.2) = 1. Thus, we will select s11 from G1 and pay her 1.5, and select s21 from G2 and pay her 1.5. Then, the total payment is 3 < B = 10 and we will try next ratio 0.25.
2. Try ratio 0.25: We have I1(0.25) = 1 and I2(0.25) = 2. Thus, we will select s11 from G1 and pay her 1.5, and select s21 , s22 fromG2 and pay each of them 2. Then, the total payment is 5.5 < 10 and we will try next ratio 0.4.
3. Try ratio 0.4: We have I1(0.4) = 2 and I2(0.4) = 2. Thus, we will select s11 , s12 from G1 and pay each of them 3, and select s21 , s22 fromG2 and pay each of them 2. Then, the total payment is 10 = B and we will try next ratio 0.5.

(4) Try ratio 0.5: We have I1(0.5) = 2 and I2(0.5) = 3. Thus, we will select s11 , s12 from G1 and pay each of them 3,

1 Note that the first virtual ratio in R is 0. At such a ratio, we select no agents and pay each agent zero.

Algorithm 1: Mechanism BPSG(B, b, S, G)

Input: B, b, S, G. Output: P, Sw 1 P ← 0, Sw ← ∅; 2 Sort agents in Gj(∀1 ≤ j ≤m), in the non-decreasing order of their bids bj1 ≤ bj2 ≤ · · · ≤ bjnj and generate the virtual ratio set R with value sorted and indexed by γl's; 3 // Determine the final base selection ratio; 4 for 1 ≤ l ≤ |R| do 5 Compute Ij(γl) = ⌈γl · nj⌉ for any 1 ≤ j ≤m; 6 if Ij (γl) < nj , ∀j ≤ m then 7 Compute the payment Pγl according to (3); 8 if Pγl ≤ B then 9 l ← l + 1; 10 else 11 break; 12 end 13 else 14 break; 15 end 16 end 17 rf ← γl-1; 18 // Agent selection and payment scheme; 19 Add agent sji (∀j ≤ m) with i ≤ kj = Ij(rf ) into the selected agent set Sw; 20 Decide the payments to agents according to (4); 21 return P, Sw

and select s21 , s22 , s23 from G2 and pay each of them 3. Then, the total payment is 15 > B = 10.

Then, Mechanism BPSG terminates with the final base selection ratio 0.4. The selected agent set is Sw = {s11 , s12 , s21 , s22 } with payments p11 = 3, p12 = 3, p21 = 2, p22 = 2, while the payments for unselected agents are zero.

Next, we analyze the performance of Mechanism BPSG.

Theorem 1. Mechanism BPSG guarantees individual rationality, budget feasibility, and computational efficiency.

Proof. 1) Individual rationality: SinceMechanismBPSG is truthful (proved below), we have bji = cji where cji is the true cost of agent sji . For each selected agent sji , we have bji ≤ bjkj+1 where i ≤ kj in group Gj, and her payment is bjkj+1 which implies that her utility is bjkj+1 -cji = bjkj+1 -bji ≥ 0 which is non-negative. 2) Budget feasibility: After determining the selection ratio, it is easy to see that the total payment is ∑1≤j≤m kj · bjkj+1 ≤ B which is no greater than the budget B. 3) Computational efficiency: The running time of Mechanism BPSG is dominated by the sorting (line 2) and the loop in determining the final base selection ratio (line 4-15) as shown in Algorithm 1. Therefore, the total computational complexity is O(n2 ). This completes the proof.

We first provide a well-known Myerson's characterization for truthful mechanisms in the single parameter domain.

Theorem 2. (Monotone Theorem, [Myerson, 1981]) In the single parameter domains, a mechanism M = (X , P) guarantees sellers' truthfulness if and only if:

1. X is monotone: ∀si ∈ S, if bi ≤ ci, then si ∈ X(ci, C-i) implies si ∈ X(bi, C-i) for every C-i;

(2) winners are paid threshold payments: the payment to each winning bidder is the critical value inf{ci : i /∈ X (ci, C-i)}.

We prove the truthfulness of Mechanism BPSG by leveraging the theorem above. Suppose that the final base selection ratio is the l-th element in virtual set R, i.e., rf = γl.

Theorem 3. Mechanism BPSG guarantees truthfulness.

Proof (Sketch). Depending on the final base selection ratio, we consider the following two cases:

Case 1: There exists no group Gj in which when trying the next virtual ratio γl+1, we select all its agents, i.e., Ij(γl+1) < nj, ∀1 ≤ j ≤ m. 1) We first show that if the selected agent sji in group Gj, i.e., i ≤ kj, reports a lower cost bji′ < bji ≤ bjkj+1 , she will still be selected. Thus, BPSG is monotone. 2) If agent sji with i ≤ kj reports a cost higher than her payment bji′ > bjkj+1 , we prove that sji will not be selected with zero utility. Thus, the selected agents are paid threshold payments.

Case 2: There exists a group Gj in which when trying the next virtual ratio γl+1, we select all its agents, i.e., ∃1 ≤ j ≤ m, Ij(γl+1) = nj . We similarly prove that Mechanism BPSG is monotonic and the selected agents are paid threshold payments.

Therefore, Mechanism BPSG guarantees truthfulness.

Next, we introduce a useful property of Mechanism BPSG. Let rj(γl) denote the selection ratio of group Gj after selecting kj agents, i.e., rj(γl) = kj nj . We use rmax and rmin to denote the maximum and minimum selection ratios among groups when the final base selection ratio is γl, i.e., rmax = max1≤j≤m{rj(γl)} and rmin = min1≤j≤m{rj(γl)}. Specifically, we have rmin = γl = rf since there must exist at least one group Gj whose selection ratio is rj(γl) = γl due to the generation of R in (2). Denote by α the ratio between nmax and nmin, i.e., α = nmax nmin .

Lemma 1. Mechanism BPSG has the following two properties: (1) γh+1 - γh ≤ 1 nmax , ∀1 ≤ h ≤ |R| - 1; (2) rmax - rmin < 1 nmin .

Given the above lemma, we consider the approximation guarantee of BPSG. Let ALG and OP T denote the minimum selection ratio of Mechanism BPSG and the optimal solution, respectively. Our analysis considers two separate cases. In the first case when BPSG is able to select at least one agent from each group, we show that BPSG obtains an approximation ratio that depends on the ratio between the maximum and minimum number of agents among groups. In fact, the ratio is asymptomatically tight as we showed later. If Mechanism BPSG cannot select at least one agent from each group, we show that no budget-feasible proportion-representative mechanisms can output a better solution than BPSG.

Theorem 4. (1) Mechanism BPSG achieves (3 + α)- approximation ratio if BPSG selects at least one agent from each group (i.e., ALG ≥ 1 nmax ) where α = nmax nmin .

(2) No budget-feasible proportion-representative mechanism M can achieve ALGM ≥ θ for any θ > 0 where ALGM is the solution of M if Mechanism BPSG cannot select at least one agent from each group, i.e., ALG = 0.

Proof (Sketch). Recall that the final base selection ratio is γl, i.e., ALG = γl. We have nj ≥ 2, ∀j ≤ m since BFSG can select at least one agent from each group. Depending on the conditions at the termination of BPSG, we consider two cases: i) There exists group Gj in which we select all agents, i.e., ∃j ≤ m, Ij(γl+1) = nj, when trying the next virtual ratio γl+1. We prove that γl · nj = nj - 1 and OP T ALG ≤ 1/(1 - 1 nj ) ≤ 2. ii) Next, we focus on the case that not all agents are selected from any group Gj when trying γl+1, i.e., Ij(γl+1) < nj, ∀j ≤ m. Let G′ denote the set of all groups that can choose exactly rf · nj = kj agents making the selection ratio in group Gj equal to rf , ∀Gj ∈ G′ . Depending on whether the next ratio γl+1 is generated from a group in G′ or not, we consider the following two sub-cases:

Sub-case 1: The virtual ratio γl+1 is generated from the group Gj /∈ G′ . We divide agents into two parts: ˜ S = {sji |i ≤ kj, ∀Gj /∈ G′ } ∪ {sji |i ≤ kj + 1, ∀Gj ∈ G′ } and S \ ˜ S for further analysis.

For set ˜ S: The optimal solution can select all agents in ˜ S with cost zero in the best case and spend the budget on the remaining agents in S \ ˜ S. We show that after OPT chooses all agents in ˜ S, the maximum selection ratio among all groups is rmin + 1 nmin , and the minimum selection ratio is γl+1.

For set S \ ˜ S: We show that the optimal solution can select kj agents from the remaining agents after skj from group Gj for any Gj /∈ G′ , and kj + 1 agents from the group Gj ∈ G′ with budget B. Thus, we prove that the minimum selection ratio among groups by selecting these numbers of agents is γl+1 and the maximum selection ratio is rmin + 1 nmin .

Thus, by combining the set ˜ S and S \ ˜ S, we have

due to Lemma 1.

Sub-case 2: The virtual ratio γl+1 is generated from the group Gj ∈ G′ . We can similarly prove that OPT ≤ 2rf + 1 nmax + 1 nmin .

Therefore, we have OPT ≤ 2ALG + 1 nmin + 1 nmax . Specifically, if ALG ≥ 1 nmax , we have OPT ALG ≤ 3 + α which means BPSG achieves (3 + α)-approximation ratio.

Next, we provide an asymptotic tight lower bound for all of budget-feasible proportion-representative mechanisms.

Theorem 5. No budget-feasible proportion-representative mechanism obtains an approximation ratio better than Ω(α).

In particular, it is worth stating that this lower bound also applies to the multiple group setting.

4 Mechanisms for Multiple Group Settings

In this section, we consider the multiple group setting where each agent si might belong to multiple groups, i.e., 1 ≤

Algorithm 2: Mechanism BPMG-S(B, b, S, G)

Input: B, b, S, G. Output: P, Sw 1 P ← 0, Sw ← ∅; 2 Sort all agents in the non-decreasing order of their bids bi, i.e., b1 ≤ b2 ≤ · · · ≤ bn; 3 // Determine the candidate agent set; 4 for 1 ≤ i ≤ n do 5 Compute r(si) according to (6); 6 F(si) ← ∑1≤j≤m⌈r(si) · nj⌉; 7 if bi · F(si) ≤ B then 8 i ← i + 1; 9 else 10 break; 11 end 12 end 13 k ← i -1; 14 // Agent selection and payment scheme; 15 X, Sw ←AgentSelect(Sk); 16 The payment for si ∈ Sw is pi =min{ B F (sk) , bk+1};

|G(si)| ≤ m. We distinguish two sub-cases according to whether the contribution of the agent is counted only once or not: single-counting case and multiple-counting case. In the single counting case, the selection ratio in one of the groups G(si), say Gj, would increase by 1 nj where nj = |Gj| if si is selected and contributes to Gj ; while in the multiple counting case, the selection ratios of all groups in G(si) would increase by 1 nj for any Gj ∈ G(si), once si is selected.

4.1 Single Counting Case

In this section, we introduce a Budget-feasible Proportionrepresentative mechanism for the Multiple Group setting in Single counting case, called BPMG-S.

Intuitively, we measure the supply of agents for a given fixed payment. Given all agents who have bids lower than this payment, we can compute the solution that maximizes the minimum selection ratio among groups. This minimum ratio will increase and reflect the supply as the number of agents increases. We then try to find the payment which can maximize such a ratio and ensure the budget feasibility, simultaneously.

In detail, we first sort all the agents according to their nondecreasing order of bids b1 ≤ b2 ≤ b3 ≤ · · · ≤ bn. Let xij = 1 indicate that agent si is matched to group Gj, otherwise, xij = 0. Agent si can only be matched to at most one group, i.e., ∑j≤m xij ≤ 1, ∀i ≤ n. Denote by S(sh) = {si|i ≤ h} the set containing agents before agent bh+1.

Before introducing our mechanism, we first introduce an important component, an integer programming formulation to compute a matching result under a given agent set S(sh), that maximizes the minimum selection ratio among groups while ignoring the costs and budget constraint, denoted by ILP(sh) as follows,

where these three conditions indicate that agents in S(sh) can only be matched to at most one of the groups they belong to. Notice that the optimal solution in (6) can be computed in polynomial time by constructing Max-Flow networks as follows. In detail, given agent set S(sh), all possible selection ratios for group Gj are in ∪y≤|S(sh)∩Gj|{ y nj }. Thus, the optimal selection ratio in the solution of (6) must be one of the ratios in R = ∪y≤|S(sh)∩Gj|,j≤m{ y nj }. Particularly, we remove duplicate elements in R. We say a ratio rs ∈ R is feasible if we can find a matching result ensuring that the selection ratio in each group is at least rs and satisfying all conditions in (6). To find the optimal solution, we take rs ∈ R as an input and construct a flow network based on such a ratio. As shown in Fig. 1, we use blue, red and black circles to represent source node s/terminal node t, groups and agents, respectively. Specifically, there exists a directed edge from source s to each group Gj, an edge from each Gj to si if si ∈ Gj, and from each agent si to terminal node t. Each edge from s to Gj is assigned with a capacity ⌈rs · nj⌉, while the capacity of each directed edge from Gj to sj and from si to t is 1. If the maximum flow on this network equals ∑j≤m⌈rs · nj⌉, then rs is a feasible ratio. We can find the optimal solution in (6) by testing every possible input of rs and validating its feasibility, i.e., the maximum one among all feasible ratios is the desired optimal solution.

Let X(sh) denote the solution of ILP(sh), and r(sh) is the minimum selection ratio among groups under X(sh). Denote by F(sh) the total number of agents under ratio r(sh), i.e.,

It is obvious that F(sh) ≤ |S(sh)|.

Candidate agent selection. Now we are ready to select agents. We first decide on a set of candidate agents, from which we select agents. We iteratively test each agent's bid

Algorithm 3: Function AgentSelect( S, G, k)

Input: S, G, k. Output: X, Sw

• 1 X ← 0, Sw ← ∅;
• 2 Assign each agent si a weight wi = 2zi where zi ∈ N+ is an arbitrary integer such that no two agents have the same weight, i.e., zi ̸= zi′ for any i ̸= i′ ;
• 3 Compute the final allocation Xw(sk) according to (8);
• 4 X ←Xw(sk);
• 5 Add agent si(∀1 ≤ i ≤ n) into Sw if ∑j≤m xij = 1;

starting from the first agent's bid b1. Suppose that we are now trying agent si and calculate the value of F(si) by equation (7). If bi ·F(si) ≤ B, we consider the next agent si+1, otherwise, we select agents from the previous i-1 agents S(si-1). Assume that sk is the last agent who satisfies bk · F(sk) ≤ B which implies bk+1 · F(sk+1) > B. After determining the value k, we define agent set S(sk) = {si : i ≤ k} as the candidate agent set, where |S(sk)| ≥ F(sk) follows.

Agent selection and payment scheme. Now we select agents from the candidate agent set S(sk). First, we assign each agent si a weight wi = 2zi where zi ∈ N+ is an arbitrary integer such that no two agents have the same weight, i.e., zi ̸= zi′ for any i ̸= i′ . Then, we use the function AgentSelect(S,G, k) to select F(sk) agents from S(sk). The detail of AgentSelect(S, G, k) is shown in Algorithm 3. We try to find a minimum weight matching between agents and groups that can minimize the total weight of matched agents satisfying that each group Gj is matched ⌈r(sk) · nj⌉ agents from set S(sk) as follows, denoted by ILPw(sk)2 ,

Since we assign agents exponential weights, there is a unique matching result in (8). Let Xw(sk) denote the solution of ILPw(sk). If agent si:i≤k is matched to one of the groups, i.e., ∑1≤j≤m xij = 1, then she is selected, i.e., si ∈ Sw. The payment for each selected agent is pi = min{ B F (sk) , bk+1} while the payments for unselected agents are zero 3 .

Next we analyze the performance of Mechanism BPMG-S.

Theorem 6. Mechanism BPMG-S guarantees individual rationality, budget feasibility and computational efficiency.

We prove the truthfulness of Mechanism BPMG-S by showing that it satisfies Theorem 2.

2 This problem can be similarly solved in polynomial time by constructing Max-Flow Min-Cost networks.

3 The payment for each selected agent is B F(sk) if k = n.

Theorem 7. Mechanism BPMG-S guarantees truthfulness.

Let OPTs and ALGs denote the optimal solution and the solution of BPMG-S, respectively. We show that BPFGS generally achieves an approximation ratio with respect to the size of groups when at least one agent is selected in each group, while there is a small gap between BPFG-S and any other budget-feasible proportion-representative mechanism when BPFG-S cannot select at least one agent from each group.

Theorem 8. (1) Mechanism BPMG-S achieves (mα(α + 2) + 1)-approximation ratio if BPMG-S can select at least one agent from each group (i.e., ALGs ≥ 1 nmax ) where α = nmax nmin .

(2) No budget-feasible proportion-representative mechanismM′ can obtain ALGM′ ≥ θ for any θ > 1 nmin where ALGM′ is the solution ofM′ if MechanismBPMG-S cannot select at least one agent from each group, i.e., ALGs = 0.

4.2 Multiple Counting Case

In this section, we consider the multiple counting case where the selection ratio of each group Gj in G(si) can increase by 1 nj for Gj ∈ G(si) when si is selected. We propose a modified version of Mechanism BPMG-S, called BPMG-M.

In general, Mechanism BPMG-M applies the methodological framework in Mechanism BPMG-S. We first sort all the agents according to their non-decreasing order of bids b1 ≤ b2 ≤ b3 ≤ · · · ≤ bn. We then use an integer programming formulation to compute a result given an agent set S(sh) = {si : i ≤ h}, that maximizes the minimum selection ratio among groups, denoted by ILP m(sh) as follows,

where the two conditions mean that we only consider agents in S(sh). Similar to that of (6), we can solve this problem by using the Max-Flow method. Let Xm(sh) denote the solution of ILP m(sh), and rm(sh) denote the minimum selection ratios under Xm(sh). We denote Fm(sh) as the total counted number of selected agents among groups by ratio rm(sh), i.e., Fm(sh) = ∑j≤m⌈rm(sh) · nj⌉.

Candidate agent selection. We also decide on a set of candidate agents by iteratively testing each agent's bid starting from the first agent's bid b1. That is, we find the last agent sk who ensures bk · Fm(sk) ≤ B and bk+1 · Fm(sk+1) > B. Then, the agent set S(sk) is the candidate agent set.

Agent selection and payment scheme. Similar to the agent selection function AgentSelect(Sk,G,B), we assign each agent si a weight wi = 2zi where zi ∈ N+ is an arbitrary integer such that no two agents have the same weight, i.e., zi ̸= zi′ for any i ̸= i′ . We try to select agents with the minimum total weight satisfying that each group Gj is selected at least ⌈rm(sk) · nj⌉ agents from set S(sk) as follows, denoted by ILP m

Let Xm w (sk) denote the solution of ILP m w (sk). If xi = 1, agent si is selected and her payment is pi = min{ B Fm(sk) , bk+1}, otherwise, pi = 0.

Theorem 9. Mechanism BPMG-M guarantees individual rationality, budget feasibility, computational efficiency and truthfulness.

Let ALGm denote the solution of Mechanism BPMG-M.

Theorem 10. (1) Mechanism BPMG-M achieves (mα(α + 2) + 1)-approximation ratio if BPMG-M can obtain at least one agent from each group (i.e., ALGm ≥ 1 nmax ) where α = nmax nmin .

(2) No budget-feasible proportion-representative mechanism M′′ can obtain ALGM′′ ≥ θ for any θ > 2m nmin where ALGM′′ is the solution of M′′ if Mechanism BPMGM cannot select at least one agent from each group, i.e., ALGm = 0.

5 Conclusion

We consider the proportion representation budget-feasible mechanism design problem where agents may have diverse group attributes. We focus on designing budget-feasible mechanisms that can select appropriate proportions of agents from various groups satisfying individual rationality, budget feasibility, and truthfulness under several settings. For the single group setting, we propose Mechanism BPSG, which iteratively tests each virtual ratio generated by the distribution of agents across groups and finds the maximum one as the base selection ratio for all groups. For the multiple group setting, we first consider the single counting case by proposing Mechanism BPMG-S, which leverages Max-Flow solution to measure the supply of agents under a fixed payment and finds the payment which can maximize the minimum selection ratio among groups. We then extend BPMG-S to the multiple counting case.

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China under grant No. 2019YFB2102200, Natural Science Foundation of China under Grant No. 61902062, 61672154, 61972086, the Project 11771365 supported by NSFC, the Postgraduate Research & Practice Innovation Program of Jiangsu Province of China (KYCX19 0089), and partially sponsored by Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education.