SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Fair and Truthful Mechanisms for Dichotomous Valuations

2021-05-18
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.
View PDF Chat

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models

2020-07-09
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown.
View PDF Chat

Fair and Truthful Mechanisms for Dichotomous Valuations

2020-02-25
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.

Fair-Share Allocations for Agents with Arbitrary Entitlements

2021-07-18
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) … We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. The AnyPrice share of an agent is the value she can guarantee to herself if she is given a budget equal to her entitlement, and she buys her highest value affordable set when items are adversarially priced with a total price equal to the total entitlements. Even for the equal entitlements case, this notion is new, and satisfies APS ≥ MMS, where the inequality is sometimes strict. We also present an alternative definition for the APS as a maximization problem (a fractional version of the MMS), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a 3/5-fraction of her APS. This algorithm can also be viewed as providing a strategy in a certain natural bidding game, and this strategy secures each agent that uses it at least a 3/5-fraction of her APS, regardless of the strategies used by other agents.
View PDF Chat

Prophets and Secretaries with Overbooking

2018-06-11
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the l-out-of- k setting, where the decision maker can select up to k elements immediately and irrevocably, but her performance is measured by the top l elements in the selected set. Equivalently, the decision makes can hold up to l elements at any given point in time, but can make up to k-l returns as new elements arrive. We give upper and lower bounds on the competitive ratio of l-out-of- k prophet and secretary scenarios. For l-out-of- k prophet scenarios we provide a single-sample algorithm with competitive ratio 1-l· e-Θ((k-l)2/k) . The algorithm is a single-threshold algorithm, which sets a threshold that equals the (l+k/2)th highest sample, and accepts all values exceeding this threshold, up to reaching capacity k . On the other hand, we show that this result is tight if the number of possible returns is linear in l (i.e., k-l =Θ(l)). In particular, we show that no single-sample algorithm obtains a competitive ratio better than 1 - 2-(2k+1)/k+1 . We also present a deterministic single-threshold algorithm for the 1-out-of- k prophet setting which obtains a competitive ratio of 1-3/2 · e-s/k 6, knowing only the distribution of the maximum value. This result improves the result of [Assaf & Samuel-Cahn, J. of App. Prob., 2000].
View PDF Chat

On Best-of-Both-Worlds Fair-Share Allocations

2022-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
View PDF Chat

Combinatorial Contracts

2022-02-01
Paul Dütting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.
View PDF Chat

A General Framework for Endowment Effects in Combinatorial Markets

2020-07-09
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been traditionally studied mainly using experimental … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been traditionally studied mainly using experimental methodology. Recently, Babaioff, Dobzinski and Oren (2018) proposed a specific formulation of the endowment effect in combinatorial markets, and showed that the existence of Walrasian equilibrium with respect to the endowed valuations (referred to as endowment equilibrium) extends from gross substitutes to submodular valuations, but provably fails to extend to more general valuations, like XOS.
View PDF Chat

Pricing Multi-unit Markets

2018-01-01
Tomer Ezra , Michal Feldman , Tim Roughgarden +1 more
View PDF Chat

Pricing Multi-Unit Markets

2019-11-30
Tomer Ezra , Michal Feldman , Tim Roughgarden +1 more
We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction … We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer's information and agents' valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices.
View PDF Chat

On a Competitive Secretary Problem with Deferred Selections

2021-08-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes … We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. We introduce a novel multi-agent secretary model, in which the competition is explicit. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
View PDF Chat

“Who is Next in Line?” On the Significance of Knowing the Arrival Order in Bayesian Online Settings

2023-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in … We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far.We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.* This work is supported by Science and Technology Innovation 2030 –"New Generation of Artificial Intelligence" Major Project No.(2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 866132), by the Israel Science Foundation (grant number 317/17), by an Amazon Research Award, and by the NSF-BSF (grant number 2020788). Tomer Ezra was partially supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets" and MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets". Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.
View PDF Chat

Pricing Identical Items.

2017-05-18
Tomer Ezra , Michal Feldman , Tim Roughgarden +1 more

Complement-Free Couples Must Communicate: A Hardness Result for Two-Player Combinatorial Auctions

2018-01-01
Tomer Ezra , Michal Feldman , Eric Neyman +2 more
We study the communication complexity of welfare maximization in combinatorial auctions with $m$ items and two subadditive bidders. A $\frac{1}{2}$-approximation can be guaranteed by a trivial randomized protocol with zero … We study the communication complexity of welfare maximization in combinatorial auctions with $m$ items and two subadditive bidders. A $\frac{1}{2}$-approximation can be guaranteed by a trivial randomized protocol with zero communication, or a trivial deterministic protocol with $O(1)$ communication. We show that outperforming these trivial protocols requires exponential communication, settling an open question of [DobzinskiNS10, Feige09]. Specifically, we show that any (randomized) protocol guaranteeing a $(\frac{1}{2}+\frac{6}{\log_2 m})$-approximation requires communication exponential in $m$. This is tight even up to lower-order terms: we further present a $(\frac{1}{2}+\frac{1}{O(\log m)})$-approximation in poly($m$) communication. To derive our results, we introduce a new class of subadditive functions that are "far from" fractionally subadditive functions, and may be of independent interest for future works. Beyond our main result, we consider the spectrum of valuations between fractionally-subadditive and subadditive via the MPH hierarchy. Finally, we discuss the implications of our results towards combinatorial auctions with strategic bidders.

Secretary Matching with General Arrivals

2020-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with arbitrary weights that … We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with arbitrary weights that are unknown from the outset, and are revealed online. Under vertex arrival, vertices arrive online in a uniformly random order; upon the arrival of a vertex $v$, the weights of edges from $v$ to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. Under edge arrival, edges arrive online in a uniformly random order; upon the arrival of an edge $e$, its weight is revealed, and the algorithm decides whether to include it in the matching or not. We provide a $5/12$-competitive algorithm for vertex arrival, and show it is tight. For edge arrival, we provide a $1/4$-competitive algorithm. Both results improve upon state of the art bounds for the corresponding settings. Interestingly, for vertex arrival, secretary matching in general graphs outperforms secretary matching in bipartite graphs with 1-sided arrival, where $1/e$ is the best possible guarantee.

Fair-Share Allocations for Agents with Arbitrary Entitlements

2023-10-26
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves … We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves as an attractive fairness criterion for which, to qualify as fair, an allocation needs to give every agent at least a substantial fraction of the agent’s MMS. In this paper, we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new and satisfies [Formula: see text], for which the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem) and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a [Formula: see text] - fraction of the agent’s APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a [Formula: see text] - fraction of the agent’s APS. Funding: T. Ezra’s research is partially supported by the European Research Council Advanced [Grant 788893] AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets.” U. Feige’s research is supported in part by the Israel Science Foundation [Grant 1122/22].
View PDF Chat

Fair and Truthful Mechanisms for Dichotomous Valuations

2020-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.
View PDF Chat

Fair Division with Interdependent Values

2023-01-01
Georgios Birmpas , Tomer Ezra , Stefano Leonardi +1 more
We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set of goods that needs … We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set of goods that needs to be allocated to a set of agents (without disposal). Each agent is given a private signal, and his valuation function depends on the signals of all agents. Without the use of payments, there are strong impossibility results for designing strategyproof allocation mechanisms even in settings without interdependent values. Therefore, we turn to design mechanisms that always admit equilibria that are fair with respect to their true signals, despite their potentially distorted perception. To do so, we first extend the definitions of pure Nash equilibrium and well-studied fairness notions in literature to the interdependent setting. We devise simple allocation mechanisms that always admit a fair equilibrium with respect to the true signals. We complement this result by showing that, even for very simple cases with binary additive interdependent valuation functions, no allocation mechanism that always admits an equilibrium, can guarantee that all equilibria are fair with respect to the true signals.
View PDF Chat

A General Framework for Endowment Effects in Combinatorial Markets

2019-03-27
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with respect to a single item. Babaioff et al. [EC'18] took a first step at extending this study beyond a single item. They proposed a specific formulation of the endowment effect in combinatorial settings, and showed that equilibrium existence with respect to the endowed valuations extends from gross substitutes to submodular valuations, but provably fails to extend to XOS valuations. Extending the endowment effect to combinatorial settings can take different forms. In this work, we devise a framework that captures a space of endowment effects, upon which we impose a partial order, which preserves endowment equilibrium existence. Within this framework, we provide existence and welfare guarantees for endowment equilibria corresponding to various endowment effects. Our main results are the following: (1) For markets with XOS valuations, we introduce an endowment effect that is stronger than that of Babaioff et al., for which an endowment equilibrium is guaranteed to exist and gives at least half of the optimal welfare. Moreover, this equilibrium can be reached via a variant of the flexible ascent auction. (2) For markets with arbitrary valuations, we show that bundling leads to a sweeping positive result. In particular, if items can be prepacked into indivisible bundles, there always exists an endowment equilibrium with optimal welfare. Moreover, we provide a polynomial algorithm that given an arbitrary allocation $S$, computes an endowment equilibrium with the same welfare guarantee as in $S$.

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

2020-02-23
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.

On a Competitive Secretary Problem with Deferred Selections

2020-07-14
Tomer Ezra , Michal Feldman , Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker … We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.

A general framework for endowment effects in combinatorial markets

2020-12-02
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect , coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. Recently, Babaioff, Dobzinski and Oren [EC'18] introduced the … The endowment effect , coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. Recently, Babaioff, Dobzinski and Oren [EC'18] introduced the notion of endowed valuations --- valuations that capture the endowment effect --- and studied the stability and efficiency of combinatorial markets with endowed valuations. They showed that under a specific formulation of the endowment effect, an endowed equilibrium --- market equilibrium with respect to endowed valuations --- is guaranteed to exist in markets with submodular valuations, but fails to exist under XOS valuations. We harness the endowment effect further by introducing a general framework that captures a wide range of different formulations of the endowment effect. The different formulations are (partially) ranked from weak to strong, based on a stability-preserving order. We then provide algorithms for computing endowment equilibria with high welfare for sufficiently strong endowment effects, and non-existence results for weaker ones. Among other results, we prove the existence of endowment equilibria under XOS valuations, and show that if one can pre-pack items into irrevocable bundles then an endowment equilibrium exists for arbitrary markets.
View PDF Chat

Prophet Inequality with Competing Agents

2021-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
View PDF Chat

Combinatorial Contracts.

2021-09-29
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

On a Competitive Secretary Problem with Deferred Selections

2020-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker … We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
View PDF Chat

Multi-Agent Contracts

2022-01-01
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of … We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of ``prices'' and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. Our second main result is an $\Omega(\sqrt{n})$ impossibility for settings with $n$ agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.
View PDF Chat

On the (In)approximability of Combinatorial Contracts

2023-01-01
Tomer Ezra , Michal Feldman , M Schlesinger
We study two combinatorial contract design models -- multi-agent and multi-action -- where a principal delegates the execution of a costly project to others. In both settings, the principal cannot … We study two combinatorial contract design models -- multi-agent and multi-action -- 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, which is a payment scheme that specifies the payment to the agent(s) upon a project's success. In the multi-agent setting, the project is delegated to a team of agents, and every agent chooses whether or not to exert effort. A success probability function specifies the probability of success for every subset of agents exerting effort. For the family of submodular success probability functions, Duetting et al. [2023] established a poly-time constant-factor approximation to the optimal contract, and left open whether this problem admits a PTAS. We show that no poly-time algorithm guarantees a better than $0.7$-approximation to the optimal contract. For XOS functions, Duetting et al. [2023] 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 specifies the probability of success for any subset of actions. Duetting et al. [2021a] devised a poly-time algorithm for computing an optimal contract for gross substitutes success probability functions, and established NP-hardness with respect to submodular functions. We further strengthen this hardness result by showing that this problem does not admit any constant approximation either. For the broader class of XOS functions, we establish the hardness of obtaining a $n^{-1/2+\varepsilon}$-approximation for any $\varepsilon > 0$.

Multi-Agent Combinatorial Contracts

2025-01-01
Paul Dütting , Tomer Ezra , Michal Feldman +1 more
View PDF Chat

Pricing Social Goods

2017-06-30
Alon Eden , Tomer Ezra , Michal Feldman
Social goods are goods that grant value not only to their owners but also to the owners' surroundings, be it their families, friends or office mates. The benefit a non-owner … Social goods are goods that grant value not only to their owners but also to the owners' surroundings, be it their families, friends or office mates. The benefit a non-owner derives from the good is affected by many factors, including the type of the good, its availability, and the social status of the non-owner. Depending on the magnitude of the benefit and on the price of the good, a potential buyer might stay away from purchasing the good, hoping to free ride on others' purchases. A revenue-maximizing seller who sells social goods must take these considerations into account when setting prices for the good. The literature on optimal pricing has advanced considerably over the last decade, but little is known about optimal pricing schemes for selling social goods. In this paper, we conduct a systematic study of revenue-maximizing pricing schemes for social goods: we introduce a Bayesian model for this scenario, and devise nearly-optimal pricing schemes for various types of externalities, both for simultaneous sales and for sequential sales.

Prophets and Secretaries with Overbooking

2018-05-14
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $\ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $\ell$ elements in the selected set. Equivalently, the decision makes can hold up to $\ell$ elements at any given point in time, but can make up to $k-\ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $\ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-\ell\cdot e^{-\Theta\left(\frac{\left(k-\ell\right)^2}{k}\right)}$, which is asymptotically tight for $k-\ell=\Theta(\ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-\ell e^{-\frac{k-8\ell}{2+2\ln \ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {\em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the seller's capacity, then allocate to the agents with the highest values among the selected agents.

Prophet Inequality with Competing Agents

2021-07-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but … We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but they are drawn from a known probability distribution. In the standard prophet setting, a single agent makes selection decisions in an attempt to maximize her expected reward. The novelty of our model is the introduction of a competition setting, where multiple agents compete over the arriving rewards, and make online selection decisions simultaneously, as rewards arrive. If a given reward is selected by more than a single agent, ties are broken either randomly or by a fixed ranking of the agents. The consideration of competition turns the prophet setting from an online decision making scenario to a multi-agent game. For both random and ranked tie-breaking rules, we present simple threshold strategies for the agents that give them high guarantees, independent of the strategies taken by others. In particular, for random tie-breaking, every agent can guarantee herself at least $\frac{1}{k+1}$ of the highest reward, and at least $\frac{1}{2k}$ of the optimal social welfare. For ranked tie-breaking, the $i$th ranked agent can guarantee herself at least a half of the $i$th highest reward. We complement these results by matching upper bounds, even with respect to equilibrium profiles. For ranked tie-breaking rule, we also show a correspondence between the equilibrium of the $k$-agent game and the optimal strategy of a single decision maker who can select up to $k$ rewards.

"Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings

2022-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in … We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.
View PDF Chat

Prophet Inequalities via the Expected Competitive Ratio

2022-01-01
Tomer Ezra , Stefano Leonardi , Rebecca Reiffenhäuser +2 more
We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to constraints. Traditionally, performance is compared to the expected … We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to constraints. Traditionally, performance is compared to the expected offline optimum, called the \textit{Ratio of Expectations} (RoE). However, RoE has limitations as it only guarantees the average performance compared to the optimum, and might perform poorly against the realized ex-post optimal value. We study an alternative performance measure, the \textit{Expected Ratio} (EoR), namely the expectation of the ratio between algorithm's and prophet's value. EoR offers robust guarantees, e.g., a constant EoR implies achieving a constant fraction of the offline optimum with constant probability. For the special case of single-choice problems the EoR coincides with the well-studied notion of probability of selecting the maximum. However, the EoR naturally generalizes the probability of selecting the maximum for combinatorial constraints, which are the main focus of this paper. Specifically, we establish two reductions: for every constraint, RoE and the EoR are at most a constant factor apart. Additionally, we show that the EoR is a stronger benchmark than the RoE in that, for every instance (constraint and distribution), the RoE is at least a constant fraction of the EoR, but not vice versa. Both these reductions imply a wealth of EoR results in multiple settings where RoE results are known.
View PDF Chat

Combinatorial Contracts

2021-01-01
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.
View PDF Chat

Prophet Inequality with Competing Agents

2021-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but … We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but they are drawn from a known probability distribution. In the standard prophet setting, a single agent makes selection decisions in an attempt to maximize her expected reward. The novelty of our model is the introduction of a competition setting, where multiple agents compete over the arriving rewards, and make online selection decisions simultaneously, as rewards arrive. If a given reward is selected by more than a single agent, ties are broken either randomly or by a fixed ranking of the agents. The consideration of competition turns the prophet setting from an online decision making scenario to a multi-agent game. For both random and ranked tie-breaking rules, we present simple threshold strategies for the agents that give them high guarantees, independent of the strategies taken by others. In particular, for random tie-breaking, every agent can guarantee herself at least $\frac{1}{k+1}$ of the highest reward, and at least $\frac{1}{2k}$ of the optimal social welfare. For ranked tie-breaking, the $i$th ranked agent can guarantee herself at least a half of the $i$th highest reward. We complement these results by matching upper bounds, even with respect to equilibrium profiles. For ranked tie-breaking rule, we also show a correspondence between the equilibrium of the $k$-agent game and the optimal strategy of a single decision maker who can select up to $k$ rewards.
View PDF Chat

Fair-Share Allocations for Agents with Arbitrary Entitlements

2021-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) … We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new, and satisfies $APS \ge MMS$, where the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a $\frac{3}{5}$-fraction of her APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a $\frac{3}{5}$-fraction of her APS.
View PDF Chat

Best-of-Both-Worlds Fair-Share Allocations

2021-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds … We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness mechanisms aim to give all agents both an ex-ante guarantee (such as getting the proportional share in expectation) and an ex-post guarantee. Prior BoBW results have focused on ex-post guarantees that are based on the "up to one item" paradigm, such as envy-free up to one item (EF1). In this work we attempt to give every agent a high value ex-post, and specifically, a constant fraction of his maximin share (MMS). The up to one item paradigm fails to give such a guarantee, and it is not difficult to present examples in which previous BoBW mechanisms give agents only a $\frac{1}{n}$ fraction of their MMS. Our main result is a deterministic polynomial time algorithm that computes a distribution over allocations that is ex-ante proportional, and ex-post, every allocation gives every agent at least his proportional share up to one item, and more importantly, at least half of his MMS. Moreover, this last ex-post guarantee holds even with respect to a more demanding notion of a share, introduced in this paper, that we refer to as the truncated proportional share (TPS). Our guarantees are nearly best possible, in the sense that one cannot guarantee agents more than their proportional share ex-ante, and one cannot guarantee agents more than a $\frac{n}{2n-1}$ fraction of their TPS ex-post.
View PDF Chat

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

2020-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.
View PDF Chat

A General Framework for Endowment Effects in Combinatorial Markets

2019-01-01
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with respect to a single item. Babaioff et al. [EC'18] took a first step at extending this study beyond a single item. They proposed a specific formulation of the endowment effect in combinatorial settings, and showed that equilibrium existence with respect to the endowed valuations extends from gross substitutes to submodular valuations, but provably fails to extend to XOS valuations. Extending the endowment effect to combinatorial settings can take different forms. In this work, we devise a framework that captures a space of endowment effects, upon which we impose a partial order, which preserves endowment equilibrium existence. Within this framework, we provide existence and welfare guarantees for endowment equilibria corresponding to various endowment effects. Our main results are the following: (1) For markets with XOS valuations, we introduce an endowment effect that is stronger than that of Babaioff et al., for which an endowment equilibrium is guaranteed to exist and gives at least half of the optimal welfare. Moreover, this equilibrium can be reached via a variant of the flexible ascent auction. (2) For markets with arbitrary valuations, we show that bundling leads to a sweeping positive result. In particular, if items can be prepacked into indivisible bundles, there always exists an endowment equilibrium with optimal welfare. Moreover, we provide a polynomial algorithm that given an arbitrary allocation $S$, computes an endowment equilibrium with the same welfare guarantee as in $S$.
View PDF Chat

Prophets and Secretaries with Overbooking

2018-01-01
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $\ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $\ell$ elements in the selected set. Equivalently, the decision makes can hold up to $\ell$ elements at any given point in time, but can make up to $k-\ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $\ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-\ell\cdot e^{-\Theta\left(\frac{\left(k-\ell\right)^2}{k}\right)}$, which is asymptotically tight for $k-\ell=\Theta(\ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-\ell e^{-\frac{k-8\ell}{2+2\ln \ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {\em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the seller's capacity, then allocate to the agents with the highest values among the selected agents.
View PDF Chat

Pandora's Problem with Combinatorial Cost

2023-01-01
Ben Berger , Tomer Ezra , Michal Feldman +1 more
Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing … Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing many real-life scenarios where search cost is non-additive. Weitzman's celebrated algorithm [1979] establishes the remarkable result that, for additive costs, the optimal search strategy is non-adaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond additive cost functions. Our main result is that the class of submodular cost functions admits an optimal strategy that follows a fixed, non-adaptive order, thus preserving the structural simplicity of additive cost functions. In contrast, for the more general class of subadditive (or even XOS) cost functions, the optimal strategy may already need to determine the search order adaptively. On the computational side, obtaining any approximation to the optimal utility requires super polynomially many queries to the cost function, even for a strict subclass of submodular cost functions.
View PDF Chat

Pandora's Problem with Combinatorial Cost

2023-07-07
Ben Berger , Tomer Ezra , Michal Feldman +1 more
Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing … Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing many real-life scenarios where search cost is non-additive. Weitzman's celebrated algorithm [1979] establishes the remarkable result that, for additive costs, the optimal search strategy is non-adaptive and computationally feasible.
View PDF Chat

The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings

2023-01-01
Tomer Ezra , Tamar Garbuz
We study the measure of order-competitive ratio introduced by Ezra et al. [2023] for online algorithms in Bayesian combinatorial settings. In our setting, a decision-maker observes a sequence of elements … We study the measure of order-competitive ratio introduced by Ezra et al. [2023] for online algorithms in Bayesian combinatorial settings. In our setting, a decision-maker observes a sequence of elements that are associated with stochastic rewards that are drawn from known priors, but revealed one by one in an online fashion. The decision-maker needs to decide upon the arrival of each element whether to select it or discard it (according to some feasibility constraint), and receives the associated rewards of the selected elements. The order-competitive ratio is defined as the worst-case ratio (over all distribution sequences) between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss incurred due to the lack of knowledge of the arrival order. Ezra et al. [2023] showed how to design algorithms that achieve better approximations with respect to the new benchmark (order-competitive ratio) in the single-choice setting, which raises the natural question of whether the same can be achieved in combinatorial settings. In particular, whether it is possible to achieve a constant approximation with respect to the best online algorithm for downward-closed feasibility constraints, whether $\omega(1/n)$-approximation is achievable for general (non-downward-closed) feasibility constraints, or whether a convergence rate to $1$ of $o(1/\sqrt{k})$ is achievable for the multi-unit setting. We show, by devising novel constructions that may be of independent interest, that for all three scenarios, the asymptotic lower bounds with respect to the old benchmark, also hold with respect to the new benchmark.
View PDF Chat

The Competition Complexity of Prophet Inequalities

2024-02-16
Johannes Brustle , José R. Correa , Paul Dütting +3 more
We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks … We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1-\varepsilon)$-approximation to the expected offline optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of $k = \Theta(\log \log 1/\varepsilon)$. This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of $k = \Theta(\log 1/\varepsilon)$, establishing an exponential gap between block threshold algorithms and single threshold algorithms. Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications.
View PDF Chat

Contracts with Inspections

2024-02-26
Tomer Ezra , Stefano Leonardi , M.V. Russo
In the classical principal-agent hidden-action model, a principal delegates the execution of a costly task to an agent for which he can choose among actions with different costs and different … In the classical principal-agent hidden-action model, a principal delegates the execution of a costly task to an agent for which he can choose among actions with different costs and different success probabilities to accomplish the task. To incentivize the agent to exert effort, the principal can commit to a contract, which is the amount of payment based on the task's success. A crucial assumption of this model is that the principal can only base the payment on the outcome but not on the agent's chosen action. In this work, we relax the hidden-action assumption and introduce a new model where the principal is allowed to inspect subsets of actions at some cost that depends on the inspected subset. If the principal discovers that the agent did not select the agreed-upon action through the inspection, the principal can withhold payment. This relaxation of the model introduces a broader strategy space for the principal, who now faces a tradeoff between positive incentives (increasing payment) and negative incentives (increasing inspection). We show how to find the best deterministic incentive-compatible inspection scheme for all monotone inspection cost functions. We then turn to randomized inspection schemes and show that one can efficiently find the best randomized incentive-compatible inspection scheme when the inspection cost function is submodular. We complement this result by showing that it is impossible to efficiently find the optimal randomized inspection scheme for the more general case of XOS inspection cost functions.
View PDF Chat

Optimal Mechanisms for Consumer Surplus Maximization

2024-02-26
Tomer Ezra , Daniel Schoepflin , Ariel Shaulker
We consider the problem of designing auctions which maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller … We consider the problem of designing auctions which maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way which maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller's objective is welfare maximization [Clarke, 1971, Groves, 1973, Vickrey, 1961] or revenue maximization [Myerson, 1981]. However, in the case of consumer surplus maximization the picture is less clear -- using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms which maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with optimal approximation guarantees against the total social welfare. Along the way, we answer an open question posed by Hartline and Roughgarden [2008], who, to our knowledge, were the first to study the question of consumer surplus approximation guarantees in single-parameter settings, regarding optimal mechanisms for two bidders.
View PDF Chat

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms

2024-02-26
Tomer Ezra , Michal Feldman , Zhihao Gavin Tang
In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequentially. Upon … In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequentially. Upon the arrival of an element, its value is revealed, and the decision maker needs to decide, immediately and irrevocably, whether to accept it or not. While most previous work has assumed that the decision maker, upon observing the element's value, also becomes aware of its identity -- namely, its distribution -- practical scenarios frequently demand that decisions be made based solely on the element's value, without considering its identity. This necessity arises either from the algorithm's ignorance of the element's identity or due to the pursuit of fairness. We call such algorithms identity-blind algorithms, and propose the identity-blindness gap as a metric to evaluate the performance loss caused by identity-blindness. This gap is defined as the maximum ratio between the expected performance of an identity-blind online algorithm and an optimal online algorithm that knows the arrival order, thus also the identities. We study the identity-blindness gap in the paradigmatic prophet inequality problem, under the two objectives of maximizing the expected value, and maximizing the probability to obtain the highest value. For the max-expectation objective, the celebrated prophet inequality establishes a single-threshold algorithm that gives at least 1/2 of the offline optimum, thus also an identity-blindness gap of at least 1/2. We show that this bound is tight. For the max-probability objective, while the competitive ratio is tightly 1/e, we provide a deterministic single-threshold algorithm that gives an identity-blindness gap of $\sim 0.562$ under the assumption that there are no large point masses. Moreover, we show that this bound is tight with respect to deterministic algorithms.
View PDF Chat

Sequential Contracts

2024-03-14
Tomer Ezra , Michal Feldman , M Schlesinger
We study the principal-agent setting, where a principal delegates the execution of a costly project to an agent. In the classical model, the agent chooses an action among a set … We study the principal-agent setting, where a principal delegates the execution of a costly project to an agent. In the classical model, the agent chooses an action among a set of available actions. Every action is associated with some cost, and leads to a stochastic outcome for the project. The agent's action is hidden from the principal, who only observes the outcome. The principal incentivizes the agent through a payment scheme (a contract) that maps outcomes to payments, with the objective of finding the optimal contract - the contract maximizing the principal's expected utility. In this work, we introduce a sequential variant of the model, capturing many real-life settings, where the agent engages in multiple attempts, incurring the sum of costs of the actions taken and being compensated for the best realized outcome. We study the contract design problem in this new setting. We first observe that the agent's problem - finding the sequential set of actions that maximizes his utility for a given contract - is equivalent to the well-known Pandora's Box problem. With this insight at hand, we provide algorithms and hardness results for the (principal's) contract design problem, under both independent and correlated actions. For independent actions, we show that the optimal linear contract can be computed in polynomial time. Furthermore, this result extends to the optimal arbitrary contract when the number of outcomes is a constant. For correlated actions we find that approximating the optimal contract within any constant ratio is NP-hard.
View PDF Chat

Pricing Social Goods

2017-01-01
Alon Eden , Tomer Ezra , Michal Feldman
Social goods are goods that grant value not only to their owners but also to the owners' surroundings, be it their families, friends or office mates. The benefit a non-owner … Social goods are goods that grant value not only to their owners but also to the owners' surroundings, be it their families, friends or office mates. The benefit a non-owner derives from the good is affected by many factors, including the type of the good, its availability, and the social status of the non-owner. Depending on the magnitude of the benefit and on the price of the good, a potential buyer might stay away from purchasing the good, hoping to free ride on others' purchases. A revenue-maximizing seller who sells social goods must take these considerations into account when setting prices for the good. The literature on optimal pricing has advanced considerably over the last decade, but little is known about optimal pricing schemes for selling social goods. In this paper, we conduct a systematic study of revenue-maximizing pricing schemes for social goods: we introduce a Bayesian model for this scenario, and devise nearly-optimal pricing schemes for various types of externalities, both for simultaneous sales and for sequential sales.

Prophet Inequality from Samples: Is the More the Merrier?

2024-08-31
Tomer Ezra
We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from the … We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from the distributions. Rubinstein et al. [2020] showed that the optimal competitive-ratio of $\frac{1}{2}$ can surprisingly be obtained by observing a set of $n$ samples, one from each of the distributions. In this paper, we prove that this competitive-ratio of $\frac{1}{2}$ becomes unattainable when the decision-maker is provided with a set of more samples. We then examine the natural class of ordinal static threshold algorithms, where the algorithm selects the $i$-th highest ranked sample, sets this sample as a static threshold, and then chooses the first value that exceeds this threshold. We show that the best possible algorithm within this class achieves a competitive-ratio of $0.433$. Along the way, we utilize the tools developed in the paper and provide an alternative proof of the main result of Rubinstein et al. [2020].
View PDF Chat

Multi-Agent Combinatorial Contracts

2025-01-01
Paul Dütting , Tomer Ezra , Michal Feldman +1 more
View PDF Chat

The Competition Complexity of Prophet Secretary

2024-11-16
Tomer Ezra , Tamar Garbuz
We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-\epsilon)$-competition complexity for different classes of online algorithms. This metric asks … We study the classic single-choice prophet secretary problem through a resource augmentation lens. Our goal is to bound the $(1-\epsilon)$-competition complexity for different classes of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1 - \epsilon)$-approximation to the expected offline optimum on the original instance (without added copies). We consider four natural classes of online algorithms: single-threshold, time-based threshold, activation-based, and general algorithms. We show that for single-threshold algorithms the $(1-\epsilon)$-competition complexity is $\Theta(\ln(\frac{1}{\epsilon}))$ (as in the i.i.d. case). Additionally, we demonstrate that time-based threshold and activation-based algorithms (which cover all previous approaches for obtaining competitive-ratios for the classic prophet secretary problem) yield a sub-optimal $(1-\epsilon)$-competition complexity of $\Theta\left(\frac{\ln(\frac{1}{\epsilon})}{\ln\ln(\frac{1}{\epsilon})}\right)$, which is strictly better than the class of single-threshold algorithms. Finally, we find that the $(1-\epsilon)$-competition complexity of general adaptive algorithms is $\Theta(\sqrt{\ln(\frac{1}{\epsilon})})$, which is in sharp contrast to $\Theta(\ln\ln(\frac{1}{\epsilon}))$ in the i.i.d. case.
View PDF Chat

The Competition Complexity of Prophet Inequalities with Correlations

2024-09-10
Tomer Ezra , Tamar Garbuz
We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the … We initiate the study of the prophet inequality problem through the resource augmentation framework in scenarios when the values of the rewards are correlated. Our goal is to determine the number of additional rewards an online algorithm requires to approximate the maximum value of the original instance. While the independent reward case is well understood, we extend this research to account for correlations among rewards. Our results demonstrate that, unlike in the independent case, the required number of additional rewards for approximation depends on the number of original rewards, and that block-threshold algorithms, which are optimal in the independent case, may require an infinite number of additional rewards when correlations are present. We develop asymptotically optimal algorithms for the following three scenarios: (1) where rewards arrive in blocks corresponding to the different copies of the original instance; (2) where rewards across all copies are arbitrarily shuffled; and (3) where rewards arrive in blocks corresponding to the different copies of the original instance, and values within each block are pairwise independent rather than fully correlated.
View PDF Chat

Prophet Inequality from Samples: Is the More the Merrier?

2024-08-31
Tomer Ezra
We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from the … We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distribution and has only access to a set of samples from the distributions. Rubinstein et al. [2020] showed that the optimal competitive-ratio of $\frac{1}{2}$ can surprisingly be obtained by observing a set of $n$ samples, one from each of the distributions. In this paper, we prove that this competitive-ratio of $\frac{1}{2}$ becomes unattainable when the decision-maker is provided with a set of more samples. We then examine the natural class of ordinal static threshold algorithms, where the algorithm selects the $i$-th highest ranked sample, sets this sample as a static threshold, and then chooses the first value that exceeds this threshold. We show that the best possible algorithm within this class achieves a competitive-ratio of $0.433$. Along the way, we utilize the tools developed in the paper and provide an alternative proof of the main result of Rubinstein et al. [2020].
View PDF Chat

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

2024-07-22
Tomer Ezra , Stefano Leonardi , Michał E. Pawłowski +2 more
The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with … The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou [Tou23a] developed a non-clairvoyant framework that provided an $O(\sqrt{n \log n})$ upper bound for a wide class of generalized JRP, where $n$ is the number of request types. We advance the study of non-clairvoyant algorithms by providing a simpler, modular framework that matches the competitive ratio established by Touitou for the same class of generalized JRP. Our key insight is to leverage universal algorithms for Set Cover to approximate arbitrary monotone subadditive functions using a simple class of functions termed \textit{disjoint}. This allows us to reduce the problem to several independent instances of the TCP Acknowledgement problem, for which a simple 2-competitive non-clairvoyant algorithm is known. The modularity of our framework is a major advantage as it allows us to tailor the reduction to specific problems and obtain better competitive ratios. In particular, we obtain tight $O(\sqrt{n})$-competitive algorithms for two significant problems: Multi-Level Aggregation and Weighted Symmetric Subadditive Joint Replenishment. We also show that, in contrast, Touitou's algorithm is $\Omega(\sqrt{n \log n})$-competitive for both of these problems.
View PDF Chat

The Competition Complexity of Prophet Inequalities

2024-07-08
Johannes Brustle , José R. Correa , Paul Duetting +3 more
View PDF Chat

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms

2024-07-08
Tomer Ezra , Michal Feldman , Zhihao Gavin Tang
View PDF Chat

Sequential Contracts

2024-03-14
Tomer Ezra , Michal Feldman , M Schlesinger
We study the principal-agent setting, where a principal delegates the execution of a costly project to an agent. In the classical model, the agent chooses an action among a set … We study the principal-agent setting, where a principal delegates the execution of a costly project to an agent. In the classical model, the agent chooses an action among a set of available actions. Every action is associated with some cost, and leads to a stochastic outcome for the project. The agent's action is hidden from the principal, who only observes the outcome. The principal incentivizes the agent through a payment scheme (a contract) that maps outcomes to payments, with the objective of finding the optimal contract - the contract maximizing the principal's expected utility. In this work, we introduce a sequential variant of the model, capturing many real-life settings, where the agent engages in multiple attempts, incurring the sum of costs of the actions taken and being compensated for the best realized outcome. We study the contract design problem in this new setting. We first observe that the agent's problem - finding the sequential set of actions that maximizes his utility for a given contract - is equivalent to the well-known Pandora's Box problem. With this insight at hand, we provide algorithms and hardness results for the (principal's) contract design problem, under both independent and correlated actions. For independent actions, we show that the optimal linear contract can be computed in polynomial time. Furthermore, this result extends to the optimal arbitrary contract when the number of outcomes is a constant. For correlated actions we find that approximating the optimal contract within any constant ratio is NP-hard.
View PDF Chat

Contracts with Inspections

2024-02-26
Tomer Ezra , Stefano Leonardi , M.V. Russo
In the classical principal-agent hidden-action model, a principal delegates the execution of a costly task to an agent for which he can choose among actions with different costs and different … In the classical principal-agent hidden-action model, a principal delegates the execution of a costly task to an agent for which he can choose among actions with different costs and different success probabilities to accomplish the task. To incentivize the agent to exert effort, the principal can commit to a contract, which is the amount of payment based on the task's success. A crucial assumption of this model is that the principal can only base the payment on the outcome but not on the agent's chosen action. In this work, we relax the hidden-action assumption and introduce a new model where the principal is allowed to inspect subsets of actions at some cost that depends on the inspected subset. If the principal discovers that the agent did not select the agreed-upon action through the inspection, the principal can withhold payment. This relaxation of the model introduces a broader strategy space for the principal, who now faces a tradeoff between positive incentives (increasing payment) and negative incentives (increasing inspection). We show how to find the best deterministic incentive-compatible inspection scheme for all monotone inspection cost functions. We then turn to randomized inspection schemes and show that one can efficiently find the best randomized incentive-compatible inspection scheme when the inspection cost function is submodular. We complement this result by showing that it is impossible to efficiently find the optimal randomized inspection scheme for the more general case of XOS inspection cost functions.
View PDF Chat

Optimal Mechanisms for Consumer Surplus Maximization

2024-02-26
Tomer Ezra , Daniel Schoepflin , Ariel Shaulker
We consider the problem of designing auctions which maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller … We consider the problem of designing auctions which maximize consumer surplus (i.e., the social welfare minus the payments charged to the buyers). In the consumer surplus maximization problem, a seller with a set of goods faces a set of strategic buyers with private values, each of whom aims to maximize their own individual utility. The seller, in contrast, aims to allocate the goods in a way which maximizes the total buyer utility. The seller must then elicit the values of the buyers in order to decide what goods to award each buyer. The canonical approach in mechanism design to ensure truthful reporting of the private information is to find appropriate prices to charge each buyer in order to align their objective with the objective of the seller. Indeed, there are many celebrated results to this end when the seller's objective is welfare maximization [Clarke, 1971, Groves, 1973, Vickrey, 1961] or revenue maximization [Myerson, 1981]. However, in the case of consumer surplus maximization the picture is less clear -- using high payments to ensure the highest value bidders are served necessarily decreases their surplus utility, but using low payments may lead the seller into serving lower value bidders. Our main result in this paper is a framework for designing mechanisms which maximize consumer surplus. We instantiate our framework in a variety of canonical multi-parameter auction settings (i.e., unit-demand bidders with heterogeneous items, multi-unit auctions, and auctions with divisible goods) and use it to design auctions achieving consumer surplus with optimal approximation guarantees against the total social welfare. Along the way, we answer an open question posed by Hartline and Roughgarden [2008], who, to our knowledge, were the first to study the question of consumer surplus approximation guarantees in single-parameter settings, regarding optimal mechanisms for two bidders.
View PDF Chat

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms

2024-02-26
Tomer Ezra , Michal Feldman , Zhihao Gavin Tang
In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequentially. Upon … In Bayesian online settings, every element has a value that is drawn from a known underlying distribution, which we refer to as the element's identity. The elements arrive sequentially. Upon the arrival of an element, its value is revealed, and the decision maker needs to decide, immediately and irrevocably, whether to accept it or not. While most previous work has assumed that the decision maker, upon observing the element's value, also becomes aware of its identity -- namely, its distribution -- practical scenarios frequently demand that decisions be made based solely on the element's value, without considering its identity. This necessity arises either from the algorithm's ignorance of the element's identity or due to the pursuit of fairness. We call such algorithms identity-blind algorithms, and propose the identity-blindness gap as a metric to evaluate the performance loss caused by identity-blindness. This gap is defined as the maximum ratio between the expected performance of an identity-blind online algorithm and an optimal online algorithm that knows the arrival order, thus also the identities. We study the identity-blindness gap in the paradigmatic prophet inequality problem, under the two objectives of maximizing the expected value, and maximizing the probability to obtain the highest value. For the max-expectation objective, the celebrated prophet inequality establishes a single-threshold algorithm that gives at least 1/2 of the offline optimum, thus also an identity-blindness gap of at least 1/2. We show that this bound is tight. For the max-probability objective, while the competitive ratio is tightly 1/e, we provide a deterministic single-threshold algorithm that gives an identity-blindness gap of $\sim 0.562$ under the assumption that there are no large point masses. Moreover, we show that this bound is tight with respect to deterministic algorithms.
View PDF Chat

The Competition Complexity of Prophet Inequalities

2024-02-16
Johannes Brustle , José R. Correa , Paul Dütting +3 more
We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks … We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1-\varepsilon)$-approximation to the expected offline optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of $k = \Theta(\log \log 1/\varepsilon)$. This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of $k = \Theta(\log 1/\varepsilon)$, establishing an exponential gap between block threshold algorithms and single threshold algorithms. Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications.
View PDF Chat

Fair-Share Allocations for Agents with Arbitrary Entitlements

2023-10-26
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves … We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves as an attractive fairness criterion for which, to qualify as fair, an allocation needs to give every agent at least a substantial fraction of the agent’s MMS. In this paper, we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new and satisfies [Formula: see text], for which the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem) and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a [Formula: see text] - fraction of the agent’s APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a [Formula: see text] - fraction of the agent’s APS. Funding: T. Ezra’s research is partially supported by the European Research Council Advanced [Grant 788893] AMDROMA “Algorithmic and Mechanism Design Research in Online Markets” and MIUR PRIN project ALGADIMAR “Algorithms, Games, and Digital Markets.” U. Feige’s research is supported in part by the Israel Science Foundation [Grant 1122/22].
View PDF Chat

Pandora's Problem with Combinatorial Cost

2023-07-07
Ben Berger , Tomer Ezra , Michal Feldman +1 more
Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing … Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing many real-life scenarios where search cost is non-additive. Weitzman's celebrated algorithm [1979] establishes the remarkable result that, for additive costs, the optimal search strategy is non-adaptive and computationally feasible.
View PDF Chat

“Who is Next in Line?” On the Significance of Knowing the Arrival Order in Bayesian Online Settings

2023-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in … We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far.We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.* This work is supported by Science and Technology Innovation 2030 –"New Generation of Artificial Intelligence" Major Project No.(2018AAA0100903), Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 866132), by the Israel Science Foundation (grant number 317/17), by an Amazon Research Award, and by the NSF-BSF (grant number 2020788). Tomer Ezra was partially supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets" and MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets". Zhihao Gavin Tang is supported by NSFC grant 61902233. Nick Gravin is supported by NSFC grant 62150610500.
View PDF Chat

Pandora's Problem with Combinatorial Cost

2023-01-01
Ben Berger , Tomer Ezra , Michal Feldman +1 more
Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing … Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing many real-life scenarios where search cost is non-additive. Weitzman's celebrated algorithm [1979] establishes the remarkable result that, for additive costs, the optimal search strategy is non-adaptive and computationally feasible. We inquire to which extent this structural and computational simplicity extends beyond additive cost functions. Our main result is that the class of submodular cost functions admits an optimal strategy that follows a fixed, non-adaptive order, thus preserving the structural simplicity of additive cost functions. In contrast, for the more general class of subadditive (or even XOS) cost functions, the optimal strategy may already need to determine the search order adaptively. On the computational side, obtaining any approximation to the optimal utility requires super polynomially many queries to the cost function, even for a strict subclass of submodular cost functions.
View PDF Chat

Fair Division with Interdependent Values

2023-01-01
Georgios Birmpas , Tomer Ezra , Stefano Leonardi +1 more
We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set of goods that needs … We introduce the study of designing allocation mechanisms for fairly allocating indivisible goods in settings with interdependent valuation functions. In our setting, there is a set of goods that needs to be allocated to a set of agents (without disposal). Each agent is given a private signal, and his valuation function depends on the signals of all agents. Without the use of payments, there are strong impossibility results for designing strategyproof allocation mechanisms even in settings without interdependent values. Therefore, we turn to design mechanisms that always admit equilibria that are fair with respect to their true signals, despite their potentially distorted perception. To do so, we first extend the definitions of pure Nash equilibrium and well-studied fairness notions in literature to the interdependent setting. We devise simple allocation mechanisms that always admit a fair equilibrium with respect to the true signals. We complement this result by showing that, even for very simple cases with binary additive interdependent valuation functions, no allocation mechanism that always admits an equilibrium, can guarantee that all equilibria are fair with respect to the true signals.
View PDF Chat

The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings

2023-01-01
Tomer Ezra , Tamar Garbuz
We study the measure of order-competitive ratio introduced by Ezra et al. [2023] for online algorithms in Bayesian combinatorial settings. In our setting, a decision-maker observes a sequence of elements … We study the measure of order-competitive ratio introduced by Ezra et al. [2023] for online algorithms in Bayesian combinatorial settings. In our setting, a decision-maker observes a sequence of elements that are associated with stochastic rewards that are drawn from known priors, but revealed one by one in an online fashion. The decision-maker needs to decide upon the arrival of each element whether to select it or discard it (according to some feasibility constraint), and receives the associated rewards of the selected elements. The order-competitive ratio is defined as the worst-case ratio (over all distribution sequences) between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss incurred due to the lack of knowledge of the arrival order. Ezra et al. [2023] showed how to design algorithms that achieve better approximations with respect to the new benchmark (order-competitive ratio) in the single-choice setting, which raises the natural question of whether the same can be achieved in combinatorial settings. In particular, whether it is possible to achieve a constant approximation with respect to the best online algorithm for downward-closed feasibility constraints, whether $\omega(1/n)$-approximation is achievable for general (non-downward-closed) feasibility constraints, or whether a convergence rate to $1$ of $o(1/\sqrt{k})$ is achievable for the multi-unit setting. We show, by devising novel constructions that may be of independent interest, that for all three scenarios, the asymptotic lower bounds with respect to the old benchmark, also hold with respect to the new benchmark.
View PDF Chat

On the (In)approximability of Combinatorial Contracts

2023-01-01
Tomer Ezra , Michal Feldman , M Schlesinger
We study two combinatorial contract design models -- multi-agent and multi-action -- where a principal delegates the execution of a costly project to others. In both settings, the principal cannot … We study two combinatorial contract design models -- multi-agent and multi-action -- 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, which is a payment scheme that specifies the payment to the agent(s) upon a project's success. In the multi-agent setting, the project is delegated to a team of agents, and every agent chooses whether or not to exert effort. A success probability function specifies the probability of success for every subset of agents exerting effort. For the family of submodular success probability functions, Duetting et al. [2023] established a poly-time constant-factor approximation to the optimal contract, and left open whether this problem admits a PTAS. We show that no poly-time algorithm guarantees a better than $0.7$-approximation to the optimal contract. For XOS functions, Duetting et al. [2023] 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 specifies the probability of success for any subset of actions. Duetting et al. [2021a] devised a poly-time algorithm for computing an optimal contract for gross substitutes success probability functions, and established NP-hardness with respect to submodular functions. We further strengthen this hardness result by showing that this problem does not admit any constant approximation either. For the broader class of XOS functions, we establish the hardness of obtaining a $n^{-1/2+\varepsilon}$-approximation for any $\varepsilon > 0$.

Combinatorial Contracts

2022-02-01
Paul Dütting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.
View PDF Chat

On Best-of-Both-Worlds Fair-Share Allocations

2022-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
View PDF Chat

"Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings

2022-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in … We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.
View PDF Chat

Prophet Inequalities via the Expected Competitive Ratio

2022-01-01
Tomer Ezra , Stefano Leonardi , Rebecca Reiffenhäuser +2 more
We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to constraints. Traditionally, performance is compared to the expected … We consider prophet inequalities under downward-closed constraints. In this problem, a decision-maker makes immediate and irrevocable choices on arriving elements, subject to constraints. Traditionally, performance is compared to the expected offline optimum, called the \textit{Ratio of Expectations} (RoE). However, RoE has limitations as it only guarantees the average performance compared to the optimum, and might perform poorly against the realized ex-post optimal value. We study an alternative performance measure, the \textit{Expected Ratio} (EoR), namely the expectation of the ratio between algorithm's and prophet's value. EoR offers robust guarantees, e.g., a constant EoR implies achieving a constant fraction of the offline optimum with constant probability. For the special case of single-choice problems the EoR coincides with the well-studied notion of probability of selecting the maximum. However, the EoR naturally generalizes the probability of selecting the maximum for combinatorial constraints, which are the main focus of this paper. Specifically, we establish two reductions: for every constraint, RoE and the EoR are at most a constant factor apart. Additionally, we show that the EoR is a stronger benchmark than the RoE in that, for every instance (constraint and distribution), the RoE is at least a constant fraction of the EoR, but not vice versa. Both these reductions imply a wealth of EoR results in multiple settings where RoE results are known.
View PDF Chat

Multi-Agent Contracts

2022-01-01
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of … We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a reward function, which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy. Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value and demand oracles, respectively. It relies on an unconventional use of ``prices'' and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest. Our second main result is an $\Omega(\sqrt{n})$ impossibility for settings with $n$ agents and subadditive reward functions, even with demand oracle access. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This presents a surprising departure from previous literature, e.g., on combinatorial auctions.
View PDF Chat

Combinatorial Contracts.

2021-09-29
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.

On a Competitive Secretary Problem with Deferred Selections

2021-08-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes … We study the secretary problem in multi-agent environments. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. We introduce a novel multi-agent secretary model, in which the competition is explicit. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
View PDF Chat

Fair-Share Allocations for Agents with Arbitrary Entitlements

2021-07-18
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) … We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. The AnyPrice share of an agent is the value she can guarantee to herself if she is given a budget equal to her entitlement, and she buys her highest value affordable set when items are adversarially priced with a total price equal to the total entitlements. Even for the equal entitlements case, this notion is new, and satisfies APS ≥ MMS, where the inequality is sometimes strict. We also present an alternative definition for the APS as a maximization problem (a fractional version of the MMS), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a 3/5-fraction of her APS. This algorithm can also be viewed as providing a strategy in a certain natural bidding game, and this strategy secures each agent that uses it at least a 3/5-fraction of her APS, regardless of the strategies used by other agents.
View PDF Chat

Prophet Inequality with Competing Agents

2021-07-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but … We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but they are drawn from a known probability distribution. In the standard prophet setting, a single agent makes selection decisions in an attempt to maximize her expected reward. The novelty of our model is the introduction of a competition setting, where multiple agents compete over the arriving rewards, and make online selection decisions simultaneously, as rewards arrive. If a given reward is selected by more than a single agent, ties are broken either randomly or by a fixed ranking of the agents. The consideration of competition turns the prophet setting from an online decision making scenario to a multi-agent game. For both random and ranked tie-breaking rules, we present simple threshold strategies for the agents that give them high guarantees, independent of the strategies taken by others. In particular, for random tie-breaking, every agent can guarantee herself at least $\frac{1}{k+1}$ of the highest reward, and at least $\frac{1}{2k}$ of the optimal social welfare. For ranked tie-breaking, the $i$th ranked agent can guarantee herself at least a half of the $i$th highest reward. We complement these results by matching upper bounds, even with respect to equilibrium profiles. For ranked tie-breaking rule, we also show a correspondence between the equilibrium of the $k$-agent game and the optimal strategy of a single decision maker who can select up to $k$ rewards.

Fair and Truthful Mechanisms for Dichotomous Valuations

2021-05-18
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.
View PDF Chat

Prophet Inequality with Competing Agents

2021-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
View PDF Chat

Combinatorial Contracts

2021-01-01
Paul Duetting , Tomer Ezra , Michal Feldman +1 more
We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take … We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal's reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract, based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.
View PDF Chat

Prophet Inequality with Competing Agents

2021-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but … We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the outset, but they are drawn from a known probability distribution. In the standard prophet setting, a single agent makes selection decisions in an attempt to maximize her expected reward. The novelty of our model is the introduction of a competition setting, where multiple agents compete over the arriving rewards, and make online selection decisions simultaneously, as rewards arrive. If a given reward is selected by more than a single agent, ties are broken either randomly or by a fixed ranking of the agents. The consideration of competition turns the prophet setting from an online decision making scenario to a multi-agent game. For both random and ranked tie-breaking rules, we present simple threshold strategies for the agents that give them high guarantees, independent of the strategies taken by others. In particular, for random tie-breaking, every agent can guarantee herself at least $\frac{1}{k+1}$ of the highest reward, and at least $\frac{1}{2k}$ of the optimal social welfare. For ranked tie-breaking, the $i$th ranked agent can guarantee herself at least a half of the $i$th highest reward. We complement these results by matching upper bounds, even with respect to equilibrium profiles. For ranked tie-breaking rule, we also show a correspondence between the equilibrium of the $k$-agent game and the optimal strategy of a single decision maker who can select up to $k$ rewards.
View PDF Chat

Fair-Share Allocations for Agents with Arbitrary Entitlements

2021-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) … We consider the problem of fair allocation of indivisible goods to $n$ agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new, and satisfies $APS \ge MMS$, where the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a $\frac{3}{5}$-fraction of her APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a $\frac{3}{5}$-fraction of her APS.
View PDF Chat

Best-of-Both-Worlds Fair-Share Allocations

2021-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds … We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness mechanisms aim to give all agents both an ex-ante guarantee (such as getting the proportional share in expectation) and an ex-post guarantee. Prior BoBW results have focused on ex-post guarantees that are based on the "up to one item" paradigm, such as envy-free up to one item (EF1). In this work we attempt to give every agent a high value ex-post, and specifically, a constant fraction of his maximin share (MMS). The up to one item paradigm fails to give such a guarantee, and it is not difficult to present examples in which previous BoBW mechanisms give agents only a $\frac{1}{n}$ fraction of their MMS. Our main result is a deterministic polynomial time algorithm that computes a distribution over allocations that is ex-ante proportional, and ex-post, every allocation gives every agent at least his proportional share up to one item, and more importantly, at least half of his MMS. Moreover, this last ex-post guarantee holds even with respect to a more demanding notion of a share, introduced in this paper, that we refer to as the truncated proportional share (TPS). Our guarantees are nearly best possible, in the sense that one cannot guarantee agents more than their proportional share ex-ante, and one cannot guarantee agents more than a $\frac{n}{2n-1}$ fraction of their TPS ex-post.
View PDF Chat

A general framework for endowment effects in combinatorial markets

2020-12-02
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect , coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. Recently, Babaioff, Dobzinski and Oren [EC'18] introduced the … The endowment effect , coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. Recently, Babaioff, Dobzinski and Oren [EC'18] introduced the notion of endowed valuations --- valuations that capture the endowment effect --- and studied the stability and efficiency of combinatorial markets with endowed valuations. They showed that under a specific formulation of the endowment effect, an endowed equilibrium --- market equilibrium with respect to endowed valuations --- is guaranteed to exist in markets with submodular valuations, but fails to exist under XOS valuations. We harness the endowment effect further by introducing a general framework that captures a wide range of different formulations of the endowment effect. The different formulations are (partially) ranked from weak to strong, based on a stability-preserving order. We then provide algorithms for computing endowment equilibria with high welfare for sufficiently strong endowment effects, and non-existence results for weaker ones. Among other results, we prove the existence of endowment equilibria under XOS valuations, and show that if one can pre-pack items into irrevocable bundles then an endowment equilibrium exists for arbitrary markets.
View PDF Chat

On a Competitive Secretary Problem with Deferred Selections

2020-07-14
Tomer Ezra , Michal Feldman , Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker … We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.

A General Framework for Endowment Effects in Combinatorial Markets

2020-07-09
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been traditionally studied mainly using experimental … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias has been traditionally studied mainly using experimental methodology. Recently, Babaioff, Dobzinski and Oren (2018) proposed a specific formulation of the endowment effect in combinatorial markets, and showed that the existence of Walrasian equilibrium with respect to the endowed valuations (referred to as endowment equilibrium) extends from gross substitutes to submodular valuations, but provably fails to extend to more general valuations, like XOS.
View PDF Chat

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models

2020-07-09
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown.
View PDF Chat

Fair and Truthful Mechanisms for Dichotomous Valuations

2020-02-25
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

2020-02-23
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.

Secretary Matching with General Arrivals

2020-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with arbitrary weights that … We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with arbitrary weights that are unknown from the outset, and are revealed online. Under vertex arrival, vertices arrive online in a uniformly random order; upon the arrival of a vertex $v$, the weights of edges from $v$ to all previously arriving vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. Under edge arrival, edges arrive online in a uniformly random order; upon the arrival of an edge $e$, its weight is revealed, and the algorithm decides whether to include it in the matching or not. We provide a $5/12$-competitive algorithm for vertex arrival, and show it is tight. For edge arrival, we provide a $1/4$-competitive algorithm. Both results improve upon state of the art bounds for the corresponding settings. Interestingly, for vertex arrival, secretary matching in general graphs outperforms secretary matching in bipartite graphs with 1-sided arrival, where $1/e$ is the best possible guarantee.

On a Competitive Secretary Problem with Deferred Selections

2020-01-01
Tomer Ezra , Michal Feldman , Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker … We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agent's strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
View PDF Chat

Fair and Truthful Mechanisms for Dichotomous Valuations

2020-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, … We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $\epsilon$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + \epsilon]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $\epsilon$-dichotomous valuations with sufficiently small $\epsilon$, we design a randomized truthful mechanism with strong ex-post guarantees. For $\rho = \frac{1}{1 + \epsilon}$, the allocations that it produces generate at least a $\rho$-fraction of the maximum welfare, and enjoy $\rho$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.
View PDF Chat

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models

2020-01-01
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.
View PDF Chat

Pricing Multi-Unit Markets

2019-11-30
Tomer Ezra , Michal Feldman , Tim Roughgarden +1 more
We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction … We study the power and limitations of posted prices in multi-unit markets, where agents arrive sequentially in an arbitrary order. We prove upper and lower bounds on the largest fraction of the optimal social welfare that can be guaranteed with posted prices, under a range of assumptions about the designer's information and agents' valuations. Our results provide insights about the relative power of uniform and non-uniform prices, the relative difficulty of different valuation classes, and the implications of different informational assumptions. Among other results, we prove constant-factor guarantees for agents with (symmetric) subadditive valuations, even in an incomplete-information setting and with uniform prices.
View PDF Chat

A General Framework for Endowment Effects in Combinatorial Markets

2019-03-27
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with respect to a single item. Babaioff et al. [EC'18] took a first step at extending this study beyond a single item. They proposed a specific formulation of the endowment effect in combinatorial settings, and showed that equilibrium existence with respect to the endowed valuations extends from gross substitutes to submodular valuations, but provably fails to extend to XOS valuations. Extending the endowment effect to combinatorial settings can take different forms. In this work, we devise a framework that captures a space of endowment effects, upon which we impose a partial order, which preserves endowment equilibrium existence. Within this framework, we provide existence and welfare guarantees for endowment equilibria corresponding to various endowment effects. Our main results are the following: (1) For markets with XOS valuations, we introduce an endowment effect that is stronger than that of Babaioff et al., for which an endowment equilibrium is guaranteed to exist and gives at least half of the optimal welfare. Moreover, this equilibrium can be reached via a variant of the flexible ascent auction. (2) For markets with arbitrary valuations, we show that bundling leads to a sweeping positive result. In particular, if items can be prepacked into indivisible bundles, there always exists an endowment equilibrium with optimal welfare. Moreover, we provide a polynomial algorithm that given an arbitrary allocation $S$, computes an endowment equilibrium with the same welfare guarantee as in $S$.

A General Framework for Endowment Effects in Combinatorial Markets

2019-01-01
Tomer Ezra , Michal Feldman , Ophir Friedler
The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with … The endowment effect, coined by Nobel Laureate Richard Thaler, posits that people tend to inflate the value of items they own. This bias was studied, both theoretically and empirically, with respect to a single item. Babaioff et al. [EC'18] took a first step at extending this study beyond a single item. They proposed a specific formulation of the endowment effect in combinatorial settings, and showed that equilibrium existence with respect to the endowed valuations extends from gross substitutes to submodular valuations, but provably fails to extend to XOS valuations. Extending the endowment effect to combinatorial settings can take different forms. In this work, we devise a framework that captures a space of endowment effects, upon which we impose a partial order, which preserves endowment equilibrium existence. Within this framework, we provide existence and welfare guarantees for endowment equilibria corresponding to various endowment effects. Our main results are the following: (1) For markets with XOS valuations, we introduce an endowment effect that is stronger than that of Babaioff et al., for which an endowment equilibrium is guaranteed to exist and gives at least half of the optimal welfare. Moreover, this equilibrium can be reached via a variant of the flexible ascent auction. (2) For markets with arbitrary valuations, we show that bundling leads to a sweeping positive result. In particular, if items can be prepacked into indivisible bundles, there always exists an endowment equilibrium with optimal welfare. Moreover, we provide a polynomial algorithm that given an arbitrary allocation $S$, computes an endowment equilibrium with the same welfare guarantee as in $S$.
View PDF Chat

Prophets and Secretaries with Overbooking

2018-06-11
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the l-out-of- k setting, where the decision maker can select up to k elements immediately and irrevocably, but her performance is measured by the top l elements in the selected set. Equivalently, the decision makes can hold up to l elements at any given point in time, but can make up to k-l returns as new elements arrive. We give upper and lower bounds on the competitive ratio of l-out-of- k prophet and secretary scenarios. For l-out-of- k prophet scenarios we provide a single-sample algorithm with competitive ratio 1-l· e-Θ((k-l)2/k) . The algorithm is a single-threshold algorithm, which sets a threshold that equals the (l+k/2)th highest sample, and accepts all values exceeding this threshold, up to reaching capacity k . On the other hand, we show that this result is tight if the number of possible returns is linear in l (i.e., k-l =Θ(l)). In particular, we show that no single-sample algorithm obtains a competitive ratio better than 1 - 2-(2k+1)/k+1 . We also present a deterministic single-threshold algorithm for the 1-out-of- k prophet setting which obtains a competitive ratio of 1-3/2 · e-s/k 6, knowing only the distribution of the maximum value. This result improves the result of [Assaf & Samuel-Cahn, J. of App. Prob., 2000].
View PDF Chat

Prophets and Secretaries with Overbooking

2018-05-14
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the $\ell-out-of-k$ setting, where the decision maker can select up to $k$ elements immediately and irrevocably, but her performance is measured by the top $\ell$ elements in the selected set. Equivalently, the decision makes can hold up to $\ell$ elements at any given point in time, but can make up to $k-\ell$ returns as new elements arrive. We give upper and lower bounds on the competitive ratio of $\ell$-out-of-$k$ prophet and secretary scenarios. These include a single-sample prophet algorithm that gives a competitive ratio of $1-\ell\cdot e^{-\Theta\left(\frac{\left(k-\ell\right)^2}{k}\right)}$, which is asymptotically tight for $k-\ell=\Theta(\ell)$. For secretary settings, we devise an algorithm that obtains a competitive ratio of $1-\ell e^{-\frac{k-8\ell}{2+2\ln \ell}} - e^{-k/6}$, and show that no secretary algorithm obtains a better ratio than $1-e^{-k}$ (up to negligible terms). In passing, our results lead to an improvement of the results of Assaf et al. [2000] for $1-out-of-k$ prophet scenarios. Beyond the contribution to online algorithms and optimal stopping theory, our results have implications to mechanism design. In particular, we use our prophet algorithms to derive {\em overbooking} mechanisms with good welfare and revenue guarantees; these are mechanisms that sell more items than the seller's capacity, then allocate to the agents with the highest values among the selected agents.

Pricing Multi-unit Markets

2018-01-01
Tomer Ezra , Michal Feldman , Tim Roughgarden +1 more
View PDF Chat
Coauthor Papers Together
Michal Feldman 38
Moshe Babaioff 8
Uriel Feige 8
Zhihao Gavin Tang 8
Nick Gravin 6
Ron Kupfer 6
Thomas Keßelheim 5
M.V. Russo 4
Ophir Friedler 4
Stefano Leonardi 4
Tim Roughgarden 3
Warut Suksompong 3
Paul Duetting 3
Paul Dütting 3
Ilan Nehama 3
Tamar Garbuz 2
Alon Eden 2
Federico Fusco 2
M Schlesinger 2
José R. Correa 2
Johannes Brustle 2
Víctor Verdugo 2
Seeun William Umboh 1
Ben Berger 1
Daniel Schoepflin 1
Ariel Shaulker 1
Alexandros Tsigonias-Dimitriadis 1
Paul Duetting 1
S. Matthew Weinberg 1
Eric Neyman 1
Ben Berger 1
Rebecca Reiffenhäuser 1
Inbal Talgam-Cohen 1
Georgios Birmpas 1
Tamar Garbuz 1
Michał E. Pawłowski 1

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables

1984-11-01
Ester Samuel‐Cahn
Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined … Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined by $t(c) = \text{smallest} i$ for which $X_i \geq c(s(c) = \text{smallest} i$ for which $X_i > c), = n$ otherwise. Let $m$ be a median of the distribution of $X^\ast_n$. It is shown that for every $n$ and $\underline{X}$ either $EX^\ast_n \leq 2EX_{t(m)}$ or $EX^\ast_n \leq 2EX_{s(m)}$. This improves previously known results, [1], [4]. Some results for i.i.d. $X_i$ are also included.
View PDF Chat

Prophets and Secretaries with Overbooking

2018-06-11
Tomer Ezra , Michal Feldman , Ilan Nehama
The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, … The prophet and secretary problems demonstrate online scenarios involving the optimal stopping theory. In a typical prophet or secretary problem, selection decisions are assumed to be immediate and irrevocable. However, many online settings accommodate some degree of revocability. To study such scenarios, we introduce the l-out-of- k setting, where the decision maker can select up to k elements immediately and irrevocably, but her performance is measured by the top l elements in the selected set. Equivalently, the decision makes can hold up to l elements at any given point in time, but can make up to k-l returns as new elements arrive. We give upper and lower bounds on the competitive ratio of l-out-of- k prophet and secretary scenarios. For l-out-of- k prophet scenarios we provide a single-sample algorithm with competitive ratio 1-l· e-Θ((k-l)2/k) . The algorithm is a single-threshold algorithm, which sets a threshold that equals the (l+k/2)th highest sample, and accepts all values exceeding this threshold, up to reaching capacity k . On the other hand, we show that this result is tight if the number of possible returns is linear in l (i.e., k-l =Θ(l)). In particular, we show that no single-sample algorithm obtains a competitive ratio better than 1 - 2-(2k+1)/k+1 . We also present a deterministic single-threshold algorithm for the 1-out-of- k prophet setting which obtains a competitive ratio of 1-3/2 · e-s/k 6, knowing only the distribution of the maximum value. This result improves the result of [Assaf & Samuel-Cahn, J. of App. Prob., 2000].
View PDF Chat

Beyond matroids: secretary problem and prophet inequality with general constraints

2016-06-10
Aviad Rubinstein
We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both … We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both problems. This is close to the Omega(n/log n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log(n) log(r))-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(loglog(n) log(r)) factor) an open question posed to us by Bobby Kleinberg.
View PDF Chat

Lower Bounds for Bruss’ Odds Problem with Multiple Stoppings

2016-02-10
Tomomi Matsui , Katsunori Ano
This paper addresses Bruss’ odds problem with multiple stopping chances. A decision maker sequentially observes a sequence of independent 0/1 (failure/success) random variables to correctly predict the last success with … This paper addresses Bruss’ odds problem with multiple stopping chances. A decision maker sequentially observes a sequence of independent 0/1 (failure/success) random variables to correctly predict the last success with multiple stopping chances. First, we give a nontrivial lower bound of the probability of win (obtaining the last success) for the problem with m-stoppings. Next, we show that the asymptotic value for each classical secretary problem with multiple stoppings attains our lower bound. Finally, we prove a conjecture on the classical secretary problem, which gives a connection between the probability of win and the threshold values of the optimal stopping strategy.
View PDF Chat

Polymatroid Prophet Inequalities

2015-01-01
Paul Dütting , Robert Kleinberg
View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2018-01-01
Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more
The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1 – 1/e)-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item.Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.
View PDF Chat

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-10-01
Saeed Alaei
For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to the mechanism design problem for each individual buyer. Our frame- … For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to the mechanism design problem for each individual buyer. Our frame- work can be applied to any setting which roughly satisfies the following assumptions: (i) the buyer's types must be distributed independently (not necessarily identically), (ii) the objective function must be linearly separable over the set of buyers, and (iii) the supply constraints must be the only constraints involving more than one buyer. Our framework is general in the sense that it makes no explicit assumption about any of the following: (i) the buyer's valuations (e.g., submodular, additive, etc), (ii) The distribution of types for each buyer, and (iii) the other constraints involving individual buyers (e.g., budget constraints, etc). We present two generic ra-buyer mechanisms that use 1- buyer mechanisms as black boxes. Assuming that we have an α-approximate 1-buyer mechanism for each buyer and assuming that no buyer ever needs more than 1/k of all copies of each item for some integer k ≥ 1, then our generic n- buyer mechanisms are γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> · α-approximation of the optimal n-buyer mechanism, in which γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is a constant which is at least 1 - 1/√(k+3). Observe that γ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> is at least1/2 (for k = 1) and approaches 1 as k increases. As a byproduct of our construction, we improve a generalization of prophet inequalities. Furthermore, as applications of our main theorem, we improve several results from the literature.
View PDF Chat

Algorithmic pricing via virtual valuations

2007-06-11
Shuchi Chawla , Jason D. Hartline , Robert Kleinberg
Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. … Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami etal. (SODA, 2005) proposed this problem and gave logarithmic approximations (in the number of consumers) for the unit-demand and single-parameter cases where there is a specific set of consumers and their valuations for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic in approximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter agent settings; however, for this purpose approximation factors logarithmic in the number of agents are inadequate. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this pricing problem. Here a consumer has a valuation for each different item and their value for aset of items is simply the maximum value they have for any item in the set. Instead of considering a set of consumers with precisely known preferences, like the prior algorithmic pricing literature, we assume that the preferences of the consumers are drawn from a distribution. This is the standard assumption in economics; furthermore, the setting of a specific set of customers with specific preferences, which is employed in all of the prior work in algorithmic pricing, is a special case of this general Bayesian pricing problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Notice that the distribution over the valuations for the individual items that this generates is obviously correlated. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation algorithm for this problem that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.
View PDF Chat

Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution

2019-06-17
José R. Correa , Paul Dütting , Felix Fischer +1 more
A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1, ..., Xn drawn independently from … A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1, ..., Xn drawn independently from a distribution F, the goal is to choose a stopping time τ so as to maximize α such that for all distributions F we have E[Xτ]≥α•E[maxt Xt]. What makes this problem challenging is that the decision whether τ=t may only depend on the values of the random variables X1, ..., Xt and on the distribution F. For a long time the best known bound for the problem had been α≥1-1/e≅0.632, but quite recently a tight bound of α≅0.745 was obtained. The case where F is unknown, such that the decision whether τ=t may depend only on the values of the random variables X1, ..., Xt, is equally well motivated but has received much less attention. A straightforward guarantee for this case of α≥1-1/e≅0.368 can be derived from the solution to the secretary problem, where an arbitrary set of values arrive in random order and the goal is to maximize the probability of selecting the largest value. We show that this bound is in fact tight. We then investigate the case where the stopping time may additionally depend on a limited number of samples from~F, and show that even with o(n) samples α≥1/e. On the other hand, n samples allow for a significant improvement, while O(n2) samples are equivalent to knowledge of the distribution: specifically, with n samples α≥1-1/e≅0.632 and α≥ln(2)≅0.693, and with O(n2) samples α≥0.745-ε for any ε>0.
View PDF Chat

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-06-06
Saeed Alaei
For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any … For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) buyers' types must be distributed independently (not necessarily identically), (ii) objective function must be linearly separable over the buyers, and (iii) except for the supply constraints, there should be no other inter-buyer constraints. Our framework is general in the sense that it makes no explicit assumption about buyers' valuations, type distributions, and single buyer constraints (e.g., budget, incentive compatibility, etc). We present two generic multi buyer mechanisms which use single buyer mechanisms as black boxes; if an $\alpha$-approximate single buyer mechanism can be constructed for each buyer, and if no buyer requires more than $\frac{1}{k}$ of all units of each item, then our generic multi buyer mechanisms are $\gamma_k\alpha$-approximation of the optimal multi buyer mechanism, where $\gamma_k$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. Observe that $\gamma_k$ is at least 1/2 (for $k=1$) and approaches 1 as $k \to \infty$. As a byproduct of our construction, we present a generalization of prophet inequalities. Furthermore, as applications of our framework, we present multi buyer mechanisms with improved approximation factor for several settings from the literature.

A tight negative example for MMS fair allocations.

2021-04-11
Uriel Feige , Ariel Sapir , Laliv Tauber
We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang [JACM, 2018] present instances for which every allocation gives some agent less … We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang [JACM, 2018] present instances for which every allocation gives some agent less than her maximin share. We present such examples with larger gaps. For three agents and nine items, we design an instance in which at least one agent does not get more than a $\frac{39}{40}$ fraction of her maximin share. Moreover, we show that there is no negative example in which the difference between the number of items and the number of agents is smaller than six, and that the gap (of $\frac{1}{40}$) of our example is worst possible among all instances with nine items. For $n \ge 4$ agents, we show examples in which at least one agent does not get more than a $1 - \frac{1}{n^4}$ fraction of her maximin share. In the instances designed by Kurokawa, Procaccia and Wang, the gap is exponentially small in $n$.

Approximation Algorithms for Computing Maximin Share Allocations

2017-10-31
Georgios Amanatidis , Evangelos Markakis , Afshin Nikzad +1 more
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a … We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to $\{0, 1, 2\}$, extending the $\{0, 1\}$ setting studied in Bouveret and Lema\^itre. We obtain an exact algorithm for any number of agents in this case.
View PDF Chat

Fair Division with Binary Valuations: One Rule to Rule Them All

2020-01-01
Daniel Halpern , Ariel D. Procaccia , Alexandros Psomas +1 more
View PDF Chat

On Best-of-Both-Worlds Fair-Share Allocations

2022-01-01
Moshe Babaioff , Tomer Ezra , Uriel Feige
View PDF Chat

An Improved Approximation Algorithm for Maximin Shares

2020-07-09
Jugal Garg , Setareh Taki
We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. … We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ε MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.
View PDF Chat

Approximating Maximin Shares with Mixed Manna.

2020-07-17
Rucha Kulkarni , Ruta Mehta , Setareh Taki
We initiate the study of fair allocations of a mixed manna under the popular fairness notion of maximin share (MMS). A mixed manna allows an item to be a good … We initiate the study of fair allocations of a mixed manna under the popular fairness notion of maximin share (MMS). A mixed manna allows an item to be a good for some agents and chore for others, hence strictly generalizes the well-studied goods (chores) only manna. For the good manna, Procaccia and Wang [PW14] showed non-existence of MMS allocation. This prompted works on finding an $\alpha$-MMS allocation. A series of works obtained efficient algorithms, improving $\alpha$ to $\frac{3}{4}$ for $n\ge 5$ agents. Computing an $\alpha$-MMS allocation for the maximum $\alpha$ for which it exists is known to be NP-hard. But the question of finding $\alpha$-MMS for the near best $\alpha$ remains unresolved. We make significant progress towards this question for mixed manna by showing a striking dichotomy: We derive two conditions and show that the problem is tractable under these, while dropping either renders the problem intractable. The conditions are: $(i)$ number of agents is constant, and $(ii)$ for every agent, her total value for goods differs significantly from that for chores. For instances satisfying $(i)$ and $(ii)$ we design a PTAS - an efficient algorithm to find $(\alpha-\epsilon)$-MMS allocation given $\epsilon>0$ for the best possible $\alpha$. We also show that if either condition is not satisfied then finding $\alpha$-MMS for any $\alpha\in(0,1]$ is NP-hard, even when solution exists for $\alpha=1$. As a corollary, our algorithm resolves the open question of designing a PTAS for the goods only setting with constantly many agents (best known $\alpha=\frac{3}{4}$), and similarly also for chores only setting. In terms of techniques, we use market equilibrium as a tool to solve an MMS problem, which may be of independent interest.

Contracts under Moral Hazard and Adverse Selection

2021-07-18
Guru Guruganesh , Jon Schneider , Joshua R. Wang
In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical principal-agent problem … In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical principal-agent problem in a setting where the agent can be of one of several types (affecting the outcome of actions they might take). This combines the contract theory phenomena of "moral hazard" (incomplete information about actions) with that of "adverse selection" (incomplete information about types).
View PDF Chat

Tight competitive ratios of classic matching algorithms in the fully online model

2019-01-06
Zhiyi Huang , Binghui Peng , Zhihao Gavin Tang +3 more
Huang et al. (STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and … Huang et al. (STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al. (STOC 1990) is strictly better than 0.5-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be (1 --- 1/e)-competitive.This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is [MATH HERE]-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art [MATH HERE] upper bound. For integral algorithms, we show a tight competitive ratio of ≈ 0.567 for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018).

How Do Classifiers Induce Agents to Invest Effort Strategically?

2019-06-17
Jon Kleinberg , Manish Raghavan
Algorithms are often used to produce decision-making rules that classify or evaluate individuals. When these individuals have incentives to be classified a certain way, they may behave strategically to influence … Algorithms are often used to produce decision-making rules that classify or evaluate individuals. When these individuals have incentives to be classified a certain way, they may behave strategically to influence their outcomes. We develop a model for how strategic agents can invest effort in order to change the outcomes they receive, and we give a tight characterization of when such agents can be incentivized to invest specified forms of effort into improving their outcomes as opposed to "gaming" the classifier. We show that whenever any "reasonable" mechanism can do so, a simple linear mechanism suffices.
View PDF Chat

Discrete convex analysis: A tool for economics and game theory

2016-12-14
Kazuo Murota
This paper presents discrete convex analysis as a tool for use in economics and game theory.Discrete convex analysis is a new framework of discrete mathematics and optimization, developed during the … This paper presents discrete convex analysis as a tool for use in economics and game theory.Discrete convex analysis is a new framework of discrete mathematics and optimization, developed during the last two decades.Recently, it has been recognized as a powerful tool for analyzing economic or game models with indivisibilities.The main feature of discrete convex analysis is the distinction of two convexity concepts, M-convexity and L-convexity, for functions in integer or binary variables, together with their conjugacy relationship.The crucial fact is that M-concavity in its variant is equivalent to the gross substitutes property in economics.Fundamental theorems in discrete convex analysis such as the M-L conjugacy theorems, discrete separation theorems and discrete fixed point theorems yield structural results in economics such as the existence of equilibria and the lattice structure of equilibrium price vectors.Algorithms in discrete convex analysis provide iterative auction algorithms for finding equilibria.
View PDF Chat

Simple versus Optimal Contracts

2019-06-17
Paul Dütting , Tim Roughgarden , Inbal Talgam-Cohen
We consider the classic principal-agent model of contract theory, in which a principal designs an outcome-dependent compensation scheme to incentivize an agent to take a costly and unobservable action. When … We consider the classic principal-agent model of contract theory, in which a principal designs an outcome-dependent compensation scheme to incentivize an agent to take a costly and unobservable action. When all of the model parameters---including the full distribution over principal rewards resulting from each agent action---are known to the designer, an optimal contract can in principle be computed by linear programming. In addition to their demanding informational requirements, however, such optimal contracts are often complex and unintuitive, and do not resemble contracts used in practice. This paper examines contract theory through the theoretical computer science lens, with the goal of developing novel theory to explain and justify the prevalence of relatively simple contracts, such as linear (pure commission) contracts. First, we consider the case where the principal knows only the first moment of each action's reward distribution, and we prove that linear contracts are guaranteed to be worst-case optimal, ranging over all reward distributions consistent with the given moments. Second, we study linear contracts from a worst-case approximation perspective, and prove several tight parameterized approximation bounds.
View PDF Chat

Combinatorial Auctions with Endowment Effect

2018-06-11
Moshe Babaioff , Shahar Dobzinski , Sigal Oren
We study combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC'14] and its … We study combinatorial auctions with bidders that exhibit endowment effect. In most of the previous work on cognitive biases in algorithmic game theory (e.g., [Kleinberg and Oren, EC'14] and its follow-ups) the focus was on analyzing the implications and mitigating their negative consequences. In contrast, in this paper we show how in some cases cognitive biases can be harnessed to obtain better outcomes. Specifically, we study Walrasian equilibria in combinatorial markets. It is well known that Walrasian equilibria exist only in limited settings, e.g., when all valuations are gross substitutes, but fails to exist in more general settings, e.g., when the valuations are submodular. We consider combinatorial settings in which bidders exhibit the endowment effect, that is, their value for items increases with ownership. Our main result shows that when the valuations are submodular, even a mild degree of endowment effect is sufficient to guarantee the existence of Walrasian equilibria. In fact, we show that in contrast to Walrasian equilibria with standard utility maximizing bidders -- in which the equilibrium allocation must be efficient -- when bidders exhibit endowment effect any local optimum can be an equilibrium allocation. Our techniques reveal interesting connections between the LP relaxation of combinatorial auctions and local maxima. We also provide lower bounds on the intensity of the endowment effect that the bidders must have in order to guarantee the existence of a Walrasian equilibrium in various settings.
View PDF Chat

Dynamic Pricing with Limited Supply

2015-03-27
Moshe Babaioff , Shaddin Dughmi , Robert Kleinberg +1 more
We consider the problem of designing revenue-maximizing online posted-price mechanisms when the seller has limited supply. A seller has k identical items for sale and is facing n potential buyers … We consider the problem of designing revenue-maximizing online posted-price mechanisms when the seller has limited supply. A seller has k identical items for sale and is facing n potential buyers (“agents”) that are arriving sequentially. Each agent is interested in buying one item. Each agent’s value for an item is an independent sample from some fixed (but unknown) distribution with support [0,1]. The seller offers a take-it-or-leave-it price to each arriving agent (possibly different for different agents), and aims to maximize his expected revenue. We focus on mechanisms that do not use any information about the distribution; such mechanisms are called detail-free (or prior-independent ). They are desirable because knowing the distribution is unrealistic in many practical scenarios. We study how the revenue of such mechanisms compares to the revenue of the optimal offline mechanism that knows the distribution (“offline benchmark”). We present a detail-free online posted-price mechanism whose revenue is at most O(( k log n )2/3) less than the offline benchmark, for every distribution that is regular. In fact, this guarantee holds without any assumptions if the benchmark is relaxed to fixed-price mechanisms. Further, we prove a matching lower bound. The performance guarantee for the same mechanism can be improved to O (√ k log n ), with a distribution-dependent constant, if the ratio k / n is sufficiently small. We show that, in the worst case over all demand distributions, this is essentially the best rate that can be obtained with a distribution-specific constant. On a technical level, we exploit the connection to multiarmed bandits (MAB). While dynamic pricing with unlimited supply can easily be seen as an MAB problem, the intuition behind MAB approaches breaks when applied to the setting with limited supply. Our high-level conceptual contribution is that even the limited supply setting can be fruitfully treated as a bandit problem.
View PDF Chat

Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models

2020-07-09
Tomer Ezra , Michal Feldman , Nick Gravin +1 more
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is … We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution schemes (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For vertex arrival, our result is tight. Interestingly, pricing-based prophet inequalities with comparable competitive ratios are unknown.
View PDF Chat

Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

2014-01-01
Chandra Chekuri , J. Vondrák , Rico Zenklusen
We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid … We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.
View PDF Chat

M-Convex Function on Generalized Polymatroid

1999-02-01
Kazuo Murota , Akiyoshi Shioura
The concept of M-convex function, introduced by Murota (1996), is a quantitative generalization of the set of integral points in an integral base polyhedron as well as an extension of … The concept of M-convex function, introduced by Murota (1996), is a quantitative generalization of the set of integral points in an integral base polyhedron as well as an extension of valuated matroid of Dress and Wenzel (1990). In this paper, we extend this concept to functions on generalized polymatroids with a view to providing a unified framework for efficiently solvable nonlinear discrete optimization problems.
View PDF Chat

Online Stochastic Matching with Edge Arrivals

2019-01-01
Nick Gravin , Zhihao Gavin Tang , Kangning Wang
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no … Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no online policy is better than the straightforward greedy algorithm, i.e., no online algorithm has a worst-case competitive ratio better than $0.5$. In this work, we consider the bipartite matching problem with edge arrivals in a natural stochastic framework, i.e., Bayesian setting where each edge of the graph is independently realized according to a known probability distribution. We focus on a natural class of prune & greedy online policies motivated by practical considerations from a multitude of online matching platforms. Any prune & greedy algorithm consists of two stages: first, it decreases the probabilities of some edges in the stochastic instance and then runs greedy algorithm on the pruned graph. We propose prune & greedy algorithms that are $0.552$-competitive on the instances that can be pruned to a $2$-regular stochastic bipartite graph, and $0.503$-competitive on arbitrary bipartite graphs. The algorithms and our analysis significantly deviate from the prior work. We first obtain analytically manageable lower bound on the size of the matching, which leads to a non linear optimization problem. We further reduce this problem to a continuous optimization with a constant number of parameters that can be solved using standard software tools.
View PDF Chat

Revenue Maximization for Selling Multiple Correlated Items

2015-01-01
MohammadHossein Bateni , Sina Dehghani , MohammadTaghi Hajiaghayi +1 more
View PDF Chat

Simultaneously Achieving Ex-ante and Ex-post Fairness

2020-01-01
Haris Aziz
View PDF Chat

A Secretary Problem with a Sliding Window for Recalling Applicants

2015-01-01
Shan-Yuan Ho , Abijith Krishnan
The Sliding Window Secretary Problem allows a window of choices to the Classical Secretary Problem, in which there is the option to choose the previous $K$ choices immediately prior to … The Sliding Window Secretary Problem allows a window of choices to the Classical Secretary Problem, in which there is the option to choose the previous $K$ choices immediately prior to the current choice. We consider a case of this sequential choice problem in which the interviewer has a finite, known number of choices and can only discern the relative ranks of choices, and in which every permutation of ranks is equally likely. We examine three cases of the problem: (i) the interviewer has one choice to choose the best applicant; (ii) the interviewer has one choice to choose one of the top two applicants; and (iii) the interviewer has two choices to choose the best applicant. The form of the optimal strategy is shown, the probability of winning as a function of the window size is derived, and the limiting behavior is discussed for all three cases.

Approximation Algorithms for Maximin Fair Division

2020-02-29
Siddharth Barman , Sanath Kumar Krishnamurthy
We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share , which is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations, a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations . Specifically, we show that when the valuations of the agents are nonnegative , monotone , and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the article is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions .
View PDF Chat

Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems

2016-02-03
Chien-Ju Ho , Aleksandrs Slivkins , Jennifer Wortman Vaughan
Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task's requester, and … Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the task's requester, and may be adjusted based on the quality of the completed work, for example, through the use of "bonus" payments. In this paper, we study the requester's problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each "arm" representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.
View PDF Chat

The power of randomness in bayesian optimal mechanism design

2010-06-07
Shuchi Chawla , David L. Malec , Balasubramanian Sivan
We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds … We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem - a single seller aims to maximize expected revenue by allocating multiple kinds of resources to "unit-demand" agents with preferences drawn from a known distribution. When the agents' preferences are single-dimensional Myerson's seminal work [14] shows that randomness offers no benefit - the optimal mechanism is always deterministic. In the multi-dimensional case, where each agent's preferences are given by different values for each of the available services, Briest et al.[6] recently showed that the gap between the expected revenue obtained by an optimal randomized mechanism and an optimal deterministic mechanism can be unbounded even when a single agent is offered only 4 services. However, this large gap is attained through unnatural instances where values of the agent for different services are correlated in a specific way. We show that when the agent's values involve no correlation or a specific kind of positive correlation, the benefit of randomness is only a small constant factor (4 and 8 respectively). Our model of positively correlated values (that we call the common base value model) is a natural model for unit-demand agents and items that are substitutes. Our results extend to multiple agent settings as well.
View PDF Chat

Online Fair Division: analysing a Food Bank problem

2015-02-26
Martin Aleksandrov , Haris Aziz , Serge Gaspers +1 more
We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply … We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse several axiomatic properties of these mechanisms like strategy-proofness and envy-freeness. Finally, we perform a competitive analysis and compute the price of anarchy.

Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems

2019-01-09
Nikhil R. Devanur , Kamal Jain , Balasubramanian Sivan +1 more
We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a … We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1−ϵ fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor ϵ approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast ϵ approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1−ϵ fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary’s distribution, then we design an algorithm that achieves a 1−ϵ fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1+ϵ) the mixed packing-covering problem with O (γ m log ( n /δ)/ϵ 2 ) oracle calls where the constraint matrix of this LP has dimension n × m , the success probability of the algorithm is 1−δ, and γ quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing, and the adwords problem.
View PDF Chat

Non-price equilibria in markets of discrete goods

2011-06-05
Avinatan Hassidim , Haim Kaplan , Yishay Mansour +1 more
No abstract available. No abstract available.
View PDF Chat

Combinatorial Auctions via Posted Prices

2014-12-22
Michal Feldman , Nick Gravin , Brendan Lucier
We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in … We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in an arbitrary order, each purchasing her favorite bundle from among the unsold items at the posted prices. These mechanisms are simple, transparent and trivially dominant strategy incentive compatible (DSIC).We show that when agent preferences are fractionally subadditive (which includes all submodular functions), there always exist prices that, in expectation, obtain at least half of the optimal welfare. Our result is constructive: given black-box access to a combinatorial auction algorithm A, sample access to the prior distribution, and appropriate query access to the sampled valuations, one can compute, in polytime, prices that guarantee at least half of the expected welfare of A. As a corollary, we obtain the first polytime (in n and m) constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions, given access to demand query oracles. Our results also extend to valuations with complements, where the approximation factor degrades linearly with the level of complementarity.
View PDF Chat

Combinatorial Walrasian Equilibrium

2016-01-01
Michal Feldman , Nick Gravin , Brendan Lucier
We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept … We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (noncombinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half the optimal (unconstrained) social welfare. Moreover, we devise a polynomial time algorithm that, given an arbitrary allocation, computes a CWE that achieves at least half its welfare. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, to motivate the use of bundles, we establish strong lower bounds when the seller is restricted to using item prices only. The strength of our results derives partly from their generality---our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements.
View PDF Chat

Simultaneous auctions are (almost) efficient

2013-05-28
Michal Feldman , Hu Fu , Nick Gravin +1 more
Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. … Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. The allocation and prices are then resolved for each item separately, based solely on the bids submitted on that item. We study the efficiency of Bayes-Nash equilibrium (BNE) outcomes of simultaneous first- and second-price auctions when bidders have complement-free (a.k.a. subadditive) valuations. While it is known that the social welfare of every pure Nash equilibrium (NE) constitutes a constant fraction of the optimal social welfare, a pure NE rarely exists, and moreover, the full information assumption is often unrealistic. Therefore, quantifying the welfare loss in Bayes-Nash equilibria is of particular interest. Previous work established a logarithmic bound on the ratio between the social welfare of a BNE and the expected optimal social welfare in both first-price auctions (Hassidim et al., 2011) and second-price auctions (Bhawalkar and Roughgarden, 2011), leaving a large gap between a constant and a logarithmic ratio. We introduce a new proof technique and use it to resolve both of these gaps in a unified way. Specifically, we show that the expected social welfare of any BNE is at least 1/2 of the optimal social welfare in the case of first-price auctions, and at least 1/4 in the case of second-price auctions.
View PDF Chat

Approximation Algorithms for Maximin Fair Division

2017-06-20
Siddharth Barman , Sanath Kumar Krishna Murthy
We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin … We consider the problem of dividing indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focussed on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.
View PDF Chat

The Invisible Hand of Dynamic Market Pricing

2016-07-21
Vincent Cohen-Addad , Alon Eden , Michal Feldman +1 more
Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, … Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrarily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done. We further extend our results to Bayesian and bounded rationality models.
View PDF Chat

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

2017-06-20
Georgios Amanatidis , Georgios Birmpas , George Christodoulou +1 more
We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how … We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how do truthful mechanisms look like. We focus on the case of two players with additive valuation functions and our purpose is twofold. First, our main result provides a complete characterization of truthful mechanisms that allocate all the items to the players. Our characterization reveals an interesting structure underlying all truthful mechanisms, showing that they can be decomposed into two components: a selection part where players pick their best subset among prespecified choices determined by the mechanism, and an exchange part where players are offered the chance to exchange certain subsets if it is favorable to do so. In the remaining paper, we apply our main result and derive several consequences on the design of mechanisms with fairness guarantees. We consider various notions of fairness, (indicatively, maximin share guarantees and envy-freeness up to one item) and provide tight bounds for their approximability. Our work settles some of the open problems in this agenda, and we conclude by discussing possible extensions to more players.
View PDF Chat

A Simple and Approximately Optimal Mechanism for an Additive Buyer

2014-10-01
Moshe Babaioff , Nicole Immorlica , Brendan Lucier +1 more
We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a … We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue.It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting:item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.
View PDF Chat

A Simple and Approximately Optimal Mechanism for a Buyer with Complements

2017-06-20
Alon Eden , Michal Feldman , Ophir Friedler +2 more
We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation v for the items may exhibit both substitutes (i.e., for some S, T, v(S ∪ … We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation v for the items may exhibit both substitutes (i.e., for some S, T, v(S ∪ T) < v(S) + v(T)) and complements (i.e., for some S, T, v(S ∪ T) > v(S) + v(T)). We show that the mechanism first proposed by Babaioff et al. [2014] -- the better of selling the items separately and bundling them together -- guarantees a Θ(d) fraction of the optimal revenue, where $d$ is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity. It extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations.
View PDF Chat

Prophet Inequalities with Limited Information

2013-12-18
Pablo Azar , Robert Kleinberg , S. Matthew Weinberg
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Prophet Inequalities with Limited InformationPablo D. Azar, Robert Kleinberg, and S. Matthew WeinbergPablo D. … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Prophet Inequalities with Limited InformationPablo D. Azar, Robert Kleinberg, and S. Matthew WeinbergPablo D. Azar, Robert Kleinberg, and S. Matthew Weinbergpp.1358 - 1377Chapter DOI:https://doi.org/10.1137/1.9781611973402.100PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract In the classical prophet inequality, a gambler observes a sequence of stochastic rewards V1, …, Vn and must decide, for each reward Vi, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value Vi. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose k items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards V1, …, Vn are drawn. The assumption that the gambler knows the distribution from which V1, …, Vn are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, even with full knowledge of the distribution. Specifically, we provide a novel single-sample algorithm when the gambler can choose any k elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related secretary problem to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. In addition, we apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders. Connections between prophet inequalities and posted-price mechanisms are already known, but applying the existing framework requires knowledge of the underlying distributions, as well as the so-called "virtual values" even when the underlying prophet inequalities do not. We therefore provide an extension of this framework that bypasses virtual values altogether, allowing our mechanisms to take full advantage of the limited information required by our new prophet inequalities. Previous chapter Next chapter RelatedDetails Published:2014ISBN:978-1-61197-338-9eISBN:978-1-61197-340-2 https://doi.org/10.1137/1.9781611973402Book Series Name:ProceedingsBook Code:PRDA14Book Pages:viii + 1885
View PDF Chat

On the Construction of Substitutes

2018-06-11
Eric Balkanski , Renato Paes Leme
Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many … Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.
View PDF Chat

Multi-unit assignment under dichotomous preferences

2019-11-14
Josué Ortega
View PDF Chat

Delegated Search Approximates Efficient Search

2018-06-11
Jon Kleinberg , Robert Kleinberg
There are many settings in which a principal performs a task by delegating it to an agent, who searches over possible solutions and proposes one to the principal. This describes … There are many settings in which a principal performs a task by delegating it to an agent, who searches over possible solutions and proposes one to the principal. This describes many aspects of the workflow within organizations, as well as many of the activities undertaken by regulatory bodies, who often obtain relevant information from the parties being regulated through a process of delegation. A fundamental tension underlying delegation is the fact that the agent's interests will typically differ -- potentially significantly -- from the interests of the principal, and as a result the agent may propose solutions based on their own incentives that are inefficient for the principal. A basic problem, therefore, is to design mechanisms by which the principal can constrain the set of proposals they are willing to accept from the agent, to ensure a certain level of quality for the principal from the proposed solution. In this work, we investigate how much the principal loses -- quantitatively, in terms of the objective they are trying to optimize -- when they delegate to an agent. We develop a methodology for bounding this loss of efficiency, and show that in a very general model of delegation, there is a family of mechanisms achieving a universal bound on the ratio between the quality of the solution obtained through delegation and the quality the principal could obtain in an idealized benchmark where they searched for a solution themself. Moreover, it is possible to achieve such bounds through mechanisms with a natural threshold structure, which are thus structurally simpler than the optimal mechanisms typically considered in the literature on delegation. At the heart of our framework is an unexpected connection between delegation and the analysis of prophet inequalities, which we leverage to provide bounds on the behavior of our delegation mechanisms.
View PDF Chat

Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

2023-01-30
Haris Aziz , Rupert Freeman , Nisarg Shah +1 more
Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of … Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of fairness such as EV, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as EV up to one good can be guaranteed. In “Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation,” H. Aziz, R. Freeman, N. Shah, and R. Vaish ask whether it is possible to achieve both types of guarantees simultaneously. More specifically, they ask whether there exists a probability distribution over deterministic allocations such that every deterministic allocation is envy-free up to one good and the distribution is exactly envy-free in expectation. The main result of the paper answers this question in the affirmative, showing that ex ante and ex post fairness need not be in conflict.
View PDF Chat

Are Gross Substitutes a Substitute for Submodular Valuations?

2021-07-18
Shahar Dobzinski , Uriel Feige , Michal Feldman
The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of complement free valuations introduced by Lehmann, Lehmann … The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of complement free valuations introduced by Lehmann, Lehmann and Nisan, along with other prominent classes: GS ⊊ Submodular ⊊ XOS ⊊ Subadditive$. The GS class has always been more enigmatic than its counterpart classes, both in its definition and in its relation to the other classes. For example, while it is well understood how closely the Submodular, XOS and Subadditive classes (point-wise) approximate one another, approximability of these classes by GS remained wide open. In particular, the largest gap known between Submodular and GS valuations was some constant ratio smaller than 2. Our main result is the existence of a submodular valuation (one that is also budget additive) that cannot be approximated by GS within a ratio better than $Ømega(łog m/łogłog m), where m is the number of items. En route, we uncover a new symmetrization operation that preserves GS, which may be of independent interest. We show that our main result is tight with respect to budget additive valuations. However, whether GS approximates general submodular valuations within a poly-logarithmic factor remains open, even in the special case of concave of GS valuations (a subclass of Submodular containing budget additive). For concave of Rado valuations (Rado is a significant subclass of GS, containing, e.g., weighted matroid rank functions and OXS), we show approximability by GS within an O(łog2m) factor.
View PDF Chat