On Revenue-Maximizing Walrasian Equilibria for Size-Interchangeable Bidders

Abstract

We study a market setting in which bidders are single-valued but size-interchangeable, and there exist multiple copies of heterogeneous goods. Our contributions are as follows: (1) providing polynomial-time algorithms for finding a restricted envy-free equilibrium with reserve prices (EFEr); (2) posing the problem of finding a revenue-maximizing EFEr, and running experiments to show that our algorithms perform well on the metrics of revenue, efficiency, and time, without incurring too many violations of the stronger Walrasian equilibrium with reserve (envy-free plus market clearance) conditions.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In a centralized combinatorial matching market (CCMM), a market maker offers a set of $n$ heterogeneous goods to $m$ consumers (or bidders), the latter of which are interested in acquiring certain combinations (or bundles) of goods. In general, there are multiple copies of each good $i$, but the total supply $N_i$ of each good is finite. Bidder $j$’s preferences are captured by a valuation function $v_j(\cdot )$ that describes how bidder $j$ values each bundle.

In general, a bidder’s valuation function can be an arbitrary function of the set of all bundles. We study a case where bidders are only interested in specific varieties of goods, and we model these interests as edges in a graph connecting bidders only to their goods of interest. Furthermore, in our model, bidder’s valuations are single-valued, and depend only on the bundle’s size, assuming the bundle is a match for the bidder. The value then is either a positive value $R_j$, if the size of the bundle is at least some threshold $I_j$, and 0 otherwise.

Our model is motivated by the Trading Agent Competition Ad Exchange game (TAC AdX) [15], which in turn models online ad exchanges in which agents face the challenge of bidding for display-ad impressions needed to fulfill advertisement contracts, after which they earn the amount the advertiser budgeted. Other settings captured by this model include the problem of how to allocate specialized workers to firms, and how to compensate the workers, where each firm requires a certain number of workers to produce an output (a new technology, for instance) that yields a certain revenue.

One well-studied special case of our model is that of (single-valued) single-minded consumers [11]. There, bidders are only interested in one particular bundle. Hence their valuation function can be understood as assigning value $R_j$ to that bundle or any superset thereof, and 0 to all other bundles. We call our valuations (single-valued) size-interchangeable, because bidders can be satisfied (i.e., achieve value $R_j$) by any bundle of size $I_j$ that consists of their desired goods. Like single-minded valuations, our interchangeable valuations model complements, since a bidder is not satisfied unless it receives a bundle of sufficient size. Furthermore, our interchangeable valuations model (perfect) substitutes, since any bundle of sufficient size that consists of suitable goods will do.

In this paper, we assume valuations are known to the market maker. Thus, our problem is one of equilibrium computation rather than traditional mechanism design (where values are private). A market outcome is an allocation-pricing pair $(\varvec{X}, {\varvec{p}})$, where $\varvec{X}$ describes the assignment of goods to bidders, and ${\varvec{p}}$ ascribes prices to goods. While $\varvec{X}$ is a matrix, we assume ${\varvec{p}}$ is a vector, which precludes any form of price discrimination (all copies of the same good must have the same price). Furthermore, we assume item pricing, not bundle pricing, so that the price of a bundle is the sum of the prices of all the goods (items) in the bundle. Both of these assumptions—no price discrimination and item pricing—are most natural.

Example 1

(CCMM and possible outcomes). Consider the CCMM in Figure (A). There are two goods, G and F, with 2 copies of good G and 3 copies of good F, and two bidders, Y and Z. Bidder Y wants two copies of good G (as indicated by the edge from G to Y) and values this bundle at 10, and bidder Z ascribes the value 5 to any bundle of size 2 comprised of any combination of Gs and Fs (also indicated by edges). Possible outcomes of this markets are depicted in Figures (B) and (C).

Outcome (B) allocates 2 copies of good G to bidder Y at a price of $5 per copy, and 2 copies of good F to bidder Z at a price of $1 per copy. This outcome results in the optimal social welfare ($15) and a revenue of $12.

Outcome (C) allocates to bidder Z only, 1 copy of good G at a price of $1, and 1 copy of good F at a price of $2. This outcome results in a social welfare of $5 and a revenue of $3.

In an important related setting, bidders have unit-demand valuations, meaning they are interested in at most one good, but may have different valuations for different goods. This is a well-studied setting [1, 2, 6, 7], with important theoretical guarantees. In particular, there always exists a Walrasian equilibrium (WE) outcome [5] in which bidders are envy-free, meaning they all receive one of their favorite bundles at the set prices, and the market clears, meaning unallocated goods are priced at zero. It follows from this second condition, by the first welfare theorem of economics, that any allocation that is part of any WE outcome maximizes social welfare. In addition, it is possible to find a revenue-maximizing WE among all WE outcomes in polynomial-time (assuming unit demand) [6].

Building on Myerson’s [10] intuition, Guruswami et al. [7] generalized the problem of searching for a revenue-maximizing WE to that of searching for a revenue-maximizing Walrasian equilibrium with reserve prices (WEr), where bidders are envy-free and the market clears up to the reserve price: i.e., unallocated goods are priced at the reserve. For bidders with unit-demand valuations a WE always exists [5]; likewise, a WEr always exists. In addition, for a fixed reserve price, we can find the revenue-maximizing WEr in polynomial-time (using the same approach as in [6]). With this more general solution concept in mind, Guruswami et al. pose the problem of finding a revenue-maximizing WEr, for which they propose a polynomial-time approximation algorithm that picks a particular set of candidate reserve prices, generates a revenue-maximizing WEr for each, and then returns the revenue-maximizing WEr among those considered.

For our model—single-valued, size-interchangeable bidders—we remind the reader that WE do not exist in general; in fact, they are not guaranteed to exist even for single-minded bidders. By relaxing the market clearance condition, we arrive at more general solution concept—an Envy-Free Equilibirum (EFE)—which insists only that bidders are envy-free, and which always exists. However, the first welfare theorem does not hold for EFE, so maximal social welfare is not guaranteed by this solution concept.

Departing from the social welfare concern, we instead tackle the competing problem of maximizing seller revenue. Since finding revenue-maximizing WEr is APX-hard in a CCMM assuming single-minded bidders [7], we propose a polynomial time heuristic for approximately solving for revenue-maximizing EFEr (an EFE in which unallocated goods are priced at a reserve), where we relax the envy-free condition to a restricted envy-free condition, which we are able to express as linear constraints. Building on the ideas of Guruswami et al., we then search over a space of carefully chosen reserve prices to find an approximately revenue-maximizing EFEr. In particular, whereas Guruswami et al. used this approach to find an approximately revenue-maximizing WEr for unit-demand bidders, we apply this same idea to the case of size-interchangeable (and hence, single-minded) bidders.

In sum, our contributions are: (1) providing polynomial-time algorithms for finding a restricted envy-free equilibrium with reserve prices (EFEr); (2) posing the problem of finding a revenue-maximizing EFEr, and running experiments to show that our algorithms perform well on the metrics of revenue, efficiency, and time, without incurring too many violations of the WEr (envy-free plus market clearance) conditions.

2 Model and Solution Concepts

We define a centralized combinatorial matching market (CCMM) to be an augmented bipartite graph $(U, C, E, {\varvec{N}},{\varvec{I}})$ with a set of $n$ types of goods $U$, a set of $m$ bidders $C$, a set of edges $E$ from bidders to goods indicating which goods are of interest to which bidders, a supply vector ${\varvec{N}} = (N_1,\ldots ,N_n)$, and a demand vector ${\varvec{I}} = (I_1,\ldots ,I_m)$. That is, there are $N_i>0$ copies of good $i\in U$, and $I_j>0$ total goods are demanded by bidder $j\in C$. Note, however, that bidder $j$ only demands copies of goods it is connected to via an edge.

In other words, in a CCMM, bidders are interested in acquiring bundles of goods of at least some fixed size. Note that this is a more general case of the well-studied problem of single-minded consumers [11] where bidders are interested only in one particular bundle of goods. For this reason, we call our valuation function size-interchangeable. Formally:

Definition 1

(Single-valued, Size-interchangeable valuations). Given a CCMM $M = (U, C, E, {\varvec{N}},{\varvec{I}})$, a bidder $j$ is single-valued, size-interchangeable, if it demands $I_j> 0$ goods among those to which it is connected, and values all such bundles by the function: $v_j(X_j) = R_j> 0$, if $\sum _{i\mid (i, j) \in E} x_{ij} \ge I_j$, and 0 otherwise. We call $R_j$ the reward attained by $j$ in case its demand $I_j$ is fulfilled.

Definition 2

(Market). We call a market $M$ a pair consisting of a CCMM $(U, C, E, {\varvec{N}},{\varvec{I}})$ and a reward vector ${\varvec{R}} = (R_1,\ldots ,R_m)$.

Given a market $M$, an allocation $A$ is a labeling $x(i, j) \in \mathbb {Z}_{\ge 0}$ of $E$ that represents the number of copies of good $i$ allocated to bidder $j$. Such an allocation can be represented by a matrix $\varvec{X}\in \mathbb {Z}_{\ge 0}^n\times \mathbb {Z}_{\ge 0}^m$ where entry $x_{ij} = x(i, j)$. The $j$th column of an allocation matrix is the bundle of goods assigned to bidder $j$, which we denote by $X_j \in B({\varvec{N}})$, where $B({\varvec{N}}) = \prod _i \{ 0, 1, \ldots , N_i \}$.

A market outcome is an allocation-pricing pair $(\varvec{X},{\varvec{p}})$, assigning goods to bidders and per-good prices $p_i\in \mathbb {R}_+$. Given such an outcome, the cost of bundle $X_j$ to bidder $j$ is given by $P_{j} (X_j) = \sum _ix_{ij} p_{i}$.

An allocation is feasible if, for all $i$, the total number of goods assigned across bidders is no more than $i$’s supply: i.e., for all $i: \sum _{j=1}^mx_{ij} \le N_{i}$. We use $F\equiv F(M)$ to denote the set of all feasible allocations. In a feasible outcome the allocation is feasible.

The utility of bidder $j$ is defined as follows: $u_j(\varvec{X},{\varvec{p}}) = v_j(X_j) - P_{j} (X_j)$. A standard assumption is that all bidders are utility maximizers, and thus a bidder prefers outcomes with higher utilities.

A fundamental market outcome studied in the literature is that of Walrasian Equilibrium (WE) [14], which we define using our notation as follows.

Definition 3

(Walrasian Equilibrium). A feasible outcome $(\varvec{X},{\varvec{p}})$ is a Walrasian Equilibrium (WE) if the following two conditions hold:

• 1. Envy-freeness (EF): There is no bundle $X_j'$ that any bidder $j$ prefers to its assigned bundle $X_j$, i.e., for all $j$, $X_j \in \arg \max \limits _{X_j' \in B({\varvec{N}})} \{ v_j(X_j') - P_j(X_j') \}$.

• 2. Market clearance (MC): Every unallocated good is priced at zero.

The EF condition is a fairness condition; it ensures that the outcome maximizes the utility of every bidder. Note that each bidder is individually rational i.e., $u_j(\varvec{X},{\varvec{p}}) \ge 0$, since the null allocation is always a feasible allocation. The MC condition, together with EF, implies, by the first welfare theorem of economics, that any allocation that is part of a WE is also welfare-maximizing. However, a WE need not exist in the markets studied in this paper.

Example 2

(Non-existence of WE). Consider the market in Figure (A) with one good and two single-minded bidders. Good $u_1$ is supplied in $N_1 = 2$ copies, bidder $c_1$ demands $I_1$ = 1 good, and bidder $c_2$ demands $I_2 = 2$ goods. Rewards are $R_1 = 5$ and $R_2 = 7$.

There are a total of 6 feasible allocations in this market and none of them are part of a Walrasian Equilibrium. Two such allocations are depicted in (B) and (C). In (B), there is no price $p_1$ for $u_1$ at which both bidders would be envy-free. In (C), we must have that $p_1\ge 3.5$, or otherwise $c_2$ would have preferred 2 copies from $u_1$. But then the market does not clear since there is an unsold copy of $u_1$ with price greater than 0.

To address this existence problem, we drop the market clearance condition.

Definition 4

(Envy-Free Equilibrium). A feasible outcome $(\varvec{X},{\varvec{p}})$ is an Envy-Free Equilibrium (EFE) if envy-freeness holds.

Note that, in outcome (C) of Example 2, at any price $p_1$ for $u_1$ such that $3.5\le p_1\le 5$, both bidders $c_1$ and $c_2$ are envy-free. It follows that this outcome is an EFE.

Unlike in the unit-demand case, where, by the first welfare theorem, a WE implies a welfare-maximizing allocation [12], an EFE (even for unit-demand bidders) does not guarantee a welfare-maximizing allocation. An outcome with a null allocation and prices high enough such that no bidder can afford even a single good is an EFE outcome with 0 welfare. But even for non-null allocations, an EFE outcome can yield low welfare.

Example 3

(An EFE does not imply an efficient allocation). Consider a market $M$ with a single good that is supplied in $N_1 = m-1$ copies and $m$ bidders, where all bidders demand 1 good (i.e., $I_j= 1$, for all $j$). Rewards are defined as follow: for $1\le j<m: R_j= 1$ and $R_m= 2$.

Consider outcome $(\varvec{X}, {\varvec{p}})$, where bidder $m$ is allocated one good at any price $p_1$ such that $1<p_1\le 2$, and no other bidder is allocated any good. This outcome is an EFE since all bidders are envy-free. However, the welfare of this outcome is 2 for any $m>1$, since we only satisfy bidder $m$.

A welfare maximizing allocation for this market is one that satisfies bidder $m$ as well as many other bidders as possible, obtaining welfare $2 + \sum _{j=1}^{m-2}R_j= 2 + m-2 = m$. Therefore, the welfare of the EFE $(\varvec{X}, {\varvec{p}})$, relative to the optimal welfare, approaches zero, as $m$ approaches $\infty$.

Although at first glance it may seem disappointing the first welfare theorem does not hold for EFE, it is not a show stopper. Even in the unit-demand case, where the first welfare theorem does hold, there exists the competing, and incompatible goal, of maximizing seller revenue.

In a unit-demand CCMM, if we let $m(<r) = \{j\mid R_{j} < r\}$, then $|m(<r)|$ is the number of bidders with reward less than the reserve $r$. Assuming there exists an allocation that satisfies all bidders, by setting a reserve price $r$ we lose at least $R_{\min }|m(<r)|$ welfare, where $R_{\min } = \min _j\{R_j\}$, while we are guaranteed revenue of at least $r|m(<r)^c|$. (Here $A^c$ denotes the complement of set A.)

The following example further illustrate the tradeoff between welfare and revenue, in the case of single-minded bidders.

Example 4

(Welfare-Revenue Tradeoff). Consider the market in Figure (A) and the two different outcomes in Figures (B) and (C)

Outcome (B)’s allocation is welfare maximizing. To support an EFE we must have $0 \le p_{b2} \le 1$; otherwise $c_2$ would not be envy-free. Moreover, $p_{b1} \le p_{b2}$; otherwise $c_1$ would have preferred a copy of $u_2$. So prices can only be as high as $p_{b1} = p_{b2} = 1$, yielding revenue of 2. Outcome (C)’s allocation is not welfare maximizing. However, in this case, an EFE can be supported by higher prices than those in (B). In particular, $p_{c2} \ge 1$; otherwise $c_2$ would have preferred a copy of $u_2$. Again $p_{c1} \le p_{c2}$ for the same reasons as in (B). Prices could be as high as $p_{c1} = p_{c2} = 100$, yielding revenue of 100.

Example 4 motivates the introduction of reserve prices as a way to increase revenue while maintaining envy-freeness among market participants. In the previous example, we could set a reserve price of $2 for $u_2$. Doing so would increase revenue from a maximum possible of $2 (with no reserve price) to $100. However, by setting reserve prices some bidders are effectively thrown out of the market, so welfare might not be maximized, because any value these bidders bring to the market is lost.

Motivated by this discussion, we generalize the definition of WE so that unallocated goods are priced at some, possibly non-zero, reserve price $r\in \mathbb {R}_+$.

Definition 5

(Walrasian Equilibrium with reserve r). A feasible outcome (X, p) is a Walrasian Equilibrium with reserve r (WEr) if it is a WE with prices at least r, including unallocated goods, which must be priced at exactly $r$.

Analogously, we augment the definition EFE to an EFE with reserve price $r$.

Definition 6

(Envy-Free Equilibirum with reserve r). A feasible outcome $(\varvec{X},{\varvec{p}})$ is an Envy-Free Equilibirum with reserve r (EFEr) if it is an EFE with prices at least r.

3 Computation of Envy-Free Equilibria

Chen et al. [8] showed that deciding the existence of WE in a CCMM assuming single-minded bidders is NP-hard. Consequently, we propose a natural restriction on the envy-freeness condition, which lends itself to a polynomial-time computation. With it, we can find a restricted WE (outcomes that satisfy restricted EF and MC) in polynomial time in single-minded CCMMs. Furthermore, in size-interchangeable CCMMs, we can find a restricted EFE in polynomial time.

Before presenting our algorithm, we formally define restricted envy-free prices. Let $|X_j|= \sum _{i=1}^nx_{ij}$ be the size of the bundle assigned to bidder $j$.

Definition 7

(Restricted Envy-Free). A price vector p is called restricted envyfree with respect to a feasible allocation X if, for all J such that :

$$ X_j \in {\text {arg}} \max _{X_j' \in B({\varvec{N}}_{|X_j|})} \{ v_j(X_j') - P_j(X_j') \} $$

where , i.e., the set of all feasible bundles of size equal to .

This definition is “restricted” because it assumes an allocation, and then is only concerned with bidders that are allocated (non-zero) bundles in that allocation. Any envy felt by any other bidders is simply ignored.

Another seeming restriction is that even for a bidder $j$ with $|X_j|> 0$, it does not require envy-freeness with respect to all bundles $X_j' \in B({\varvec{N}})$, but only with respect to bundles of the same size as $X_j$ (i.e., $X_j' \in B({\varvec{N}}_{|X_j|})$), and the empty bundle $\varvec{0}$. This definition might seem overly restrictive, but as we are focused on bidders with single-valued, size-interchangeable valuations, we are likewise concerned with all-or-none allocations, which either allocate to a bidder in full—meaning a bundle of size $I_j$—or does not allocate at all. Hence, for our purposes the size restriction is not restrictive at all.

Finally, note that restricted envy-free prices always exist. Given an allocation, we can simply set prices equal to zero, and the condition will be satisfied. No one who is allocated would have any envy at zero prices; and the restricted envy-free condition ignores bidders that are unallocated.

Theorem 1

Given a market M and a feasible allocation X, the following conditions are necessary and sufficient for p to be restricted envy-free.

• Individual Rationality: $\forall j\in C: P_j(X_j) \le v_j(X_j)$.

• Compact Condition: $\forall i\in U,j\in C: { If }\, x_{ij}>0\,{then}$

                                          $\forall k\in U: {If}\, (k,j)\in E\,{and}\,x_{kj} <N_{k}\,{then}\,p_{i} \le p_{k}$.

Proof (Sketch): The Individual Rationality condition ensures that bidders do not pay more than their reward while the Compact Condition ensures that, among all goods assigned to a bidder, she first consumes cheaper goods before consuming more expensive ones. Equivalently, this condition states that prices of goods that are completely consumed are cheaper than those that are only partially consumed.    $\square$

The linear program shown in Algorithm 1, which uses seller revenue as the objective function and the linear conditions that characterize restricted envy-freeness as constraints, can be used to find a set of restricted envy-free prices that maximizes seller revenue.

4 Revenue Maximizing Prices

In the remainder of this paper, we will be concerned with finding prices that maximize seller revenue for different market outcomes. We start by defining what a revenue-maximizing problem means for different solution concepts and review algorithms found in the literature to compute these prices in the special case of unit-demand bidders. We then present our algorithm for finding revenue-maximizing EFEr in size-interchangeable CCMMs.

Definition 8

The revenue-maximizing WE problem: Given a CCMM, find a revenue-maximizing WE.

Gul and Stachetti [6] presented a VCG-inspired [13] polynomial-time algorithm that solves the revenue-maximizing WE problem in unit-demand CCMMs: let $V\in \mathbb {R}^n_+\times \mathbb {R}^m_+$ be the valuation matrix of a market with $n$ items and $m$ unit-demand bidders where entry $v_{ij}$ denotes bidder $j$’s valuation for good $i$. Let $\pi$ denote a maximum weight matching of $V$, and let $w(V)$ denote the weight of $\pi$. Let $V_{-i}$ denote the same valuation matrix, but with good $i$ removed. For each good $i$, set $p_i= w(V) - w(V_{-i})$. We call this algorithm, which returns $(\pi , {\varvec{p}})$, MaxWE.

Then, building on Myerson’s [10] intuition that reserve prices can boost revenue, Guruswami et al. [7] went one step further, essentially generalizing the problem of searching for a revenue-maximizing WE to that of searching for a revenue-maximizing WEr.

Definition 9

The revenue-maximizing WEr problem: Given a CCMM, find a revenue-maximizing WEr.

Recall from Example 4 that different allocations can support different levels of seller revenue, while still maintaining the envy-freeness property. Algorithm 2 is a high-level strategy for searching among WEr for one that is revenue maximizing. The algorithm searches over different allocations $\varvec{X}$, computing WEr prices ${\varvec{p}}$ for each, and then outputs a pair $(\varvec{X}, {\varvec{p}})$ among those seen with maximal seller revenue. The interesting choice, which governs the algorithm’s success, is which allocations to search over. Generally speaking, based on some initial allocation, the algorithm determines a set of reserve prices, each of which corresponds to an alternative allocation, whose supporting envy-free prices may or may not yield higher revenue than the others seen.

In the unit-demand case, Guruswami et al. [7], showed that the following instance of Algorithm 2 finds a revenue-maximizing WEr with revenue at least $\text {OPT}/(2 \ln m)$, where OPT is the revenue of a revenue-maximizing WEr. (Step 1.) Find a maximum weight matching $\varvec{X}$ of $V$. (Step 2.) For each valuation $r$ on the edges of $\varvec{X}$, compute a WEr as follows: for each good $i$ augment the valuation matrix to include two dummy bidders, each with reward $r$. Run MaxWE on the new valuation matrix to obtain a WE $(\pi , {\varvec{p}})$, based on which a new matching $\pi '$ can be inferred by reallocating goods from dummy bidders to real bidders.

As shown in Example 2, a WE might not exist for a CCMM; thus, a WEr might also not exist. But recall that an EFEr always exists. Hence, we define the following problem:

Definition 10

The revenue-maximizing EFEr problem: Given a CCMM, find a revenue-maximizing EFEr.

Like the algorithm of Guruswami et al. [7], our approach (Algorithm 3) to searching for a revenue-maximizing EFEr in a size-interchangeable CCMM follows the structure of Algorithm 2. That is, for various choices of $r$, corresponding to various allocations $\varvec{X}_r$, we find an EFEr, and then we output an EFEr which is revenue-maximizing among all those considered.

More specifically, we first find an allocation $\varvec{X}$ (Step 1), and then for all $x_{ij}>0$, we find a restricted EFEr (Step 2). Step 2.0 defines a reserve price, and Step 2.1 finds an allocation that respects this reserve price (see Definition 12). Step 2.2 then invokes a subroutine we call restricted EFEr, which is a straightforward generalization of Algorithm 1 that finds a revenue-maximizing EFEr with restricted envy-free prices in polynomial time. The generalization is simply that this algorithm takes as input a reserve price $r$, and then includes the additional set of constraints: $\forall i\in U: p_i\ge r$.

Allocations in Size-interchangeable CCMMs. Two steps in Algorithm 3 depend on an allocation. The natural place to look are among those of optimal value. A feasible allocation is optimal if it maximizes the total of all bidders’ rewards.

Definition 11

(Optimal Allocation). An optimal allocation is a solution to the following optimization problem:

$\max _{\varvec{X}} \sum \limits _{j=1}^mR_jy_j$,    subject to: $\quad \forall i: \sum \limits _{j=1}^mx_{ij} \le N_i, \quad \forall j: y_j\in \{0,1\}$

In the Appendix we present an ILP to compute optimal allocations.

Definition 12

(Optimal Allocation that respects a reserve price). An optimal allocation that respects a reserve price is a solution to the following optimization problem:

$\max _{\varvec{X}} \sum \limits _{j=1}^m(R_j- rI_j) y_j$, subject to: $\quad \forall i: \sum \limits _{j=1}^mx_{ij} \le N_i, \quad \forall j: y_j\in \{0,1\}$

The following theorem implies that is unlikely that one can devise an Algorithm that optimizes welfare in size-interchangeable CCMMs in polynomial time.

Theorem 2

Finding an optimal allocation is NP-hard. (Proof in Appendix)

Since finding an optimal allocation is NP-Hard, we present a greedy heuristic (Algorithm 4) to find allocations. This algorithm can easily be adapted to produce an allocation that respects reserve price $r$ as follows: given input market $M$, construct new market $M'$ by removing any bidder $j$ for which $R_j- rI_j< 0$, and setting the reward of the remaining bidders to be $R_j- rI_j$. Now run Algorithm 4 on input $M'$ to obtain an allocation $\varvec{X}'$, which we lift up to create an allocation, $\varvec{X}_r$, in the original market $M$ that respects reserve prices.

There are two sources of non-determinism in Algorithm 4: (1) the order in which to loop through bidders and (2) the order in which to loop through goods. One approach is to orders bidders in descending order by rewards per square root of goods demanded, i.e., $R_j/\sqrt{I_j}$, and goods in ascending order of remaining supply. We also experiment with other combinations, e.g., ordering goods in descending order of remaining supply.

5 Experiments

Experimental Setup. Given outcome $(\varvec{X},{\varvec{p}})$, seller revenue $\rho = \sum _{j}\sum _{i}x_{ij} p_{i}$, and total welfare $W= \sum _{j} R_jy_j$, where $y_j= 1$ in case bidder $j$ is a winner under $\varvec{X}$ and 0 otherwise. Let $\text {OPT}_W$ be the value of a welfare-maximizing allocation. Since we assume bidders are individually rational, seller revenue cannot exceed $\text {OPT}_W$. We thus report metrics of efficiency $W/ \text {OPT}_W$, and seller revenue $\rho / \text {OPT}_W$. We also report metrics based on violations of the (unrestricted) envy-freeness and market clearing conditions. Given a market $M$ and outcome $(\varvec{X}, {\varvec{p}})$, we define an envy-free violation (EF) as the ratio between the number of bidders that are not envy-free, and the total number of bidders in the market; and define a market clearance violation (MC) as the ratio between the number of goods completely unallocated whose price is greater than zero, and the total number of goods in the market.

All metrics are reported over random markets $M$ drawn from a distribution we call Random-k-Market $(n,m,p,k)$. Let $S = \sum _iN_i$ be the total supply of $M$, and let $D = \sum _jI_j$ be the total demand of $M$. The supply-to-demand ratio S/D, is a measure of how much over (or under) demanded a market is. A market is over demanded if $S/D < 1$ and under demanded if $S/D > 1$. A random market drawn from Random-k-Market $(n,m,p,k)$ over CCMM has $n$ goods and $m$ bidders. The parameter p is the probability that an edge $(i,j)$ is present in $E$, and thus, the expected number of edges is $pnm$. Both $N_i$ and $I_j$ are randomly and independently drawn integers between 1 and 10 such that the supply-to-demand ratio is k. Finally, each bidder’s reward $R_j$ is uniformly and independently drawn uniformly on [1, 10]. From Random-k-Market $(n,m,p,k)$ we generate markets with $n,m= 1,\ldots ,20$, $p = 0.25,0.5,0.75,1.0$ and $k = 0.25,0.33,$ 0.5, 1, 2, 3, 4. For each metric, we report the average across markets over 100 independent trials. Results are shown in Table 1.

Algorithms. Algorithms’ names are abbreviated as follows: CK refers to the Crawford-Knoer ascending auction [5] (see the Appendix for details). MaxWE and MaxWErApprox refer to Guruswami et al.’s algorithms (see Sect. 4). LP refers to our revenue-maximizing EFEr algorithm. The algorithm LP is qualified by the type of allocation given as input: LP Optimal refers to the case when an optimal allocation is given as input, and LP Greedy refers to the case when the greedy allocation is given as input. We report results where the greedy approximation orders goods by descending order of remaining supply. We also experimented with ordering goods by ascending order of remaining supply, but saw no qualitative differences in the results.

Table 1. Results.

Results. We report on two sets of experiments: singleton CCMMs, and general. In both cases, we take as a baseline the CK auction, which, in the case of unit-demand markets, like MaxWE, is guaranteed to produce an efficient outcome, but at the expense of low revenue. For singleton CCMMs, we compare our algorithm to MaxWErApprox as well.

As expected, the efficiency of CK and MaxWE in singleton CCMMs is perfect. Also, these algorithms yield zero violations, as they are known to generate Walrasian equilibria. However, their revenues are low, particularly in under-demanded markets, because there are more unallocated goods in these markets, each of which must be priced at zero, thereby limiting the price of allocated goods, in order to avoid envy. Our algorithm and MaxWErApprox both impose a reserve, enabling them to disregard some of these overly constraining goods, but ours obtains substantially more revenue than MaxWErApprox, with fewer (but not significantly fewer) violations. In over-demanded markets, the performance of our algorithm is comparable to that of MaxWErApprox, and both algorithms outperform MaxWE, which outperforms CK. Note that our algorithm produces unrestricted envy-free outcomes in singleton CCMMs.

In general CCMMs, CK is nearly efficient in under-demanded markets, but much less so in the over-demanded case. But in neither case does it strike a good balance between efficiency and revenue. In contrast, our algorithm is able to accrue upwards of 72% revenue in over-demanded markets, while retaining an efficiency of 89%, and it does so with hardly any EF violations, compared to CK, which obtains an efficiency of only 79% and revenue of only 41%. As in the case of singleton CCMMs, our algorithm does not fare as well in the harder case of under-demanded markets, where once again there are more unallocated goods, although it again produces nearly-unrestricted envy-free outcomes. These experiments suggest that while not perfect, finding revenue-maximizing restricted envy-free outcomes in polynomial time is a reasonable heuristic for maximizing revenue among nearly-unrestricted envy-free outcomes.

6 Conclusion and Future Directions

CCMMs with unit-demand valuations have some important properties, e.g., a WE always exists and there are polynomial-time algorithms to find such outcomes. A WE outcome guarantees that all bidders are envy-free and that the market clears, and thus, by the first welfare theorem of economics, yields an allocation that maximizes social welfare. Guruswami et al. [7] proposed an algorithm for the unit-demand case, sacrificing social welfare in an attempt to maximize seller revenue, while maintaining the envy-freeness property. In this paper, we proposed an algorithm that generalize this well-known algorithm for the unit-demand case to the case of single valued, size-interchangeable CCMMs. In future work, we plan to look more closely at algorithms [3, 4, 7, 9] that have been proposed for the more difficult case of single-minded bidders, and to perhaps generalize results about those algorithms to the single-valued, size-interchangeable bidder setting studied here. We will also explore alternative solution concepts where we combine the restricted EF condition with the objective of maximizing the number of allocated bidders.

Appendix

Mixed ILP to Find Optimal Allocations

Given a market $(U,C,E,{\varvec{N}},{\varvec{I}},{\varvec{R}}),$ Algorithm 5 is a mixed ILP that can be used to find an optimal allocation.

Constraints (1), (2) and (5) imply that a solution to the Mixed-ILP is a feasible allocation. Constraints (3) and (4) imply that a bidder attains reward $R_j$ if and only if it is completely fulfilled, and together with constraint (5), imply that if $y_j= 0$ then $x_{ij} = 0$ for all $i$. The objective of the mixed ILP implies that the solution maximizes bidders’ rewards over all feasible allocations and thus, it is an optimal allocation. To obtain an allocation that respects reserve price $r$, change the objective of the mixed ILP to $\sum _{j=1}^m(R_j-rI_j) y_j$, where $r\in \mathbb {R}^+$ is the reserve price parameter.

Proof of Theorem 2

Finding an optimal allocation is NP-hard. To prove this, we reduce from the following version of set packing: Given a universe $\mathcal {U} = \{u_1,u_2,\ldots ,u_n\}$ and a family of subsets $\mathcal {S} = S_1,S_2,\ldots ,S_k \subseteq \mathcal {U}$, find the maximum number of pairwise disjoint sets in $\mathcal {S}$.

Consider an input $(\mathcal {U},\mathcal {S})$ to the set packing problem as described above. Let us construct a market $(U,C,E,{\varvec{N}},{\varvec{I}},{\varvec{R}})$ from $(\mathcal {U},\mathcal {S})$ as an input to the optimal allocation problem. At a high level, the input market consists of n goods each offered in exactly 1 copy and k bidders where each bidder corresponds to a member $S_j\in \mathcal {S}$ that demand as many goods as elements in $S_j$ and attains a reward of exactly 1. A goods is connected to a bidder only if the index of the good is contained in the set $S_j$ associated with the bidder.

Formally, given $(\mathcal {U},\mathcal {S})$ where $\mathcal {U} = \{1,2,\ldots ,n\}$ and $\mathcal {S} = \{S_1,S_2,\cdots ,S_k\}$, construct $f(\mathcal {U},\mathcal {S}) = (U,C,E,{\varvec{N}},{\varvec{I}},{\varvec{R}})$ as follow: (1) let $U= \mathcal {U}$ and $N_i= 1$ for all $i= 1,2,\ldots ,n$. (2) let $C= \{1,2,\ldots , k\}$, and associate each bidder $j\in C$ to $S_j\in \mathcal {S}$ so that $I_j= |S_j|$. Also, $R_j= 1$ for all $j= 1,2,\ldots ,k$. (3) add edge $(i,j)$ to $E$ only if $i\in S_j$. Clearly the transformation f is polynomial on the size of the input $(\mathcal {U},\mathcal {S})$.

We now show that a set packing for $(\mathcal {U},\mathcal {S})$ corresponds to an optimal allocation for $f(\mathcal {U},\mathcal {S})$ and vice versa. Suppose that l is the maximum number of pairwise disjoint sets in $\mathcal {S}$ and that $S_1,S_2,\ldots ,S_l \in \mathcal {S}$ are these sets. By our transformation f we know that each bidder $j$ associated with a set $S_j$ from the previous list is connected to as many goods as $|S_j|$. Since all these sets are pairwise disjoint, all bidders are connected to different goods. Therefore, each of these bidders can be fulfilled which means that the value of the optimal allocation is at least l. Moreover, we know that is not possible to fulfill more than l bidders since l is the maximum number of pairwise disjoint sets, and selecting more than l bidders would imply, by our transformation f, that at least one good has a supply greater than 1. Therefore, l is the value of the optimal allocation of $f(\mathcal {U},\mathcal {S})$.

Suppose that l is the value of the optimal allocation of $f(\mathcal {U},\mathcal {S})$. This means that l is the maximum number of bidders that can be fulfilled. Bidder $j$ is fulfilled only if its allocation is at least $|S_j|$. By construction we know that a bidder is connected to exactly $|S_j|$ many goods. Therefore, each allocated bidder $j$ is fulfilled by exactly $|S_j|$ goods. Moreover, none of these goods are allocated to different bidders since there is exactly 1 copy of each good. Therefore, the sets associated with the selected bidders must not overlap in any element, i.e., they must be pairwise disjoint. This shows that there are at least l pairwise disjoint sets in $(\mathcal {U},\mathcal {S})$. We also know that there must be at most l pairwise disjoint sets or otherwise the value of the optimal allocation would have been more than l. Therefore, l is the maximum number of pairwise disjoint sets in $\mathcal {S}$.    $\square$

Crawford and Knoer Ascending Auction

In the unit-demand setting, it is well known that Walrasian Equilibria exist [6]. Furthermore, Crawford and Knoer [5] proposed an ascending auction mechanism which, for price increment $\epsilon$, yields an $\epsilon$WE.¹ We describe the workings of their mechanism in a unit-demand CCMM in Algorithm 6.²

This algorithm, as stated, generalizes to size-interchangeable CCMMs, except that at each step of the algorithm we must query bidders for their favorite bundles at the current prices plus $\epsilon$, rather than their favorite individual goods.