1,720,982 research outputs found
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
Full text linkWe consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations
Towards a Characterization of Worst Case Equilibria in the Discriminatory Price Auction
Full text linkWe study the performance of the discriminatory price auction under the uniform bidding interface, which is one of the popular formats for running multi-unit auctions in practice. We undertake an equilibrium analysis with the goal of characterizing the inefficient mixed equilibria that may arise in such auctions. We consider bidders with capped-additive valuations, which is in line with the bidding format, and we first establish a series of properties that help us understand the sources of inefficiency. Moving on, we then use these results to derive new lower and upper bounds on the Price of Anarchy of mixed equilibria. For the case of two bidders, we arrive at a complete characterization of inefficient equilibria and show an upper bound of 1.1095, which is also tight. For multiple bidders, we show that the Price of Anarchy is strictly worse, improving the best known lower bound for submodular valuations. We further present an improved upper bound of 4/3 for the special case where there exists a “high” demand bidder. Finally, we also study Bayes-Nash equilibria, and exhibit a separation result that had been elusive so far. Namely, already with two bidders, the Price of Anarchy for Bayes-Nash equilibria is strictly worse than that for mixed equilibria. Such separation results are not always true (e.g., the opposite is known for simultaneous second price auctions) and reveal that the Bayesian model here introduces further inefficiency
Distributional Robustness: From Pricing to Auctions
Full text linkRobust mechanism design is a rising alternative to Bayesian mechanism design,
which yields designs that do not rely on assumptions like full distributional
knowledge. We apply this approach to mechanisms for selling a single item,
assuming that only the mean of the value distribution and an upper bound on the
bidder values are known. We seek the mechanism that maximizes revenue over the
worst-case distribution compatible with the known parameters. Such a mechanism
arises as an equilibrium of a zero-sum game between the seller and an adversary
who chooses the distribution, and so can be referred to as the max-min
mechanism.
Carrasco et al. [2018] derive the max-min pricing when the seller faces a
single bidder for the item. We go from max-min pricing to max-min auctions by
studying the canonical setting of two i.i.d. bidders, and show the max-min
mechanism is the second-price auction with a randomized reserve. We derive a
closed-form solution for the distribution over reserve prices, as well as the
worst-case value distribution, for which there is simple economic intuition. In
fact we derive a closed-form solution for the reserve price distribution for
any number of bidders.
Our technique for solving the zero-sum game is quite different than that of
Carrasco et al.- it involves analyzing a discretized version of the setting,
then refining the discretization grid and deriving a closed-form solution for
the non-discretized, original setting. Our results establish a difference
between the case of two bidders and that of bidders
MAC Advice for Facility Location Mechanism Design
Full text linkAlgorithms with predictions have attracted much attention in the last years
across various domains, including variants of facility location, as a way to
surpass traditional worst-case analyses. We study the -facility location
mechanism design problem, where the agents are strategic and might
misreport their location.
Unlike previous models, where predictions are for the optimal facility
locations, we receive predictions for the locations of each of the agents.
However, these predictions are only "mostly" and "approximately" correct (or
MAC for short) -- i.e., some -fraction of the predicted locations are
allowed to be arbitrarily incorrect, and the remainder of the predictions are
allowed to be correct up to an -error. We make no assumption on
the independence of the errors. Can such predictions allow us to beat the
current best bounds for strategyproof facility location?
We show that the -median (geometric median) of a set of points is
naturally robust under corruptions, which leads to an algorithm for
single-facility location with MAC predictions. We extend the robustness result
to a "balanced" variant of the facilities case. Without balancedness, we
show that robustness completely breaks down, even for the setting of
facilities on a line. For this "unbalanced" setting, we devise a truthful
random mechanism that outperforms the best known result of Lu et al. [2010],
which does not use predictions. En route, we introduce the problem of "second"
facility location (when the first facility's location is already fixed). Our
findings on the robustness of the -median and more generally -medians may
be of independent interest, as quantitative versions of classic breakdown-point
results in robust statistics
Bayesian Persuasion under Ex Ante and Ex Post Constraints
No full textBayesian persuasion, as introduced by Kamenica and Gentzkow in 2011, is the study of information sharing policies among strategic agents. A prime example is signaling in online ad auctions: what information should a platform signal to an advertiser regarding a user when selling the opportunity to advertise to her? Practical considerations such as preventing discrimination, protecting privacy or acknowledging limited attention of the information receiver impose constraints on information sharing. We propose a simple way to mathematically model such constraints as restrictions on Receiver's admissible posterior beliefs. We consider two families of constraints - ex ante and ex post; the latter limits each instance of Sender-Receiver communication, while the former more general family can also pose restrictions in expectation. For the ex ante family, a result of Doval and Skreta (2018) establishes the existence of an optimal signaling scheme with a small number of signals - at most the number of constraints plus the number of states of nature - and we show this result is tight. For the ex post family, we tighten the previous bound of Vølund (2018), showing that the required number of signals is at most the number of states of nature, as in the original Kamenica-Gentzkow setting. As our main algorithmic result, we provide an additive bi-criteria FPTAS for an optimal constrained signaling scheme assuming a constant number of states of nature; we improve the approximation to single-criteria under a Slater-like regularity condition. The FPTAS holds under standard assumptions, and more relaxed assumptions yield a PTAS. We then establish a bound on the ratio between Sender's optimal utility under convex ex ante constraints and the corresponding ex post constraints. We demonstrate how this result can be applied to find an approximately welfare-maximizing constrained signaling scheme in ad auctions
Oblivious Rounding and the Integrality Gap
Full text linkThe following paradigm is often used for handling NP-hard combinatorial optimization problems. One first formulates the problem as an integer program, then one relaxes it to a linear program (LP, or more generally, a convex program), then one solves the LP relaxation in polynomial time, and finally one rounds the optimal LP solution, obtaining a feasible solution to the original problem. Many of the commonly used rounding schemes (such as randomized rounding, threshold rounding and others) are "oblivious" in the sense that the rounding is performed based on the LP solution alone, disregarding the objective function. The goal of our work is to better understand in which cases oblivious rounding suffices in order to obtain approximation ratios that match the integrality gap of the underlying LP. Our study is information theoretic - the rounding is restricted to be oblivious but not restricted to run in polynomial time. In this information theoretic setting we characterize the approximation ratio achievable by oblivious rounding. It turns out to equal the integrality gap of the underlying LP on a problem that is the closure of the original combinatorial optimization problem. We apply our findings to the study of the approximation ratios obtainable by oblivious rounding for the maximum welfare problem, showing that when valuation functions are submodular oblivious rounding can match the integrality gap of the configuration LP (though we do not know what this integrality gap is), but when valuation functions are gross substitutes oblivious rounding cannot match the integrality gap (which is 1)
Incentivizing Quality Text Generation via Statistical Contracts
Full text linkWhile the success of large language models (LLMs) increases demand for
machine-generated text, current pay-per-token pricing schemes create a
misalignment of incentives known in economics as moral hazard: Text-generating
agents have strong incentive to cut costs by preferring a cheaper model over
the cutting-edge one, and this can be done "behind the scenes" since the agent
performs inference internally. In this work, we approach this issue from an
economic perspective, by proposing a pay-for-performance, contract-based
framework for incentivizing quality. We study a principal-agent game where the
agent generates text using costly inference, and the contract determines the
principal's payment for the text according to an automated quality evaluation.
Since standard contract theory is inapplicable when internal inference costs
are unknown, we introduce cost-robust contracts. As our main theoretical
contribution, we characterize optimal cost-robust contracts through a direct
correspondence to optimal composite hypothesis tests from statistics,
generalizing a result of Saig et al. (NeurIPS'23). We evaluate our framework
empirically by deriving contracts for a range of objectives and LLM evaluation
benchmarks, and find that cost-robust contracts sacrifice only a marginal
increase in objective value compared to their cost-aware counterparts.Comment: Comments are welcom
When Are Welfare Guarantees Robust?
Full text linkComputational and economic results suggest that social welfare maximization and combinatorial auction design are much easier when bidders' valuations satisfy the "gross substitutes" condition. The goal of this paper is to evaluate rigorously the folklore belief that the main take-aways from these results remain valid in settings where the gross substitutes condition holds only approximately. We show that for valuations that pointwise approximate a gross substitutes valuation (in fact even a linear valuation), optimal social welfare cannot be approximated to within a subpolynomial factor and demand oracles cannot be simulated using a subexponential number of value queries. We then provide several positive results by imposing additional structure on the valuations (beyond gross substitutes), using a more stringent notion of approximation, and/or using more powerful oracle access to the valuations. For example, we prove that the performance of the greedy algorithm degrades gracefully for near-linear valuations with approximately decreasing marginal values; that with demand queries, approximate welfare guarantees for XOS valuations degrade gracefully for valuations that are pointwise close to XOS; and that the performance of the Kelso-Crawford auction degrades gracefully for valuations that are close to various subclasses of gross substitutes valuations
Multi-Channel Bayesian Persuasion
Full text linkThe celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We propose a model that smoothly interpolates between the two, by introducing a natural multi-channel communication structure in which each receiver observes a subset of the sender’s communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable.
Our main result is a complete characterization specifying when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure M₁ is (weakly) better than M₂ if and only if every information-dominating pair of receivers in M₁ is also such in M₂. This result holds in the most general model of Bayesian persuasion in which receivers may have externalities - that is, the receivers' actions affect each other. The proof is cryptographic-inspired and it has a close conceptual connection to secret sharing protocols.
As a surprising consequence of the main result, the sender can implement private Bayesian persuasion (which is the best communication structure for the sender) for k receivers using only O(log k) communication channels, rather than k channels in the naive implementation. We provide an implementation that matches the information-theoretical lower bound on the number of channels - not only asymptotically, but exactly. Moreover, the main result immediately implies some results of [Kerman and Tenev, 2021] on persuading receivers arranged in a network such that each receiver observes both the signals sent to him and to his neighbours in the network.
We further provide an additive FPTAS for an optimal sender’s signaling scheme when the number of states of nature is constant, the sender has an additive utility function and the graph of the information-dominating pairs of receivers is a directed forest. We focus on a constant number of states, as even for the special case of public persuasion and additive sender’s utility, it was shown by [Shaddin Dughmi and Haifeng Xu, 2017] that one can achieve neither an additive PTAS nor a polynomial-time constant-factor optimal sender’s utility approximation (unless P=NP). We leave for future research studying exact tractability of forest communication structures, as well as generalizing our result to more families of sender’s utility functions and communication structures.
Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is computationally hard for a general family of sender’s utility functions - separable supermajority functions, which are specified by choosing a partition of the set of receivers and summing supermajority functions corresponding to different elements of the partition, multiplied by some non-negative constants. Note that one can easily deduce from [Emir Kamenica and Matthew Gentzkow, 2011] and [Itai Arieli and Yakov Babichenko, 2019] that finding an optimal signaling scheme for such utility functions is computationally tractable for both public and private persuasion. This difference illustrates both the conceptual and the computational hardness of general multi-channel persuasion
- …
