The Communication Complexity of Combinatorial Auctions in Graphs

Christodoulou, George; Koutsoupias, Elias; Kovács, Annamária; Vlachos, Ioannis

doi:10.4230/LIPIcs.STACS.2026.27

The Communication Complexity of Combinatorial Auctions in Graphs

George Christodoulou

Aristotle University of Thessaloniki, Greece
Archimedes, Athena Research Center, Greece Elias Koutsoupias

University of Oxford, UK Annamária Kovács

Goethe University, Frankfurt am Main, Germany Ioannis Vlachos

Athens University of Economics and Business, Greece
Archimedes, Athena Research Center, Greece

Abstract

We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight – both positive and impossibility – results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.

Keywords and phrases:

Auctions, Communication Complexity, Mechanism Design, Graphs

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algorithmic mechanism design ; Theory of computation

\rightarrow

Computational pricing and auctions ; Theory of computation

\rightarrow

Communication complexity

Acknowledgements:

We would like to thank an anonymous reviewer for suggesting a refined analysis of an earlier version of the proof in Theorem 8, which helped us obtain the tight bound presented in the current version.

Funding:

George Christodoulou, Ioannis Vlachos: This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.

DOI:

10.4230/LIPIcs.STACS.2026.27

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Combinatorial auctions, perhaps one of the most fundamental settings in mechanism design, involve allocating a set of $m$ items to a set of $n$ bidders. Each bidder $i$ has a private valuation $v_{i}$ for every possible subset of items, and the auctioneer aims to allocate the items in a way that maximizes a given objective. In this work, we focus exclusively on the standard objective of maximizing social welfare, which is defined as the total value obtained by all bidders.

Maximizing social welfare is an “easy” mechanism design objective from a game-theoretic perspective, as the Vickrey-Clarke-Groves (VCG) mechanism provides a general incentive-compatible solution that achieves this goal in any setting. However, from an algorithmic perspective, VCG is often unsatisfactory because computing its outcome and payments is generally computationally infeasible. This infeasibility stems from an even deeper challenge: communication complexity. Since only bidder $i$ knows their own valuation $v_{i}$ , they must communicate it to the auctioneer, which in general requires exponential communication.

In light of these challenges, a central research direction in algorithmic game theory focuses on designing protocols that trade optimality for reduced computational and communication complexity. In this work, we focus on the communication complexity of protocols. Specifically, we focus on the following questions: Are there protocols with polynomial communication complexity that achieve a good approximation of social welfare, even when bidders have unbounded computational power? and How does the answer change when we require the protocols to be incentive compatible?

There has been extensive work on these questions, and we now have an almost complete understanding of the power – but mostly the limitations – of non-truthful protocols (see Table 2). Specifically, for the classes of valuations considered in this work (general monotone, subadditive, and XOS), tight lower and upper bounds have been established [7, 18, 20, 26, 34]. In contrast, our understanding of polynomial-communication incentive-compatible (i.e., truthful) protocols remains very limited. Notable recent successes include the separation of truthful and non-truthful protocols for two bidders with XOS valuations [6], which is based on the general taxation framework proposed by Dobzinski [16], and a similar result for three bidders with (almost) subadditive valuations [37].

In this work, we consider a framework that generalizes the setting of two bidders, in which the number of bidders can be arbitrary, but each item can only be allocated to one of two eligible bidders among them. This setting can be modeled by a multigraph, where nodes represent bidders and edges represent items that can be allocated to the incident bidders. We allow the multigraphs to have arbitrary degrees, and the valuations of each bidder can be XOS, subadditive, or simply a monotone function of the incident edges. We also study interesting variants of this framework, such as graphs and hypergraphs. Multigraph settings in mechanism design have been considered before and played a crucial role in settling the Nisan-Ronen conjecture [11, 12]. They have also been studied in the context of fair division [2, 10, 42, 43]. In general, graph and hypergraph models provide a natural and fruitful intermediate setting to study questions that are otherwise inaccessible in the most general case.

Our results (Table 1) span a wide spectrum, ranging from very positive to very negative. On the negative side, we show that the questions addressed in this paper are far from trivial in the graph/multigraph framework. For instance, with general valuations, the best achievable approximation ratio is $n$ . Intriguingly, we prove that even for simple graphs, this is the best possible. On the positive extreme, we are able to show several positive results for general classes of graphs, such as $k$ -partite multigraphs and also graphs of bounded treewidth $k$ . Specifically for graphs of treewidth $1$ – that is, trees – we establish that there exists a dynamic programming framework to exactly implement VCG. However, this positive result cannot be extended much further; in particular, even simple graphs of treewidth 2 exhibit an approximation ratio of at least $5/4$ .

1.1 Contributions

In this work, we investigate the communication complexity of combinatorial auctions in the context of graphs and hypergraphs. We focus on designing protocols and mechanisms for general, subadditive and XOS valuations, but also on establishing impossibility results. Our results are summarized in Table 1, organized by valuation class and graph type.

General Valuations.

In Section 3, we focus on general monotone valuations. When we turn to general graphs, the graph structure does not offer any advantage: in Theorem 8, we extend the lower bound from [34], proving that the $\min\{n,O(\sqrt{m})\}$ -approximation algorithm by [7] is optimal for large number of items, even in the case of simple graphs.

We then provide positive and negative results for $k$ -partite multigraphs as well as for graphs of treewidth $k$ . We show that a $k$ -approximation is achievable for $k$ -partite graphs (Theorem 9) and that this bound is tight (Theorem 12). Furthermore, we examine the applicability of the VCG mechanism in graphs under polynomial communication constraints. We demonstrate that an optimal truthful mechanism can be implemented for trees (Theorem 14). We show that unfortunately this positive result is impossible to obtain for natural extensions of trees; even for simple graphs with treewidth of 2 we establish a lower bound of $5/4$ on the approximation ratio (Theorem 20). In the case of $k$ -degenerate graphs, we show a $(k+1)$ -approximation (Proposition 15) by leveraging the graph’s colorability. For graphs of treewidth $k$ , we generalize the positive result on trees, by showing an upper bound of $(k+1)/2$ (see Theorem 16). Additionally, we prove a lower bound that converges to $2$ for $k\rightarrow\infty$ (Theorem 20).

It is important to note that the aforementioned protocols providing the upper bounds are truthful, deterministic, MIR mechanisms. Also our lower bounds apply to all protocols, not just truthful ones.

Subadditive Valuations.

In Section 4, we present a deterministic polynomial-communication truthful mechanism that achieves a $2$ -approximation for subadditive multigraph valuations (Corollary 22). We also establish a matching lower bound of $2$ (Theorem 23), which we derive by adapting the previously known lower bound for subadditive valuations [18]. These results match the tight bounds already known for non-truthful protocols for subadditive valuations. However, for truthful mechanisms, they represent an improvement over the best existing truthful mechanisms – both deterministic [36] and randomized [15] – when applied to the graph setting. Our multigraph mechanism extends naturally to $k$ -uniform hypergraphs, yielding a $k$ -approximation (Lemma 21). The deterministic mechanism we provide is maximal-in-range (MIR) and relies on value queries.

XOS Valuations.

In Section 5, we consider XOS valuations, for which a tight approximation ratio of $e/(e-1)$ is known for the non-graph setting [18, 20, 26]. Interestingly, for the multigraph setting, the approximation ratio improves to $4/3$ , matching the ratio for two bidders. To achieve this upper bound of $4/3$ for multigraphs, we adapt the 2-agent protocol of [26] (Lemma 25). We further extend this result to $k$ -uniform hypergraphs, deriving an upper bound of $1/(1-(1-1/k)^{k})$ (Lemma 26) by applying the rounding technique of [27]. We also establish a matching lower bound (Theorem 27 and Corollary 28) by adapting the technique from [20]. This refines the known results, and in the limit, as $k$ tends to infinity, we recover the tight approximation ratio of $e/(e-1)$ . These protocols assume access to a demand oracle.

Table 1: Communication Complexity results on graphs. Regarding “Multigraphs” rows, Corollary 22 and Theorem 25 apply to multigraphs, while the lower bound results (Theorems 8, 23 and Corollary 28) hold for simple graphs. Note that the upper bound results for subadditive valuations (Theorem 21 and Corollary 22), as well as for

k

-partite graphs (Theorem 9), trees (Theorem 14) and treewidth-

k

graphs (Thm 16), are MIR and thus truthful mechanisms. In contrast, the tight results for XOS valuations (Theorems 27 and 26 for hypergraphs, Corollary 28 and Theorem 25 for graphs) concern non-truthful algorithms. In the “Hypergraphs” row,

k

denotes the edge size of hypergraphs.

	General
	LB	UB
Multigraphs	$n$ (Thm 8)	$\min\{n,\Theta(\sqrt{m})\}$ [7]
$k$ -Partite	$k$ (Thm 12)	$k$ (Thm 9)
Trees	$1$	$1$ (Thm 14)
Treewidth $k$	$1+\left(\frac{1}{k}\right)^{\frac{1}{(k-1)}}-\left(\frac{1}{k}\right)^{\frac{k% }{(k-1)}}$ (Thm 20)	$\frac{k+1}{2}$ (Thm 16)

	SubA		XOS
	LB	UB	LB	UB
Hypergraphs	$2$	$k$ (Thm 21)	$\frac{1}{1-(1-\frac{1}{k})^{k}}$ (Thm 27)	$\frac{1}{1-(1-\frac{1}{k})^{k}}$ (Thm 26)
Multigraphs	$2$ (Thm 23)	$2$ (Cor 22)	$\frac{4}{3}$ (Cor 28)	$\frac{4}{3}$ (Thm 25)

1.2 Related Work

Table 2 presents a brief summary of the main known bounds on the communication complexity of combinatorial auctions in the general case.

Non-Truthful Protocols.

The best known approximation protocols involve solving a specific LP relaxation, known as the configuration LP, and rounding its fractional optimum. For general valuations, an algorithm with an approximation ratio of $\min\{n,O(\sqrt{m})\}$ is provided in [7]. Dobzinski and Schapira [20] show an $\frac{e}{e-1}$ -approximation algorithm for XOS valuations assuming access to an XOS oracle. In [26], Feige presents the best possible approximation algorithms for subadditive and XOS bidders, achieving a factor of $2$ for subadditive, and $e/(e-1)$ for XOS, respectively, while employing oblivious rounding techniques.

Truthful Protocols.

The algorithms mentioned in the paragraph above are not truthful. In contrast, the classical Vickrey-Clark-Groves (VCG) mechanism [40, 13, 28] ensures truthfulness, but requires exponential communication in order to determine the welfare-maximizing allocation. Regarding deterministic mechanisms, enforcing truthfulness while maintaining polynomial communication, leads to a worsening factor of $\sqrt{m}$ compared to non-truthful protocols (see Table 2). In all settings, the best-known approximation guarantees for deterministic truthful mechanisms with polynomial communication are provided by MIR mechanisms. For general valuations, Holzman et al. [29] present an $O(m/\sqrt{\log m})$ -approximate mechanism, which was later improved to an $O(m/\log m)$ -approximation in [36]. In the case of subadditive valuations, Dobzinski et al. [18] present an $O(\sqrt{m})$ -approximate mechanism, which was subsequently improved to an approximation of $O(\sqrt{m/\log m})$ in [36]. Allowing randomization improves over the best-known deterministic truthful protocols [19, 20, 15, 32].

Lower Bounds.

Matching lower bounds for the approximation of social welfare in combinatorial auctions with polynomial communication have been established [7, 18, 20, 34]. The aforementioned truthful deterministic mechanisms perform value queries in order to achieve their guarantees. Restricted to value queries, matching lower bounds are known [23]. Moreover, in the computational model, strong separation results between truthful and non-truthful mechanisms exist [35, 9, 14, 23, 21, 22]. However, regarding deterministic truthful mechanisms in the communication model, bridging the gap remains a major open question.

Tight bounds are known for the specific class of MIR mechanisms [17, 36]. For truthful mechanisms in the communication model, the only improvements over the non-truthful lower bounds are separation results between truthful and non-truthful algorithms for two [6] and three players [37]. These results leverage the powerful taxation framework of Dobzinski [16].

Graph Model.

Modeling agent valuations using graphs has already been considered in several algorithmic and game-theoretic problems. In fair division, Christodoulou et al. [10] study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph. In this direction, extensive research on fair division settings has focused on valuations involving graphs [43, 30, 2, 42]. Verschae and Wiese [39] study the unrelated graph balancing problem, a special case of the scheduling problem with unrelated machines, where each task can be assigned to at most two machines. Graph balancing, a special case where both edge directions correspond to the same processing time, has been studied in several works [24, 33, 4, 3]. In [11], the authors investigate truthful mechanisms for allocation problems on graphs, addressing both the minimization scenario (scheduling) and the maximization setting (auctions).

Table 2: Communication Complexity: Known results for the general case of

n

agents and

m

items. Randomized algorithms and mechanisms are explicitly stated. Lower bounds apply to non-truthful protocols including randomized and nondeterministic.

Lower Bounds

Non-truthful

Truthful

Gen

\min\{n,\Omega(\sqrt{m})\}

[34]

\min\{n,O(\sqrt{m})\}

[7]

O(\frac{m}{\log m})

[36]

(rand)

\min\{n,O(\sqrt{m})\}

[19, 15, 32]

SubA

2 [18]

(rand) 2 [26]

O(\sqrt{\frac{m}{\log m}})

[36]

(rand)

O((\log\log m)^{3})

[5]

XOS

\frac{e}{e-1}

[20]

(rand)

\frac{e}{e-1}

[20, 26]

O(\sqrt{\frac{m}{\log m}})

(rand)

O((\log\log m)^{2})

[5]

2 Preliminaries

Auction Setting in Graphs

In our setting, there is a set $N$ of $n$ agents labeled $1,\dots,n$ . Let $E$ , with $|E|=m$ , be a set of items. For all $i=1,\dots,n$ let $v_{i}:2^{E}\mapsto\mathcal{R}^{+}$ be the valuation function $v_{i}\in\mathcal{V}_{i}$ of agent $i$ , such that $v_{i}(X)$ represents the value that agent $i$ assigns to the subset of items $X\subseteq E$ . The valuation functions are assumed to be normalized and monotone.

The current work considers a special case, where at most 2 players can potentially acquire each item $j\in E$ . More formally, an undirected multigraph is given, in which vertices represent agents and edges represent items. For each edge $e\in E$ , only its two incident vertices can acquire item $e$ , and they have in general different valuations over the item. Let also $E_{i}$ denote the set of edges incident to agent $i$ . The goal is to assign a direction to each edge $e$ (allocate the item) of the graph, to one of the incident vertices.

More generally, if at most $k$ players can acquire each item, a $k$ -hypergraph occurs and each item corresponds to a $k$ -hyperedge. We will then denote by $I_{e}$ the set of agents corresponding to an edge $e$ .

The designer interacts with the bidders to produce an allocation $a\in\mathcal{A}$ of the items $E$ , where $a=(X_{1},\ldots,X_{n})$ so that $X_{i}\cap X_{j}=\emptyset$ for any two agents $i\neq j$ . The objective is to maximize the social welfare $SW(a,v)=\sum_{i}v_{i}(X_{i})$ . We denote by $O_{i}$ the set of items that agent $i$ gets in an optimal allocation $a^{*}$ . We will often refer to $SW(a,v)$ as ALG and to $SW(a^{*},v)$ as OPT.

Mechanism Design

A mechanism defines for each agent $i$ , a set $\mathcal{V}_{i}$ of available strategies the player can choose from. Each agent $i$ provides a bid $b_{i}\in\mathcal{V}_{i}$ , which may not necessarily match their true type $v_{i}$ , if this serves their interests. A mechanism $(a,\mathbf{p})$ consists of two parts:

$\blacksquare$

A selection algorithm: The selection algorithm selects an alternative based on the players’ inputs (bid vector) $\mathbf{b}=(b_{1},\ldots,b_{n})$ . We denote by $X_{i}(\mathbf{b})$ the items assigned to player $i$ .
$\blacksquare$

A payment scheme: The payment scheme $\mathbf{p}=(p_{1},\ldots,p_{n})$ determines the payments, which also depend on the bid vector $\mathbf{b}$ . The functions $p_{1},\ldots,p_{n}$ represent the payments that the mechanism hands to each agent, i.e., $p_{i}:\mathcal{V}\rightarrow\mathbb{R}$ .

The utility $u_{i}$ of an agent $i$ is the actual value they gain from the chosen alternative minus the payment they will have to pay, $u_{i}(\mathbf{b})=v_{i}(a(\mathbf{b}))-p_{i}(\mathbf{b})$ . A mechanism is truthful, if for every agent, reporting their true type is a dominant strategy. Formally,

u_{i}(v_{i},\mathbf{b}_{-i})\geq u_{i}(v^{\prime}_{i},\mathbf{b}_{-i}),\qquad% \forall i\in[n],\;\;v_{i},v^{\prime}_{i}\in\mathcal{V}_{i},\;\;\mathbf{b}_{-i}% \in\mathcal{V}_{-i},

where $\mathcal{V}_{-i}$ denotes all parts of $\mathcal{V}$ except its $i$ th part.

A well-known truthful mechanism that maximizes the social welfare is the Vickrey-Clarke-Groves (VCG) mechanism. It is a special case of maximal-in-range (MIR) mechanisms, that are truthful mechanisms that maximize the social welfare over some fixed set of allocations.

A mechanism is $\rho$ -approximate with $\rho\geq 1$ , if $\text{OPT}\leq\rho\cdot\text{ALG}$ for all possible inputs $v$ .

We now formally define the valuation classes we study in this paper.

Definition 1.

The class of general monotone valuations Gen contains all nonnegative valuations with $v_{i}(S)\leq v_{i}(T)$ , whenever $S\subseteq T$ , and $v_{i}(\emptyset)=0$ .

Definition 2.

A valuation function $v_{i}$ is called subadditive iff $v_{i}(S)+v_{i}(T)\geq v_{i}(S\cup T)$ for any bundles of items $S,T\subseteq E$ . The class subA contains all valuations in Gen that are subadditive.

Definition 3.

A valuation function $v_{i}$ belongs to the XOS class iff it is in Gen and for any bundle $S\subseteq E$ , it can be expressed as the maximum of additive valuation functions $c_{1},c_{2},\ldots,c_{l}$ , also called clauses, i.e. $v_{i}(S)=\max_{j\in[l]}{\sum_{e\in S}{c_{j}(e)}}$ .

It is known that these classes form a strict hierarchy, namely XOS $\subset$ SubA $\subset$ Gen.

Communication Complexity

We follow the conventional number-in-hand framework within the blackboard communication model [31], where each player’s input is assumed to be their valuation $v_{i}$ . Communication takes place in rounds, where in each round, players simultaneously write messages on a shared blackboard visible to everyone. According to Yao’s model [41], in a deterministic protocol, the message sent by any player $i$ in each round depends only on the player’s private input $v_{i}$ , and the messages from all previous rounds – essentially, the content of the blackboard. The auctioneer does not receive any input and is responsible for providing the output in the final round based solely on the blackboard content. The communication cost of a protocol, is the sum of the worst-case message lengths (in bits) communicated by all players.

In the case of randomized protocols, we assume the public coin model, in which an infinite sequence of random bits is written on the blackboard visible to all agents. It is important to note that for randomized protocols, the communication cost is defined as the worst-case length of messages, accounting for both the randomness of the input and the public coin. The communication complexity of a function is the minimum communication cost achieved by a protocol that computes it.

In general, we assume that all numbers are limited to a certain precision, i.e., are represented by some number of bits, which is polynomial in the number of agents and items, and does not affect the overall communication complexity.

Also, the following Chernoff-bound will be used:

Proposition 4.

Let $Z_{1},\dots,Z_{m}$ be independent random variables that take values in $\{0,1\}$ , such that for all $i$ , $Pr[Z_{i}=1]=p$ for some $p$ . Then, the following holds for $0\leq\delta\leq 1$ :

Pr[\Sigma_{i}Z_{i}>(1+\delta)pm]\leq e^{-\frac{pm\delta^{2}}{3}}\,,

Pr[\Sigma_{i}Z_{i}<(1-\delta)pm]\leq e^{-\frac{pm\delta^{2}}{2}}\,.

3 General Valuations

In this section we assume that the bidders have general monotone valuations. We prove approximation bounds for combinatorial auction algorithms with polynomial communication complexity on different graph classes. The main negative result here is a lower bound of $n$ on the approximation ratio for simple graphs (Section 3.1). For large number of items (e.g. $m=\Omega(n^{2})$ ), this matches the upper bound achievable in the unstructured case, because the best known protocols achieve approximation factor of $\min\{n,O(\sqrt{m})\}$ (see Section 1.2).

Then we show a tight approximation bound of $k$ for $k$ -partite graphs (Section 3.2), and a truthful mechanism of ratio $(k+1)/2,$ as well as a constant lower bound for graphs of treewidth $k$ (Section 3.3). The latter lower bound converges to $2$ for $k\rightarrow\infty.$ It is a challenging open question to find a construction with treewidth $k,$ proving a non-constant (in $k$ linear?) lower bound. Both protocols providing the upper bounds ( $k$ and $(k+1)/2,$ respectively) are truthful, MIR mechanisms.

For the lower bound results we need the following definition of the approximate disjointness communication problem.

Approximate Disjointness Problem.

For some large integer $t\in\mathbb{N},$ each player $i\in[n]$ holds a $t$ -bit string that specifies a subset $B_{i}\subset[t]=\{1,2,\ldots t\}$ of indices (integers) in $[t].$ The players are required to distinguish between the following two extreme cases:

$\blacksquare$

at least one element $s\in[t]$ appears in all agent inputs: $\,s\in\cap_{i\in[n]}B_{i}\neq\emptyset$ ,
$\blacksquare$

no element of $[t]$ appears in more than one agent’s input: for every $i\neq j,$ $\,B_{i}\cap B_{j}=\emptyset$ .

The communication complexity of this problem is known to be $\Omega(t/n^{4})$ [1].

3.1 Lower Bound $𝒏$ for General Graphs

We present a lower bound of $\,n\,$ in the case of simple graphs (Theorem 8). Note that this negative result applies to more general structures than simple graphs, such as multigraphs. In order to prove the lower bound for simple graphs, first we introduce the notion of a balanced graph allocation.

Balanced allocations in simple graphs

We consider a complete graph $K_{n}=(V,E),$ on $n$ vertices and $m={n\choose 2}$ edges. The vertices $V=[n]$ correspond to the $n$ bidders and the edges correspond to $m$ items, so that every edge (item) can only be allocated to one of its two incident vertices. For simplicity of presentation we will assume $n$ to be an odd number.

For each bidder $i\in[n],$ we denote by $E_{i}$ the set of $n-1$ edges incident to vertex $i$ (the items available for him). Any possible valuation $v_{i}$ of any agent $i$ will be determined by a collection of subsets $S^{i}=\{S^{i}_{1},S^{i}_{2},\ldots,S^{i}_{\tau},\ldots,S^{i}_{t_{i}}\}$ of $E_{i},$ each subset of size $(n-1)/2.$ The value of an arbitrary set of items $X\subseteq E_{i}$ is $v_{i}(X)=1$ if $S^{i}_{\tau}\subseteq X$ for at least one $S^{i}_{\tau}\in S^{i},$ and $v_{i}(X)=0$ otherwise.

Any orientation of the set of edges in $E$ corresponds to a valid allocation of all items, i.e. to some partition $P=\{P^{1},P^{2},\ldots,P^{n}\}$ of $E$ with $P^{i}\subset E_{i}$ for every agent $i .$ In the rest of Subsection 3.1 we will only consider partitions that we call balanced, as defined next:

Definition 5.

A (valid) partition $P=\{P^{1},P^{2},\ldots,P^{n}\}$ of the item set $E$ among the $n$ agents is called a balanced partition if every agent $i$ receives exactly $(n-1)/2$ items from $E_{i};$ the respective edge-orientation with every vertex having the same in-degree $(n-1)/2$ is called a balanced orientation.

We use a set of balanced partitions $F=\{P_{s}\}_{s=1\ldots t}$ with the following crucial property:

Definition 6.

A (multi-)set $F=\{P_{s}\}_{s=1\ldots t},$ where every $P_{s}$ is a balanced partition $\{P^{1}_{s},P^{2}_{s},\ldots,P^{n}_{s}\}$ of the item set $E$ , has the $r$ -overlap property, if for every choice of $r$ players $i_{1}<i_{2}<\dots<i_{r}$ , and every choice of $r$ indices from $[t]$ , $1\leq s_{1},s_{2},\dots,s_{r}\leq t$ , such that no two are equal, there exists a pair of sets in $\{P^{i_{1}}_{s_{1}},P^{i_{2}}_{s_{2}},\ldots,P^{i_{r}}_{s_{r}}\},$ such that the two sets intersect.

Observe that the latter property of $F$ means that for every choice of $n$ pairwise different indices $s_{1},s_{2},\ldots,s_{n}$ there can only be strictly less than $r$ agents $i$ so that each of them receives (at least) the complete item set $P^{i}_{s_{i}}.$ We set $r=n^{\epsilon}$ , and show the following:

Lemma 7.

For every $\epsilon>0,$ and large enough $n>n(\epsilon)$ there exists a (multi-)set of balanced partitions $F=\{P_{s}\}_{s=1\ldots t}$ of size $|F|=t=\frac{1}{n}\cdot\left(\frac{4}{3}\right)^{\frac{n^{\epsilon}}{4}}$ with the $r$ -overlap property for $r=n^{\epsilon}.$

Proof.

Fix $\epsilon>0.$ We prove the existence of an appropriate $F$ by the probabilistic method: we define $t$ independent random balanced edge-orientations, and prove that the corresponding edge-partitions (allocations to the bidders) possess the $n^{\epsilon}$ -overlap property with nonzero probability.

The random construction goes as follows: We fix an arbitrary balanced orientation over $V=\{1,2,\ldots n\},$ e.g., choose the edge $(i,j)$ if $1\leq(j-i\mod n)\leq(n-1)/2$ and choose the edge $(j,i)$ if $(n-1)/2<(j-i\mod n)\leq n-1.$ The orientation $(i,j)$ means that bidder $j$ receives the item $\{i,j\}.$ Now, having such a directed graph fixed, we randomly permute the labels of the vertices $t$ times, which yields $t$ random balanced partitions, call them $\{\tilde{P}_{s}\}_{s=1\ldots t}.$

Fix arbitrary $r$ agents $i_{1}<i_{2}<\ldots<i_{r},$ and an arbitrary set of pairwise different indices $1\leq s_{1},s_{2},\dots,s_{r}\leq t.$ We upper bound the probability that the corresponding partition sets $\{\tilde{P}^{i_{1}}_{s_{1}},\tilde{P}^{i_{2}}_{s_{2}},\ldots,\tilde{P}^{i_{r}}% _{s_{r}}\}$ are pairwise disjoint.

Let $i,j\in\{i_{1},i_{2},\ldots,i_{r}\}$ be two of the selected agents, and slightly abusing notation, denote the partitions corresponding to these agents by $\tilde{P}_{s_{i}}$ and $\tilde{P}_{s_{j}}.$ We call $i$ and $j$ compatible if their own sets in the respective partitions are disjoint $\tilde{P}^{i}_{s_{i}}\cap\tilde{P}^{j}_{s_{j}}=\emptyset$ . Denote this event by $Y_{i,j}.$ Note that since $\tilde{P}^{i}_{s_{i}}\subset E_{i},$ and $\tilde{P}^{j}_{s_{j}}\subset E_{j},$ (edge orientations yield valid partitions), edge $\{i,j\}$ is the only possible item in $\tilde{P}^{i}_{s_{i}}\cap\tilde{P}^{j}_{s_{j}}.$ So, $i$ and $j$ are compatible exactly when either $\{i,j\}\not\in\tilde{P}^{i}_{s_{i}}$ according to the balanced partition $\tilde{P}_{s_{i}},$ or $\{i,j\}\not\in\tilde{P}^{j}_{s_{j}}$ according to the balanced partition $\tilde{P}_{s_{j}}.$ These are independent events, each of probability $1/2.$ Hence, $Pr[Y_{i,j}]=3/4$ for every pair of agents.

We define the undirected compatibility graph $H=(V^{\prime},E^{\prime})$ over the set of agents $V^{\prime}:=\{i_{1},i_{2},\ldots,i_{r}\}$ as vertices, and setting the edge $\{i,j\}\in E^{\prime}$ exactly when $i$ and $j$ are compatible. We upper bound the probability that $H$ is a clique $K_{r}$ of $r$ vertices, that is, the $\{\tilde{P}^{i_{1}}_{s_{1}},\tilde{P}^{i_{2}}_{s_{2}},\ldots,\tilde{P}^{i_{r}}% _{s_{r}}\}$ are pairwise disjoint. At first glance, it is a problem that $Y_{i,j}$ and $Y_{k,\ell}$ are not independent, if (and only if) $\{i,j\}\cap\{k,\ell\}\neq\emptyset.$ However, for any set of edges $\{i_{1},j_{1}\},\{i_{2},j_{2}\},\ldots,\{i_{\xi},j_{\xi}\}$ , it always holds that $Pr[Y_{i,j}\,|\,Y_{i_{1},j_{1}}\cap Y_{i_{2},j_{2}}\cap\ldots\cap Y_{i_{\xi},j_% {\xi}}]\leq 3/4$ (the condition that $i$ or $j$ is compatible with a couple of other agents – possibly because $\tilde{P}^{i}_{s_{i}}$ resp. $\tilde{P}^{j}_{s_{j}}$ does not include some item/edge – can only decrease the probability that $\tilde{P}^{i}_{s_{i}}$ or $\tilde{P}^{j}_{s_{j}}$ does not include item $\{i,j\}$ either). Thus, we can estimate the probability that $H$ is a complete graph by

Pr[H\,\cong\,K_{r}]\leq\left(\frac{3}{4}\right)^{r\choose 2}.

Using the union bound, we upper bound the probability of the bad event that $H$ is a complete graph for at least one choice of $r$ different players and $r$ different indices $1\leq s_{1},s_{2},\dots,s_{r}\leq t,$ meaning that $\{\tilde{P}_{s}\}_{s=1\ldots t}$ does not have the $n^{\epsilon}$ -overlap property:

Pr[\exists\,i_{1}<\ldots<i_{r}\,\text{and}\,1\leq s_{1},s_{2},\ldots,s_{r}\leq t% ,\,\text{so that}\,H\cong K_{r}]<t^{r}\cdot n^{r}\cdot\left(\frac{3}{4}\right)% ^{r\choose 2}<t^{r}n^{r}\left(\frac{3}{4}\right)^{\frac{r^{2}}{4}}.

The second inequality holds because $\frac{r^{2}-r}{2}\geq\frac{r^{2}}{4}$ for $r=n^{\epsilon}\geq 2.$ The probability that $F$ does not have the $r$ -overlap property is strictly less than $1$ if $t\leq\frac{1}{n}\cdot\left(\frac{4}{3}\right)^{\frac{r}{4}}=\frac{1}{n}\cdot% \left(\frac{4}{3}\right)^{\frac{n^{\epsilon}}{4}}.$

This concludes the proof, because the set of randomly generated partitions $\{\tilde{P}_{s}\}_{s=1\ldots t}$ has the $n^{\epsilon}$ -overlap property with positive probability, so there must exist at least one set of partitions $F=\{P_{s}\}_{s=1\ldots t}$ with the desired property. $\hfill\blacktriangleleft$

Having this construction of balanced partitions, one can show the following lower bound, using a reduction from approximate disjointness in a similar manner to the lower bound of [34] for general valuations.

Theorem 8 (General valuations, lower bound, simple graphs).

Any protocol approximating the combinatorial auction problem in simple graphs to a factor of $\,n^{1-\epsilon}\,$ for general (arbitrary monotone) agent valuations requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

Proof.

Assume that some protocol approximates the auction problem to a factor of $\,n^{1-\epsilon},\,$ where arbitrary normalized, monotone agent valuations are allowed. We claim that such a protocol can decide an arbitrary instance of the approximate disjointness problem for a set of players $N=[n],$ and a ground set $T=[t]$ for $t=\frac{1}{n}\cdot\left(\frac{4}{3}\right)^{\frac{n^{\epsilon}}{4}}.$

Let $\{B_{i}\}_{i\in[n]}$ be an instance of the approximate disjointness problem, where agent $i$ holds the set $B_{i}\subset[t]$ for every $i\in[n].$ We use the set $F=\{P_{s}\}_{s\in[t]}$ of balanced partitions that exist by Lemma 7, to define the valuation of each agent. The collection of subsets of items $S^{i}:=\{P^{i}_{s}\,|\,s\in B_{i}\}$ defines the valuation $v_{i}$ as follows: For an arbitrary set $X\subseteq E_{i}$ of items, let $v_{i}(X)=1$ if $P^{i}_{s}\subseteq X$ for at least one $s\in B_{i},$ i.e., for one of the given subsets in $S^{i},$ and let $v_{i}(X)=0$ otherwise.

Now, in case $s^{*}\in\bigcap_{i=1}^{n}B_{i}\neq\emptyset,$ a possible optimal allocation having social welfare $n,$ is to give each agent $i$ his own set $P^{i}_{s^{*}}$ from the partition $P_{s^{*}}$ that is an option for each of the agents. Since the protocol is $n^{1-\epsilon}$ -approximate, it will output an allocation having welfare of at least $n/n^{1-\epsilon}=n^{\epsilon}.$

In the other extreme case when the $B_{i}$ are pairwise disjoint, in every allocation $(X_{1},\allowbreak X_{2},\allowbreak\ldots,\allowbreak X_{n})$ every bidder $i$ with $v_{i}(X_{i})=1,$ completely receives some set, i.e., $P^{i}_{s_{i}}\subseteq X_{i}$ for some $s_{i}\in B_{i}$ (and the $s_{i}$ are different, because the $B_{i}$ are disjoint). However, there are no $n^{\epsilon}$ pairwise disjoint sets $P^{i}_{s_{i}}$ for any choice of $n^{\epsilon}$ different players and different associated indices $1\leq s_{1},s_{2},\dots,s_{n^{\epsilon}}\leq t$ because $F$ has the $n^{\epsilon}$ -overlap property. Thus, in this case any allocation can only achieve strictly less than $n^{\epsilon}$ total welfare. Consequently the auction protocol can distinguish between the two extreme cases of inputs for approximate disjointness. By the result of [1] such a protocol has communication complexity $\Omega(t/n^{4}),$ exponential in $n,$ which proves the theorem. $\hfill\blacktriangleleft$

3.2 k-partite Graphs

The following statement shows that there exist good maximal-in-range (MIR) mechanisms for bipartite, and more generally $k$ -partite multigraphs, with small approximation ratio.

Theorem 9 (General valuations, upper bound, $k$ -partite graphs).

There exists a deterministic $k$ -approximation polynomial-communication truthful mechanism for $k$ -partite multigraphs with general valuations.

Proof.

Consider a $k$ -partite multigraph $G=(V,E)$ , for which $V$ can be partitioned into sets $\{V_{d}\}_{d\in[k]}$ where each $V_{d}$ is an independent set of vertices. A mechanism selects the best of $k$ allocations: each allocation corresponding to assigning all items incident to $V_{d}$ to the players in $V_{d},$ and not allocating the other items. Each agent needs only to announce a single value. This is a maximal-in-range (MIR) mechanism and is truthful when using VCG payments. Its social welfare can be bounded below as follows:

\text{ALG}=\max_{1\leq d\leq k}\left\{\sum_{i\in V_{d}}{v_{i}(E_{i})}\right\}% \geq\frac{1}{k}\sum_{i}{v_{i}(E_{i})}\geq\frac{1}{k}\sum_{i}{v_{i}(O_{i})}=% \frac{1}{k}\text{OPT}.\

$\hfill\blacktriangleleft$

3.2.1 Lower Bound for $𝒌$ -partite Graphs

We prove a matching lower bound of $k$ in the case of poly-communication algorithms for combinatorial auctions in $k$ -partite (simple) graphs. We use the techniques of the lower bound proof for simple graphs, adapted to a complete $k$ -partite graph.

Consider a complete $k$ -partite graph $K_{n/k}=(V,E)$ , where $V=\cup_{d\in[k]}V_{d}$ and every part $V_{d}$ has $n^{\prime}:=n/k$ vertices/players. Assume for simplicity of presentation that $n^{\prime}$ is even. Every two vertices belonging to different parts are adjacent, whereas the $V_{d}$ are independent sets. In total, there are $n(n-n^{\prime})/2$ edges and every edge corresponds to an item that can be allocated to one of its two incident vertices. Let $E_{i}$ denote the set of edges incident to vertex $i .$ Any orientation of the edges in $E$ defines an allocation; we call the allocation strongly balanced, if for every $d\in[k],$ and every $i\not\in V_{d},$ exactly half of the edges between player $i$ and players in $V_{d}$ is allocated to $i .$

Let $\epsilon>0,$ and assume for contradiction that a protocol with approximation factor $k-\epsilon$ exists for the combinatorial auction problem. Roughly, we will show that there exists a large set $F$ of balanced allocations with the $\frac{n}{k-\epsilon}$ -overlap property of Definition 6. (Note that this property cannot hold for $\frac{n}{k}$ , since the $n/k$ vertices inside a part $V_{d}$ do not share any common edges and therefore their sets are pairwise disjoint in every allocation.) The valuations of the players will then be defined by subsets of $F,$ analogously to the simple graph case.

Let $\delta:=\frac{\epsilon}{k^{2}}.$ Simple counting yields that an arbitrary set of $\frac{n}{k-\epsilon}$ players must have more than $\delta n^{\prime}$ players in both of at least two different parts (say $V_{d}$ and $V_{d^{\prime}}$ ) of the graph partition. Otherwise it would hold that $\frac{n}{k-\epsilon}\leq n^{\prime}+(k-1)\delta n^{\prime}<n^{\prime}(1+% \epsilon/k)=n^{\prime}\frac{k+\epsilon}{k}<n^{\prime}\frac{k}{k-\epsilon}=% \frac{n}{k-\epsilon},$ a contradiction.

Thus, instead of proving the $\frac{n}{k-\epsilon}$ -overlap property, it is enough to show that an exponential set of allocations $F$ exists, where arbitrary subsets of $\delta n^{\prime}$ players from both of any two different parts $V_{d}$ and $V_{d^{\prime}}$ have overlapping sets in allocations of different indices from $[t].$ The rest of the proof is then analogous to the general (non $k$ -partite) case. We defer to the full version for the complete proofs. Next we define the suitable overlap property for this case:

Definition 10.

A (multi-)set $F=\{P_{s}\}_{s=1\ldots t},$ where every $P_{s}$ is a strongly balanced allocation $\{P^{1}_{s},P^{2}_{s},\ldots,P^{n}_{s}\}$ of the item set $E$ , has the $(r,r)$ -overlap property, if for arbitrary $d\neq d^{\prime}$ from $[k]$ and every choice of $2r$ players so that $\{i_{1},i_{2},\ldots,i_{r}\}\subset V_{d}$ and $\{i^{\prime}_{1},i^{\prime}_{2},\ldots,i^{\prime}_{r}\}\subset V_{d^{\prime}}$ and of $2r$ pairwise different indices from $[t]$ , $1\leq s_{1},s_{2},\dots,s_{r},s^{\prime}_{1},s^{\prime}_{2},\dots,s^{\prime}_{% r},\leq t$ , there exists a pair of sets $\{P^{i_{\tau}}_{s_{\tau}},P^{i^{\prime}_{\nu}}_{s^{\prime}_{\nu}}\},$ that intersect.

Lemma 11.

For every $\epsilon>0,$ and large enough $n>n(\epsilon)$ there exists a set of strongly balanced allocations $F=\{P_{s}\}_{s=1\ldots t}$ of size $|F|=t=\frac{1}{n}\cdot\left(\frac{2}{\sqrt{3}}\right)^{\epsilon n/k^{3}}$ with the $(r,r)$ -overlap property for $r=\delta n^{\prime}=\frac{\epsilon n}{k^{3}}.$

Theorem 12 (General valuations, lower bound, $k$ -partite graphs).

Any protocol approximating the combinatorial auction problem in $k$ -partite graphs to a factor of $\,k-\epsilon\,$ for some $\epsilon>0,$ for general (arbitrary monotone) agent valuations requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

In the case of bipartite graphs, we get a matching lower bound of $2 .$

Corollary 13.

Any protocol approximating the combinatorial auction problem in bipartite graphs to a factor of $\,2-\epsilon\,$ for general (arbitrary monotone) agent valuations requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

3.3 Graphs of Bounded Treewidth

We start the section with trees, the only graph class in this paper for which an exact optimal (and truthful) solution can be computable with polynomial communication. Then we briefly introduce graphs of treewidth $k$ and present a $(k+1)/2$ -approximate truthful (Maximal-In-Range) mechanism with polynomial communication for this generalization of trees. Finally we prove a nontrivial constant lower bound for graphs of treewidth $k .$ The lower bound is $5/4$ for $k=2$ and tends to 2 for $k\rightarrow\infty.$ It shows that we cannot extend the positive result about trees significantly.

3.3.1 VCG

Theorem 14 (General valuations, trees).

For general valuations on trees, there exists a polynomial-communication truthful mechanism for the combinatorial auction problem that finds the optimal solution.

Proof.

We describe how to implement the VCG mechanism on trees with polynomial communication. We root the tree at an arbitrary node and process it from the leaves to the root. Each node $v$ computes and announces the optimal welfare and allocation for its subtree in two cases: when the edge between $v$ and its parent is assigned to $v$ , and when it is assigned to its parent. This computation can be performed by $v$ – possibly in exponential time – given the values received from all its children. The root node, for which there is only one choice for the edge to its (non-existent) parent, then announces the optimal welfare and allocation for the entire tree. $\hfill\blacktriangleleft$

3.3.2 Truthful $\frac{k+1}{2}$ -Approximation for Graphs of Treewidth $𝒌$

Consider first $k$ -degenerate graphs. A graph $G(V,E)$ is called $k$ -degenerate [25] (or $k$ -inductive) if there is an ordering $v_{1},\dots,v_{n}$ of its nodes such that for every $i$ the number of neighbors of $v_{i}$ in $\{v_{i+1},\dots,v_{n}\}$ is at most $k$ . Observe now that every $k$ -degenerate $G$ is $(k+1)$ -colorable: we can simply color the vertices of $G$ greedily in the reversed order defined above. Therefore the MIR mechanism for $k$ -partite graphs is applicable, and we obtain:

Proposition 15 (General valuations, upper bound, $k$ -degenerate graphs).

There exists a deterministic $(k+1)$ -approximation polynomial-communication truthful mechanism for the combinatorial auction problem on $k$ -degenerate multigraphs with general valuations.

A special case of $k$ -degenerate graphs are $k$ -trees: a $k$ -tree is a $k$ -degenerate graph so that in the above vertex ordering every vertex $v_{i}$ (except for the last $k$ vertices) has exactly $k$ neighbors in $\{v_{i+1},\ldots v_{n}\}$ and these $k$ neighbors form a clique. It is easy to see that if we remove the vertices of arbitrary $(k-1)$ color-classes of the above greedy coloring of a $k$ -tree, the remaining subgraph is a tree: for every (remaining) vertex $v_{i}$ exactly one of its neighbors from $\{v_{i+1},\ldots,v_{n}\}$ has not been removed. So we can root the remaining graph at the highest indexed vertex and obtain a tree.

It is known [38, 8] that graphs of treewidth $k$ are exactly the subgraphs of $k$ -trees (also called partial $k$ -trees). For this special case we can use the exact protocol for trees (Theorem 14) to define a $\frac{k+1}{2}$ -approximate MIR mechanism:

Theorem 16 (General valuations, upper bound, graphs of treewidth $k$ ).

There exists a deterministic $\frac{k+1}{2}$ -approximation polynomial-communication truthful mechanism for graphs of treewidth $k$ with general valuations.

Proof.

Let $G(V,E)$ be the graph of treewidth $k$ of a given instance. Based on the definition as partial $k$ -trees, we take a $(k+1)$ -coloring of the complete $k$ -tree of which $G$ is a subgraph. The vertices of arbitrary two color classes of this coloring define a forest $F(V^{\prime},E^{\prime})\leq G(V,E),$ as observed above.

Assuming that the players in $V\setminus V^{\prime}$ are not allocated any items, first we allocate all the edges that connect a player in $V^{\prime}$ with a player in $V\setminus V^{\prime}$ to the respective players in $V^{\prime}.$ Subsequently we run the optimal protocol of Theorem 14 on the trees of the forest $F,$ with the only modification that the players in $V^{\prime}$ calculate with their marginal values of any edge set from $E^{\prime},$ i.e., with the understanding that they are assured to get all their incident edges adjacent to nodes in $V\setminus V^{\prime}.$

Finally, in an arbitrary fixed optimal allocation there are two color classes of players who receive welfare of at least $\frac{2}{(k+1)}OPT.$ Allocating to these players all edges adjacent to other color classes can just increase this welfare. Therefore, running the protocol for all pairs of color classes and choosing a solution with highest welfare yields a $(k+1)/2$ -approximation mechanism.

Note that the graph is fixed and the $(k+1)$ color classes can be fixed as well. The mechanism is Maximal-In-Range because it optimizes over all allocations that give items to players of only two color classes. $\hfill\blacktriangleleft$

3.3.3 Lower Bound for Graphs of Treewidth $𝒌$

We prove an approximation lower bound for poly-communication protocols for graphs of treewidth $k .$ The lower bound is

\alpha_{k}:=1+q-q^{k}\,\quad\text{for}\quad\,q=1/\sqrt[k-1]{k},

which yields $\alpha_{2}=5/4$ for graphs of treewidth 2, and $\alpha_{k}\rightarrow 2$ when $k$ tends to $\infty.$ ¹¹1Since $\,\lim_{k\rightarrow\infty}1/\sqrt[k-1]{k}=1,\,$ but $\,\lim_{k\rightarrow\infty}1/\sqrt[k-1]{k^{k}}=0.\,$ The graph used for the lower bound instance will be a complete bipartite graph having a small part with $k$ vertices and a large part with all other vertices. For simplicity of presentation we denote by $n$ the size of the large part (i.e., instead of $n-k$ ), and the graph by $K_{n,k}.$ Note that this graph has treewidth (actually pathwidth) $k .$

Before we prove the statement for general $k,$ we illustrate the proof idea by a sketch for the case of $K_{n,2}$ (see Figure 1). The proof is by a reduction from the (approximate) disjointness problem. Let player $I$ and player $I I$ be the two players in the small part of the bipartite graph and call them main players; the $n$ other players are called simple players. Each simple player $i\in[n]$ is only interested in getting both incident edges, for value $\frac{8}{3n}.$ For a single incident edge their valuation is $0 .$ Thus the total value that can be given to the simple players is $8/3$ , if $I$ and $I I$ get nothing. The sets of items/incident edges of the main players are $E_{I}$ and $E_{II},$ respectively. These edges are also incident to simple players, and in both $E_{I}$ and $E_{II}$ they are numbered by the corresponding adjacent simple player, so for simplicity we use the notation $E_{I}=E_{II}=[n].$

Figure 1: Graph of the lower-bound instance for treewidth 2, with main players

I

and

I I,

and

n

simple players.

As in the previous proofs, an index set $[t]$ exponential in $n,$ and a collection $F=\{P_{s}\}_{s=1..t}$ will be used. However, here each $P_{s}$ is just a subset $P_{s}\subset[n]$ of size $n/2.$ The valuation of the main players $I$ and ${II}$ will be determined by subsets of the index set $B_{I},B_{II}\subseteq[t]$ like before: for $X\subset[n]$ we have $v_{I}(X)=1$ if $P_{s}\subseteq X$ for at least one $s\in B_{I}$ and analogously for player ${II}.$ Observe that here players $I$ and ${II}$ do not compete for the same items and the more item indices they have in common, the more welfare is available for the simple players. In particular, if some $s^{*}\in B_{I}\cap B_{II},$ then the allocation $X_{I}=X_{II}=P_{s^{*}}$ results in total welfare $2+\frac{1}{2}\cdot\frac{8}{3}=\frac{10}{3}.$

On the other hand, ( $F$ will be defined so that) if $s_{1}\neq s_{2},$ then $|\,\overline{P_{s_{1}}}\cap\overline{P_{s_{2}}}\,|\,\approx\,n/4.$ So, if $B_{I}\cap B_{II}=\emptyset,$ then the simple players get only about $\frac{1}{4}\cdot\frac{8}{3}$ welfare, and the total welfare is $2+\frac{2}{3}=\frac{8}{3}.$ Thus any algorithm with approximation factor less than $5/4$ could decide whether $B_{I}\cap B_{II}=\emptyset,$ and consequently it needs exponential communication by [1]. (The value $8/3$ of the simple players is tuned so that even if $B_{I}\cap B_{II}=\emptyset$ holds, giving both $I$ and ${II}$ value $1$ is no worse option than rather giving more items to simple players.)

For general $k\geq 2,$ we use a parameter $p\in(0,1)$ for the size of the desired subsets $P_{s}$ to be $p n$ , and also use the notation $q=1-p.$ We need the following type of covering property:²²2Assume for simplicity that $pn\in\mathbb{N}.$

Definition 17.

Let $2\leq k<n,\,\,p\in(0,1),\,\,q=1-p,$ and $\epsilon>0.$ Let $F=\{P_{s}\}_{s=1\ldots t},$ be a set system over $[n],$ i.e. $P_{s}\subset[n]$ for every $s\in[t].$ We say that $F$ is a uniform $(p,k,\epsilon)$ -cover, or simply uniform cover if $|P_{s}|=pn\,(\forall s\in[t]),$ and for every choice of pairwise different indices $\,\,1\leq s_{1},s_{2},\ldots s_{k}\leq t\,\,$ it holds that

$\blacksquare$

$|\bigcap_{i=1}^{j}\,\overline{P_{s_{i}}}|<(1+\epsilon)\cdot q^{j}\cdot n\quad$ for every $2\leq j\leq k,$ and
$\blacksquare$

$|\bigcap_{i=1}^{k}\,\overline{P_{s_{i}}}|>(1-\epsilon)\cdot q^{k}\cdot n.$

The next lemma shows that large uniform covers exist.

Lemma 18.

For every $k,\,p\in(0,1),\,\epsilon>0$ and large enough $n$ there exists a uniform cover of size $|F|=t=e^{\frac{q^{k}\cdot n\cdot\epsilon^{2}}{3k}}/{k^{\frac{1}{k}}}.$

Proof.

We use the probabilistic method to prove the existence of an appropriate $F .$ We pick $t$ independent random subsets $P_{s}\subset[n],$ each of size $n p .$ For example, consider $t$ random permutations of $[n]$ and pick the first $n p$ elements of each. It is enough to show that the probability of $F$ not being a uniform cover is less than $1,$ then at least one uniform cover of the desired size $t$ must exist.

Let first a choice of $k$ pairwise different indices $1\leq s_{1},s_{2},\ldots,s_{k}\leq k$ be fixed. For any given $j\in\{2,\ldots,k\},$ and given element $i\in[n]$ we have

Pr[\,i\in\cap_{i=1}^{j}\,\overline{P_{s_{i}}}\,]=(1-p)^{j}=q^{j}.

If $Y^{j}_{i}$ denotes the random variable that takes value $1$ if $i\in\cap_{i=1}^{j}\,\overline{P_{s_{i}}},$ and value $0$ otherwise, then $\sum_{i\in[n]}Y^{j}_{i}=|\cap_{i=1}^{j}\,\overline{P_{s_{i}}}|,$ and this sum has expectation $q^{j}\cdot n.$ Using the Chernoff-bound, it holds that

Pr[|\cap_{i=1}^{j}\,\overline{P_{s_{i}}}|\geq(1+\epsilon)\cdot q^{j}\cdot n]=% Pr[\sum_{i\in[n]}Y^{j}_{i}\geq(1+\epsilon)\cdot q^{j}\cdot n]\leq e^{-\frac{q^% {j}\cdot n\cdot\epsilon^{2}}{3}}\leq e^{-\frac{q^{k}\cdot n\cdot\epsilon^{2}}{% 3}}.

By the union bound, the probability of this bad event to occur for at least one $j\in\{2,\ldots,k\}$ is less than $(k-1)e^{-\frac{q^{k}\cdot n\cdot\epsilon^{2}}{3}}.$ In addition, the probability that $|\cap_{i=1}^{k}\,\overline{P_{s_{i}}}|$ happens to be ’too small’ can be bounded as

Pr[\sum_{i\in[n]}Y^{k}_{i}\leq(1-\epsilon)\cdot q^{k}\cdot n]\leq e^{-\frac{q^% {k}\cdot n\cdot\epsilon^{2}}{2}}\leq e^{-\frac{q^{k}\cdot n\cdot\epsilon^{2}}{% 3}}.

Finally, the probability that any of these occur for at least one choice of $k$ different indices from $[t]$ , is strictly bounded by $t^{k}\cdot k\cdot e^{-\frac{q^{k}\cdot n\cdot\epsilon^{2}}{3}}.$ Note that if none of these bad events occur for any $s_{1},s_{2},\ldots s_{k}\in[t],$ then the random $F$ is a uniform $(p,k,\epsilon)$ -cover, as required. This occurs with positive probability, if $t\leq\sqrt[k]{e^{\frac{q^{k}\cdot n\cdot\epsilon^{2}}{3}}/{k}}.$ $\hfill\blacktriangleleft$

Now for a parameter $p,$ and some arbitrary small $\epsilon>0,$ fix a uniform cover set system $F=\{P_{s}\}_{s=1\ldots t}$ of exponential size $t .$ The graph for which we obtain the approximation lower bound is the complete bipartite graph $K_{n,k}.$ Analogously to the $K_{n,2}$ case, we have $k$ main players, with their incident edges indexed by the $n$ adjacent vertices from the large part of the graph, and each of whose valuations $v^{j}\,\,$ for $j=1\ldots k,$ will be defined by some subset $B_{j}\subset[t],$ so that $v^{j}(X)=1$ if $P_{s}\subseteq X$ for at least one $s\in B_{j}$ and $0$ otherwise. We also have $n$ simple players, each of whom has value $v_{i}=w/n$ if they get all $k$ incident edges, and $0$ otherwise. Thus $w$ denotes the total value of simple players for all the edges. The parameters $w$ and $q=1-p$ will be set later.

Now consider an instance $\{B_{j}\subset[t]\,|\,j\in[k]\}$ of the approximate disjointness problem. Assume first, that $s^{*}\in\cap_{j=1}^{k}B_{j}.$ Then all main players can obtain their edge set of indices in $P_{s^{*}}\subset[n].$ Since $|P_{s^{*}}|=pn,$ there remain $q n$ simple players, who can obtain all of their incident edges. The total welfare in this case is $SW_{OPT}^{1}=k+qn\cdot w/n=k+qw.$

In the other extreme case the sets $B_{j}$ are pairwise disjoint. The next technical claim will imply that if $w\leq k/(1-q^{k})$ then also in this case of disjoint $B_{j},$ the welfare is maximized iff every main player receives a desired set of value $1 .$

Claim 19.

The function $\gamma(x):=x+w\cdot q^{x}$ is convex, and over the interval $x\in[0,k]$ it has its maximum at $x=k$ assuming that $w<k/(1-q^{k}).$

Proof.

For the derivatives of $\gamma$ we obtain $\gamma^{\prime}(x)=1+w\cdot\ln q\cdot q^{x}\,$ and $\gamma^{\prime\prime}(x)=w\cdot\ln^{2}q\cdot q^{x}.\,$ Since (for positive $w$ ) $\gamma^{\prime\prime}(x)>0,$ the function $\gamma(x)$ is convex and has no local maxima. On the interval $x\in[0,k]$ it takes its maximum in one of the endpoints $x=0$ or $x=k.$ We get that $\gamma(0)=w<k+w\cdot q^{k}=\gamma(k),$ where the inequality holds by the assumption on $w .$ $\hfill\vartriangleleft$

Now if the $B_{j}$ sets of the main players are pairwise disjoint, then main players with welfare $1$ get item sets $P_{s_{j}}$ with different indices. The uniform cover property of $F$ implies that if all $k$ main players get a set of value $1,$ then the total welfare of the players can be more than $k+(1-\epsilon)\cdot w\cdot q^{k};$ on the other hand, if $j<k$ players get value $1$ then the welfare is less than $j+(1+\epsilon)\cdot w\cdot q^{j}.$ By Claim 19

j+(1+\epsilon)\cdot w\cdot q^{j}<k+(1-\epsilon)\cdot w\cdot q^{k},

if $\epsilon>0$ is small enough and $w<k/(1-q^{k}).$ Therefore for the optimal welfare of all players in the second extreme case holds

k+(1-\epsilon)q^{k}\cdot w\leq SW^{2}_{OPT}\leq k+(1+\epsilon)q^{k}\cdot w.

The goal is to obtain a high lower bound by maximizing the ratio $SW^{1}_{OPT}/SW^{2}_{OPT}=(k+wq)/(k+w(1+\epsilon)\cdot q^{k}).$ For every fixed $q\in(0,1),$ the ratio is maximized if $w$ is as large as possible. By setting $w=(1-\epsilon)k/(1-q^{k}),$ and taking $\epsilon\rightarrow 0,$ we get

\frac{SW^{1}_{OPT}}{SW^{2}_{OPT}}\,\longrightarrow\,\frac{k+\frac{kq}{1-q^{k}}% }{k+\frac{kq^{k}}{1-q^{k}}}\,=\,1-q^{k}+q.

The latter ratio takes its maximum value in $q=1/\sqrt[k-1]{k}.$ Any protocol with approximation ratio better than this maximum value $\alpha_{k}$ could distinguish the two extreme cases of an arbitrary instance $\{B_{j}\,|\,j\in[k]\}$ of approximate disjointness, and needs therefore $\Omega({t}/{k^{4}})$ communication, that is exponential in $n .$ We summarize our result:

Theorem 20 (General valuations, lower bound, treewidth $k$ graphs).

Any protocol approximating the combinatorial auction problem in graphs of treewidth $k$ to a factor better than $\alpha_{k}:=1+q-q^{k},$ where $q=(1/k)^{1/(k-1)},$ needs exponential communication. The lower bound is $\alpha_{2}=5/4$ for graphs of treewidth $2,$ and $\alpha_{k}\rightarrow 2$ for $k\rightarrow\infty.$

It is an intriguing open problem, whether an approximation lower bound linear in $k$ exists, based on some more refined graph construction.

4 Subadditive Valuations

In this section, we study the communication complexity of combinatorial auctions in graphs and $k$ -hypergraphs with subadditive bidders. Then, we show that it is possible to achieve $k$ -approximation for $k$ -hypergraphs and $2$ -approximation for multigraphs, using a deterministic MIR (and thus truthful) mechanism (Theorem 21). Finally, we prove a matching lower bound of $2$ for simple graphs, by using the construction of the lower bound for general valuations (Theorem 23).

4.1 Upper Bound

We present here a truthful mechanism that is $k$ -approximate for $k$ -hypergraphs within polynomial communication.

Theorem 21 (Subadditive, upper bound, $k$ -hypergraphs).

There exists a deterministic $k$ -approximate polynomial-communication truthful mechanism for $k$ -hypergraphs with subadditive valuations.

Proof.

Let $I_{e}$ be the set of agents in an edge $e$ . The mechanism works as follows: for each edge, arbitrarily enumerate the agents it contains from $1$ to $|I_{e}|$ . Then, assign all items to the agents with label $1$ . Name this allocation $a_{1}$ . Repeat this process for $j=2,3,\dots,k$ by cyclically assigning each edge to all of the agents with label $j$ ( or $j\mod|I_{e}|,$ in case $|I_{e}|<k$ ). This results in $k$ consistent full allocations. Keep the one achieving maximum social welfare. Name the allocations as $a_{1},a_{2}\dots a_{k}$ . Let $X_{i}^{j}$ be the bundle that player $i$ gets in $a_{j}$ .

\text{ALG}=\max_{j}\left\{\sum_{i}{v_{i}(X_{i}^{j})}\right\}\geq\frac{1}{k}% \sum_{i}\sum_{j}{v_{i}(X_{i}^{j})}\geq\frac{1}{k}\sum_{i}{v_{i}(E_{i})}\geq% \frac{1}{k}\sum_{i}v_{i}(O_{i})=\frac{1}{k}\text{OPT}.

The first inequality holds because maximum is larger than the average, the second one is due to subadditivity and the last one due to monotonicity. Communication cost is polynomial in size, because each agent reports only $k$ values. It is also truthful, because it is maximal-in-range. $\hfill\blacktriangleleft$

In the case of $k=2$ , we get the following corollary.

Corollary 22 (Subadditive, upper bound, multigraphs).

There exists a deterministic 2-approximation polynomial-communication truthful mechanism for multigraphs with subadditive valuations.

4.2 Lower Bound

In this section, we show a lower bound of $2$ for the combinatorial auction problem in simple graphs. This matches the upper bound presented in Corollary 22, closing the gap up to the case of multigraphs. We use the construction of Theorem 8 and transform the valuations to subadditive by adding $1$ to every $v_{i}(X)$ , similarly to the lower bound proof of [18] for subadditive valuations.

Theorem 23 (Subadditive, lower bound, simple graphs).

Any protocol approximating the combinatorial auction problem in simple graphs to a factor of $\,2-\epsilon\,$ for subadditive agent valuations, requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

5 XOS Valuations

In this section, we extend the deterministic (in terms of communication) protocol for two XOS players of Feige [26] to multigraphs, getting a $4/3$ -approximation algorithm. In the case of $k$ -hypergraphs, we show an approximation of $\frac{1}{1-(1-\frac{1}{k})^{k}}$ , by an adaptation of the XOS $n$ -player protocol [26, 27]. We complement these positive results with matching lower bounds, using clique instances in simple graphs and $k$ -hypergraphs. Due to space limitations, proofs and protocol definitions are deferred to the full version of the paper.

5.1 Upper Bounds

Consider the configuration LP, where $x_{i,S}$ is the fractional assignment of the bundle $S$ to agent $i$ :

Maximize $\sum_{i,S}x_{i,S}v_{i}(S)$ , subject to:

$\blacksquare$

Item constraints: $\sum_{i,S\mid j\in S}x_{i,S}\leq 1$ for every item $j;$
$\blacksquare$

Player constraints: $\sum_{S}x_{i,S}\leq 1$ for every player $i;$
$\blacksquare$

Non-negativity constraints: $x_{i,S}\geq 0$ for every player $i$ and every bundle $S .$

This LP can be solved in polynomial time by solving its dual LP [7, 34], using the ellipsoid method and having access to a separation oracle. In the protocols in [26, 27] for XOS valuations, each agent $i$ selects a single tentative set based on the distribution $(x_{i,S})_{S}$ , where $x$ is a solution of the configuration LP. Each item $j$ can be part of the tentative sets of multiple different agents. The challenge is to handle these conflicts in order to round the fractional solution. When the input of the combinatorial auction is a graph (or $k$ -hypergraph), then there exists a solution $x$ for which every item $j$ belongs to at most 2 (or $k$ ) tentative sets (see Proposition 24). This observation allows us to get improved bounds by modifying existing protocols for XOS valuations.

Proposition 24.

For every agent $i$ , let $E_{i}$ denote the set of (hyper-)edges incident with $i .$ There exists an optimal fractional solution $x^{\prime}$ of the configuration LP so that $x^{\prime}_{i,S}>0$ only if $S\subseteq E_{i}.$

Proof.

Let $x$ be a fractional solution having optimal welfare, without having the required property. We show that, starting from $x,$ we can produce a fractional solution $x^{\prime}$ of equal welfare, and with the desired property. Assume that $x_{i,S}>0$ and $v_{i}(\{j\})=0$ for some $j\in S$ . Set $x_{i,S}^{\prime}=0,$ and $x_{i,S\setminus\{j\}}^{\prime}=x_{i,S\setminus\{j\}}+x_{i,S}$ . Solution $x^{\prime}$ achieves a welfare that is equal to the one of solution $x$ : because $v_{i}$ is XOS and thus subadditive, $v_{i}(S)\leq v_{i}(S\setminus\{j\})+v_{i}(\{j\})=v_{i}(S\setminus\{j\});$ and due to monotonicity, $v_{i}(S\setminus\{j\})\leq v_{i}(S).$ Moreover, $x^{\prime}$ also continues to satisfy the constraints of the configuration LP. Applying the argument iteratively, yields the proof of the proposition. $\hfill\blacktriangleleft$

Technically, when the tentative set $S_{i}$ of bidder $i$ contains items from outside $E_{i},$ then these items can be simply ignored, and w.l.o.g. assume that $i$ does not compete for them. Alternatively, the respective $x_{i,S}$ variables for $S\nsubseteq E_{i}$ (and thus the corresponding dual constraints) can be omitted from the LP to obtain a simplified configuration LP.

The algorithm that achieves $4/3$ approximation in multigraphs, is a straightforward generalization of the 2-player 2-step randomized rounding algorithm of Feige [26] for XOS valuations. In particular, consider the following algorithm (see the full version for details), which uses the optimal fractional solution $x$ of the (simplified) configuration LP. For each player $i$ and item $j\in E_{i},$ we denote the total fraction of subsets containing $j$ and allocated to $i,$ by

f_{i,j}=\sum_{S|j\in S}x_{i,S}.

(1)

This is the probability that $j$ will be in the tentative set $S_{i}$ of bidder $i .$ For each item $j$ , we have $\sum_{i}f_{i,j}\leq 1$ due to the item constraints. If both of the candidate players (say, e.g., bidders $1$ and $2$ ) have the item $j$ in their tentative sets, then the item is assigned to them with reversed probabilities, i.e., with $\frac{f_{2,j}}{f_{1,j}+f_{2,j}}$ to bidder $1$ and with $\frac{f_{1,j}}{f_{1,j}+f_{2,j}}$ to bidder 2.

Theorem 25 (XOS, upper bound, multigraphs).

There exists a deterministic $4/3$ -approximate algorithm for the combinatorial auction problem in multigraphs with XOS valuations.

Generalizing for the case when at most $k$ dedicated players can get any particular item, we extend the Fair Contention Resolution rounding scheme of [27] and get an upper bound $\frac{1}{1-(1-\frac{1}{k})^{k}}$ for XOS bidders in $k$ -hypergraphs. By Proposition 24, we can assume that the candidate tentative sets of player $i$ (sets for which $x_{i,S}>0$ ) only include items for which he has a positive valuation. For the sake of completeness, we present the modified Fair Contention Resolution protocol of [27] for the case of $k$ -hypergraphs in the full version. The tentative sets $S_{i}$ of the players are determined by an optimal LP solution like for $k=2$ above. Also the $f_{i,j}$ probabilities for single items to get into $S_{i}$ are defined by equation (1). The contention resolution procedure is a (nontrivial) generalization of the $k=2$ case.

Theorem 26 (XOS, upper bound, $k$ -hypergraphs).

There exists a deterministic $\frac{1}{1-(1-\frac{1}{k})^{k}}$ - approximate algorithm for the combinatorial auction problem in $k$ -hypergraphs with XOS valuations.

5.2 Lower Bound

In the following theorem we present a matching lower bound for the case of $k$ -hypergraphs.

Theorem 27 (XOS, lower bound, $k$ -hypergraphs).

Any protocol approximating the combinatorial auction problem in $k$ -hypergraphs with XOS valuations to a factor of $\frac{1}{1-(1-\frac{1}{k})^{k}}-\epsilon$ requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

The result above implies the following corollary in the case of simple graphs.

Corollary 28 (XOS, lower bound, simple graphs).

Any protocol approximating the combinatorial auction problem in simple graphs with XOS valuations to a factor of $\frac{4}{3}-\epsilon$ requires exponential communication. This lower bound also applies for randomized and nondeterministic settings.

References

[1] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999. doi:10.1006/JCSS.1997.1545.
[2] Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. In EC, pages 1268–1286. ACM, 2024. doi:10.1145/3670865.3673582.
[3] Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Graph orientation to maximize the minimum weighted outdegree. Int. J. Found. Comput. Sci., 22(3):583–601, 2011. doi:10.1142/S0129054111008246.
[4] Yuichi Asahiro, Eiji Miyano, and Hirotaka Ono. Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discret. Appl. Math., 159(7):498–508, 2011. doi:10.1016/J.DAM.2010.11.003.
[5] Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 653–661. SIAM, 2021. doi:10.1137/1.9781611976465.40.
[6] Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg. Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions. SIAM J. Comput., 51(3):20–75, 2022. doi:10.1137/20M1370021.
[7] Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions. In EC, pages 29–43. ACM, 2005. doi:10.1145/1064009.1064013.
[8] Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In Timo Lepistö and Arto Salomaa, editors, Automata, Languages and Programming, pages 105–118, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. doi:10.1007/3-540-19488-6_110.
[9] Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer, and Chris Umans. Inapproximability for vcg-based combinatorial auctions. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 518–536. SIAM, 2010.
[10] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 473–488, 2023. doi:10.1145/3580507.3597764.
[11] George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Truthful allocation in graphs and hypergraphs. In ICALP, volume 198 of LIPIcs, pages 56:1–56:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.56.
[12] George Christodoulou, Elias Koutsoupias, and Annamária Kovács. A proof of the Nisan-Ronen conjecture. In STOC, pages 672–685. ACM, 2023. doi:10.1145/3564246.3585176.
[13] Edward H Clarke. Multipart pricing of public goods. Public choice, pages 17–33, 1971.
[14] Amit Daniely, Michael Schapira, and Gal Shahaf. Inapproximability of truthful mechanisms via generalizations of the vc dimension. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 401–408, 2015. doi:10.1145/2746539.2746597.
[15] Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 89–103. Springer, 2007. doi:10.1007/978-3-540-74208-1_7.
[16] Shahar Dobzinski. Computational efficiency requires simple taxation. In FOCS, pages 209–218. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.30.
[17] Shahar Dobzinski and Noam Nisan. Limitations of vcg-based mechanisms. Comb., 31(4):379–396, 2011. doi:10.1007/S00493-011-2528-4.
[18] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 610–618, 2005. doi:10.1145/1060590.1060681.
[19] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 644–652, 2006. doi:10.1145/1132516.1132607.
[20] Shahar Dobzinski and Michael Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1064–1073, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109675.
[21] Shahar Dobzinski and Jan Vondrák. The computational complexity of truthfulness in combinatorial auctions. In EC, pages 405–422. ACM, 2012. doi:10.1145/2229012.2229044.
[22] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1107–1116, 2012. doi:10.1145/2213977.2214076.
[23] Shahar Dobzinski and Jan Vondrák. Impossibility results for truthful combinatorial auctions with submodular valuations. J. ACM, 63(1):5:1–5:19, 2016. doi:10.1145/2786754.
[24] Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62–80, 2014. doi:10.1007/S00453-012-9668-9.
[25] Paul Erdős and András Hajnal. On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar, 17(61-99):1, 1966.
[26] Uriel Feige. On maximizing welfare when utility functions are subadditive. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 41–50, 2006. doi:10.1145/1132516.1132523.
[27] Uriel Feige and Jan Vondrák. Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In FOCS, pages 667–676. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.14.
[28] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617–631, 1973.
[29] Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 47(1):104–123, 2004. doi:10.1016/S0899-8256(03)00184-2.
[30] Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. Almost envy-free allocation of indivisible goods: A tale of two valuations. arXiv preprint arXiv:2407.05139, 2024. doi:10.48550/arXiv.2407.05139.
[31] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
[32] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM (JACM), 58(6):1–24, 2011. doi:10.1145/2049697.2049699.
[33] Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo. A note on graph balancing problems with restrictions. Inf. Process. Lett., 110(1):24–29, 2009. doi:10.1016/J.IPL.2009.09.015.
[34] Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. J. Econ. Theory, 129(1):192–224, 2006. doi:10.1016/J.JET.2004.10.007.
[35] Christos Papadimitriou, Michael Schapira, and Yaron Singer. On the hardness of being truthful. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 250–259. IEEE, 2008. doi:10.1109/FOCS.2008.54.
[36] Frederick V. Qiu and S. Matthew Weinberg. Settling the communication complexity of vcg-based mechanisms for all approximation guarantees. In STOC, pages 1192–1203. ACM, 2024. doi:10.1145/3618260.3649706.
[37] Shiri Ron, Clayton Thomas, S. Matthew Weinberg, and Qianfan Zhang. Communication separations for truthful auctions: Breaking the two-player barrier. In FOCS, pages 386–405. IEEE, 2024. doi:10.1109/FOCS61266.2024.00032.
[38] Donald J Rose. On simple characterizations of k-trees. Discrete mathematics, 7(3-4):317–322, 1974. doi:10.1016/0012-365X(74)90042-9.
[39] José Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. J. Sched., 17(4):371–383, 2014. doi:10.1007/S10951-013-0359-4.
[40] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8–37, 1961.
[41] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209–213, 1979. doi:10.1145/800135.804414.
[42] Jinghan A Zeng and Ruta Mehta. On the structure of envy-free orientations on graphs. arXiv preprint arXiv:2404.13527, 2024. doi:10.48550/arXiv.2404.13527.
[43] Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of EFX allocations on graphs: Goods, chores and mixed manna. In IJCAI, pages 3049–3056. ijcai.org, 2024. URL: https://www.ijcai.org/proceedings/2024/338.

[bib.bib1] [1] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999. doi:10.1006/JCSS.1997.1545.

[bib.bib2] [2] Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. In EC, pages 1268–1286. ACM, 2024. doi:10.1145/3670865.3673582.

[bib.bib3] [3] Yuichi Asahiro, Jesper Jansson, Eiji Miyano, and Hirotaka Ono. Graph orientation to maximize the minimum weighted outdegree. Int. J. Found. Comput. Sci., 22(3):583–601, 2011. doi:10.1142/S0129054111008246.

[bib.bib4] [4] Yuichi Asahiro, Eiji Miyano, and Hirotaka Ono. Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discret. Appl. Math., 159(7):498–508, 2011. doi:10.1016/J.DAM.2010.11.003.

[bib.bib5] [5] Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 653–661. SIAM, 2021. doi:10.1137/1.9781611976465.40.

[bib.bib6] [6] Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg. Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions. SIAM J. Comput., 51(3):20–75, 2022. doi:10.1137/20M1370021.

[bib.bib7] [7] Liad Blumrosen and Noam Nisan. On the computational power of iterative auctions. In EC, pages 29–43. ACM, 2005. doi:10.1145/1064009.1064013.

[bib.bib8] [8] Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In Timo Lepistö and Arto Salomaa, editors, Automata, Languages and Programming, pages 105–118, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. doi:10.1007/3-540-19488-6_110.

[bib.bib9] [9] Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer, and Chris Umans. Inapproximability for vcg-based combinatorial auctions. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 518–536. SIAM, 2010.

[bib.bib10] [10] George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 473–488, 2023. doi:10.1145/3580507.3597764.

[bib.bib11] [11] George Christodoulou, Elias Koutsoupias, and Annamária Kovács. Truthful allocation in graphs and hypergraphs. In ICALP, volume 198 of LIPIcs, pages 56:1–56:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.56.

[bib.bib12] [12] George Christodoulou, Elias Koutsoupias, and Annamária Kovács. A proof of the Nisan-Ronen conjecture. In STOC, pages 672–685. ACM, 2023. doi:10.1145/3564246.3585176.

[bib.bib13] [13] Edward H Clarke. Multipart pricing of public goods. Public choice, pages 17–33, 1971.

[bib.bib14] [14] Amit Daniely, Michael Schapira, and Gal Shahaf. Inapproximability of truthful mechanisms via generalizations of the vc dimension. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 401–408, 2015. doi:10.1145/2746539.2746597.

[bib.bib15] [15] Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 89–103. Springer, 2007. doi:10.1007/978-3-540-74208-1_7.

[bib.bib16] [16] Shahar Dobzinski. Computational efficiency requires simple taxation. In FOCS, pages 209–218. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.30.

[bib.bib17] [17] Shahar Dobzinski and Noam Nisan. Limitations of vcg-based mechanisms. Comb., 31(4):379–396, 2011. doi:10.1007/S00493-011-2528-4.

[bib.bib18] [18] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 610–618, 2005. doi:10.1145/1060590.1060681.

[bib.bib19] [19] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 644–652, 2006. doi:10.1145/1132516.1132607.

[bib.bib20] [20] Shahar Dobzinski and Michael Schapira. An improved approximation algorithm for combinatorial auctions with submodular bidders. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1064–1073, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109675.

[bib.bib21] [21] Shahar Dobzinski and Jan Vondrák. The computational complexity of truthfulness in combinatorial auctions. In EC, pages 405–422. ACM, 2012. doi:10.1145/2229012.2229044.

[bib.bib22] [22] Shahar Dobzinski and Jan Vondrák. From query complexity to computational complexity. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1107–1116, 2012. doi:10.1145/2213977.2214076.

[bib.bib23] [23] Shahar Dobzinski and Jan Vondrák. Impossibility results for truthful combinatorial auctions with submodular valuations. J. ACM, 63(1):5:1–5:19, 2016. doi:10.1145/2786754.

[bib.bib24] [24] Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62–80, 2014. doi:10.1007/S00453-012-9668-9.

[bib.bib25] [25] Paul Erdős and András Hajnal. On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar, 17(61-99):1, 1966.

[bib.bib26] [26] Uriel Feige. On maximizing welfare when utility functions are subadditive. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 41–50, 2006. doi:10.1145/1132516.1132523.

[bib.bib27] [27] Uriel Feige and Jan Vondrák. Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In FOCS, pages 667–676. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.14.

[bib.bib28] [28] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617–631, 1973.

[bib.bib29] [29] Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 47(1):104–123, 2004. doi:10.1016/S0899-8256(03)00184-2.

[bib.bib30] [30] Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. Almost envy-free allocation of indivisible goods: A tale of two valuations. arXiv preprint arXiv:2407.05139, 2024. doi:10.48550/arXiv.2407.05139.

[bib.bib31] [31] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.

[bib.bib32] [32] Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM (JACM), 58(6):1–24, 2011. doi:10.1145/2049697.2049699.

[bib.bib33] [33] Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo. A note on graph balancing problems with restrictions. Inf. Process. Lett., 110(1):24–29, 2009. doi:10.1016/J.IPL.2009.09.015.

[bib.bib34] [34] Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. J. Econ. Theory, 129(1):192–224, 2006. doi:10.1016/J.JET.2004.10.007.

[bib.bib35] [35] Christos Papadimitriou, Michael Schapira, and Yaron Singer. On the hardness of being truthful. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 250–259. IEEE, 2008. doi:10.1109/FOCS.2008.54.

[bib.bib36] [36] Frederick V. Qiu and S. Matthew Weinberg. Settling the communication complexity of vcg-based mechanisms for all approximation guarantees. In STOC, pages 1192–1203. ACM, 2024. doi:10.1145/3618260.3649706.

[bib.bib37] [37] Shiri Ron, Clayton Thomas, S. Matthew Weinberg, and Qianfan Zhang. Communication separations for truthful auctions: Breaking the two-player barrier. In FOCS, pages 386–405. IEEE, 2024. doi:10.1109/FOCS61266.2024.00032.

[bib.bib38] [38] Donald J Rose. On simple characterizations of k-trees. Discrete mathematics, 7(3-4):317–322, 1974. doi:10.1016/0012-365X(74)90042-9.

[bib.bib39] [39] José Verschae and Andreas Wiese. On the configuration-lp for scheduling on unrelated machines. J. Sched., 17(4):371–383, 2014. doi:10.1007/S10951-013-0359-4.

[bib.bib40] [40] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8–37, 1961.

[bib.bib41] [41] Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209–213, 1979. doi:10.1145/800135.804414.

[bib.bib42] [42] Jinghan A Zeng and Ruta Mehta. On the structure of envy-free orientations on graphs. arXiv preprint arXiv:2404.13527, 2024. doi:10.48550/arXiv.2404.13527.

[bib.bib43] [43] Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of EFX allocations on graphs: Goods, chores and mixed manna. In IJCAI, pages 3049–3056. ijcai.org, 2024. URL: https://www.ijcai.org/proceedings/2024/338.

The Communication Complexity of Combinatorial Auctions in Graphs

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Contributions

General Valuations.

Subadditive Valuations.

XOS Valuations.

1.2 Related Work

Non-Truthful Protocols.

Truthful Protocols.

Lower Bounds.

Graph Model.

2 Preliminaries

Auction Setting in Graphs

Mechanism Design

Definition 1.

Definition 2.

Definition 3.

Communication Complexity

Proposition 4.

3 General Valuations

Approximate Disjointness Problem.

3.1 Lower Bound 𝒏 for General Graphs

Balanced allocations in simple graphs

Definition 5.

Definition 6.

Lemma 7.

Proof.

Theorem 8 (General valuations, lower bound, simple graphs).

Proof.

3.2 k-partite Graphs

Theorem 9 (General valuations, upper bound, k-partite graphs).

Proof.

3.2.1 Lower Bound for 𝒌-partite Graphs

Definition 10.

Lemma 11.

Theorem 12 (General valuations, lower bound, k-partite graphs).

Corollary 13.

3.3 Graphs of Bounded Treewidth

3.3.1 VCG

Theorem 14 (General valuations, trees).

Proof.

3.3.2 Truthful 𝒌+𝟏𝟐-Approximation for Graphs of Treewidth 𝒌

Proposition 15 (General valuations, upper bound, k-degenerate graphs).

Theorem 16 (General valuations, upper bound, graphs of treewidth k).

Proof.

3.3.3 Lower Bound for Graphs of Treewidth 𝒌

Definition 17.

Lemma 18.

Proof.

Claim 19.

Proof.

Theorem 20 (General valuations, lower bound, treewidth k graphs).

4 Subadditive Valuations

4.1 Upper Bound

Theorem 21 (Subadditive, upper bound, k-hypergraphs).

Proof.

Corollary 22 (Subadditive, upper bound, multigraphs).

4.2 Lower Bound

Theorem 23 (Subadditive, lower bound, simple graphs).

5 XOS Valuations

5.1 Upper Bounds

Proposition 24.

Proof.

Theorem 25 (XOS, upper bound, multigraphs).

Theorem 26 (XOS, upper bound, k-hypergraphs).

5.2 Lower Bound

Theorem 27 (XOS, lower bound, k-hypergraphs).

Corollary 28 (XOS, lower bound, simple graphs).

References

3.1 Lower Bound $𝒏$ for General Graphs

Theorem 9 (General valuations, upper bound, $k$ -partite graphs).

3.2.1 Lower Bound for $𝒌$ -partite Graphs

Theorem 12 (General valuations, lower bound, $k$ -partite graphs).

3.3.2 Truthful $\frac{k+1}{2}$ -Approximation for Graphs of Treewidth $𝒌$

Proposition 15 (General valuations, upper bound, $k$ -degenerate graphs).

Theorem 16 (General valuations, upper bound, graphs of treewidth $k$ ).

3.3.3 Lower Bound for Graphs of Treewidth $𝒌$

Theorem 20 (General valuations, lower bound, treewidth $k$ graphs).

Theorem 21 (Subadditive, upper bound, $k$ -hypergraphs).

Theorem 26 (XOS, upper bound, $k$ -hypergraphs).

Theorem 27 (XOS, lower bound, $k$ -hypergraphs).