An official website of the United States government
We study combinatorial auctions with interdependent valuations, where each agent i has a private signal sithat captures her private information and the valuation function of every agent depends on the entire signal profile, [Formula: see text]. The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive-compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations; and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d. Funding: A. Eden was partially supported by NSF Award IIS-2007887, the European Research Council (ERC) under the European Union's Seventh Framework Programme [FP7/2007-2013]/ERC Grant Agreement 337122, by the Israel Science Foundation [Grant 317/17], and by an Amazon research award. M. Feldman received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program [Grant Agreement 866132], by the Israel Science Foundation [Grant 317/17], by an Amazon research award, and by the NSF-BSF [Grant 2020788]. The work of K. Goldner was supported partially by NSF awards DMS-1903037 and CNS-2228610 and a Shibulal Family Career Development Professorship. A. R. Karlin was supported by the NSF-CCF [Grant 1813135].
more »
« less
Constant Approximation for Private Interdependent Valuations
The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $$s_1, \ldots, s_n$$ of the $$n$$ bidders and public valuation functions $$v_i(s_1, \ldots, s_n)$$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and \emph{private valuations}, and established $$O(\log^2 n)$$-approximation for SOS valuations. In this paper we show that this setting admits a {\em constant} factor approximation, settling the open question raised by Eden et al. (2022).
more »
« less
- Award ID(s):
- 2228610
- PAR ID:
- 10485406
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
- ISBN:
- 979-8-3503-1894-4
- Page Range / eLocation ID:
- 148 to 163
- Format(s):
- Medium: X
- Location:
- Santa Cruz, CA, USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The word problem for a finite set of ground identities is known to be decidable in polynomial time using congruence closure, and this is also the case if some of the function symbols are assumed to be commutative or defined by certain shallow identities, called strongly shallow. We show that decidability in P is preserved if we add the assumption that certain function symbolsfareextensionalin the sense that$$f(s_1,\ldots ,s_n) \mathrel {\approx }f(t_1,\ldots ,t_n)$$ implies$$s_1 \mathrel {\approx }t_1,\ldots ,s_n \mathrel {\approx }t_n$$ . In addition, we investigate a variant of extensionality that is more appropriate for commutative function symbols, but which raises the complexity of the word problem to coNP.more » « less
-
The Nash social welfare problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents' valuations. We give an overview of the constant-factor approximation algorithm for the problem when agents have Rado valuations [Garg et al. 2021]. Rado valuations are a common generalization of the assignment (OXS) valuations and weighted matroid rank functions. Our approach also gives the first constant-factor approximation algorithm for the asymmetric Nash social welfare problem under the same valuations, provided that the maximum ratio between the weights is bounded by a constant.more » « less
-
The problem of reliable/secure all-to-all communication over low-degree networks has been essential for communication-local (CL) n-party MPC (i.e., MPC protocols where every party directly communicates only with a few, typically polylogarithmic in n, parties) and more recently for communication over ad hoc networks, which are used in blockchain protocols. However, a limited number of adaptively secure solutions exist, and they all make relatively strong assumptions on the ability of parties to act in some specific manner before the adversary can corrupt them. Two such assumptions were made in the work of Chandran et al. [ITCS ’15]—parties can (a) multisend messages to several receivers simultaneously; and (b) securely erase the message and the identities of the receivers, before the adversary gets a chance to corrupt the sender (even if a receiver is corrupted). A natural question to ask is: Are these assumptions necessary for adaptively secure CL MPC? In this paper, we characterize the feasibility landscape for all-to-all reliable message transmission (RMT) under these two assumptions, and use this characterization to obtain (asymptotically) tight feasibility results for CL MPC. First, we prove a strong impossibility result for a broad class of RMT protocols, termed here store-and-forward protocols, which includes all known communication protocols for CL MPC from standard cryptographic assumptions. Concretely, we show that no such protocol with a certain expansion rate can tolerate a constant fraction of parties being corrupted. Next, under the assumption of only a PKI, we show that assuming secure erasures, we can obtain an RMT protocol between all pairs of parties with polylogarithmic locality (even without assuming multisend) for the honest majority setting. We complement this result by showing a negative result for the setting of dishonest majority. Finally, and somewhat surprisingly, under stronger assumptions (i.e., trapdoor permutations with a reverse domain sampler, and compact and malicious circuit-private FHE), we construct a polylogarithmic-locality all-to-one RMT protocol, which is adaptively secure and tolerates any constant fraction of corruptions, without assuming either secure erasures or multisend. This last result uses a novel combination of adaptively secure (e.g., non-committing) encryption and (static) FHE to bypass the impossibility of compact adaptively secure FHE by Katz et al. [PKC’13], which we believe may be of independent interest. Intriguingly, even such assumptions do not allow reducing all-to-all RMT to all-to-one RMT (a reduction which is trivial in the non-CL setting). Still, we can implement what we call sublinear output-set RMT (SOS-RMT for short). We show how SOS-RMT can be used for SOS-MPC under the known bounds for feasibility of MPC in the standard (i.e., non-CL) setting assuming, in addition to SOS-RMT, an anonymous PKI.more » « less
-
Guruswami, Venkatesan (Ed.)We study two recent combinatorial contract design models, which highlight different sources of complexity that may arise in contract design, where a principal delegates the execution of a costly project to others. In both settings, the principal cannot observe the choices of the agent(s), only the project’s outcome (success or failure), and incentivizes the agent(s) using a contract, a payment scheme that specifies the payment to the agent(s) upon a project’s success. We present results that resolve open problems and advance our understanding of the computational complexity of both settings. In the multi-agent setting, the project is delegated to a team of agents, where each agent chooses whether or not to exert effort. A success probability function maps any subset of agents who exert effort to a probability of the project’s success. For the family of submodular success probability functions, Dütting et al. [2023] established a poly-time constant factor approximation to the optimal contract, and left open whether this problem admits a PTAS. We answer this question on the negative, by showing that no poly-time algorithm guarantees a better than 0.7-approximation to the optimal contract. For XOS functions, they give a poly-time constant approximation with value and demand queries. We show that with value queries only, one cannot get any constant approximation. In the multi-action setting, the project is delegated to a single agent, who can take any subset of a given set of actions. Here, a success probability function maps any subset of actions to a probability of the project’s success. Dütting et al. [2021a] showed a poly-time algorithm for computing an optimal contract for gross substitutes success probability functions, and showed that the problem is NP-hard for submodular functions. We further strengthen this hardness result by showing that this problem does not admit any constant factor approximation. Furthermore, for the broader class of XOS functions, we establish the hardness of obtaining a n^{-1/2+ε}-approximation for any ε > 0.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/FOCS57990.2023.00018
