skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

Title: On Simultaneous Two-Player Combinatorial Auctions
We consider the following communication problem: Alice and Bob each have some valuation functions $v_1(\cdot)$ and $v_2(\cdot)$ over subsets of $m$ items, and their goal is to partition the items into $S, \bar{S}$ in a way that maximizes the welfare, $v_1(S) + v_2(\bar{S})$. We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with $poly(m)$ communication, a tight 3/4-approximation is known for both [Fei06,DS06]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and $\log m$ additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: 1) There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least $3/4$ of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. 2) For all $\varepsilon > 0$, any simultaneous, randomized protocol that decides whether the welfare of the optimal partition is $\geq more » 1$ or $\leq 3/4 - 1/108+\varepsilon$ correctly with probability $> 1/2 + 1/ poly(m)$ requires exponential communication. This provides a separation between the attainable approximation guarantees via interactive ($3/4$) versus simultaneous ($\leq 3/4-1/108$) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. We further discuss the implications of our results for the design of truthful combinatorial auctions in general, and extensions to general XOS valuations. In particular, our protocol for the allocation problem implies a new style of truthful mechanisms. « less
Authors:
; ;
Award ID(s):
1717899
Publication Date:
NSF-PAR ID:
10069456
Journal Name:
Symposium on Discrete Algorithms
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)
    Stefano Leonardi (Ed.)
    We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m1−є that uses poly(m,n) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation with poly(m,n) communication is known. This proves the first gap between computationally efficientmore »deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.« less
  2. ; ; ; ; ( , Forum of Mathematics, Sigma)
    Abstract A bipartite graph $H = \left (V_1, V_2; E \right )$ with $\lvert V_1\rvert + \lvert V_2\rvert = n$ is semilinear if $V_i \subseteq \mathbb {R}^{d_i}$ for some $d_i$ and the edge relation E consists of the pairs of points $(x_1, x_2) \in V_1 \times V_2$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $d_1 + d_2$ variables for some s . We show that for a fixed k , the number of edges in a $K_{k,k}$ -free semilinear H is almost linear in n , namely $\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$ for any $\varepsilon> 0$ ; and more generally, $\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$ for a $K_{k, \dotsc ,k}$ -free semilinear r -partite r -uniform hypergraph. As an application, we obtain the following incidence bound: given $n_1$ points and $n_2$ open boxes with axis-parallel sides in $\mathbb {R}^d$ such that their incidence graph is $K_{k,k}$ -free, there can be at most $O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching uppermore »and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o -minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).« less
  3. ; ( , Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)
    We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that theremore »are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975031.120« less
  4. ; ( , 34th Symposium on Theoretical Aspects of Computer Science)
    We revisit the much-studied problem of space-efficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixed-sized cliques and cycles, obtaining a number of new upper and lower bounds. For the important special case of counting triangles, we give a $4$-pass, $(1\pm\varepsilon)$-approximate, randomized algorithm that needs at most $\widetilde{O}(\varepsilon^{-2}\cdot m^{3/2}/T)$ space, where $m$ is the number of edges and $T$ is a promised lower bound on the number of triangles. This matches the space bound of a very recent algorithm (McGregor et al., PODS 2016), with an arguably simpler and more general technique. We give an improved multi-pass lower bound of $\Omega(\min\{m^{3/2}/T, m/\sqrt{T}\})$, applicable at essentially all densities $\Omega(n) \le m \le O(n^2)$. We also prove other multi-pass lower bounds in terms of various structural parameters of the input graph. Together, our results resolve a couple of open questions raised in recent work (Braverman et al., ICALP 2013). Our presentation emphasizes more general frameworks, for both upper and lower bounds. We give a sampling algorithm for counting arbitrary subgraphs and then improve it via combinatorial means in the special cases of counting odd cliques and odd cycles. Our results show that these problemsmore »are considerably easier in the cash-register streaming model than in the turnstile model, where previous work had focused (Manjunath et al., ESA 2011; Kane et al., ICALP 2012). We use Tur{\'a}n graphs and related gadgets to derive lower bounds for counting cliques and cycles, with triangle-counting lower bounds following as a corollary.« less
  5. ; ; ; ; ; ( , 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020)
    We consider the classical Minimum Balanced Cut problem: given a graph $G$, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first {\em deterministic, almost-linear time} approximation algorithm for this problem. Specifically, our algorithm, given an $n$-vertex $m$-edge graph $G$ and any parameter $1\leq r\leq O(\log n)$, computes a $(\log m)^{r^2}$-approximation for Minimum Balanced Cut on $G$, in time $O\left ( m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$. In particular, we obtain a $(\log m)^{1/\epsilon}$-approximation in time $m^{1+O(1/\sqrt{\epsilon})}$ for any constant $\epsilon$, and a $(\log m)^{f(m)}$-approximation in time $m^{1+o(1)}$, for any slowly growing function $m$. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of $G$ that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an $n$-vertex graph is $n^{o(1)}$, thusmore »resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in $n$ factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.« less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email